Opened 4 years ago
Closed 4 years ago
#23546 closed defect (fixed)
two errors in treewidth for nonconnected graphs
Reported by:  evandomme  Owned by:  

Priority:  minor  Milestone:  sage8.1 
Component:  graph theory  Keywords:  tree decomposition; treewidth 
Cc:  Merged in:  
Authors:  Mélodie Lapointe, Élise Vandomme  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  cb3f492 (Commits, GitHub, GitLab)  Commit:  cb3f49228771d74ca8f6e448a1f9e1cdea7bb4a3 
Dependencies:  Stopgaps: 
Description
The function treewidth() with the option certificate=True encounters two problems on nonconnected 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 treewidth 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 nonconnected edges. This minor problem can be corrected by adding an arbitrary edge between the ith and i+1th connected components of the result (for all possible i).
Change History (13)
comment:1 Changed 4 years ago by
comment:2 Changed 4 years ago by
 Branch set to u/mlapointe/two_erros_in_treewidth_for_non_connected_graphs
comment:3 Changed 4 years ago by
 Commit set to 7ea89b8684b7bc1727387f35856944056fa790e3
 Status changed from new to needs_review
New commits:
7ea89b8  trac 23546: Correcting the errors in treewidth

comment:4 Changed 4 years ago by
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 linesage: 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 4 years ago by
But... what is an erros
!? ;)
comment:6 Changed 4 years ago by
 Reviewers set to David Coudert
 Summary changed from two erros in treewidth for nonconnected graphs to two errors in treewidth for nonconnected graphs
I have corrected the ticket title.
comment:7 Changed 4 years ago by
 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 4 years ago by
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 followup: ↓ 11 Changed 4 years ago by
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 4 years ago by
 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 4 years ago by
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] FalsePlease 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 4 years ago by
 Status changed from needs_review to positive_review
For me this patch is now good to go. Thank you.
comment:13 Changed 4 years ago by
 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
You are right and this is what we get when using
tdlib
(optional package)Are you planing to write the patch ? If so I can review it.