Opened 6 years ago
Closed 6 years ago
#22045 closed enhancement (fixed)
path_decomposition just returns vertex_separation output, it should derive the path decomposition instead
Reported by:  Rolf Morel  Owned by:  

Priority:  minor  Milestone:  sage7.5 
Component:  graph theory  Keywords:  vertexseparation, vertex_separation, pathdecomposition, path_decomposition, pathwidth 
Cc:  Merged in:  
Authors:  David Coudert  Reviewers:  Rolf Morel 
Report Upstream:  N/A  Work issues:  
Branch:  39822e8 (Commits, GitHub, GitLab)  Commit:  39822e8772127bdd0b939d0bc5a01332977ae7f6 
Dependencies:  Stopgaps: 
Description
Hi,
I am new to contributing to sage, so please bear with me.
Currently path_decomposition for graphs (in sage/graphs/graph_decompositions/vertex_separation) is implemented as no more than a wrapper round the vertex_separation function. While there exists a close relation between path decompositions and vertex separation it would be more natural to have path_decomposition return the pathwidth and an actual path decomposition, versus the current behaviour of returning the vertex separation number and a linear ordering that achieves this vertex separation number.
Due to Kinnersley [1], we know the vertex separation number is equal to the pathwidth and that there exists a simple mapping between a linear ordering for the vertex separation (number) of a graph and a path decomposition for the same graph. I already have an algorithm implementing this mapping on top of sage, but I would like to see that the path_decomposition function in sage actually returns a path decomposition, along side the pathwidth. Also, the current behaviour does not have much added value, if you wanted the pathwidth you could have just used the vertex_separation function.
Finally as the algorithms to compute the vertex separation (number) and pathwidth run in exponential time the cost of doing the mapping (in O(V^{2}E) time) is minor, and anybody wanting to forgo the cost of the mapping (because they are only interested in the pathwidth) could just call vertex_separation directly.
I am currently compiling sage in the hope of creating a patch. Please let me know if the ability to compute path decompositions would be considered a useful addition to sage.
A question regarding stability in sage: would it be considered better to modify the current path_decomposition function so as to return the pathwidth and a path decomposition, or would the current behaviour be considered stable and hence there would need to be some separate function to derive the path decomposition?
[1] The vertex separation number of a graph equals its pathwidth, Nancy G. Kinnersley, Information Processing Letters 42(6):345350, 1992.
Change History (17)
comment:1 Changed 6 years ago by
Keywords:  "vertex separation" "path decomposition" added; vertex separation path decomposition removed 

comment:2 Changed 6 years ago by
Keywords:  vertexseparation vertex_separation pathdecomposition path_decomposition added; "vertex separation" "path decomposition" removed 

comment:3 Changed 6 years ago by
Keywords:  pathwidth added; pathwitdh removed 

comment:4 Changed 6 years ago by
comment:5 Changed 6 years ago by
Yes, bringing pathwidth
in line with the current treewidth
API seems like an appropriate change as well.
The initial algorithm that I put together for decompositions is just a straightforward translation of the constructive proof for Theorem 3.1 in The vertex separation number of a graph equals its pathwidth by Kinnersley. Here is the function:
def decomposition1(g): pw, l_ord = vertex_separation(g) decomp = [] def l_cut(i): for j in range(i + 1): if any(n in l_ord[i+1:] for n in g.neighbors(l_ord[j])): yield l_ord[j] for i, i_node in enumerate(l_ord): decomp.append([i_node] + list(l_cut(i1))) return pw, decomp
I had not considered efficiency much (yet) for the above algorithm, but due to your comment I came up with a O(pw(G)*V + E)
algorithm. It builds on the previous algorithm. The first idea is to keep track of the maximum linear ordering index of a connected node per vertex, which makes it an
amortized O(1)
lookup whether a vertex at index j
connects to another vertex at some index m
of the ordering with m > i
for any position i
within the ordering (which is essentially the check in l_cut
).
For constructing a bag_i
for a vertex at index i
in the ordering we again consider all
nodes before i
in the ordering but now we exploit the property of path decompositions that
if a bag shares vertices with a previous bag, then all intermediate bags must also contain those
vertices. So in particular the previous bag must contain all nodes that are in bag_i
(except for the node at i
) and before i
in the ordering. So it suffices to check if the vertices of the previous bag are (still) connected to vertices beyond i
in the ordering.
(Note that the current psuedo code assumes undirected edges.)
def decomposition2(g): pw, l_ord = vertex_separation(g) decomp = [] l_ord_inv = {v : i for i, v in enumerate(l_ord)} max_l_ord_idx_of_neighs = {} for u, v, label in g.edges(): old_max_u = max_l_ord_idx_of_neighs.get(u, l_ord_inv[u]) max_u = max(l_ord_inv[v], old_max_u) max_l_ord_idx_of_neighs[u] = max_u old_max_v = max_l_ord_idx_of_neighs.get(v, l_ord_inv[v]) max_v = max(l_ord_inv[u], old_max_v) max_l_ord_idx_of_neighs[v] = max_v for i in range(len(l_ord)): bag_i = [l_ord[i]] prev_bag = decomp[i1] if i >= 1 else [] for vert_prev_bag in prev_bag: if max_l_ord_idx_of_neighs[vert_prev_bag] >= i: bag_i.append(vert_prev_bag) decomp.append(bag_i) return pw, decomp
There might still be some clever tricks to get the runtime further down, but versus the runtime
of vertrex_separation
it does not seem worth the effort.
Note that while these functions give correct path decompositions they produce V
bags, while
sometimes it is possible to do with less. A simple algorithm to produce less bags is to check for each bag (consecutively) if it is a proper subset of the next bag. Would this be a worthwhile addition?
And finally, any pointers for contributing the code to sage
?
comment:6 Changed 6 years ago by
There is something wrong with both methods, although the principle is good.
sage: G = graphs.PathGraph(5) sage: decomposition1(G) (1, [[0], [1, 0], [2, 1], [4, 2], [3, 2, 4]]) sage: decomposition2(G) (1, [[0], [1, 0], [2, 1], [4, 2], [3, 4, 2]])
I prefer the following method.
def linear_ordering_to_path_decomposition(G, L): """ """ from sage.graphs.graph_decompositions.vertex_separation import is_valid_ordering if not is_valid_ordering(G, L): raise ValueError("The input linear vertex ordering L is not valid for G.") seen = set() # already treated vertices covered = set() # vertices in the neighborhood of seen but not in seen bags = list() # The bags of the path decomposition # We build the bags of the pathdecomposition, and avoid adding useless bags for u in L: seen.add(u) covered.update(G.neighbors(u)) covered.difference_update(seen) new_bag = covered.union([u]) if bags: if new_bag.issubset(bags[1]): continue if new_bag.issuperset(bags[1]): bags.pop() bags.append(new_bag) # We now build a graph whose vertices are bags H = Graph() H.add_path([sage.sets.set.Set(bag) for bag in bags]) print bags return H
To start contributing, you can check http://doc.sagemath.org/html/en/developer/index.html and http://doc.sagemath.org/html/en/developer/manual_git.html
So you create a new git branch on your local sage installation. You do your changes (preferably with clear commits) and when you are ready, you push your changes to the trac server.
If you prefer, you can start as a reviewer: I do the changes and I soon as it's on the server, you can review it. You then have to check the code, try to install/compile on your system, play with it, check if it gives good answer, etc.
Let me know.
comment:7 Changed 6 years ago by
Authors:  → David Coudert 

Branch:  → u/dcoudert/pathwidth 
Commit:  → 39822e8772127bdd0b939d0bc5a01332977ae7f6 
Status:  new → needs_review 
I have pushed a proposal for discussed issues: expose method pathwidth with similar behavior than treewidth. Let me know if something is missing.
New commits:
65cadd2  trac #22045: add method to compute a path decomposition from an ordering

a64a67c  trac #22045: add method to compute pathwidth

44cbb14  trac #22045: expose method pathwidth for graphs

39822e8  trac #22045: fix doc and examples

comment:8 Changed 6 years ago by
The problem that you identified with the functions seems to originate from the vertex_separation
function. While the vertex separation number is correct (for the path graphs) the linear ordering
that is returned does not seems like a proper witness/certificate to this vertex separation number.
sage: G = graphs.PathGraph(3) sage: G.edges() [(0, 1, None), (1, 2, None)] sage: vertex_separation_BAB(G) # correct vertex separation number, incorrect ordering (1, [0, 2, 1]) sage: vertex_separation_MILP(G) # correct vertex separation number, incorrect ordering (1, [0, 2, 1]) sage: vertex_separation_exp(G) # correct vertex separation number, and correct ordering (1, [0, 1, 2])
Note that for the Branch and Bound and MILP algorithms the ordering has node 2 in the middle, which means that both it and node 0 to the left of it have a neighbor to the right of node 2, namely node 1 (third in the ordering). So by the definition of vertex separation (of an ordering) the vertex separation for this ordering is 2. While the exponential algorithm gives the correct witness to the vertex separation number being equal to 1.
Unless there is some kind of misunderstanding, it seems like the vertex_separation_BAB
and vertex_separation_MILP
do not give correct output. In particular sometimes they do not give back the linear ordering that acts as a witness to the vertex separation number that was found.
It seems prudent to me to first clear this up before looking into incorporating new code for path decompositions.
Would very much like to know what is going on here.
comment:9 Changed 6 years ago by
The way to measure the width of an ordering used in this module is clearly presented at the beginning of the module's documentation. It is equivalent to [1], up to reversing the ordering. I have to say that it is more intuitive for me to count the number of neighbors on the right of the nodes on the left, than the number of nodes of the left that have a neighbor on the right. The simple method I wrote to go from an ordering to a decomposition is based on this.
If you want your methods to return correct results, just add l_ord.reverse()
inside.
[1] Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, Dimitrios M. Thilikos: A Note on Exact Algorithms for Vertex Ordering Problems on Graphs. Theory Comput. Syst. 50(3): 420432 (2012) http://dx.doi.org/10.1007/s0022401193120
comment:11 Changed 6 years ago by
Apologies for taking so long to get back to this. I looked at it some time ago and didn't understand your algorithm (with the notion of the ordering reversed). Decided to get back to it later and that got postponed.
Thank you for clearing up the matter of the orderings. The vertex separations I tried on a my limited number of test graphs happened to be okay even if they were reversed and with only knowledge of the other definition I didn't look in detail at the definition given at the top of the file.
I verified the properties of a path decomposition with pathwidth equal to the vertex separation for your algorithm and they are indeed fine. I ran the pathwidth
method on a couple of graphs and this seems to work fine as well.
So, looks good to me.
comment:12 Changed 6 years ago by
Have you tried to run the doc tests using a command like sage btp src/sage/graphs/graph_decompositions/vertex_separation.pyx
? same with graph.py
since this patch exposes the method for Graph
. You can also try to build the doc using e.g. sage docbuild reference/graphs html
and check if it looks good.
If everything is ok, then you can set the patch to positive review, or let me know if I should improve something.
It will now be easier to verify if a graph is asteroidal triple free graphs then we have treewidth = pathwidth ;)
By the way, I could change ref CMN14 with the journal version, but it's not so important.
comment:13 Changed 6 years ago by
Status:  needs_review → positive_review 

Ran the tests you suggested and checked the documentation. All the tests passed and the docs look fine. Everything seems okay from here.
comment:15 Changed 6 years ago by
Reviewers:  → Rolf Morel 

I put my real name in the 'Reviewers' field.
comment:17 Changed 6 years ago by
Branch:  u/dcoudert/pathwidth → 39822e8772127bdd0b939d0bc5a01332977ae7f6 

Resolution:  → fixed 
Status:  positive_review → closed 
Welcome. I can certainly help here.
We could add a method
pathwidth
with similar behavior thantreewidth
. Then we can change the behavior ofpath_decomposition
but we must add an appropriate warning message (decprecation?).What's your algorithm? the announced complexity seems excessive. I believe it can be done in
O(V*E)
or evenO(E)
.