Ask Your Question
0

subgraph_search_iterator gives duplicate subgraphs

asked 2023-06-23 14:26:24 +0100

licheng gravatar image

updated 2023-06-24 10:34:36 +0100

I use subgraph_search_iterator to obtain all the subgraphs isomorphic to $H$ of a graph $G$. However, in the following example, I found that many obtained subgraphs appear to be duplicates, which surprises me. Have I misunderstood this function?

G=graphs.OctahedralGraph()
H = graphs.CycleGraph(3)
L = list(G.subgraph_search_iterator(H, induced=False,return_graphs=False)) 
len(L)

image description

L[1]
L[4]
L[18]

We will see that the 3-cycle formed by vertices 0, 1, and 3 appears three times. What could be the reason for this? How can we avoid such occurrences?


Edits: In fact, the 3-cycle formed by vertices 0, 1, and 3 appears six times.

Perhaps the $C_3$ are too specific and overshadowing something. If we consider the following example, we will discover that $H$ appears as many times as the number of copies of H without labels multiplied by the order of automorphisms of $H$. (label $H$ ?)

G=graphs.OctahedralGraph()
H=copy(G)
H.delete_edges( [(0,1), (1,2), ( 0,2 )])
print( sum(1 for _ in G.subgraph_search_iterator(H, induced=False,return_graphs=False) ) )
L = { tuple(g.edges(labels=False,sort_vertices=True,sort=True)) for g in G.subgraph_search_iterator(H, induced=False) }
print(len(L))
H.automorphism_group( ).order( )

image description

48
8
6
edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2023-06-23 17:03:14 +0100

Max Alekseyev gravatar image

updated 2023-06-23 17:03:57 +0100

It looks like a bug. Please submit a bugreport at https://github.com/sagemath/sage/issues

Meanwhile, a workaround would be to store subgraphs as sorted tuples of edges in a set, which will eliminate the duplicates:

G=graphs.OctahedralGraph()
H = graphs.CycleGraph(3)
print( sum(1 for _ in G.subgraph_search_iterator(H, induced=False,return_graphs=False) ) )
L = { tuple(g.edges(labels=False,sort_vertices=True,sort=True)) for g in G.subgraph_search_iterator(H, induced=False) }
print(len(L))

This prints 48 and 8, meaning that among the 48 reported subgraphs only 8 are unique.

edit flag offensive delete link more

Comments

1

Why it was made that way is a mystery to me as well. It appears to be giving back all possible $H$-automorphisms. I would submit a bugreport. See https://github.com/sagemath/sage/issu...

licheng gravatar imagelicheng ( 2023-06-24 03:01:15 +0100 )edit
1

Looks like it was meant to return pairs (S,f) where S is a subgraph of G and f is a bijective mapping of H into S. However, it returns only S. The duplicates correspond to different ways to map H into S.

In your example: H is a 3-cycle, it can be mapped to another 3-cycle in 6 different ways. Hence, we have $48 = 8\cdot 6$.

Max Alekseyev gravatar imageMax Alekseyev ( 2023-06-24 04:47:23 +0100 )edit

Yes. Indeed. It appears not only three times but six times.

licheng gravatar imagelicheng ( 2023-06-24 05:51:55 +0100 )edit

3 rotations and 2 "flips over" give 6 ways.

Max Alekseyev gravatar imageMax Alekseyev ( 2023-06-24 06:19:35 +0100 )edit

Yes. See new Edits.

licheng gravatar imagelicheng ( 2023-06-24 09:45:08 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2023-06-23 14:26:24 +0100

Seen: 184 times

Last updated: Jun 24 '23