Opened 3 years ago

Closed 3 years ago

#22045 closed enhancement (fixed)

path_decomposition just returns vertex_separation output, it should derive the path decomposition instead

Reported by: RMorel Owned by:
Priority: minor Milestone: sage-7.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) 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 path-width, Nancy G. Kinnersley, Information Processing Letters 42(6):345-350, 1992.

Change History (17)

comment:1 Changed 3 years ago by RMorel

  • Keywords "vertex separation" "path decomposition" added; vertex separation path decomposition removed

comment:2 Changed 3 years ago by RMorel

  • Keywords vertexseparation vertex_separation pathdecomposition path_decomposition added; "vertex separation" "path decomposition" removed

comment:3 Changed 3 years ago by RMorel

  • Keywords pathwidth added; pathwitdh removed

comment:4 Changed 3 years ago by dcoudert

Welcome. I can certainly help here.

We could add a method pathwidth with similar behavior than treewidth. Then we can change the behavior of path_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 even O(|E|).

comment:5 Changed 3 years ago by RMorel

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 path-width 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(i-1)))
    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[i-1] 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 3 years ago by dcoudert

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 path-decomposition, 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 3 years ago by dcoudert

  • Authors set to David Coudert
  • Branch set to u/dcoudert/pathwidth
  • Commit set to 39822e8772127bdd0b939d0bc5a01332977ae7f6
  • Status changed from new to 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:

65cadd2trac #22045: add method to compute a path decomposition from an ordering
a64a67ctrac #22045: add method to compute pathwidth
44cbb14trac #22045: expose method pathwidth for graphs
39822e8trac #22045: fix doc and examples

comment:8 Changed 3 years ago by RMorel

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 3 years ago by dcoudert

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): 420-432 (2012) http://dx.doi.org/10.1007/s00224-011-9312-0

comment:10 Changed 3 years ago by dcoudert

Any help reviewing this patch is more than welcome.

comment:11 Changed 3 years ago by RMorel

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 3 years ago by dcoudert

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 3 years ago by RMorel

  • Status changed from needs_review to 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:14 Changed 3 years ago by tscrim

You will need to put your real name as the reviewer.

comment:15 Changed 3 years ago by RMorel

  • Reviewers set to Rolf Morel

I put my real name in the 'Reviewers' field.

comment:16 Changed 3 years ago by dcoudert

Thanks for the review.

comment:17 Changed 3 years ago by vbraun

  • Branch changed from u/dcoudert/pathwidth to 39822e8772127bdd0b939d0bc5a01332977ae7f6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.