[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:
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