7
$\begingroup$

Recently I discovered for myself IGraphM package and find it really great!

<< IGraphM`

I am still learning its basic functionality. I need to verify isomorphism of a large set of graphs. I have already simplified them to avoid directed edges as they possibly are harder to treat. However, they still possess 3 features:

  • Colored vertices
  • Colored edges
  • There could be more than 1 edge connecting some of the vertices

Thus, they are colored multigraphs. In the manual to the IGVF2IsomorphicQfunction it is written that

VF2 supports vertex coloured and edge coloured graphs. A colour specification consists of one of more of the "VertexColors" and "EdgeColors" options.

In a different place it is also stated that

Additionally, IGIsomorphicQ[] and IGSubisomorphicQ[] try to select the best algorithm for the given graphs. For graphs without multiple edges, they use igraph's default algorithm selection. For multigraphs, they use VF2 after internally transforming the multigraphs to an edge coloured simple graph.

Thus, we seems to be on the safe side and can try one example

gr[1]={1 <-> 2, 3 <-> 8, 8 <-> 9, 9 <-> 4, 1 <-> 10, 10 <-> 11, 11 <-> 2, 5 <-> 5, 5 <-> 6, 3 <-> 6, 6 <-> 7, 4 <-> 7, 5 <-> 7}
vr[1]=<|8 -> 3, 10 -> 3, 9 -> 7, 11 -> 7|>
ed[1]=<|6 <-> 7 -> 10|>

gr[2]={1 <-> 2, 3 <-> 8, 8 <-> 9, 9 <-> 3, 4 <-> 10, 10 <-> 11, 11 <-> 2, 5 <-> 5, 3 <-> 3, 5 <-> 6, 5 <-> 6, 6 <-> 7, 1 <-> 7, 4 <-> 7}
vr[2]=<|8 -> 3, 10 -> 3, 9 -> 7, 11 -> 7|>
ed[2]=<|6 <-> 7 -> 10|>

Let us visualize them first:

decorateGraph[con_, vrts_, edgs_] := Module[{g, gv},
  g = Graph[con];
  gv = Fold[SetProperty[{#1, #2}, 
  {VertexStyle -> ColorData[60, vrts[[Key[#2]]] ], VertexSize -> Medium}] &, g, 
    Keys[vrts]];
  Fold[SetProperty[{#1, #2}, 
     EdgeStyle -> {ColorData[60, edgs[[Key[#2]]]], Thick}] &, gv, 
   Keys[edgs]]
  ]

GraphicsRow[
{decorateGraph[Graph[gr[1]], vr[1], ed[1]],
 decorateGraph[Graph[gr[2]], vr[2], ed[2]]}, 
   Dividers -> Center, FrameStyle -> Directive[Dashed, Blue]]

They look quite different: enter image description here

Now we use IGVF2IsomorphicQ to check the isomorphism

IGVF2IsomorphicQ[{Graph[gr[1]], "VertexColors" -> vr[1], "EdgeColors" -> ed[1]}, {Graph[gr[2]], "VertexColors" -> vr[2], "EdgeColors" -> ed[2]}]

But the result is not what I've expected:

IGraphM::vf2nmg: VF2 does not support multigraphs.

How to deal with this problem? Is it at all possible? I appreciate your help.

$\endgroup$
  • $\begingroup$ None of the isomorphism algorithms in the core igraph library support multigraphs, but several support coloured graphs. It is possible to transform the multigraph isomorphism problem to a coloured simple graph isomorphism problem. Simply count the multiplicity of each edge and use that number of the colour of the edge. I implemented this for IGIsomorphicQ. It is the only builtin function that supports multigraphs, but it does not support colours. $\endgroup$ – Szabolcs Dec 12 '17 at 22:35
  • $\begingroup$ If you need to work with coloured multigraphs, you will need to somehow encode the both the current colour and the edge multiplicity into a new colour. There are multiple ways one could do this, though all I could think of are hackish. E.g. you could construct new colours so that the QuotientRemainder[newColour, n] will be {multiplicity, oldColour}. Of course, you would need to choose n correctly based on the colour count of both graphs you are comparing. $\endgroup$ – Szabolcs Dec 12 '17 at 22:38
  • 1
    $\begingroup$ This takes a bit of work, and I do not have time to write an answer (hence the comments). I won't have time for at least a week. I only logged in because I accidentally saw your question. I hope you can get it working based on this guidance. You can see how the current multigraph -> coloured simple graph transformation works, and go from there: github.com/szhorvat/IGraphM/blob/master/IGraphM/IGraphM.m#L1656 $\endgroup$ – Szabolcs Dec 12 '17 at 22:40
  • 1
    $\begingroup$ Check this for ideas too: mathematica.stackexchange.com/q/22813/12 (what whuber implements is a bit different from the usual coloured isomorphism problem though). Be sure to read the comments. I'll give this a shot when I'm back. Time to log out now, sorry. $\endgroup$ – Szabolcs Dec 12 '17 at 22:52
  • 1
    $\begingroup$ If you are not in a hurry, I'll get a DOI through Zenodo and will write a citation guide for January. I think it is important to keep in mind that most of IGraph/M is based on igraph, parts of which are based on other published works (e.g. bliss). If you do cite IGraph/M, it would be appropriate to also cite some of these, especially igraph itself. $\endgroup$ – Szabolcs Dec 23 '17 at 16:53
5
$\begingroup$

One possible solution is to find an injective mapping from coloured multigraphs to coloured simple graphs. We then test the isomorphism of the transformed graphs with IGVF2IsomorphicQ.

My idea for such a mapping is the following:

  1. Subdivide every edge a <-> b to a <-> x <-> b. This eliminates multi-edges between distinct vertices.

  2. Subdivide self-loops a <-> a to a <-> x <-> y <-> a. This transforms self-loops to 3-cycles. A 3-cycle cannot be created with the type of subdivision in point 1. above, thus I believe that the injective property of the mapping stands.

The injective property, i.e. that non-isomorphic graphs map to non-isomoprhic ones, is critical. Therefore I encourage you to think through that the above approach is indeed valid.


To implement this, we start by introducing a new notation for coloured edges. col[a <-> b, c] represents an edge with colour c. Example:

edges = { col[1 <-> 2, 1], col[1 <-> 2, 2], 2 <-> 3 };

The following function brings edge representations to a canonical form. Uncoloured edges are assigned the colour 0.

normalizeEdges[edges_] :=
 Block[{TwoWayRule = UndirectedEdge},
  Replace[edges, e_UndirectedEdge -> col[e, 0], {1}]
 ]

This function creates a new symbol to be used as a node:

newNode[] := Unique[node]

Implement subdivision of normal edges and self-loops:

subdivide[col[UndirectedEdge[a_, a_], c_]] :=     
 With[{n1 = newNode[], n2 = newNode[]},
  Unevaluated@Sequence[
    col[UndirectedEdge[a, n1], c],
    col[UndirectedEdge[n1, n2], c],
    col[UndirectedEdge[n2, a], c]
    ]
  ]

subdivide[col[UndirectedEdge[a_, b_], c_]] :=
 With[{n1 = newNode[]},
  Unevaluated@Sequence[
    col[UndirectedEdge[a, n1], c],
    col[UndirectedEdge[n1, b], c]
    ]
  ]

Convert an edge list in the above format to a subdivided edge list in a format suitable for IGraph/M:

colouredSubdividedGraph[edges_] := 
 With[{newEdges = subdivide /@ normalizeEdges[edges]},
  {Graph[newEdges[[All, 1]]], "EdgeColors" -> newEdges[[All, 2]]}
 ]


colouredSubdividedGraph[edges]

Mathematica graphics

Finally, use IGVF2IsomorphicQ to compare these transformed coloured graphs.

I won't address the visualization question as that in itself deserves a separate question and has been asked before.

Unfortunately, Mathematica cannot properly deal with edge attributes of multigraphs, which makes visualization very messy. If you feel limited by this problem, I encourage you to report it to Wolfram.

$\endgroup$
  • $\begingroup$ Thank you! I will try your solution and give little more time in case other people would like to propose a solution. $\endgroup$ – yarchik Dec 17 '17 at 12:21
4
$\begingroup$

Preamble

A few weeks ago I needed to find isomorphisms of colored multigraphs for my research, so I quickly wrote some ugly code that only worked if (a) none of the original colors were the same as the multi-edge counts used to color multi-edges; and (b) multi-edges were not originally colored. This sloppy 'solution' didn't sit well with me, so I decided to write an answer.

Disclaimers:

  1. I haven't tested this terribly throroughly. Additional suggestions for test code is welcome -- I just don't currently have the willpower to invent exhaustive test cases (partialy because I wrote this code on an overnight flight). I did make some test cases, with an ad hoc series of assertions that I cooked up.
  2. I didn't read the links in Szabolcs' comments. They might do things better than I do.

Answer

Full code

The full code is on github.

If you're really bored, you can look up my horrible original implementation in the earliest version(s).

Warning -- It seems Mathematica 11.2 automatically replaces \[UndirectedEdge] with <-> in .m files, but only upon saving the file. I haven't investigated fully, but it seems that some edges are still \[UndirectedEdge]'s, while others are <->, and IGraphM distinguishes between them, so the tests break. As such, beware that this code will break if you open and save these .m files in MMA 11.2.

Overview

  • first combine original colors (I refer to these as optsColors, as they are specified in an option-like way to the isomorphism function) with multicolors (computed in the standard way) into a two-element list
    • write these combined 'colors' in an association (associated by edges), in a similar form to the standard color specification
  • map each color pair to an integer
    • this is done by adding each unique color pair as a key in a master association, with he nth unique color having value n.
    • this looks like, e.g., `<| {1,2} -> 1, {2,3} -> 2, ... |>

Note that the keys in this master association can be anything, not necessarily lists of integers

Colored (and multicolored) multi-edges:

(When I say 'multi-edge', I mean a graph which appears more than once in a multigraph. For now, I identify directed edges with their reverses. When I say a multi-edge is colored, I mean that different instances of that edge have different colors.)

If a multi-edge is given a color in the normal way, it is naturally assumed that every instance of that edge has that color. In order to give different instances of that edge distinct colors, one can specify, e.g., (1<->2) -> {2,3,4}, which gives one instance color 2, one color 3, and one color 4, with all others defaulting to zero.

It seems natural to identify different permutations of multi-edge colors -- e.g., (1<->2) -> {2,3,4} is identified with (1<->2) -> {3,2,4}. As such, all 'colors' which are lists will be assumed to refer to multi-edges, and will be sorted.

Further considerations

Things left to do

  • Deal with directed graphs
  • More exhaustive tests
  • Figure out a way around the \[UndirectedEdge] vs <-> issue
  • Consider type-checking color lists
  • Make sure multicolored multi-edges aren't colored with more colors than their multiplicity

Minor notes

  • I overloaded OP's decorateGraph function to work with IGVF2* color spec conventions. See the testing file.
$\endgroup$
  • 1
    $\begingroup$ "Figure out a way around the \[UndirectedEdge] vs <-> issue." I suggest wrapping relevant functions with Block[{TwoWayRule = UndirectedEdge}, ...]. The next version of IGraph/M will support TwoWayRule in isomorphism functions. $\endgroup$ – Szabolcs Dec 17 '17 at 12:12
  • $\begingroup$ I have not tried your code, but the description is reasonable. An advantage of this transformation compared to mine is that automorphism results (e.g. automorphism group) should be valid as well. With my approach, only isomorphism results will be valid between two graphs. If you use IGraph/M, consider joining the chatroom for any feedback or questions. $\endgroup$ – Szabolcs Dec 18 '17 at 14:23
  • $\begingroup$ @Szabolcs Could you elaborate on this automorphism issue (perhaps in your answer)? I'm not sure exactly what you mean, though it now me that when using your method, the output of e.g. FindIsomorphisms will need to be processed to eliminate extraneous edges. $\endgroup$ – jjc385 Dec 18 '17 at 21:42
  • $\begingroup$ @Szabolcs I'm also interested in the performance differences between our methods. I think mine has the advantage of not having to modify the graph itself, but I'd have to think about whether the processing involved in my method overshadows this advantage. $\endgroup$ – jjc385 Dec 18 '17 at 21:45
  • $\begingroup$ @Szabolcs (Last comment, I think) There's also the issue that my method maps pairs to integers in a way that's dependent upon both graphs, not just one. But I think that can be fixed by implementing a new syntax which allows these pairs to be computed in advance and passed to isomorphism functions, somewhat similar to your method -- just without modifying the original graph itself. $\endgroup$ – jjc385 Dec 18 '17 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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