Vérification des cycles impairs dans un graphe non orienté

Question

Je suis de retour avec une autre question similaire. Je travaille actuellement sur un programme Java qui va vérifier si un graphe est 2-colorable, c'est-à-dire s'il ne contient pas de cycles impairs (cycles de longueur de nombre impair). L'algorithme entier est supposé s'exécuter en O (V + E) temps (V étant tous les sommets et E étant tous les arêtes du graphe). Mon algorithme actuel fait une profondeur de recherche d'abord, l'enregistrement de tous les sommets dans le chemin qu'il faut, cherche ensuite un bord arrière, puis enregistre entre lesquels sommets du bord est entre les deux. Ensuite, il trace un chemin d'une extrémité du bord arrière jusqu'à ce qu'il frappe l'autre sommet à l'autre extrémité du bord, retraçant ainsi le cycle que le bord arrière se termine. J'avais l'impression que ce genre de déplacement pouvait être fait en temps O (V + E) pour tous les cycles qui existent dans mon graphe, mais il me manque quelque chose, car mon algorithme tourne pendant une durée ridiculement longue temps pour les très grands graphiques (10k nœuds, aucune idée du nombre d'arêtes).

est mon algorithme complètement faux? Et si oui, quelqu'un peut-il me diriger dans la bonne direction pour un meilleur moyen d'enregistrer ces cycles ou éventuellement dire s'ils ont des nombres impairs de sommets? Merci à tous pour votre aide. Le code est ci-dessous si vous en avez besoin.

Addition: Désolé j'ai oublié, si le graphique n'est pas 2-colorable, je dois fournir un cycle étrange qui prouve que ce n'est pas.

package algorithms311; 

import java.util.*; 
import java.io.*; 

public class CS311 { 

public static LinkedList[] DFSIter(Vertex[] v) { 
    LinkedList[] VOandBE = new LinkedList[2]; 
    VOandBE[0] = new LinkedList(); 
    VOandBE[1] = new LinkedList(); 

    Stack stack = new Stack(); 

    stack.push(v[0]); 
    v[0].setColor("gray"); 

    while(!stack.empty()) { 
     Vertex u = (Vertex) stack.peek(); 
     LinkedList adjList = u.getAdjList(); 
     VOandBE[0].add(u.getId()); 

     boolean allVisited = true; 
     for(int i = 0; i < adjList.size(); i++) { 
      if(v[(Integer)adjList.get(i)].getColor().equals("white")) { 
       allVisited = false; 
       break; 
      } 
      else if(v[(Integer)adjList.get(i)].getColor().equals("gray") && u.getPrev() != (Integer)adjList.get(i)) { 
       int[] edge = new int[2]; //pair of vertices 
       edge[0] = u.getId(); //from u 
       edge[1] = (Integer)adjList.get(i); //to v 
       VOandBE[1].add(edge); 
      } 
     } 
     if(allVisited) { 
      u.setColor("black"); 
      stack.pop(); 
     } 
     else { 
      for(int i = 0; i < adjList.size(); i++) { 
       if(v[(Integer)adjList.get(i)].getColor().equals("white")) { 
        stack.push(v[(Integer)adjList.get(i)]); 
        v[(Integer)adjList.get(i)].setColor("gray"); 
        v[(Integer)adjList.get(i)].setPrev(u.getId()); 
        break; 
       } 
      } 
     } 
    } 
    return VOandBE; 
} 

public static void checkForTwoColor(String g) { //input is a graph formatted as assigned 

    String graph = g; 

    try { 

     // --Read First Line of Input File 
     // --Find Number of Vertices 

     FileReader file1 = new FileReader("W:\\Documents\\NetBeansProjects\\algorithms311\\src\\algorithms311\\" + graph); 
     BufferedReader bReaderNumEdges = new BufferedReader(file1); 

     String numVertS = bReaderNumEdges.readLine(); 
     int numVert = Integer.parseInt(numVertS); 

     System.out.println(numVert + " vertices"); 





     // --Make Vertices 

     Vertex vertex[] = new Vertex[numVert]; 

     for(int k = 0; k <= numVert - 1; k++) { 
      vertex[k] = new Vertex(k); 
     } 

     // --Adj Lists 


     FileReader file2 = new FileReader("W:\\Documents\\NetBeansProjects\\algorithms311\\src\\algorithms311\\" + graph); 
     BufferedReader bReaderEdges = new BufferedReader(file2); 
     bReaderEdges.readLine(); //skip first line, that's how many vertices there are 

     String edge; 

     while((edge = bReaderEdges.readLine()) != null) { 

      StringTokenizer ST = new StringTokenizer(edge); 

      int vArr[] = new int[2]; 
      for(int j = 0; ST.hasMoreTokens(); j++) { 
       vArr[j] = Integer.parseInt(ST.nextToken()); 
      } 


      vertex[vArr[0]-1].addAdj(vArr[1]-1); 
      vertex[vArr[1]-1].addAdj(vArr[0]-1); 

     } 

     LinkedList[] l = new LinkedList[2]; 

     l = DFSIter(vertex);//DFS(vertex); 

     System.out.println(l[0]); 



     for(int i = 0; i < l[1].size(); i++) { 
      int[] j = (int[])l[1].get(i); 
      System.out.print(" [" + j[0] + ", " + j[1] + "] "); 
     } 



     LinkedList oddCycle = new LinkedList(); 
     boolean is2Colorable = true; 


     //System.out.println("iterate through list of back edges"); 

     for(int i = 0; i < l[1].size(); i++) { //iterate through the list of back edges 
      //System.out.println(i); 
      int[] q = (int[])(l[1].get(i)); // q = pair of vertices that make up a back edge 
      int u = q[0]; // edge (u,v) 
      int v = q[1]; 

      LinkedList cycle = new LinkedList(); 

      if(l[0].indexOf(u) < l[0].indexOf(v)) { //check if u is before v 
       for(int z = l[0].indexOf(u); z <= l[0].indexOf(v); z++) { //if it is, look for u first; from u to v 
        cycle.add(l[0].get(z)); 
       } 
      } 
      else if(l[0].indexOf(v) < l[0].indexOf(u)) { 
       for(int z = l[0].indexOf(v); z <= l[0].indexOf(u); z++) { //if it is, look for u first; from u to v 
        cycle.add(l[0].get(z)); 
       } 
      } 



      if((cycle.size() & 1) != 0) { //if it has an odd cycle, print out the cyclic nodes or write them to a file 

       is2Colorable = false; 

       oddCycle = cycle; 

       break; 
      } 
     } 
     if(!is2Colorable) { 
      System.out.println("Graph is not 2-colorable, odd cycle exists"); 
      if(oddCycle.size() <= 50) { 
       System.out.println(oddCycle); 
      } 
      else { 
       try { 
        BufferedWriter outFile = new BufferedWriter(new FileWriter("W:\\Documents\\NetBeansProjects\\algorithms311\\src\\algorithms311\\" + graph + "OddCycle.txt")); 
        String cyc = oddCycle.toString(); 
        outFile.write(cyc); 
        outFile.close(); 
       } 
       catch (IOException e) { 
        System.out.println("Could not write file"); 
       } 
      } 
     } 
    } 
    catch (IOException e) { 
     System.out.println("Could not open file"); 
    } 
    System.out.println("Done!"); 
} 

public static void main(String[] args) { 
     //checkForTwoColor("smallgraph1"); 
     //checkForTwoColor("smallgraph2"); 
     //checkForTwoColor("smallgraph3"); 
     //checkForTwoColor("smallgraph4"); 
     checkForTwoColor("smallgraph5"); 

     //checkForTwoColor("largegraph1"); 
    } 
} 

Vertex classe

package algorithms311; 

import java.util.*; 

public class Vertex implements Comparable { 

    public int id; 
    public LinkedList adjVert = new LinkedList(); 
    public String color = "white"; 
    public int dTime; 
    public int fTime; 
    public int prev; 
    public boolean visited = false; 

    public Vertex(int idnum) { 
     id = idnum; 
    } 

    public int getId() { 
     return id; 
    } 

    public int compareTo(Object obj) { 
     Vertex vert = (Vertex) obj; 
     return id-vert.getId(); 
    } 

    @Override public String toString(){ 
     return "Vertex # " + id; 
    } 

    public void setColor(String newColor) { 
     color = newColor; 
    } 

    public String getColor() { 
     return color; 
    } 

    public void setDTime(int d) { 
     dTime = d; 
    } 

    public void setFTime(int f) { 
     fTime = f; 
    } 

    public int getDTime() { 
     return dTime; 
    } 

    public int getFTime() { 
     return fTime; 
    } 

    public void setPrev(int v) { 
     prev = v; 
    } 

    public int getPrev() { 
     return prev; 
    } 

    public LinkedList getAdjList() { 
     return adjVert; 
    } 

    public void addAdj(int a) { //adds a vertex id to this vertex's adj list 
     adjVert.add(a); 
    } 

    public void visited() { 
     visited = true; 
    } 

    public boolean wasVisited() { 
     return visited; 
    } 
} 

Answer 1

J'avais l'impression que ce genre de déplacement pourrait se faire en O (V + E) temps pour tous les cycles qui existent dans mon graphique

Il peut y avoir des cycles beaucoup plus que O (V + E) dans un graphique. Si vous les itérez tous, vous courrez longtemps. Pour revenir à votre idée originale, vous pouvez simplement essayer d'implémenter un algorithme simple pour colorier le graphique en deux couleurs (marquer un nœud arbitraire en noir, tous les voisins en blanc, tous les voisins en noir, etc. recherche en largeur). C'est en effet fait en O (V + E) temps. Si vous réussissez, alors le graphique est 2-colorable. Si vous échouez, ce n'est pas le cas.

Editer: Si vous avez besoin d'un cycle qui prouve que le graphe n'est pas à 2 couleurs, il suffit d'enregistrer pour chaque noeud le sommet dans lequel vous l'avez traversé. Lorsque vous arrivez à traverser du sommet noir A à sommet noir B (donc besoin de couleur noire B en blanc et prouver votre graphique n'est pas 2-colorable), vous obtenez le cycle en regardant en arrière aux parents:

X -> Y -> Z -> U -> V -> P -> Q -> A 
        \-> D -> E -> B 

Ensuite, A-B-E-D-V-P-Q (les chemins jusqu'à leur ancêtre commun) est le cycle dont vous aviez besoin. Notez que dans cette version, vous n'avez pas besoin de vérifier tous les cycles, vous venez de sortir un premier cycle, où le bord arrière de l'arbre a les deux sommets colorés dans la même couleur.

Answer 2

vous décrivez un graphique bipartite. un graphique bipartite est 2 colorable et il ne contient aucun cycle de longueur impaire. Vous pouvez utiliser BFS pour prouver qu'un graphique est bipartite ou non. J'espère que cela t'aides.