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 vérifie si un graphique est 2-colorable, à savoir si elle ne contient pas de cycles impairs (cycles de longueur de nombre impair). L'algorithme complet est censé fonctionner en temps O (V + E) (V étant tous les sommets et E étant toutes 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 pourrait se faire en O (V + E) temps pour tous les cycles qui existent dans mon graphique, mais je dois manquer quelque chose, parce que mon algorithme est en cours d'exécution pour un ridiculement longtemps pour très grands graphiques (10k nœuds, aucune idée de combien de bords).

est mon algorithme complètement faux? Et si oui, quelqu'un peut me diriger dans la bonne direction pour une meilleure façon d'enregistrer ces cycles ou peut-être dire s'ils ont un nombre impair de sommets? Merci pour tout et tous vous aider les gars peuvent donner. 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 qu'il 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");
    }
}

classe Vertex

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 beaucoup plus de cycles que O (V + E) dans un graphique. Si vous itérer tous, vous courrez longtemps.

Retour à votre idée originale, vous pouvez juste essayer de mettre en œuvre un algorithme simple de graphique couleur en deux couleurs (marquer un nœud arbitraire en noir, tous les voisins blancs, tous leurs voisins en noir, etc, ce serait une largeur recherche -Premier). Cela est en effet fait en O (V + E) temps. Si vous réussissez, représenter graphiquement est 2-colorable. Si vous ne parvenez pas, ce n'est pas.

Modifier Si vous avez besoin d'un cycle qui prouve graphique n'est pas 2-colorable, juste enregistrer pour chaque noeud le sommet dans ce que vous qui parcourront de. 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 avez besoin.

Notez que dans cette version, vous ne devez pas vérifier tous les cycles, vous venez de sortir un premier cycle, où en arrière-bord dans l'arbre a des couleurs dans la vertex même couleur.

Answer 2

vous décrivez un graphe biparti. un graphe biparti est colorable et 2 ne contient pas de cycles de longueur impaire. Vous pouvez utiliser BFS pour prouver qu'un graphe est biparti ou non. Espérons que cela aide.