Ask Your Question
2

How to find the spanning elementary subgraphs of a given graph

asked 2018-09-04 15:02:42 +0200

rewi gravatar image

updated 2022-02-06 20:10:05 +0200

consider the following definition: A subgraph $H$ of a graph $G$ is called an elementary subgraph if each component of $H$ is either an edge ( $K_{2}$ ) or a cycle of length at least $3$. A spanning elementary subgraph is a subgraph having all components either path(i.e. $K_{2}$) or cycles and verex set is same as those of $G$. for example consider the graph $C_{4}$ with $V(G)$={1,2,3,4}. then it has 3 spanning elementary subgraphs two edge components namely {12,34};{14,23} and the whole cycle itself.The cycle is named in anticlockwise direction. Now my problem is: Consider the following code:

G=graphs.EmptyGraph()
G.add_edges([(1,2),(2,3),(3,4),(4,5),(5,1),(6,5),(6,8),(8,9),(7,9),(7,6),(7,10),(10,11),(10,12),(11,12)])
G.show()

Can we have a sage code that gives all possible spanning subgraphs of this graph.

edit retag flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted
3

answered 2018-09-17 19:56:17 +0200

tmonteil gravatar image

updated 2018-09-17 20:05:04 +0200

There is a generic tool for solving such problems without having to think too much: Integer Linear Programming.

For each edge $uv$ of your graph, you define two binary variables (with values in {0, 1} ): one named $c(uv)$ telling that a cycle from you spanning configuration that is passing through the edge $uv$, and one names $e(uv)$ telling whether the edge the edge $uv$ is selected as an edge of the spanning configuration.

Then, you add the following constraint: for each vertex $v$, there is either exactly one edge adjacent to it that is selected to be an edge of the spanning configuration, or there are exactly two edges adjacent to it that are selected to be part of a cycle of the spanning configuration.

This constraints translates into the following linear equalities: $\forall v \in V(G), \sum_{uv \in E(G)} 2*e(uv) + c(uv) =1$ (E)

Hence, the set of solutions you want can be seen as the set of integer points of the polytope defined by the equation (E) together with the equations $0\leq e(uv)\leq1$ and $0\leq c(uv)\leq1$ for all edge $uv \in E(G)$.

The way to define this polytope in Sage is done by using the polyhedron method of the MixedIntegerLinearProgram class.

Here is the code of the function (some explanations will follow):

def spanning_elementary_subgraphs(G):
    p = MixedIntegerLinearProgram(solver='ppl')
    e = p.new_variable(binary=True)
    c = p.new_variable(binary=True)

    # those are useless constraints, only to control the order in which the variables are created, see discussion below
    for edge in G.edges(labels=False):
        p.add_constraint(e[edge] >= 0)
    for edge in G.edges(labels=False):
        p.add_constraint(c[edge] >= 0)

    for v in G.vertices():
        p.add_constraint(sum(2*e[edge] + c[edge] for edge in G.edges_incident(v, labels=False)) == 2)

    P = p.polyhedron(backend='normaliz')
    for i,L in enumerate(P.integral_points()):
        edges = []
        cycle_edges = []
        for j,edge in enumerate(G.edges(labels=False)):
            if L[j] == 1:
                edges.append(edge)
            if L[j+G.num_edges()] == 1:
                cycle_edges.append(edge)
        H = Graph(cycle_edges, format='list_of_edges')
        yield {'edges': edges, 'cycles': H.connected_components()}

This function returns an iterator over all solutions. At each iteration, you get a dictionary

Here is it working on your example:

sage: G = graphs.EmptyGraph()
sage: G.add_edges([(1,2),(2,3),(3,4),(4,5),(5,1),(6,5),(6,8),(8,9),(7,9),(7,6),(7,10),(10,11),(10,12),(11,12)])

sage: s = spanning_elementary_subgraphs(G)
sage: list(s)
[{'cycles': [[1, 2, 3, 4, 5], [6, 7, 8, 9], [10, 11, 12]], 'edges': []},
 {'cycles': [[1, 2, 3, 4, 5], [10, 11, 12]], 'edges': [(6, 8), (7, 9)]},
 {'cycles': [[1, 2, 3, 4, 5], [10, 11, 12]], 'edges': [(6, 7), (8, 9)]},
 {'cycles': [], 'edges': [(1, 2), (3, 4), (5, 6), (7, 10), (8, 9), (11, 12)]}]

So, you can see that there are exactly 4 possible spanning configurations.

Now, some more explanations about the code.

First, when we construct the polyhedron, we have to use the normaliz backend or the computation will be too slow. To be able to use it, you have to install the pynormaliz optional package, by typing from a terminal:

sage -i pynormaliz

Then, there is a total of $2*|E(G)|$ variables: for each edge $uv$, there is $e(uv)$ and $c(uv)$. Each variable will be an element of the basis of the space where the polyhedron lives.

The problem is that, in the current Sage user interface, there is no easy way to see order of the variables that are used to define that basis.

The variables are created on the fly when used for the first time. Since there is a loop over the vertices $v$ and then a loop over the edges $uv$ adjacent to the current vertex $v$ and then a constraint involving both $e(uv)$ and $c(uv)$, it is hard to guess the order of the basis.

Hence, we added some useless constraints in two flat loops in whch the edges appear in a simple-to-handle order.

Note that it trick has nothing to do with interesting algorithmics or mathematics, it is only an annoyance of the current Sage user interface and should be solved by Sage developers (a ticket will follow).

edit flag offensive delete link more
1

answered 2018-09-05 17:48:02 +0200

updated 2022-02-05 15:37:40 +0200

A perfect matching (if the graph has one) is a spanning elementary subgraph according your definition. You can get all the perfect matchings (only 1 in your graph) using

sage: list(G.perfect_matchings())
[[(7, 10), (1, 2), (11, 12), (3, 4), (5, 6), (8, 9)]]

Now if you want all spanning elementary subgraphs, you have to design a specific algorithm.

EDIT:

A solution is to enumerate all elementary subgraphs and to prune subgraphs without enough vertices.

def elementary_subgraphs(G, nmin=0):
    r"""
    Iterator over the elementary subgraphs of `G`.

    A subgraph `H` of a graph `G` is *elementary* if each of its connected
    components is either an edge or a cycle.

    INPUT:

    - ``G`` -- a Graph

    - ``nmin`` -- integer (default: ``0``); lower bound on the number of
      vertices involved in the elementary subgraphs of any returned
      solution. When set to ``G.order()``, the subgraphs must be spanning.
    """
    G._scream_if_not_simple()

    def rec(H, low):
        if not H.size():
            yield {'cycles': [], 'edges': []}, 0
            return
        if H.order() < low:
            # no solution
            return

        # We select an edge e = (u, v) of H and remove it
        u, v = next(H.edge_iterator(labels=False))
        H.delete_edge((u, v))

        # Case 1: return solutions without e
        for sol, n in rec(H, low):
            if n >= low:
                yield sol, n

        # Case 2: select e as an isolated edge
        I = H.edges_incident([u, v])
        H.delete_vertices([u, v])
        for sol, n in rec(H, low - 2):
            if n + 2 >= low:
                sol['edges'].append((u, v))
                yield sol, n + 2
        H.add_vertices([u, v])
        H.add_edges(I)

        # Case 3: select e as part of a cycle
        for P in H.all_paths(u, v):
            C = [(P[i], P[i + 1]) for i in range(len(P) - 1)]
            C.append((u, v))
            K = H.copy()
            K.delete_vertices(P)
            nP = len(P)
            for sol, n in rec(K, low - nP):
                if n + nP >= low:
                    sol['cycles'].append(C)
                    yield sol, n + nP

        # Finally restore edge e
        H.add_edge(u, v)

    for sol, n in rec(G.copy(), nmin):
        if n >= nmin:
            yield sol

The idea behind the algorithm is, given any edge e=(u,v), to

  1. either search for solutions without edge e. We return all elementary subgraphs of G-e.
  2. or e is in the solution and is a connected component. We remove the end vertices of e from the graph, search for all elementary subgraphs of the remaining graph, and add e to each found subgraph before returning it
  3. or e is part of a cycle. We enumerate all paths between the end vertices of e. Each path combined with e forms a cycle. For each of these cycles, we search for all elementary subgraphs of the graph G without the vertices of the cycle.

We get the spanning elementary subgraphs as follows:

sage: G = Graph([(1,2),(2,3),(3,4),(4,5),(5,1),(6,5),(6,8),(8,9),(7,9),(7,6),(7,10),(10,11),(10,12),(11,12)])
sage: for s in elementary_subgraphs(G, G.order()):
....:     print(s)
{'cycles': [], 'edges': [(8, 9), (7, 10), (5, 6), (3, 4), (1, 2), (11, 12)]}
{'cycles': [[(1, 5), (5, 4), (4, 3), (3, 2), (1, 2)], [(10, 11), (11, 12), (10, 12)]], 'edges': [(7, 9), (6, 8)]}
{'cycles': [[(1, 5), (5, 4), (4, 3), (3, 2), (1, 2)], [(10, 11), (11, 12), (10, 12)]], 'edges': [(8, 9), (6, 7)]}
{'cycles': [[(6, 8), (8, 9), (9, 7), (6, 7)], [(1, 5), (5, 4), (4, 3), (3, 2), (1, 2)], [(10, 11), (11, 12), (10, 12)]], 'edges': []}

We can also get the elementary subgraphs with at least G.order() - 1 vertices:

sage: len(list(elementary_subgraphs(G, G.order()-1)))
32

or all elementary subgraphs (including the empty graph):

sage: len(list(elementary_subgraphs(G, 0)))
647

This method is faster for this graph than the (nice) solution using linear programming:

sage: %timeit list(spanning_elementary_subgraphs(G))
16.2 s ± 3.41 s per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit list(elementary_subgraphs(G, G.order()))
14.3 ms ± 459 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
edit flag offensive delete link more

Comments

Thank you. I am trying. But I have not been able to find the algorithm .

rewi gravatar imagerewi ( 2018-09-05 18:00:59 +0200 )edit

Another solution for the enumeration of elementary subgraphs: https://ask.sagemath.org/question/609...

David Coudert gravatar imageDavid Coudert ( 2022-02-08 09:10:41 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-09-04 15:02:42 +0200

Seen: 1,152 times

Last updated: Feb 06