#23546 closed defect (fixed)

two errors in treewidth for non-connected graphs

Reported by: evandomme Owned by:
Priority: minor Milestone: sage-8.1
Component: graph theory Keywords: tree decomposition; tree-width
Cc: Merged in:
Authors: Mélodie Lapointe, Élise Vandomme Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: cb3f492 (Commits) Commit: cb3f49228771d74ca8f6e448a1f9e1cdea7bb4a3
Dependencies: Stopgaps:

Description

The function treewidth() with the option certificate=True encounters two problems on non-connected graphs.

Firstly, if I run

g=Graph({0:[1,2], 3:[4,5], 4:[5]})
g.treewidth(certificate=True)

I obtain
http://lacim.uqam.ca/~elise.vandomme/treewidth.png
which contradicts the fact that the tree-width of the graph is 2.

The problem comes from the part ".edges(labels=False)" in

     # Disconnected cases
      if not g.is_connected():
          if certificate is False:
              if k is None:
                  return max(cc.treewidth() for cc in g.connected_components_subgraphs())
              else:
                  return all(cc.treewidth(k) for cc in g.connected_components_subgraphs())
          else:
              return Graph(sum([cc.treewidth(certificate=True).edges(labels=False)
                                for cc in g.connected_components_subgraphs()],[]),
                           name="Tree decomposition")

Indeed, one of the connected components has a tree decomposition that consists of a single vertex. So its list of edges is an empty list and we lose information when we just consider the concatenation of edges list.

Secondly, a tree decomposition is a tree by definition. But when I run

g=Graph({0:[1,2], 3:[4,5]})
g.treewidth(certificate=True)

the result is two non-connected edges. This minor problem can be corrected by adding an arbitrary edge between the i-th and i+1-th connected components of the result (for all possible i).

Change History (13)

comment:1 Changed 23 months ago by dcoudert

You are right and this is what we get when using tdlib (optional package)

sage: g = Graph({0:[1,2], 3:[4,5], 4:[5]})
sage: T = g.treewidth(algorithm='tdlib', certificate=True)
sage: print T.edges(labels=0)
[({3, 4, 5}, {0, 2}), ({0, 2}, {0, 1})]

Are you planing to write the patch ? If so I can review it.

comment:2 Changed 22 months ago by mlapointe

  • Branch set to u/mlapointe/two_erros_in_treewidth_for_non_connected_graphs

comment:3 Changed 22 months ago by mlapointe

  • Commit set to 7ea89b8684b7bc1727387f35856944056fa790e3
  • Status changed from new to needs_review

New commits:

7ea89b8trac 23546: Correcting the errors in treewidth

comment:4 Changed 22 months ago by dcoudert

The patch is working well. However, a few minor changes are needed.

  • :trac:`23546`:: -> The decomposition is a tree (:trac:`23546`)::. This will improve the documentation.
  • You must add an empty line after between the line with :trac:`23546` and the line sage: g = Graph({0:[1,2], 3:[4,5]}).
  • sage: vertices = set({}) -> sage: vertices = {}.
  • v = T[0].vertices()[0] -> v = next(T[0].vertex_iterator()). There is no need for first building the list of vertices. We can use the iterator to get the first vertex.
  • tree.add_edge([t.vertices()[0],v]) -> tree.add_edge(t.vertices()[0], v). Here also, there is no need for creating a list.

Thank you.

comment:5 Changed 22 months ago by vdelecroix

But... what is an erros!? ;-)

comment:6 Changed 22 months ago by dcoudert

  • Reviewers set to David Coudert
  • Summary changed from two erros in treewidth for non-connected graphs to two errors in treewidth for non-connected graphs

I have corrected the ticket title.

comment:7 Changed 22 months ago by git

  • Commit changed from 7ea89b8684b7bc1727387f35856944056fa790e3 to fc216636b3553e54e9b7ce3b89e2feae7bcc609b

Branch pushed to git repo; I updated commit sha1. New commits:

fc21663trac: 23546 implementing minors changing suggested by dcoubert.

comment:8 Changed 22 months ago by mlapointe

I have implemented all the suggestion except this one:

sage: vertices = set({}) -> sage: vertices = {}

since the object {} is a dictionary and I want to have an empty set.

comment:9 follow-up: Changed 22 months ago by dcoudert

In the example, the last test assumes an ordering of the vertices. This is not a good idea (actually, ticket #22349 proposes to remove the sorting).

sage: [1,2,3,4] == [4,3,2,1]
False

Please change to

sage: for s in t.vertices():
....:    vertices.update(s)
sage: vertices == set(g.vertices())
True

comment:10 Changed 22 months ago by git

  • Commit changed from fc216636b3553e54e9b7ce3b89e2feae7bcc609b to cb3f49228771d74ca8f6e448a1f9e1cdea7bb4a3

Branch pushed to git repo; I updated commit sha1. New commits:

cb3f492trac 23546: Remove the assumption on the other of vertices in the test.

comment:11 in reply to: ↑ 9 Changed 22 months ago by mlapointe

Replying to dcoudert:

In the example, the last test assumes an ordering of the vertices. This is not a good idea (actually, ticket #22349 proposes to remove the sorting).

sage: [1,2,3,4] == [4,3,2,1]
False

Please change to

sage: for s in t.vertices():
....:    vertices.update(s)
sage: vertices == set(g.vertices())
True

I agree and I have made the modification.

comment:12 Changed 22 months ago by dcoudert

  • Status changed from needs_review to positive_review

For me this patch is now good to go. Thank you.

comment:13 Changed 22 months ago by vbraun

  • Branch changed from u/mlapointe/two_erros_in_treewidth_for_non_connected_graphs to cb3f49228771d74ca8f6e448a1f9e1cdea7bb4a3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.