Seems like you are searching for non labelled occurrences of cycles. In such case dividing by the size of the automorphism group of the graph that is being searched for might do the trick. Say you are trying to count the number of unlabelled appearances of graph H in graph G. You can define
subgraph_count = lambda G,H: G.subgraph_search_cound(H)/H.automorphism_group(return_group=False,order=True)
and then use
G=graphs.Grid2dGraph(3,3)
H=graphs.CycleGraph(4)
subgraph_count(G,H)
This should output 4, as expected.
For the particular case of cycles, if you are searching for cycles of length k then it suffices to divide by 2*k, so the following should work.
cycle_subgraph_count = lambda G,k: G.subgraph_search_cound(graphs.CycleGraph(k))/(2*k)
then
G=graphs.Grid2dGraph(10,10)
cycle_subgraph_count(G,4)
should output 81.
Asked: 2016-12-01 09:07:54 +0200
Seen: 1,144 times
Last updated: Dec 03 '16
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
Would it suffice to divide by the size of the automorphism group of the subgraph that is being searched for, perhaps? In other words, are you trying to count non labelled occurrences of cycles? For the particular case stated in your question, dividing by 8 might do the trick.
Yes ,That's what I'm trying to do,but what is 8 that it should be divided by?
I meant you should divide by 8 if you are searching 4-cycles, since the size of the automorphism group of the 4-cycle is 8. See answer below for further details.