Ask Your Question

find embedded subgraphs

asked 2017-12-13 09:13:56 -0600

ctst gravatar image

updated 2017-12-13 09:54:41 -0600

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



Sadly, the following is only available on directed graphs

sage: G = graphs.RandomGNP(10,.3)
sage: G.to_directed().all_simple_cycles()
vdelecroix gravatar imagevdelecroix ( 2017-12-14 17:07:16 -0600 )edit

2 answers

Sort by ยป oldest newest most voted

answered 2017-12-13 14:55:31 -0600

ctst gravatar image

updated 2017-12-13 14:56:43 -0600

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]):
    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 more

answered 2017-12-13 09:43:45 -0600

tmonteil gravatar image

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 more


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 gravatar imagectst ( 2017-12-13 11:58:10 -0600 )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


Asked: 2017-12-13 09:13:56 -0600

Seen: 29 times

Last updated: Dec 13 '17