
From:  Wen Cheng 
Subject:  Re: [igraph] MCS and result of "igraph_get_subisomorphisms_vf2" 
Date:  Sun, 21 Jul 2013 19:01:49 0500 
Hello,
There is no implementation for the MCS problem in igraph yet. If your graphs are not too large, you can try building the modular product manually (see http://en.wikipedia.org/wiki/Modular_product_of_graphs) and then find the largest clique in the modular product graph  this will correspond to a solution of the MCS problem. Finding largest cliques is implemented in igraph_largest_cliques.
> Firstly, I wonder whether igraph can help find maximum common subgraph (or just common subgraphs) of two or more graphs. If so, could you please let me know which function can do that?
Let's see. The edges in your first graph are:
> 0, 1, 2, 3, 4
> 0, 1, 3, 2, 4
> 4, 2, 1, 3, 0
> 4, 2, 3, 1, 0
>
> The first three mappings make sense but the last one seems weird. I wonder whether you have any comment on it.
01, 03, 12, 13, 23, 24, 34
The edges in the second graph are:
01, 12, 13, 23, 24, 34
The mapping vector is [4, 2, 3, 1, 0]. This describes the mapping _from_ the vertices of the _second_ graph _to_ the vertices of the _first_ graph. In other words, vertex 0 in the second graph is mapped to vertex 4 of the first graph, vertex 1 of the second graph is mapped to vertex 2 of the first graph and so on. So, let's take the edge list of the second graph and do all these replacements at once:
Replace 0 with 4; 1 with 2; 2 with 3; 3 with 1 and 4 with 0.
The remapped edge list is:
42, 23, 21, 31, 30, 10
Let's swap the order of vertices where the smaller vertex index comes second because I used the convention of writing the smaller index first when I wrote down the edge list of the first graph. This gives us:
24, 23, 12, 13, 03, 01
As you can see, this is a subset of the edge list of the first graph; only edge 34 is missing. Therefore, the mapping describes a proper subisomorphism.
Cheers,
Tamas
_______________________________________________
igraphhelp mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraphhelp
[Prev in Thread]  Current Thread  [Next in Thread] 