Ask Your Question

Revision history [back]

click to hide/show revision 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)

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 2k2*k, so the following should work.

    cycle_subgraph_count = lambda G,k: G.subgraph_search_cound(graphs.CycleGraph(k))/(2*k)

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.