Prim-algorithm on a graph with weights only 1 and 2 on each edge using two lists

Question

Given a weighted, connected, simple undirected graph G with weights of only 1 and 2 on each edge

I want to implement the Prim algorithm as follows:

the weights are 1 or 2, so I can just save the edges in two separate lists, one for edges with a weight of 1, and the second for edges with a weight of 2.

To find the edge with the lowest weight, I simply take one from the first list if it is not empty, in which case I take an edge from the second list.

Access and removal of an item from the list is O (1), so the Prim algorithm will work in O (V + E).

package il.ac.oranim.alg2016; import edu.princeton.cs.algs4.*; public class MST12 { private int weight; // weight of the tree private Edge[] mstEdges; // use this to store the edges of your Minimum Spanning Tree public MST12(EdgeWeightedGraph G, int s) throws IndexOutOfBoundsException, DisconnectedGraphException, WrongWeightException { // check that the starting vertex is in the range 0,1,...,GV() if (s < 0 || s >= GV()) { throw new IndexOutOfBoundsException(); } // check that the input graph is connected otherwise there is no (minimum) spanning tree if (isConnected(G) == false) { throw new DisconnectedGraphException(); } // check that all the weights are 1 or 2 for (Edge e : G.edges()) { if (e.weight() != 1 && e.weight() != 2) { throw new WrongWeightException(); } } this.weight = 0; // make sure you update this value // replace --> // your code goes here // <-- replace } // returns the weight of the tree public int weight() { return this.weight; } // checks whether a graph is connected private static boolean isConnected(EdgeWeightedGraph G) { // create a graph of class Graph with the same edges (weights) Graph g = new Graph(GV()); for (Edge e : G.edges()) { int v = e.either(); g.addEdge(v, e.other(v)); } // compute the connected components of the graph CC cc = new CC(g); // return true iff there is only one connected component return cc.count() == 1; } /** * Returns the edges in a minimum spanning tree as * an iterable of edges */ public Iterable<Edge> edges() { Queue<Edge> edges = new Queue<Edge>(); for (int i = 0; i < this.mstEdges.length; i++) { Edge e = this.mstEdges[i]; int v = e.either(); edges.enqueue(new Edge(v, e.other(v), e.weight())); } return edges; } /** * test the computing of an MST of a graph with weights 1 and 2 only * the first argument is the name of the file that contains the graph (graph1.txt, graph2.txt, or graph3.txt) * you can define this argument in Run.. --> (x)=Arguments */ public static void main(String[] args) { In in = new In(args[0]); EdgeWeightedGraph G = new EdgeWeightedGraph(in); PrimMST primMST = new PrimMST(G); MST12 mst12 = null; try { mst12 = new MST12(G,0); } catch (DisconnectedGraphException e) { System.err.println("the input graph is not connected and hence has no (minimum) spanning tree"); } catch (WrongWeightException e) { System.err.println("not all weights in the input graph are 1 or 2"); } System.out.println("Prim MST weight = " + primMST.weight()); System.out.println("My MST weight = " + mst12.weight()); } } 

I am stuck in part //replace-->//your code goes here//replace<--

two classes are needed:

 package il.ac.oranim.alg2016; public class DisconnectedGraphException extends Exception { public DisconnectedGraphException() {} } 

and

  package il.ac.oranim.alg2016; public class WrongWeightException extends Exception { public WrongWeightException() {} } 

I am also allowed to use all this http://algs4.cs.princeton.edu/code/

can someone help me with this part //replace-->//your code goes here//replace<--

I tried to copy this code into the //<--relpace,//replace--> , and then at my feet to change it to use the heap into two lists.

Prim Algorithm Pseudocode

In other words, I need code for this:

Answer 1

  package il.ac.oranim.alg2016; import edu.princeton.cs.algs4.*; public class MST_12 { private int weight; // weight of the tree private Edge[] mstEdges; // MST edges private boolean[] marked;// MST vertices private Queue<Edge> queueWeight1; private Queue<Edge> queueWeight2; public MST_12(EdgeWeightedGraph G, int s) throws IndexOutOfBoundsException, DisconnectedGraphException, WrongWeightException { // check that the starting vertex is in the range 0,1,...,GV() if (s < 0 || s >= GV()) { throw new IndexOutOfBoundsException(); } // check that the input graph is connected otherwise there is no (minimum) spanning tree if (isConnected(G) == false) { throw new DisconnectedGraphException(); } // check that all the weights are 1 or 2 for (Edge e : G.edges()) { if (e.weight() != 1 && e.weight() != 2) { throw new WrongWeightException(); } } this.weight = 0; // make sure you update this value // replace --> queueWeight1 = new Queue<Edge>(); queueWeight2 = new Queue<Edge>(); mstEdges=new Edge[GV()]; marked=new boolean[GV()]; for (int v = 0; v < GV(); v++) // run from each vertex to find if (!marked[v]) KPrim(G,v);// minimum spanning forest } private void KPrim ( EdgeWeightedGraph G, int s) { visit(G,s); while (!queueWeight1.isEmpty()||!queueWeight2.isEmpty()){ Edge e=null; if (!queueWeight1.isEmpty()) { e=queueWeight1.dequeue();} else if (!queueWeight2.isEmpty()){e=queueWeight2.dequeue();} int v=e.either(), w=e.other(v); assert marked [v]||marked [w]; if(marked[v]&&marked[w]) continue; mstEdges[s]=e; weight+=e.weight(); if(!marked[v]) visit(G,v);// v becomes part of tree if(!marked[w]) visit(G,w);// w becomes part of a tree } } //add all edges e incident to v onto queue if the other endpoint has not yet been scanned private void visit (EdgeWeightedGraph G, int v) { marked[v]=true;// add v to T for (Edge e : G.adj(v))// for each edge e=vw, add to queueWeight if w not already in T { if(!marked[e.other(v)]) { if (e.weight()==1.0) {queueWeight1.enqueue(e);mstEdges[v]=e;}//add the smallest edge weight to the mst weight else {queueWeight2.enqueue(e);mstEdges[v]=e;}}} } // <-- replace // returns the weight of the tree public int weight() { return this.weight; } // checks whether a graph is connected private static boolean isConnected(EdgeWeightedGraph G) { // create a graph of class Graph with the same edges (weights) Graph g = new Graph(GV()); for (Edge e : G.edges()) { int v = e.either(); g.addEdge(v, e.other(v)); } // compute the connected components of the graph CC cc = new CC(g); // return true iff there is only one connected component return cc.count() == 1; } /** * Returns the edges in a minimum spanning tree as * an iterable of edges */ public Iterable<Edge> edges() { Queue<Edge> edges = new Queue<Edge>(); for (int i = 0; i < this.mstEdges.length; i++) { Edge e = this.mstEdges[i]; int v = e.either(); edges.enqueue(new Edge(v, e.other(v), e.weight())); } return edges; } /** * test the computing of an MST of a graph with weights 1 and 2 only * the first argument is the name of the file that contains the graph (graph1.txt, graph2.txt, or graph3.txt) * you can define this argument in Run.. --> (x)=Arguments */ public static void main(String[] args) { In in = new In(args[0]); EdgeWeightedGraph G = new EdgeWeightedGraph(in); PrimMST primMST = new PrimMST(G); MST_12 mst12 = null; try { mst12 = new MST_12(G,0); } catch (DisconnectedGraphException e) { System.err.println("the input graph is not connected and hence has no (minimum) spanning tree"); } catch (WrongWeightException e) { System.err.println("not all weights in the input graph are 1 or 2"); } System.out.println("Prim MST weight = " + primMST.weight()); System.out.println("My MST weight = " + mst12.weight()); } } 

Answer 2

First, we implement the usual Prim-algorithm with a priority queue, which runs in O (| E | log (| V |)). And do it yourself, instead of copying the book code. If you cannot implement Prim Algorithm yourself, you will not understand how to extend the algorithm.

Then, as the DW suggested at https://cs.stackexchange.com/questions/66498/prims-algorithm-on-graph-with-weights-of-only-1-and-2-on-each-edge , you can change its ExtractMin, Remove, and Insert functions to O (1).

The idea is that you can save the list of edges with weights 1 and 2. If the list for the weight of edge 1 is not empty, you can get the next best edge to use by selecting the list in O (1) time. If the list for the weight of the edge 1 is empty, then the next best edges can be obtained by setting the list of weights 2 O (1) times.

The only change from the usual Prim algorithm is that you need a data structure like this:

 private class SpecialPQ { ArrayList<NodeWeightPair> _queueWeight1 = new ArrayList<NodeWeightPair>(); ArrayList<NodeWeightPair> _queueWeight2 = new ArrayList<NodeWeightPair>(); public void insert(NodeWeightPair e) { if (e._weight == 1) { _queueWeight1.add(e); } else { _queueWeight2.add(e); } } public void remove() { if (_queueWeight1.size() == 0) { _queueWeight2.remove(_queueWeight2.size()-1); } else { _queueWeight1.remove(_queueWeight1.size()-1); } } public NodeWeightPair extractMin() { if (_queueWeight1.size() > 0) { return _queueWeight1.get(_queueWeight1.size()-1); } else { return _queueWeight2.get(_queueWeight2.size()-1); } } public boolean empty() { return _queueWeight1.size() == 0 && _queueWeight2.size() == 0; } }; 

The Normal Prim Algorithm uses the binary heap priority queue to get O (| E | log (| V |)). You just need to replace the binary heap priority queue with the faster SpecialPQ .

Thus, the book code has the following line:

 private IndexMinPQ<Double> pq; 

You just need to change this to

 private SpecialPQ pq; 

and get the rest of the code to compile. Do not arbitrarily copy and paste my code for SpecialPQ . You will need a lot of time to be compatible with the book code. Instead, I think you should write your own SpecialPQ that will work with your own implementation of Prim Algorithm.

I have a working example locally - my own implementation, so it is not compatible with the book code. I will share with you if you publish your attempt to implement this.

Changes:

NodeWeightPair

 private class NodeWeightPair { private int _parent; private int _node; private int _weight; public NodeWeightPair(int parent, int node, int weight) { _node = node; _weight = weight; _parent = parent; } }