Check if two graphs have same shape

Question

How can I check if two graphs have same shape or not? By shape I mean the two graphs are equivalent under a set of "name" replacements, like:

Graph[{1->2,2->3,3->1}] == Graph[{1->3,3->2,2->1}]
Graph[{1->2,2->3,3->1}] != Graph[{1->2,2->3,3->4,4->1}]

And by the way how can I check if they have same topological(?) shape, which means

Graph[{1->2,2->3,3->1}] == Graph[{1->2,2->3,3->4,4->1}]
Graph[{1->2,2->3,3->1}] != Graph[{1->2,2->3,3->4,4->1,1->5,5->2,2->1}]

Answer 1

The first equivalence you mention is called isomorphism. Use IsomorphicGraphQ.

The second is not entirely clear to me, but you probably mean homeomorphism.

It seems reasonable (but I have not proven it!) that two directed graphs would be homeomorphic if we obtain isomorphic graphs after repeatedly removing vertices that have one incoming and one outgoing edge, like vertex 2 below, and replacing them with a single edge (would be 1 -> 3 below).

To avoid obtaining multigraphs or self loops, the removal should only be done if vertices 1 and 3 are distinct and there is no edge 1 -> 3 already.

Here's an implementation of this for directed graphs (since that is what you have in your example):

out[g_, v_] := First@DeleteCases[VertexOutComponent[g, v], v]
in[g_, v_] := First@DeleteCases[VertexInComponent[g, v], v]

smooth[graph_?DirectedGraphQ]:=
    Module[{g=graph,candidates,v},
        While[True,
            candidates=Pick[VertexList[g],Transpose[{VertexOutDegree[g],VertexInDegree[g]}],{1,1}];
            candidates=Select[candidates, With[{i=in[g,#1],o=out[g,#1]},!EdgeQ[g,i\[DirectedEdge]o]&&i=!=o]&];
            If[candidates==={},Break[]];
            v=First[candidates];
            g=VertexContract[g,{v,out[g,v]}]
        ];
        g
    ]

homeomorphicQ[g1_?DirectedGraphQ, g2_?DirectedGraphQ] := 
 IsomorphicGraphQ[smooth[g1], smooth[g2]]

Answer 2

To check that two undirected graphs have the same topological shape, now you can use IGHomeomorphicQ from IGraph/M 0.3.99 or later.

For example,

The IGSmoothen function will smooth out degree-2 vertices like this:

Check the documentation for more examples.

Here's a copyable snippet:

IGHomeomorphicQ[CycleGraph[3], CycleGraph[4]]
(* True *)