finding all cycles in undirected graph

[AhmedGhazey]

hello, i ask for help if you can :

i have to write algorithm detect all cycles in undirected graph , I don't know , can any one help.

Thanks .

[TrustyTony]

What have you tried?

[AhmedGhazey]

import java.util.ArrayList;

public class Main {

    //============================================================================
    public void fillMat(int[] a, int cityNo, boolean[][] G) {
        for (int i = 0; i < a.length; i++) {

                //if depot is connected with each city
              


            ArrayList<Integer> l = new ArrayList<Integer>();
            while (i < a.length && a[i] <= cityNo) {
                l.add(a[i]);
                ++i;
            }
          
            for (int j = 0; j < l.size(); j++) {
               

                for (int k = 0; k < l.size(); k++) {
                    /* buting assumption that all cities are connected .
                    order does not important all cities are connected .
                    each node are fully connected with the others node .
                     */
                    G[l.get(j)][l.get(k)] = true;
                }
            }

        }
        for (int i = 0; i < G.length; i++) {
            G[i][0]=true;
            G[0][i]=true;
        }
    }
    //============================================================================

    public void xor(boolean[][] A, boolean[][] B, boolean[][] GAB) {
        for (int i = 0; i < GAB.length; i++) {
            for (int j = 0; j < GAB.length; j++) {
                if (A[i][j] != B[i][j]) {
                    GAB[i][j] = true;
                }
            }
        }
    }
    //============================================================================

    public int[] eax(int[] a, int[] b, int cityNo) {
        int[] ofsprng = new int[a.length];
        // cityNo + 1 because the depot is counted
        boolean GA[][] = new boolean[cityNo + 1][cityNo + 1];
        boolean GB[][] = new boolean[cityNo + 1][cityNo + 1];
        boolean GAB[][] = new boolean[cityNo + 1][cityNo + 1];

        fillMat(a, cityNo, GA);
        fillMat(b, cityNo, GB);

        xor(GA, GB, GAB);

        print(GAB);
        ArrayList<ArrayList<Integer>> c = new ArrayList<ArrayList<Integer>>();

        for (int i = 0; i < GAB.length; i++) {
            for (int j = 0; j < GAB.length; j++) {
                if (GAB[i][j]) {
                    boolean vis[] = new boolean[GAB.length];
                    ArrayList<Integer> l = new ArrayList<Integer>();
                    boolean[][] GAbcopy = GAB.clone();
                    if (DFS(GAbcopy, GA, j, GA[i][j], i, vis, l)) {
                        l.add(i);
                        GAB[i][j] = false;
                        c.add(l);
                    }
                }

            }

        }
        System.out.println(c);
        return ofsprng;
    }
    //============================================================================

    public boolean DFS(boolean[][] GAB, boolean[][] A, int node, boolean isA, int startNode, boolean[] visited, ArrayList<Integer> result) {
        if (node == startNode) {
            return true;
        }
        if (visited[node]) {
            return false;
        }
        visited[node] = true;
        for (int i = 0; i < GAB.length; i++) {
            if (GAB[node][i] && A[node][i] != isA) {
                if (DFS(GAB, A, i, !isA, startNode, visited, result)) {
                    result.add(node);
                    GAB[node][i] = false;
                    return true;
                }
            }
        }
        return false;
    }
    //============================================================================

    //============================================================================
    public void print(boolean[][] a) {
        System.out.println("");
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[0].length; j++) {
                System.out.print(a[i][j] + "  ");
            }
            System.out.println("");
        }
        System.out.println("");
    }
    //============================================================================

    public static void main(String[] args) {
        int p1[] = {1, 2, 3, 4, 100, 5, 6, 7, 8};
        int p3[] = {1, 3, 2, 4, 100, 5, 6, 7, 8};
        int p2[] = {5, 1, 7, 8, 100, 6, 2, 3, 4};
        Main m = new Main();
        boolean k[][] = new boolean[9][9];
//        m.fillMat(p1, 8, k);
//         m.print(k);
        m.eax(p1, p2, 8);
         /*

             1 2 3 4
          1  * * * *
          2  * * * *
          3  * * * *
          4  * * * *
          */

        // TODO code application logic here
    }
}

my code I have to graphs A and B and graph GAB where GAB is equals to A xor B it is required to get all cycles in the GAB under condition that alternating edges between A & B if you hit in Edge where no alternating exist take any one .

the DFS get the cycles , but there exist a problem .

[AhmedGhazey]

BTW this is a genetic algorithm crossover called edge assembly recombination and get cycles is a step in the algorithm .

i wanna get all the cycles in the Graph . but Um get stuck .

[JamesCherrill]

Hi AhmedGhazey.
It's good that you are giving so much help in this forum, and your code sets a very good example for its structure and clarity.
Just one thing to watch out for - we try to help people learn enough to solve their own problems, especially if it's homework. If we give someone a complete working program they will probably just use that for their homework and learn nothing. The Validating Strings post is a good example of this. You will see that most of the long-term contributors here tend to give some guidance in terms of direction and structure, then refer the original poster to the API doc. If they do give code it's usually pseudo-code or a relevant but different example that forces the OP to understand it before they can use it.
Anyway, keep up the good work.
J

[TrustyTony]

He is the OP this time, though. And Java forum might be better place to get advice on this.

[JamesCherrill]

(Buries head in shame)
[Apology]You are absolutely right. I read this post immediately after reading the Validating Strings post and jumped to the wrong conclusion that this was more of the same. @AhmedGhazey: I apologise unreservedly.[/Apology]

@tonyjv: isn't this the Java forum???

[TrustyTony]

OK, it got transfered allready.

[AhmedGhazey]

NVM U R welcome any Time , and Thanks for your attention .