Opened 4 years ago
Closed 4 years ago
#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, GitHub, GitLab) | 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 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 non-connected graphs to two errors in treewidth for non-connected 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 follow-up: ↓ 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.