Prim's Algorithm Implementation

[Recaip Sanli]

I am totally lost, have no idea even where to start on this. If you understand and have a clear suggestion, please let me know. I don't understand what this pseudocode code, can't even translate it.

Prim's Algorithm Pseudocode


Question

int[] prim(int n, int[][] W, Edge[] F)

This method takes as parameters an int n which is the number of vertices in the graph, an adjacency matrix held in a two-dimensional int array W, as well as an edge set F simulated by an array of the Edge class. The method implements the Prim’s minimum spanning tree algorithm (Algorithm 4.1 on page 160 in the textbook) and returns the nearest array. The Edge array F is already initialized with n – 1 slots (only n – 1 edges are needed) in the test driver so you don’t have to do it in this method. You need to make sure that after the method call is completed, F should have all the edges in the minimum spanning tree.

I uploaded provided Java files here:
https://ufile.io/4zvrc

Also entered them in text format below:
Edge.java

public class Edge
{
    // instance variables
    private int m_srcVertex;  // index of the source vertex
    private int m_destVertex; // index of the destination vertex
    
    // constructor
    public Edge(int srcVertex, int destVertex)
    {
        m_srcVertex = srcVertex;
        m_destVertex = destVertex;
    }
    
    // return a string representation of the Edge
    @Override
    public String toString()
    {
        return "(v" + m_srcVertex + ", " + "v" + m_destVertex + ")";
    }
    
    // compare two Edge objects and return true if they have the same source and
    // destination vertices, and false otherwise
    public boolean equals(Edge e)
    {
        if (m_srcVertex == e.m_srcVertex && m_destVertex == e.m_destVertex
                || m_srcVertex == e.m_destVertex && m_destVertex == e.m_srcVertex)
            return true;
        else
            return false;
    }
}

Homework4.java

public class Homework4
{
    // instance variable
    public final int inf = 99999;   // define infinity
    
    // This method implements the Prim's algorithm for the minimum spanning tree
    // problem. It take as parameters an int (# of vertices), an adjacency matrix 
    // held in a two-dimensional int array, and an edge set F. The method returns
    // the "nearest" array.
    public int[] prim(int n, int[][] W, Edge[] F)
    {
        // TODO: implement this method
		
        return null; // replace this statement with your own return
    }
    
    // This method takes as parameters an int (# of vertices), the "nearest" 
    // array, and an adjacency matrix held in a two-dimensional int array. It 
    // returns the total cost of the tree.
    public int costMST(int n, int[] nearest, int[][] W)
    {
        // TODO: implement this method
		
        return -1; // replace this statement with your own return
    }
    
    // This method verifies the edge set.
    // Do not make any changes to this method!
    public boolean verifyEdgeSet(Edge[] yours, Edge[] solution)
    {
        int sizeY = yours.length;
        int sizeS = solution.length;
        int actualEdges = 0;
        
        // check for the actual number of edges
        for (int i = 0; i < sizeY; i++)
            if (yours[i] != null)
                actualEdges++;
        
        if (actualEdges != sizeS)
            return false;
        
        // verify the edges
        for (int i = 0; i < sizeS; i++)
        {
            Edge tmpS = solution[i];
            boolean found = false;
            
            // search for tmpS in your edge set
            for (int j = 0; j < sizeY; j++)
            {
                Edge tmpY = yours[j];
                if (tmpY != null && tmpS.equals(tmpY) == true)
                {
                    found = true;
                    break;
                }
            }
            
            // if the edge is not found, return false
            if (found == false)
                return false;
        }
        
        return true;
    }
}

TestHomework4.java

public class TestHomework4 
{
    public static void main(String[] args)
    {
        
        Homework4 myHW4 = new Homework4();
        int src = -1, dest = -1;
        int inf = myHW4.inf;
        int n;
        int[] nearest = null;
        int numPassedTests = 0;
        int numTotalTests = 0;
        String testResult;
        
        n = 5;
        Edge[] F = new Edge[n];
        int[][] W1 = {
            {0, 0, 0, 0, 0, 0},
            {0, 0, 1, 3, inf, inf},
            {0, 1, 0, 3, 6, inf},
            {0, 3, 3, 0, 4, 2},
            {0, inf, 6, 4, 0, 5},
            {0, inf, inf, 2, 5, 0}
        };
        Edge[] sol = new Edge[4];
        sol[0] = new Edge(1, 2);
        sol[1] = new Edge(1, 3);
        sol[2] = new Edge(3, 5);
        sol[3] = new Edge(3, 4);

        System.out.println("W1 = ");
        for (int i = 1; i < W1.length; i++)
        {
            for (int j = 1; j < W1[i].length; j++)
                if (W1[i][j] == inf)
                    System.out.format("%-6s", "∞");
                else
                    System.out.format("%-6d", W1[i][j]);
            
            System.out.println("\n");
        }
        
        // Test 1
        numTotalTests++;
        boolean bReturn = false;
        testResult = "[Failed]";
        String eMsg = "N/A";
        try
        {
            nearest = myHW4.prim(n, W1, F);
            bReturn = myHW4.verifyEdgeSet(F, sol);
            
            if (bReturn == true)
            {
                numPassedTests++;
                testResult = "[Passed]";
            }
        }
        catch (RuntimeException e)
        {
            eMsg = "RuntimeException - \"" + e.getMessage()  + "\"";
        }

        
        System.out.println("Test " + numTotalTests + ": MST built for W1 - " + testResult);
        System.out.print(" Expected: ");
        printEdges(sol);
        if (eMsg.equals("N/A"))
        {
            System.out.print(" Yours: ");
            printEdges(F);
            System.out.println();
        }
        else
            System.out.println(" Yours: " + eMsg + "\n");
        
        // Test 2
        numTotalTests++;
        int iReturn = -1;
        testResult = "[Failed]";
        eMsg = "N/A";
        try
        {
            iReturn = myHW4.costMST(n, nearest, W1);
            
            if (iReturn == 10)
            {
                numPassedTests++;
                testResult = "[Passed]";
            }
        }
        catch (RuntimeException e)
        {
            eMsg = "RuntimeException - \"" + e.getMessage()  + "\"";
        }

        
        System.out.println("Test " + numTotalTests + ": Total cost of the MST of W1 - " + testResult);
        System.out.println(" Expected: 10");
        if (eMsg.equals("N/A"))
            System.out.println(" Yours: " + iReturn + "\n");
        else
            System.out.println(" Yours: " + eMsg + "\n");        

        
        n = 5;
        F = new Edge[n];
        int[][] W2 = {
            {0, 0, 0, 0, 0, 0},
            {0, 0, 9, inf, inf, 3},
            {0, 9, 0, 3, 2, inf},
            {0, inf, 3, 0, 4, inf},
            {0, inf, 2, 4, 0, 3},
            {0, 3, inf, inf, 3, 0}
            };
        sol = new Edge[4];
        sol[0] = new Edge(1, 5);
        sol[1] = new Edge(4, 5);
        sol[2] = new Edge(2, 4);
        sol[3] = new Edge(2, 3);

        System.out.println("W2 = ");
        for (int i = 1; i < W2.length; i++)
        {
            for (int j = 1; j < W2[i].length; j++)
                if (W2[i][j] == inf)
                    System.out.format("%-6s", "∞");
                else
                    System.out.format("%-6d", W2[i][j]);
            
            System.out.println("\n");
        }
        
        // Test 3
        numTotalTests++;
        bReturn = false;
        testResult = "[Failed]";
        eMsg = "N/A";
        try
        {
            nearest = myHW4.prim(n, W2, F);
            bReturn = myHW4.verifyEdgeSet(F, sol);
            
            if (bReturn == true)
            {
                numPassedTests++;
                testResult = "[Passed]";
            }
        }
        catch (RuntimeException e)
        {
            eMsg = "RuntimeException - \"" + e.getMessage()  + "\"";
        }

        
        System.out.println("Test " + numTotalTests + ": MST built for W2 - " + testResult);
        System.out.print(" Expected: ");
        printEdges(sol);
        if (eMsg.equals("N/A"))
        {
            System.out.print(" Yours: ");
            printEdges(F);
            System.out.println();
        }
        else
            System.out.println(" Yours: " + eMsg + "\n");
        
        // Test 4
        numTotalTests++;
        iReturn = -1;
        testResult = "[Failed]";
        eMsg = "N/A";
        try
        {
            iReturn = myHW4.costMST(n, nearest, W2);
            
            if (iReturn == 11)
            {
                numPassedTests++;
                testResult = "[Passed]";
            }
        }
        catch (RuntimeException e)
        {
            eMsg = "RuntimeException - \"" + e.getMessage()  + "\"";
        }

        
        System.out.println("Test " + numTotalTests + ": Total cost of the MST of W2 - " + testResult);
        System.out.println(" Expected: 11");
        if (eMsg.equals("N/A"))
            System.out.println(" Yours: " + iReturn + "\n");
        else
            System.out.println(" Yours: " + eMsg + "\n");  
        
        System.out.println("Total test cases: " + numTotalTests + "\nCorrect: " + numPassedTests + "\nWrong: " + (numTotalTests - numPassedTests));
    }
    
    public static void printEdges(Edge[] edges)
    {
        System.out.print("F = {");
        for (int i = 0; i < edges.length - 1; i++)
            if (edges[i] != null)
                System.out.print(edges[i].toString() + ", ");
        
        if (edges[edges.length - 1] != null)
                System.out.print(edges[edges.length - 1].toString());
        
        System.out.println("}");
    }
}

[Knute Snortum]

Recaip Sanli wrote:I am totally lost, have no idea even where to start on this. If you understand and have a clear suggestion, please let me know. I don't understand what this pseudocode code, can't even translate it.  

It can be frustrating to do something complex when you're not sure what to do, but if you break down the problem into smaller chunks, you can divide and conquer.

So, what is the first thing that confuses you about the pseudocode? Pick one thing.

[Campbell Ritchie]

Too difficult for this forum: moving.

I think you are going to have to start from scratch. Nobody is going to go through all that code looking for bugs, I am afraid. Start by writing the algorithm on paper without using any words borrowed from a computing language. What you have posted is not pseudocode, but mostly some sort of code in a specification language.
When you get round to coding something, variable names like m_srcVertex are very unhelpful; it is not obvious from reading them what they mean. Also don't use _ characters in Java® variable names. You might do well to look somewhere for an explanation of that algorithm.

[Recaip Sanli]

@Knute Snortum
First five lines in the Pseudocode shows initialization of variables. It's got two index and two numbers. Are they all int? The second part of index and number variables cannot be int, they must be int[].

@Campbell Ritchie
Most of the java files I put on this question is written by my instructor. This is my assignment. He didn't go over the Prim's algorithm code and I have no clue what is happening with it.

Going over someone elses code is harder than writing from scratch, especially when you have no idea how implementation of certain algorithm should be like.

I understand the concept of Prim's algorithm, but implementation, no idea.
I feel like I need to learn how to implement first from some youtube video, understand the kind of implementation instructor did and figure out what I need to do to make it work. Is this the only viable way?

[Campbell Ritchie]

I wouldn't use a video myself, but I might be mistaken on that point. Start with Wikipedia: Prim's_algorithm.
Make sure you know what the notation means: read ∅ as, “empty set”. Find out whether the & operator is “address of” or “pass‑by‑reference”. Address is a C programming construct allowing you to get the address (a pointer) out of a variable. Pass‑by‑reference exists in C++, but not in C or Java®.
Then go through the code line by line, writing down what you think each part means.

Yes, it is much more difficult to complete code which somebody else has already written, especially when it contains serious errors like an incorrectly‑written equals() method.

[Recaip Sanli]

Thank you Campbell Ritchie

[Campbell Ritchie]

Recaip Sanli wrote:Thank you Campbell Ritchie

I usually say, “That's a pleasure,” or similar, but that isn't quite accurate when I have given you such bad news. We try to help and don't like bringing such bad news.
At least you only need to implement one method by the looks of it.

[Knute Snortum]

Recaip Sanli wrote:@Knute Snortum
First five lines in the Pseudocode shows initialization of variables. It's got two index and two numbers. Are they all int? The second part of index and number variables cannot be int, they must be int[].

i is definitely an int, as it is used like this:

for (i = 2; i <= n; i++)

In Java, you are encouraged to declare variables as you need them, if possible.  In this case you would not need to declare i separately, just do it in the for loop itself:

for (int i = 2; i <= n; i++)

vnear is also an index and would be an int.

min is declared as a "number", by which I think it means a real number, which in Java would likely be a type double.

e is declared as a type edge.  This is an object that has been declared for you in Edge.java.  In Java you would simply type

Edge e;

nearest looks like an int array, as you suggested, with indices from 2 to n.  In Java, arrays start at zero.  I wouldn't bother with worrying about indices 0 and 1 and just declare the array as

int[] nearest = new int[n];

With all this information, I bet you can figure out how to declare distance.

[Piet Souris]

In case the preudo-code is still unclear after Knute's tips, maybe this will help you as well.

We start with an empty edge set F. Also is given a 2D weight matrix W[][], that gives for each pair of vertices (i, j) the weight (or distance). And, not unimportant, the arrays here start with 1, instead of 0.

Pick a vertex, say vertex 1 (assumng the vertices are named 1...n).

Now, for every other vertex, set vertex 1 as its nearest neighbor. Secondly, set the distance from every vertex i (i = 2...n) to vertex 1 (or, more general, to the start vertex we are dealing in this round) to W[1][i].
This is happening in this part (and now you see the disadvantage of using an image instead of real code, I cannot copy the relevant passage, and so must type it in. Next time, please supply real text)

for (i = 2; i <= n; i++) {
    nearest[i] = 1;   // vertex 1
    distance[i] = W[1][i];
}

Main loop:  We enter he loop in the preudo-code with "repeat n-1 times"...

1) find the edge with the minimum distance to vertex 'nearest[i]' (which is initially vertex 1), but only if that weight is >= 0 and less than infinity. As you can see, if two vertices are not connected, then you can set the distance safely to -1, it will then not be considered anymore

2) call the vertex that is closest to vertex 'nearest[i]' vnear.

3) all this is happening in the loop right behind the line 'min = infinity'.

3) add the edge (neares[i], vnear) to F. In the first round, as said, nearest[i] is vertex 1.

4) Now in the loop at the bottom: set for all vertices, starting with vertex 2, the distance to W[i][vnear]
  and set nearest[i] to vnear. As you saw, vertices that are already in F have their distance set to -1 and are not considered anymore)

5) in fact this is the same routine as we applied before entering the main loop. There we started with vertex 1, but now we start with vertex vnear

And goto main loop again until done.

Well there are some preconditions for the graph to apply this algo. In the first place, the graph must be connected. And the W[][] must start with a suitable vertex. Can you tell us a bit about the given preconditions?

And lastly: I found some old topic about MST, where a structure called 'unionfind' was used to good effect. Maybe it is of any use.
Here is the link: click here

Edit: I haven't looked at your code yet, but it seems rather large. Do you have any questions about your code?