[igraph] Question about subgraph detections!

[Zhigang Wu]

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