1 | initial version |
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 2k
, so the following should work.
cycle_subgraph_count = lambda G,k: G.subgraph_search_cound(graphs.CycleGraph(k))/(2*k)
2 | No.2 Revision |
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
, so the following should work.2k2*k
cycle_subgraph_count = lambda G,k: G.subgraph_search_cound(graphs.CycleGraph(k))/(2*k)
3 | No.3 Revision |
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
.