Message Boards Message Boards

GROUPS:

Compare two "equivalent" graphs?

Posted 1 month ago
444 Views
|
2 Replies
|
2 Total Likes
|

Hi everyone,

I have seemingly easy problem that I really can't wrap my head around. I am not that experienced with graphs, so I apologize in advance if I am using incorrect terminology.

I have some graphs where I am not sure in which order the nodes have been specified, and I want to see if they are "equal" (not sure about the terminology. Say I have:

g1 = Graph[{1 <-> 2}];
g2 = Graph[{2 <-> 1}];

If I do

g1 == g2

Then the output is false, even though as far as I understand it they are describing the same thing. I know I can use IsomorphicGraphQ but that doesn't seem to work if the vertex names convey some meaning. Say I have:

g3 = Graph[{1 <-> 2, 2 <-> 3}];
g4 = Graph[{3 <-> 2, 2 <-> 1}];
g5 = Graph[{1 <-> 3, 3 <-> 2}];

Then both of these return True:

IsomorphicGraphQ[g3, g4]
IsomorphicGraphQ[g3, g5]

But in g3 and g4, vertex 2 is the one that has two connections. In my application, it is then not equivalent to the graph having 2 connections for vertex 3. My current implementation is to extract the edges and sort them twice, and then compare them. It works but it seems super inelegant.

In[]: Sort[Map[Sort, EdgeList[g3]]] === Sort[Map[Sort, EdgeList[g4]]]
Out[]: True
In[]: Sort[Map[Sort, EdgeList[g3]]] === Sort[Map[Sort, EdgeList[g5]]]
Out[]: False

There seems like there must be some better way. Does anyone know of one?

Thanks ever so much!

Attachments:
2 Replies

Thanks!

That works really, really well. It was exactly what I was looking for.

Regards, Patrik

My IGraph/M package includes a utility function to compare labelled graphs.

Needs["IGraphM`"]

IGSameGraphQ[g1, g2]
(* True *)

IGSameGraphQ[g1, Graph[{a <-> b}]]
(* False *)

As you noted, it's very easy to implement this yourself, but also tedious. This is why IGraph/M includes it. I find that such a function is often needed.

You can see the implementation here:

https://github.com/szhorvat/IGraphM/blob/2c9cdae93aacba9b6c60b147cc751fe7d98960e8/IGraphM/Utilities.m#L37

(This is written so that it works for directed and mixed graphs as well.)

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract