Re: [igraph] MCS and result of "igraph_get_subisomorphisms_vf2"

[Wen Cheng]

Hello Tamas,

Thank you very much for your quick and detailed reply! Your answers are very helpful. I apologize that I didn't write back sooner.

Regarding result of "igraph_get_subisomorphism_vf2()" I found mapped the second graph to the first one in an inverse way. For example, for mapping "4, 2, 3, 1, 0", I mapped vertex 4 in the second graph to vertex 0 in the first graph, mapped vertex 2 in the second graph to vertex 1 in the first graph, vertex 3 in the second graph to vertex 2 in the first graph and so on. Now I know how to map according to your answer.

With respect to MCS problem, I will study how to build the modular product manually. One more concern is that my dataset has 140 graphs and I need to find MCS for each pair of graphs. I wonder whether building modular product manually is practical or not. However, I will try to do it and see how long it may take.

Again, thank you very much for your time and effort on my questions!

Best regards,

Wen

On Fri, Jul 19, 2013 at 4:39 PM, Tamás Nepusz <address@hidden> wrote:

Hello,

> 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?

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.

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

Let's see. The edges in your first graph are:

0-1, 0-3, 1-2, 1-3, 2-3, 2-4, 3-4

The edges in the second graph are:

0-1, 1-2, 1-3, 2-3, 2-4, 3-4

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:

4-2, 2-3, 2-1, 3-1, 3-0, 1-0

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:

2-4, 2-3, 1-2, 1-3, 0-3, 0-1

As you can see, this is a subset of the edge list of the first graph; only edge 3-4 is missing. Therefore, the mapping describes a proper sub-isomorphism.

Cheers,
Tamas
_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help