search

Lance-Inman / ai-project-1

Artificial Intelligence Project 1: Search, Constraint Satisfaction, and Graph Coloring
0 stars 1 forks source link

Exception in Backtracking with Forward Checking #1

Closed Lance-Inman closed 8 years ago

Lance-Inman commented 8 years ago

The following exception was thrown when trying to solve a graph of size 50 with 3 colors using Backtracking with Forward Checking.

g graph size:50 s Choose a solver (Min-conflicts, Simple-backtracking, backtracking-Fc, Backtracking-mac, Genetic: f Exception in thread "main" java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:859) at java.util.ArrayList$Itr.next(ArrayList.java:831) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:34) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.solve(FCBacktrack.java:21) at src.GraphColorer.main(GraphColorer.java:75) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57) at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43) at java.lang.reflect.Method.invoke(Method.java:606) at com.intellij.rt.execution.application.AppMain.main(AppMain.java:147)

blackbelt238 commented 8 years ago

K. Is the line it's thrown on in a for-each loop?

On Sep 22, 2016 10:16 PM, "Lance Inman" notifications@github.com wrote:

The following exception was thrown when trying to solve a graph of size 50 with 3 colors using Backtracking with Forward Checking.

g graph size:50 s Choose a solver (Min-conflicts, Simple-backtracking, backtracking-Fc, Backtracking-mac, Genetic: f Exception in thread "main" java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:859) at java.util.ArrayList$Itr.next(ArrayList.java:831) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:34) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.fcBacktrack(FCBacktrack.java:44) at src.FCBacktrack.solve(FCBacktrack.java:21) at src.GraphColorer.main(GraphColorer.java:75) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke( NativeMethodAccessorImpl.java:57) at sun.reflect.DelegatingMethodAccessorImpl.invoke( DelegatingMethodAccessorImpl.java:43) at java.lang.reflect.Method.invoke(Method.java:606) at com.intellij.rt.execution.application.AppMain.main(AppMain.java:147)

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/Lance-Inman/project-1/issues/1, or mute the thread https://github.com/notifications/unsubscribe-auth/AVR1bgKK16UoLFM6GWSoIfha9DXwbo0_ks5qs1KDgaJpZM4KEmK0 .

Lance-Inman commented 8 years ago

FCBacktrack.java:44: Graph result = fcBacktrack(g); //continues the coloring at the next vertex FCBacktrack.java:21: return fcBacktrack(g);

private Graph fcBacktrack(Graph g)
{
    //checking if the assignment (graph coloring problem) is complete
    if(isColored(g))
        return g;

    //var <- Select-Unassigned-Variable(csp, assignment)
    Vertex currentVertex = g.getVertices().get(curVertex); //since this is simple backtracking, progression is done simply by iterating through the Graph's list of vertices

    //test each possible color at the vertex (which list comes from each Vertex's possible color list, the one that is trimmed by forward checking)
    for(Integer color : currentVertex.getPossibleColor())
    {
        //check if the color is valid in this spot
        if(checkColorOnNeighbors(color, currentVertex.getNeighbors()))
        {
            currentVertex.setColor(color); //sets the color of currentVertex to color
            incDecision(); //Decision was made to color the vertex. Count it.
            forwardCheck(currentVertex, color); //remove the selected color as a possiblility from all connected vertices
            curVertex++; //allows the coloring to move to the next vertex

            Graph result = fcBacktrack(g); //continues the coloring at the next vertex
            //return the result if there wasn't a failure
            if(result != null)
                return result;
            else
                curVertex--; //ensures curVertex is returned to what really is the current vertex. Problems would be caused without this line.
        }
        currentVertex.setColor(-1); //Uncolor the vertex. The color ended up not working.
        undoForwardCheck(currentVertex, color); //re-instate the previously removed color to neighbor verteces' list of possible colors
        incDecision(); //The decision was made to backtrack. Count it.
    }

    return null; //null signifies failure
}
blackbelt238 commented 8 years ago

Push your most recent changes and I'll work to debug on my end.

On Sep 22, 2016 10:20 PM, "Lance Inman" notifications@github.com wrote:

FCBacktrack.java:44: Graph result = fcBacktrack(g); //continues the coloring at the next vertex FCBacktrack.java:21: return fcBacktrack(g);

private Graph fcBacktrack(Graph g) { //checking if the assignment (graph coloring problem) is complete if(isColored(g)) return g;

//var <- Select-Unassigned-Variable(csp, assignment)
Vertex currentVertex = g.getVertices().get(curVertex); //since this is simple backtracking, progression is done simply by iterating through the Graph's list of vertices

//test each possible color at the vertex (which list comes from each Vertex's possible color list, the one that is trimmed by forward checking)
for(Integer color : currentVertex.getPossibleColor())
{
    //check if the color is valid in this spot
    if(checkColorOnNeighbors(color, currentVertex.getNeighbors()))
    {
        currentVertex.setColor(color); //sets the color of currentVertex to color
        incDecision(); //Decision was made to color the vertex. Count it.
        forwardCheck(currentVertex, color); //remove the selected color as a possiblility from all connected vertices
        curVertex++; //allows the coloring to move to the next vertex

        Graph result = fcBacktrack(g); //continues the coloring at the next vertex
        //return the result if there wasn't a failure
        if(result != null)
            return result;
        else
            curVertex--; //ensures curVertex is returned to what really is the current vertex. Problems would be caused without this line.
    }
    currentVertex.setColor(-1); //Uncolor the vertex. The color ended up not working.
    undoForwardCheck(currentVertex, color); //re-instate the previously removed color to neighbor verteces' list of possible colors
    incDecision(); //The decision was made to backtrack. Count it.
}

return null; //null signifies failure

}

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/Lance-Inman/project-1/issues/1#issuecomment-249099420, or mute the thread https://github.com/notifications/unsubscribe-auth/AVR1blCrXYOGef2R-fPSUiP_5QdBGxT4ks5qs1N6gaJpZM4KEmK0 .

Lance-Inman commented 8 years ago

The most recent changes are pushed to the master branch.

blackbelt238 commented 8 years ago

Replace the for loop declaration on line 34 with this: for(int i = 0; i < currentVertex.getPossibleColor().size(); i++) { Integer color = currentVertex.getPossibleColor().get(i);

On Thu, Sep 22, 2016 at 10:40 PM, Lance Inman notifications@github.com wrote:

The most recent changes are pushed to the master branch.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/Lance-Inman/project-1/issues/1#issuecomment-249101508, or mute the thread https://github.com/notifications/unsubscribe-auth/AVR1bgEbtUrad0pD7zyTjrvjfY8G7QH1ks5qs1gogaJpZM4KEmK0 .

blackbelt238 commented 8 years ago

There'll likely be a similar problem on the MAC backtrack, so I'd change line 34 there as well

On Thu, Sep 22, 2016 at 11:31 PM, Ethan Peterson cap2010.ep@gmail.com wrote:

Replace the for loop declaration on line 34 with this: for(int i = 0; i < currentVertex.getPossibleColor().size(); i++) { Integer color = currentVertex.getPossibleColor().get(i);

On Thu, Sep 22, 2016 at 10:40 PM, Lance Inman notifications@github.com wrote:

The most recent changes are pushed to the master branch.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/Lance-Inman/project-1/issues/1#issuecomment-249101508, or mute the thread https://github.com/notifications/unsubscribe-auth/AVR1bgEbtUrad0pD7zyTjrvjfY8G7QH1ks5qs1gogaJpZM4KEmK0 .