Message Boards Message Boards

1
|
5444 Views
|
2 Replies
|
2 Total Likes
View groups...
Share
Share this post:

Compare two "equivalent" graphs?

Posted 5 years ago

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:
POSTED BY: Patrik Ekenberg
2 Replies

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.)

POSTED BY: Szabolcs Horvát

Thanks!

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

Regards, Patrik

POSTED BY: Patrik Ekenberg
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