# Compare two "equivalent" graphs?

Posted 2 years ago
2415 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: Answer
2 Replies
Sort By:
Posted 2 years ago
 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.) Answer
Posted 2 years ago
 Thanks!That works really, really well. It was exactly what I was looking for.Regards, Patrik Answer