Prim.java

[GoogleCodeExporter]

What steps will reproduce the problem?
1. any graph it has cicle in prim.java
2.
3.

What is the expected output? What do you see instead?

What version of the product are you using? On what operating system?



Please provide any additional information below.

add to prim.java after "Graph.Edge e = edgesAvailable.remove();"
 this "while(!unvisited.contains(e.getToVertex()) && !unvisited.contains(e.getFromVertex())){
                e = edgesAvailable.remove();
            }"

bye!

Original issue reported on code.google.com by alejandr...@gmail.com on 6 Dec 2012 at 10:09

[GoogleCodeExporter]

I don't see a problem using this graph with a cycle:

// Prim on a graph with cycles
java.util.List<Vertex<Integer>> cyclicVerticies = new 
ArrayList<Vertex<Integer>>();
Graph.Vertex<Integer> cv1 = new Graph.Vertex<Integer>(1);
cyclicVerticies.add(cv1);
Graph.Vertex<Integer> cv2 = new Graph.Vertex<Integer>(2);
cyclicVerticies.add(cv2);
Graph.Vertex<Integer> cv3 = new Graph.Vertex<Integer>(3);
cyclicVerticies.add(cv3);
Graph.Vertex<Integer> cv4 = new Graph.Vertex<Integer>(4);
cyclicVerticies.add(cv4);
Graph.Vertex<Integer> cv5 = new Graph.Vertex<Integer>(5);
cyclicVerticies.add(cv5);

java.util.List<Edge<Integer>> cyclicEdges = new ArrayList<Edge<Integer>>();
Graph.Edge<Integer> ce1_2 = new Graph.Edge<Integer>(3, cv1, cv2);
cyclicEdges.add(ce1_2);
Graph.Edge<Integer> ce2_3 = new Graph.Edge<Integer>(2, cv2, cv3);
cyclicEdges.add(ce2_3);
Graph.Edge<Integer> ce3_4 = new Graph.Edge<Integer>(4, cv3, cv4);
cyclicEdges.add(ce3_4);
Graph.Edge<Integer> ce4_1 = new Graph.Edge<Integer>(1, cv4, cv1);
cyclicEdges.add(ce4_1);
Graph.Edge<Integer> ce4_5 = new Graph.Edge<Integer>(1, cv4, cv5);
cyclicEdges.add(ce4_5);

Graph<Integer> cyclicUndirected = new Graph<Integer>(cyclicVerticies, 
cyclicEdges);
Graph.CostPathPair<Integer> cyclicPair = 
Prim.getMinimumSpanningTree(cyclicUndirected, start);

//// output ////
start vertex: value=1 weight=0
    edge: [1] -> [2] = 3
    edge: [1] -> [4] = 1

Cost = 7
    edge: [1] -> [4] = 1
    edge: [4] -> [5] = 1
    edge: [1] -> [2] = 3
    edge: [2] -> [3] = 2
//// end ////

Original comment by phishman3579@gmail.com on 8 Jan 2013 at 7:17

[GoogleCodeExporter]

Original comment by phishman3579@gmail.com on 8 Jan 2013 at 7:18

• Changed state: Started

[GoogleCodeExporter]

Original comment by phishman3579@gmail.com on 17 Mar 2013 at 1:42

[GoogleCodeExporter]

Original comment by phishman3579@gmail.com on 14 Nov 2013 at 10:28

• Changed state: Invalid