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

edit retag close merge delete

1

Sadly, the following is only available on directed graphs

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

( 2017-12-14 17:07:16 -0600 )edit

Sort by » oldest newest most voted

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.

more

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]]

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).

( 2017-12-13 11:58:10 -0600 )edit