szhorvat / IGraphM

IGraph/M is the igraph interface for Mathematica
http://szhorvat.net/mathematica/IGraphM
Other
91 stars 17 forks source link

Is there a problem with the function IGLADFindSubisomorphisms? #125

Closed lichengzhang1 closed 2 years ago

lichengzhang1 commented 2 years ago

Cross-posted at how-to-properly-display-some-highlight-subgraphs.

I want to highlight all the subgraphs isomorphic to $K{3,3}$ in a graph. I followed the codes from document (IGLADFindSubisomorphisms) and the number "30" should be correct (The built-in function (FindIsomorphicSubgraph[g, CompleteGraph[{3, 3}], All]) goes to verify). But some graphs from the output shows something not isomorphic to $K{3,3}$.

Needs["IGraphM`"]
g=Graph[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, {UndirectedEdge[1, 2], UndirectedEdge[1, 3], UndirectedEdge[1, 4], 
UndirectedEdge[2, 5], UndirectedEdge[4, 5], UndirectedEdge[2, 6], UndirectedEdge[2, 7], UndirectedEdge[2, 8], 
UndirectedEdge[3, 8], UndirectedEdge[3, 9], UndirectedEdge[4, 9], UndirectedEdge[5, 10], UndirectedEdge[6, 10], 
UndirectedEdge[9, 10], UndirectedEdge[6, 11], UndirectedEdge[7, 11], UndirectedEdge[9, 11], UndirectedEdge[7, 12], 
UndirectedEdge[8, 12], UndirectedEdge[9, 12], UndirectedEdge[1, 8], UndirectedEdge[2, 3], UndirectedEdge[1, 9], 
UndirectedEdge[3, 4], UndirectedEdge[1, 5], UndirectedEdge[4, 2], UndirectedEdge[2, 10], UndirectedEdge[5, 6], 
UndirectedEdge[2, 11], UndirectedEdge[6, 7], UndirectedEdge[2, 12], UndirectedEdge[7, 8], UndirectedEdge[3, 12], 
UndirectedEdge[8, 9], UndirectedEdge[4, 10], UndirectedEdge[9, 5], UndirectedEdge[6, 9], UndirectedEdge[10, 11], 
UndirectedEdge[7, 9], UndirectedEdge[11, 12]}, {FormatType -> TraditionalForm}];
HighlightGraph[g1, Subgraph[g, #], 
   GraphHighlightStyle -> "Thick"] & /@ 
 Union[Sort@*Values /@ 
   IGLADFindSubisomorphisms[CompleteGraph[{3, 3}], g]]

image

Is there a problem with the sample code in the help documentation or is the function IGLADFindSubisomorphisms incorrect?

Version information

szhorvat commented 2 years ago

The issue is that you are highlighting not the matches, but subgraphs induced but the vertices of the matches. I wrote an answer at https://mathematica.stackexchange.com/a/274630/12