Java - find if graph contains a length-3 cycle

Vote count:

0

I'm developing a game in Java where you play against an AI drawing lines on a graph, and the first person to make a triangle loses. I'm having trouble with the code that detects if the graph indeed encounters a length-3 cycle. It works sometimes, but often not, and I would love some help clarifying what needs to be done. Here's my code:

public class Graph {
private int vertices = 6;

public Graph (int n) {
    if (n < 0) {
        throw new IllegalArgumentException("number of vertices cannot be negative");
    }
    vertices = n;
}

public int[][] B = new int[vertices][vertices];

public boolean isEdge(int u, int v, int w) {
    if (u >= vertices || v >= vertices) {
        throw new IllegalArgumentException("graph does not have enough vertices");
    } else if (B[u][v] != w) {
        return false;
    } else {
        return true;
    }
}

public boolean isCycleOfLength(int n, int w) {
    return isCycleHelper(0, 0, 0, n, w);
}

private boolean isCycleHelper(int u, int v, int prev, int n, int w) {
    if (n == 0) {
        return true;
    } else if (isEdge(u, v, w) && (u < vertices && v < vertices) && (v != prev)) {
        return isCycleHelper(v, 0, u, n-1, w);
    } else if (u < vertices && v < vertices - 1) {
        return isCycleHelper(u, v+1, prev, n, w);
    } else {
        return false;
    }
}

All my other methods seem to work just fine (add edge, remove edge, etc) which aren't included, though I can post those if needed. What seems to be the issue if only isCycleHelper. To clarify, the number of vertices if 6, u and v are the vertices of the move (the graph is undirected), and w distinguishes the player making the move (1 for human, -1 for computer, 0 if no edge). Since it is an undirected graph, the method that adds an edge to the graph puts w in B[u][v] and B[v][u].

Another bit of clarification for the isCycleOfLength method: Because I'm trying to find a cycle of length 3 (though the code is designed to be altered for different lengths), n = 3 at the beginning, then decreases each time the method finds an edge to a vertex that is not the one that it just came from (I think an infinite loop would begin). So basically I'm doing depth-first search. I think at this point in the algorithm, it only detects paths of length 3 (though it's iffy about that too), not triangles. I tried to add a "start" field in the recursive algorithm, but it only led to problems, so I removed. Any help would be greatly appreciated.

asked 33 secs ago

Adam Eisenstein

18