3
$\begingroup$

I want to check whether the two graphs are the same. With the same, I mean that they have the same edges and nodes.

For example, I want

SameGraph[
   Graph[{{3, 4}, {1, 2}}], 
   Graph[{{1, 2}, {3, 4}}]
]
(* True *)

but

SameGraph[
   Graph[{{3, 4}, {1, 2}}], 
   Graph[{{1, 5}, {3, 4}}]
]
(* False *)

Unfortunately, it seems that regular equality checking (both == and ===) in Mathematica somehow checks whether the edges were inputted in the same order so it would reject both of these graphs and only return true when I ask

SameGraph[
    Graph[{{1, 2}, {3, 4}}], 
    Graph[{{1, 2}, {3, 4}}]
]
(* True *)

I found in the comments to this a reference to an IGSameGraphQ but this does not appear to exist in my installation of Mathematica.

$\endgroup$
5
  • $\begingroup$ I have decided to delete my answer for now as I'm worried I am not fully grasping the question. If at all possible, could you come up with more test cases? My feeling is that if the adjacency matrices of the graphs are equal, then the graphs are equivalent because the same nodes are connected to each other. In the meantime, I will just leave my suggested SameGraph as a comment: $$ $$ SameGraph[graphs_] :=With[{(adj = AdjacencyMatrix /@ graphs)}, Apply[Equal, adj] ] $\endgroup$
    – ydd
    Commented Nov 13, 2023 at 15:44
  • 2
    $\begingroup$ github.com/szhorvat/IGraphM $\endgroup$
    – Kuba
    Commented Nov 13, 2023 at 16:06
  • $\begingroup$ @ydd Your implementation requires the vertex ordering to be the same (i.e. doesn't treat the vertex set as a set), and does not compare vertex names. $\endgroup$
    – Szabolcs
    Commented Nov 13, 2023 at 18:22
  • 1
    $\begingroup$ It is unfortunately not documented what == or === do for Graphs, even though the documentation actually uses these comparison operators in some examples. I requested these operations to be clearly defined several times, but there never was any reasonable response ... this is very frustrating. $\endgroup$
    – Szabolcs
    Commented Nov 13, 2023 at 18:25
  • $\begingroup$ @Szabolcs Ah I see thanks. $\endgroup$
    – ydd
    Commented Nov 13, 2023 at 21:23

2 Answers 2

4
$\begingroup$

The IGSameGraphQ function from the IGraph/M package will do this check. Vertex names are required to match, but edge/vertex ordering doesn't. Edge tags, if present, are not taken into account. Neither are any "annotations" such as edge weights.

You can also look at the source code of this function to see what a careful and reliable check requires. Naïve implementation of this check can very easily go wrong. I am actually very surprised that a build-in version of this is not available.

$\endgroup$
0
$\begingroup$

Try inputting the edges as a list of edges using:"[UndirectedEdge]" what displays as:

[UndirectedEdge]

Then "EdgeList" can achieve what you want. Define e.g.:

check[g1, g2_] := (EdgeList@g1 // Sort) === (EdgeList@g2 // Sort)

Now with this we may check:

g1 = Graph[{3 \[UndirectedEdge] 4, 1 \[UndirectedEdge] 2}]
g2 = Graph[{1 \[UndirectedEdge] 2, 3 \[UndirectedEdge] 4}]
check[g1,g2]

True

And:

g1 = Graph[{3 \[UndirectedEdge] 4, 1 \[UndirectedEdge] 2}];
g2 = Graph[{1 \[UndirectedEdge] 5, 3 \[UndirectedEdge] 4}];
check[g1, g2]

False
$\endgroup$
1
  • 1
    $\begingroup$ This does not work correctly when there are isolated vertices, or when edge tags are present, or when some undirected edges happen to be represented in the opposite order in one graph compared to the other. $\endgroup$
    – Szabolcs
    Commented Nov 13, 2023 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.