ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 14 Dec 2017 17:07:16 -0600find embedded subgraphshttp://ask.sagemath.org/question/40140/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).Wed, 13 Dec 2017 09:13:56 -0600http://ask.sagemath.org/question/40140/find-embedded-subgraphs/Comment by vdelecroix for <p>Hi there,</p>
<p>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:</p>
<pre><code>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)
</code></pre>
<p>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. </p>
<p>PS: In my case the graph has multiedges (and loops, but we can ignore this here).</p>
http://ask.sagemath.org/question/40140/find-embedded-subgraphs/?comment=40163#post-id-40163Sadly, the following is only available on directed graphs
sage: G = graphs.RandomGNP(10,.3)
sage: G.to_directed().all_simple_cycles()Thu, 14 Dec 2017 17:07:16 -0600http://ask.sagemath.org/question/40140/find-embedded-subgraphs/?comment=40163#post-id-40163Answer by ctst for <p>Hi there,</p>
<p>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:</p>
<pre><code>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)
</code></pre>
<p>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. </p>
<p>PS: In my case the graph has multiedges (and loops, but we can ignore this here).</p>
http://ask.sagemath.org/question/40140/find-embedded-subgraphs/?answer=40144#post-id-40144I 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.Wed, 13 Dec 2017 14:55:31 -0600http://ask.sagemath.org/question/40140/find-embedded-subgraphs/?answer=40144#post-id-40144Answer by tmonteil for <p>Hi there,</p>
<p>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:</p>
<pre><code>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)
</code></pre>
<p>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. </p>
<p>PS: In my case the graph has multiedges (and loops, but we can ignore this here).</p>
http://ask.sagemath.org/question/40140/find-embedded-subgraphs/?answer=40141#post-id-40141You 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]]
Wed, 13 Dec 2017 09:43:45 -0600http://ask.sagemath.org/question/40140/find-embedded-subgraphs/?answer=40141#post-id-40141Comment by ctst for <p>You can use the <code>subgraph_search_iterator</code> method:</p>
<pre><code>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]]
</code></pre>
<p>Note that the order of the returned vertices is important.</p>
<p>Regarding cycles, you can have a look at the <code>cycle_basis</code> method, which gives you a compact representation of cycles:</p>
<pre><code>sage: G.cycle_basis()
[[2, 3, 1], [2, 4, 3]]
</code></pre>
http://ask.sagemath.org/question/40140/find-embedded-subgraphs/?comment=40142#post-id-40142First 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).Wed, 13 Dec 2017 11:58:10 -0600http://ask.sagemath.org/question/40140/find-embedded-subgraphs/?comment=40142#post-id-40142