[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Complex node attributes for subgraph isomorphism via vf2

From: Tamas Nepusz
Subject: Re: [igraph] Complex node attributes for subgraph isomorphism via vf2
Date: Thu, 19 Jan 2012 10:26:59 +0100
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:8.0) Gecko/20111124 Thunderbird/8.0

> What I want to do is to find graph anti-isomorphisms. By
> anti-isomorphic I mean a graph which is isomorphic to a (proper) edge
> induced subgraph of the graph complement of another graph (of course
> provided that the graphs are not complete).
> How would the igraph.isomorphic functions (under the BLISS or the VF2
> algorithms) work in this case?
Theoretically this could be done by creating the adjacency list of the
complement graph of one of the graphs in igraph_subisomorphic_function_vf2
and working with that. There is no way to do it from R or Python directly
without messing around with the C source -- of course excluding the
possibility of actually generating the complement graph. Chances are that
the memory requirements would be huge for even moderately large graphs (with
a few thousand nodes) since most graphs that igraph users work with are
sparse, hence their complement is very dense.

If your graphs are small, I advise you to simply generate the complement
graph for graph2 explicitly and run the subisomorphism function on graph1
and the complement of graph2.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]