I'm trying to implement a genetic algorithm to find a set of edges whose removal will disconnect the graph. To be more specific I'm using a directed acyclic graph consisted of vertices and edges. Each edge has a cost or weight. The genetic algorithm generates lots of sets C (ie selects some edges in between two vertices). Now my problem is check whether this set of edges represents a cut set or disconnect the graph. Then, the genetic algorithm is looking for the possible minimum sum of edges costs included in the cut set.

So, I used this method called Connected Graph Testing taken from the book 'A java library of Graph Algorithms and Optimization' to test connectivity. This doesn't work for me because it only scans for neighbour of vertices.

public static boolean isConnected(Individual ind)
{
    int n= Settings.numOfNodes;
    int m= Settings.numOfEdges-ind.cutSet.size();
    int nodei[]= new int[m+1];
    int nodej[]= new int[m+1];

    int tempi[]= new int[m];
    int tempj[]= new int[m];

    int[] temp= (int[])Settings.nodei.clone();

    for(int edg:ind.cutSet)
        temp[edg]= -1;

        int count=0;
        for(int i=0; i<Settings.numOfEdges; i++)
    {
       if(temp[i]!=-1)
      {
        tempi[count]=Settings.nodei[i];
        tempj[count]=Settings.nodej[i];            
        count++;
      }
   }
    nodei[0]=0;
    nodej[0]=0;
    for(int i=0; i<tempi.length;i++)
       {
          nodei[i+1]=tempi[i];
          nodej[i+1]=tempj[i]; 
       }



    int i,j,k,r,connect;
    int neighbor[] = new int[m + m + 1];
    int degree[] = new int[n + 1];
    int index[] = new int[n + 2];
    int aux1[] = new int[n + 1];
    int aux2[] = new int[n + 1];
    for (i=1; i<=n; i++)
    degree[i] = 0;
    for (j=1; j<=m; j++) {
         degree[nodei[j]]++;
         degree[nodej[j]]++;
    }
    index[1] = 1;
    for (i=1; i<=n; i++) {
        index[i+1] = index[i] + degree[i];
        degree[i] = 0;
    }
    for (j=1; j<=m; j++) {
        neighbor[index[nodei[j]] + degree[nodei[j]]] = nodej[j];
        degree[nodei[j]]++;
        neighbor[index[nodej[j]] + degree[nodej[j]]] = nodei[j];
        degree[nodej[j]]++;
    }
    for (i=2; i<=n; i++)
         aux1[i] = 1;
         aux1[1] = 0;
         connect = 1;
         aux2[1] = 1;
         k = 1;
         while (true) {
              i = aux2[k];
              k--;
              for (j=index[i]; j<=index[i+1]-1; j++) {
                    r = neighbor[j];
                    if (aux1[r] != 0) {
                       connect++;
                    if (connect == n) {
                       connect /= n;
                    if (connect == 1) return true;
                       return false;
                    }
                    aux1[r] = 0;
                    k++;
               aux2[k] = r;
         }
    }
        if (k == 0) {

    connect /= n;
    if (connect == 1) return true;
    return false;
    }
    }
  }   

Given the following directed acyclic graph:

number of vertices = 4
number of edges = 5
1->2
1->3
1->4
2->4
3->4

If we remove the following edges:

1->2
1->3
2->4

Then, the method returns that this graph is disconnected while there is still a path between:

1->4

I'm looking for an algorithm or way to check if we remove some edges, the graph is still connected between the start and goal vertices. In other words, the graph still has some other paths existed between these two vertices.

An example of a valid set which when removed the graph is NOT connected:

1->2
1->3
1->4

or

2->4
1->4
3->4

Please, I'm open to any thoughts or ideas for solving this problem.

Thanks

---

Checking for connectivity:

Your graph is directed a-cyclic, thus you can pre-process and find Paths = { (u,v) | there is a path from u to v } Paths = { (u,v) | there is a path from u to v } .

After removing/adding each edge (u,v) all you need to do is reset Paths accordingly. Note that for each v' , (u,v') is in Paths if and only if there exist u' such that (u,u') is still an edge in your graph, and (u',v') is in Paths .
Don't forget to recursively invoke the Paths modification recursively on each of u 's parents.
Though this solution is not better then BFS on the worst case, it should be better on average case - since you don't need to explore the entire graph after each change.

Edit: example
For example, in your graph, Path={(1,2),(1,3),(1,4),(2,4),(3,4)} - there is a path to all vertex to all "forward" vertex except from 2 to 3.
Now, if you remove edge (1,4) you get Path={(1,2),(1,3),(1,4),(2,4),(3,4)} note that (1,4) is still in there because there is an edge (1,2) and (2,4) is in Path .
Now remove (2,4) , it will result in: Path={(1,2),(1,3),(1,4),(3,4)} . Again, (1,4) is still in because (1,3) is still an edge and (3,4) is in Path .
Now remove (3,4) . There is no path left from 3 to 4 , so you remove (3,4) . Now, recursively modify all of 3 's parents. Since 1 is a parent of 3 , invoke it on him, and you find that there is no more edges (1,u) such that (u,4) is still in path, so we remove it from Path , resulting in Path={(1,2),(1,3)} .

Finding the set of edges to remove:

I'd start from removing all edges , and add edges, instead of removing them. You can only add an edge that does not make the graph connected. With this approach, you try to maximize the value of edges you add instead of minimizing the edges you remove.
By doing so - you ensure your solution is feasible , and the graph is indeed not connected.

链接地址: http://www.djcxy.com/p/70664.html

上一篇: 一种绘制图形而不检查所有顶点对的算法？

下一篇: 如何检查两个顶点之间的图形连通性