find embedded subgraphs

asked 2017-12-13 16:13:56 +0100

ctst
81 ●1 ●4 ●12

updated 2017-12-13 16:54:41 +0100

Hi there,

is there a method to find all embedded copies of a graph in another graph, e.g. given two graphs H and G I want something like:

G = graphs.RandomGNP(10,.3)       #some graph
H = Graph({1:[1,2], 2:[1,2]})     #some other graph
list = G.find_subgraphs(H, homeomorphic=False/True)

Where the elements list are all the subgraphs in G which are isomorphic/homeomorphic to H. If this is too much to ask for, there should be at least a method to return all cycles in G (i.e. closed paths in G with each vertex at most once). Since there exists the Hamiltonian cycle method this one should exist too.

PS: In my case the graph has multiedges (and loops, but we can ignore this here).

edit retag flag offensive close merge delete

Comments

Sadly, the following is only available on directed graphs

sage: G = graphs.RandomGNP(10,.3)
sage: G.to_directed().all_simple_cycles()

vdelecroix ( 2017-12-15 00:07:16 +0100 )edit

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2017-12-13 16:43:45 +0100

tmonteil
27423 ●31 ●204 ●517 http://wiki.sagemath.o...

You can use the subgraph_search_iterator method:

sage: G = Graph([[0,1], [1,2], [2,3], [3,1], [2,4], [3,4], [4,5]]) 
sage: H = Graph([[0,1], [1,2], [2,3], [3,1]]) 
sage: list(G.subgraph_search_iterator(H))
[[0, 1, 2, 3],
 [0, 1, 3, 2],
 [1, 2, 3, 4],
 [1, 2, 4, 3],
 [1, 3, 2, 4],
 [1, 3, 4, 2],
 [4, 2, 1, 3],
 [4, 2, 3, 1],
 [4, 3, 1, 2],
 [4, 3, 2, 1],
 [5, 4, 2, 3],
 [5, 4, 3, 2]]

Note that the order of the returned vertices is important.

Regarding cycles, you can have a look at the cycle_basis method, which gives you a compact representation of cycles:

sage: G.cycle_basis()
[[2, 3, 1], [2, 4, 3]]

edit flag offensive delete link

Comments

First of all thanks for the quick response. After some testing I found out, that the subgraph-function doesn't recognize loops (or ignores them), not sure how it works with multi-edges, since the list are vertices (also mentioned in the manual). (I wanted to check for barbells in a graph: Barb = Graph({0:[0,1], 1:[0,1]}) Gamma = Graph({1:[1,2,4],2:[1,3,5],3:[2,3,6],4:[1,4,5],6:[3,5,6]}); subg = list(Gamma.subgraph_search_iterator(Barb)) subg == list(Gamma.subgraph_search_iterator(Graph([[0,1]]))) If you want to see an example where it breaks (it gives the edges). You don't know by any chance a fix and a homeomorphic instead of isomorphic embedding (meaning edges can be send to several edges).

ctst ( 2017-12-13 18:58:10 +0100 )edit

add a comment

answered 2017-12-13 21:55:31 +0100

ctst
81 ●1 ●4 ●12

updated 2017-12-13 21:56:43 +0100

I felt a little bit uncomfortable with 'cycle_basis' since it gives me a basis for all sets of disjoint cycles, but I actually want a set of all simple cycles (disjoint vertices).

A non optimal solution i came up with (using the implemented path function):

def simple_cycles(Gamma):
    """
    Returns a list of all simple cycles in the given graph Gamma as lists of vertices.
    """
    G = Graph(Gamma)    #make copy of given graph
    edges = G.edges()
    cycleList =[]
    for edge in edges:
        G.delete_edge(edge)        #delete starting edge to avoid duplicates
        if edge[0]==edge[1]:         #if its loop
            cycleList.append([edge[0], edge[1]])        
        for path in G.all_paths(edge[1], edge[0]):
            if(len(path)>1):
                cycleList.append([edge[0]]+path)
    return cycleList;

Optimizations or corrections will be appreciated (e.g. the description right now is horrible). Also I am not sure how well this behaves with multiedges.

edit flag offensive delete link

add a comment

Your Answer

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

Add Answer

find embedded subgraphs

Comments

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

find embedded subgraphs edit

Comments

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

find embedded subgraphs