[Top][All Lists]

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

Re: [igraph] Question about subgraph detections!

From: Gabor Csardi
Subject: Re: [igraph] Question about subgraph detections!
Date: Thu, 6 Mar 2008 22:37:34 +0100
User-agent: Mutt/1.5.13 (2006-08-11)

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:

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

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.


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

reply via email to

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