Context Navigation

← Previous Ticket
Next Ticket →

#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

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 2 years 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 2 years ago by mlapointe

Branch set to u/mlapointe/two_erros_in_treewidth_for_non_connected_graphs

comment:3 Changed 2 years ago by mlapointe

Commit set to 7ea89b8684b7bc1727387f35856944056fa790e3
Status changed from new to needs_review

New commits:

7ea89b8 trac 23546: Correcting the errors in treewidth

comment:4 Changed 2 years 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 2 years ago by vdelecroix

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

comment:6 Changed 2 years 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 2 years ago by git

Commit changed from 7ea89b8684b7bc1727387f35856944056fa790e3 to fc216636b3553e54e9b7ce3b89e2feae7bcc609b

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

fc21663 trac: 23546 implementing minors changing suggested by dcoubert.

comment:8 Changed 2 years 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: ↓ 11 Changed 2 years 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 2 years ago by git

Commit changed from fc216636b3553e54e9b7ce3b89e2feae7bcc609b to cb3f49228771d74ca8f6e448a1f9e1cdea7bb4a3

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

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

comment:11 in reply to: ↑ 9 Changed 2 years 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 2 years 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 2 years 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.

Download in other formats: