Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

find embedded subgraphs

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 may case the graph has multiedges (and loops, but we can ignore this here).

find embedded subgraphs

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)

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 may my case the graph has multiedges (and loops, but we can ignore this here).