Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Exception in Backtracking with Forward Checking #1

Closed
Lance-Inman opened this issue Sep 23, 2016 · 6 comments
Closed

Exception in Backtracking with Forward Checking #1

Lance-Inman opened this issue Sep 23, 2016 · 6 comments

Comments

@Lance-Inman
Copy link
Owner

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
Copy link
Collaborator

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
#1, or mute the thread
https://github.com/notifications/unsubscribe-auth/AVR1bgKK16UoLFM6GWSoIfha9DXwbo0_ks5qs1KDgaJpZM4KEmK0
.

@Lance-Inman
Copy link
Owner Author

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
Copy link
Collaborator

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
#1 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AVR1blCrXYOGef2R-fPSUiP_5QdBGxT4ks5qs1N6gaJpZM4KEmK0
.

@Lance-Inman
Copy link
Owner Author

The most recent changes are pushed to the master branch.

@blackbelt238
Copy link
Collaborator

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
#1 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AVR1bgEbtUrad0pD7zyTjrvjfY8G7QH1ks5qs1gogaJpZM4KEmK0
.

@blackbelt238
Copy link
Collaborator

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
#1 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AVR1bgEbtUrad0pD7zyTjrvjfY8G7QH1ks5qs1gogaJpZM4KEmK0
.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@Lance-Inman @blackbelt238