
From:  Zhigang Wu 
Subject:  [igraph] Question about subgraph detections! 
Date:  Thu, 6 Mar 2008 22:40:39 +0800 
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
realtime digital simulator called RTDS, which use its own special hardwares to
do the parellelcomputing 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 preoccupied by partition 6 and partition
15.
However, I have convert such problems into a subgraph detection problem, as
follow:
1. Valid rackpartition mapping is a subgraph detection in a type of
rackconnection 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 rackconnection graph so
that every arbitrary 3 nodes can form a triangle;
3. The 5th vertex in the rackconnection graph must correspond to the 6th
vertex in the partitionconnection graph, while the 6th vertex in the
rackconnection graph must correspond to the 15th vertex in the
partitionconnection 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
20080306
Zhigang Wu

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