Prim's Algorithm - Minimum Spanning Tree

Question

I have implemented Prim's Algorithm from Introduction to Algorithms. I have observed that the code is similar to Dijkstra's Algorithm, so I have used my Dijkstra's Algorithm implementation.

Please review this code and suggest improvements.

To compile on Linux: g++ -std=c++14 prims.cpp

#include <iostream>
#include <map>
#include <limits>
#include <list>
#include <queue>
class Graph
{
 struct Vertex
 {
 std::size_t id;
 int distance = std::numeric_limits<int>::max();
 Vertex * parent = nullptr;
 Vertex(std::size_t id) : id(id) {}
 };
 using pair_ = std::pair<std::size_t, int>;
 std::vector<Vertex> vertices = {};
 //adjacency list , store src, dest, and weight
 std::vector< std::vector< pair_> > adj_list;
 //to store unprocessed vertex min-priority queue
 std::priority_queue< pair_, std::vector<pair_>,
 std::greater<pair_> > unprocessed;
 public:
 Graph(std::size_t size);
 void add_edge(std::size_t src, std::size_t dest, int weight);
 void prim(std::size_t vertex);
 std::size_t minimum_cost() ;
};
Graph::Graph(std::size_t size)
{
 vertices.reserve(size);
 adj_list.resize(size);
 for (int i = 0; i < size; i++)
 {
 vertices.emplace_back(i);
 }
}
void Graph::add_edge(std::size_t src , std::size_t dest, int weight)
{
 if(weight >= 0)
 {
 if (src == dest)
 {
 throw std::logic_error("Source and destination vertices are same");
 }
 if (src < 0 || vertices.size() <= src)
 {
 throw std::out_of_range("Enter correct source vertex");
 }
 if (dest < 0 || vertices.size() <= dest)
 {
 throw std::out_of_range("Enter correct destination vertex");
 }
 int flag = 0, i = src;
 for (auto& it : adj_list[i])
 {
 if (it.first == dest)
 {
 flag = 1;
 break;
 }
 }
 if (flag == 0)
 {
 adj_list[src].push_back( {dest, weight} );
 }
 else
 {
 throw std::logic_error("Existing edge");
 }
 }
 else
 {
 std::cerr << "Negative weight\n";
 }
}
void Graph::prim(std::size_t vertex)
{
 vertices[vertex].distance = 0;
 vertices[vertex].parent = &vertices[vertex];
 unprocessed.push( std::make_pair(vertices[vertex].distance, vertex) );
 while (!unprocessed.empty())
 {
 int curr_vertex_dist = unprocessed.top().first;
 std::size_t curr_vertex = unprocessed.top().second;
 unprocessed.pop();
 for (auto& ver: adj_list[curr_vertex])
 {
 auto& next_dist = vertices[ver.first].distance;
 const auto curr_dist = ver.second;
 if (curr_dist < next_dist)
 {
 next_dist = curr_dist;
 //make src vertex parent of dest vertex
 vertices[ver.first].parent = &vertices[curr_vertex];
 unprocessed.push( std::make_pair(next_dist, ver.first)); 
 }
 }
 }
}
std::size_t Graph::minimum_cost() 
{
 std::size_t cost = 0;
 for (auto vertex: vertices)
 {
 cost = cost + vertex.distance;
 }
 return cost;
}
int main()
{
 Graph grp(9);
 grp.add_edge(0, 1, 4);
 grp.add_edge(0, 2, 8);
 grp.add_edge(1, 2, 11);
 grp.add_edge(1, 3, 8);
 grp.add_edge(3, 4, 2);
 grp.add_edge(4, 2, 7);
 grp.add_edge(2, 5, 1);
 grp.add_edge(5, 4, 6);
 grp.add_edge(3, 6, 7);
 grp.add_edge(3, 8, 4);
 grp.add_edge(5, 8, 2);
 grp.add_edge(6, 7, 9);
 grp.add_edge(6, 8, 14);
 grp.add_edge(7, 8, 10);
 grp.prim(0);
 std::cout << "The total cost is : " << grp.minimum_cost() << "\n";
}

Answer 1

1. Keeping references to potentially dangling pointers

I can see a potential problem with the line

vertices[ver.first].parent = &vertices[curr_vertex];

if the std::vector<Vertex> vertices would be reorganised due to changes in length. The address you take there isn't stable.

Maybe a better solution would be to keep a

std::vector<std::unique_ptr<Vertex>> vertices;

instead of keeping copies of the Vertex instances.

Then you can change

vertices[ver.first].parent = &vertices[curr_vertex];

to

vertices[ver.first].parent = vertices[curr_vertex].get();

Since all the vertices are in private scope of the Graph class the std::unique_ptr<Vertex> instances stored to the vertices vector will never invalidate, as long you guarantee to remove all child Vertex instances when a parent Vertex instane is removed from the graph (Well, that's not an operation in question here, but needs to be considered for production code).

2. Inconsistent error handling

Here

else
{
 std::cerr << "Negative weight\n";
}

you just use kind of errorneous input being reported to the console, while you throw exceptions for other cases.

For this condition you should rather do

• throwing an exception
• applying an assert() call in 1st place

• clarify from the function signature

  If Negative weight is erroneous input you should make that clear in 1st place:

   void Graph::add_edge(std::size_t src , std::size_t dest, unsigned weight)
   // ^^^^^^^^
  

  This way violations would be covered by the compiler, before runtime detects that flaw.

3. Storing unnecessary information

In your code example parent is never used besides storing the information. I am aware that you might have been simplified the actual usage of parent with this review question, but with the code context you give, that member variable doesn't make any sense.

• coder: I do not understand. Here we are making a node/vertex as a parent to other node/vertex.
• πάντα ῥεῖ: @coder As mentioned, the address you take there isn't stable. It points to an element address in that std::vector. As soon this std::vector will be resized, that address is invalidated.
• πάντα ῥεῖ: @coder I realized that using std::reference_wrapper won't work either. std::unique_ptr seems to be the right tool to express ownership here.
• miscco: std::unique_ptr is not the right tool. The right tool is std::size_t. The problem with the invalidation of iterators/references can be completely alleviated by storing the index of the member and not a reference to it. The only thing necessary is then to call operator[]
• πάντα ῥεῖ: @miscco Feel free to write another answer with some example code.