Prim's Algorithm Implementation in Java

Question

I'm trying to implement Prim's Algorithm in Java using for my graph HashMap + LinkedList and a class Edge which contains the connected vertex and the weight:

adjacencyList = new HashMap<T, LinkedList<Edge<T>>>();

My idea was, starting from a given vertex: 1)save all vertices into a LinkedList so I can remove them every time they've been visisted 2)saving the path into another LinkedList so I can have my final MST 3)using a PriorityQueue to find MIN weight

In the end I'll need MST, number of edges and total weight. I'm very confused about how to return MST and I have few errors on my code which I have no idea on how to fix them!

First of all I get this error:

    Prim.java:21: error: no suitable method found for addAll(LinkedList<Edge<T>>)
        unvisited.addAll(graph.getVertices());
                 ^
    method Collection.addAll(Collection<? extends T>) is not applicable
      (argument mismatch; LinkedList<Edge<T>> cannot be converted to Collection<? extends T>)
    method List.addAll(Collection<? extends T>) is not applicable
      (argument mismatch; LinkedList<Edge<T>> cannot be converted to Collection<? extends T>)
    method AbstractCollection.addAll(Collection<? extends T>) is not applicable
      (argument mismatch; LinkedList<Edge<T>> cannot be converted to Collection<? extends T>)
    method LinkedList.addAll(Collection<? extends T>) is not applicable
      (argument mismatch; LinkedList<Edge<T>> cannot be converted to Collection<? extends T>)
  where T is a type-variable: T extends Comparable<T> declared in class Prim

It seems the problem is in my getVertices() method (which return all the vertices of the graph) as it returns a Set<T>; I tried to put everything inside a LinkedList using addAll and get as return this LinkedList but it gives me the same error. What am I doing wrong?

public class Graph<T extends Comparable<T>> {
    .
    .
    public Set<T> getVertices() {
            if (adjacencyList.isEmpty()) {
                System.out.println("Error message.\n");
                return null;
            } else
                return adjacencyList.keySet();
        }
    }

The second error is:

   Prim.java:28: error: incompatible types: T cannot be converted to Edge<T>
            for (Edge<T> edge : graph.getAdjacentVertices(source)) {
                                                          ^
  where T is a type-variable:
    T extends Comparable<T> declared in class Prim
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output

I can fix it by casting Edge<T> to source but I think it doesn't make any sense at all because the idea was that I give a vertex which can contain any type, not only Edges.

Prim's:

public class Prim<T extends Comparable<T>> {
    public <SHOULD I RETURN graph ?> minimumSpanningTree(Graph<Edge<T>> graph, T vertex) {
        //ArgumentException

        double weight = 0;
        T source = vertex;

        LinkedList<T> vertexSet = new LinkedList<>();
        LinkedList<Edge<T>> path = new LinkedList<>();

        vertexSet.addAll(graph.getVertices()); //unvisited ERROR HERE
        vertexSet.remove(source);

        double numberOfVertices = graph.getVertices().size();
        PriorityQueue<Edge<T>> priorityQueue = new PriorityQueue<>();

        while (!vertexSet.isEmpty()) {
            for (Edge<T> edge : graph.getAdjacentVertices(source)) {//ERROR
               if (vertexSet.contains(edge.getDestination())) 
                    priorityQueue.insert(edge);
            }
            Edge<T> minWeight = priorityQueue.extractMin();
            weight += minWeight.getWeight();
            path.add(HERE I SHOULD PUT MST PATH BUT I DON'T KNOW HOW!!);

            source = minWeight.getDestination();
            vertexSet.remove(source);
        }
        return <graph??>;
    }
}

As I said before, I don't know if I should return a graph as MST (maybe the one I give as input deleting the most expensive edges) or the LinkedList called path which saves the path with lowest weight. I also don't know how to find the number of edges in the MST; should I for every vertex (keySet of my HashMap) find the size of the LinkedList (which is its value) and sum them all?

EDIT: getAdjacentVertices method

public LinkedList<T> getAdjacentVertices(T vertex) {
    if (adjacencyList.isEmpty() || adjacencyList.containsKey(vertex) == false) {
        System.out.println("Error msg.\n");
        return null;
    } else {
        LinkedList<T> allAdjacents = new LinkedList<>();
        for (Edge<T> edge : adjacencyList.get(vertex)) {
            allAdjacents.add(edge.getDestination());
        }
        return allAdjacents;
    }
}

phagio · Accepted Answer · 2018-08-13 11:45:56Z

2

1) I guess the error is not in getVertices() but in the fact that your Graph was defined as generic on Edge<T> and not T. Graph<T> is instantiated as Graph<Edge<T1>>, so Set<T> as return value is istantiated as Set<Edge<T1>>.

I suggest you define Graph as Graph<Edge<T>>, and refactor the graph's logics from there, or define a IEdge<T> as superinterface of Edge<T> and redefine Graph as Graph<? extends IEdge<T>>.

For instance (going blindfolded):

public class Graph<T> {
    Map<T, Edge<T>> adjacencyList;
    public Set<T> getVertices() {
        if (adjacencyList.isEmpty()) {
            System.out.println("Error message.\n");
            return null;
        } else {
            return adjacencyList.keySet();
        }
    }
}

Graph<Point> p;
List<Point> points = new LinkedList<>();
points.addAll(p.getVertices());

2) A variant of 1. In this case, you're returning a List<T> but since you're cycling with:

for (Edge<T> edge : graph.getAdjacentVertices(source))

the return value of getAdjacentVertices should be an Enumerable<Edge<T>>, while you're providing a Enumerable<T>. You probably want to return something like this in your getAdjacentVertices implementation:

LinkedList<Edge<T>> allAdjacents = new LinkedList<>();
for (Edge<T> edge : adjacencyList.get(vertex)) {
    allAdjacents.add(edge);
}
return allAdjacents;

edited Aug 13, 2018 at 11:45

answered Aug 13, 2018 at 10:32

phagio

1961 silver badge15 bronze badges

Sign up to request clarification or add additional context in comments.

12 Comments

NoProg Over a year ago

Ok, worked for (1) but didn't understand which Graph should I define as Graph<Edge<T>> for point (2). Do you mean the class or the minimumSpanningTree(Graph<T> graph, T vertex)?

phagio Over a year ago

Edited my answer to provide an example. Right now I have no way to test, but you should be able to grasp the juice.

NoProg Over a year ago

um ok, I think I got it but this will mess half of my graph class!! I think I'll need to find another solution!

phagio Over a year ago

No problem. Also I wouldn't return null when I can return an empty list ;)

phagio Over a year ago

Be careful, I guess you've edited the type of List but left the add(edge.getDestination()) unchanged. You can't add a Edge<T> to a List<T>. Moreover, what's the point of getting the edge destination when in the caller you cycle the result edges and check if your vertexes already contain their destination? You want to return Edges, not Ts.

|

Collectives™ on Stack Overflow

Prim's Algorithm Implementation in Java

1 Answer 1

12 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

12 Comments

Your Answer

Sign up or log in

Post as a guest

Related