Re: [igraph] Question about subgraph detections!

[Gabor Csardi]

Zhigang Wu,

the thing is that the original VF2 implementation allows using 
edge/vertex attributes for the matching process, and then two 
vertices can match only if their attributes match, etc.
See more here:
http://amalfi.dis.unina.it/graph/db/vflib-2.0/doc/vflib.html

I think that the speed of this implementation is about the same 
as the igraph one, although i've never tried it with 
attributes. 

VFlib is, however, a different library, you cannot use anything
from your igraph code unfortunately. :( When i answered your previous 
email i completely forgot about VFlib supporting attributes, sorry 
about that, and for the extra work you did.

The attributes surely speed up the matching, but how much, whether
it will be 5 hours of 5 minutes, i don't know.

Best,
G.

On Thu, Mar 06, 2008 at 10:40:39PM +0800, Zhigang Wu wrote:
> Hello, Dear all!
>  
> I am sorry to bother you again by my subgraph detection problem. My question 
> is
> a bit different from normal subisomorphic problems, so Gabor called it
> "constrained" subisomorphic problems, since a few nodes in the result 
> subgraphs
> are fixed.
>  
> In fact, we are trying to model a large power system in a powerful real-time
> digital simulator called RTDS, which use its own special hardwares to do the
> parellel-computing work, we usually call them "racks". There are totally 18
> racks in our simulator, so our power system is divided into 18 partitions.
> Since each rack is only connected to up to 6 racks, communication problems
> should be considered. The constraints are:
> 1. Geographical neighbor partitions in real power systems must correspond to
> adjacent racks, or
> 2. There is only one rack between the two corresponding racks modelling
> geographical neighbor partitions,
> 3. Rack 5 and rack 6 are pre-occupied by partition 6 and partition 15.
>  
> However, I have convert such problems into a subgraph detection problem, as
> follow:
> 1. Valid rack-partition mapping is a subgraph detection in a type of
> rack-connection graph, including all the vertices;
> 2. Since all the vertice pairs with the distance no more than 2 is acceptable,
> I have to add new edges in the original rack-connection graph so that every
> arbitrary 3 nodes can form a triangle;
> 3. The 5th vertex in the rack-connection graph must correspond to the 6th
> vertex in the partition-connection graph, while the 6th vertex in the
> rack-connection graph must correspond to the 15th vertex in the
> partition-connection graph.
>  
> With the powerful IGRAPH library, I have write a program to invoke the 
> function
> igraph_subisomorphic_function_vf2 to detect acceptable subgraphs. However,
> another problem emerged: it takes quite a long period to finish the task (more
> than 10 hours!). I am afraid that this may be caused by so many triangles in
> the large graph since there are too many suitable subisomorphisms. Can some of
> you be kindly enough to help me to reduce the calculation task? Many thanks in
> advance!
>  
> Best regards
>  
> 2008-03-06
> ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
> Zhigang Wu

> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help


-- 
Csardi Gabor <address@hidden>    UNIL DGM