Implementation of Prim's minimum spanning tree

Question

Feel free to tell about every possible issue (style, errors, inffective solution etc.) you found. Here is the main part of what I want to be reviewed, through there is some related code on GitHub.

Header

#ifndef PRIM_GRAPH_MST_H
#define PRIM_GRAPH_MST_H

#include <list>
#include "graph.h"

class PrimGraphMstImplementation;

class PrimGraphMst
// class that should find minimum spanning tree (MST) for the given graph
// and then store obtained result as a list of edges and summary weight
{
public:
    PrimGraphMst(const Graph&);
    // all work is actualy done in constructor
    // then we hold obtained result in some immutable fields

    const std::list<Graph::EdgeKey>& edges();
    // returns a list of edges from the given graph that forms MST

    double weight() const;
    // returns MST summary weight

   bool valid() const;
   // checks if obtained mst contains same number of vertices as the given graph
   // it could be wrong if the given graph was not connected

   Graph* makeTreeGraph();
   // construct new graph that have only edges from our MST

   private:
   std::shared_ptr<PrimGraphMstImplementation> impl;
};

#endif // PRIM_GRAPH_MST_H

C++ Source

#include <queue>
#include <cassert>
#include "prim_graph_mst.h"

class EdgeWithPriority
// helper class to use graph eges in priority queue
{
public:
double weight;
Graph::EdgeKey key;

EdgeWithPriority(int x, int y, const Graph& graph)
{
    weight = graph.distance(x, y);
    assert(weight >= 0);
    key = Graph::makeEdgeKey(x, y);
}

bool operator<(const EdgeWithPriority& other) const
// such behavior is needed to use this type in std::priority queue
// where top element is always max element and wee need to retrieve
// edge with the lowest weight
{
    return weight >= other.weight;
}
};

class PrimGraphMstImplementation
{
//actual implementation of Prim's algorithm
public:
PrimGraphMstImplementation(const Graph& graph)  :
    graph(graph),
    summaryWeight(0)
  // we do all the work here in constructor
  // we assume that graph is connected
{
    assert(graph.verticesCount() > 0);
    visitVertex(0);

    while(!pq.empty() && visited.size() < graph.verticesCount())
    {
        EdgeWithPriority element = pq.top();
        pq.pop();

        if(visited.find(element.key.first) == visited.end())
        {
            edges.push_back(element.key);
            summaryWeight += element.weight;
            visitVertex(element.key.first);
        }
        else if (visited.find(element.key.second) == visited.end())
        {
            edges.push_back(element.key);
            summaryWeight += element.weight;
            visitVertex(element.key.second);
        }
        else
        {
            continue;
        }
    }
}

void visitVertex(size_t index)
// helper method marks vertex as visited and adds all it's
// edges to priority queue
{
    visited.insert(index);
    for(size_t other : graph.getVertexNeighbors(index))
    {
        pq.push(EdgeWithPriority(index, other, graph));
    }
}

bool valid() const
// it could be wrong if given graph was not connected
{
    return visited.size() == graph.verticesCount();
}


const Graph& graph;
double summaryWeight;
std::list<Graph::EdgeKey> edges;

private:
std::priority_queue<EdgeWithPriority> pq;
std::set<size_t> visited;
};

PrimGraphMst::PrimGraphMst(const Graph& graph)
{
impl = std::make_shared<PrimGraphMstImplementation>(graph);
}

const std::list<Graph::EdgeKey>& PrimGraphMst::edges()
{
return impl->edges;
}

bool PrimGraphMst::valid() const
{
return impl->valid();
}

double PrimGraphMst::weight() const
{
return impl->summaryWeight;
}

Graph* PrimGraphMst::makeTreeGraph()
{
if(!valid())
    return nullptr;

Graph* result = new Graph(impl->graph.verticesCount());
for(Graph::EdgeKey element : impl->edges)
{
    double weight = impl->graph.distance(element.first, element.second);
    result->connect(element.first, element.second, weight);
}

return result;
}

Answer 1

Generally speaking, it seems to be coded pretty well. I can just find one or two things that could be improved:

---

else
{
    continue;
}

This piece of code at the end of a while seems fairly useless. I guess it would be the same without it.

---

void visitVertex(size_t index)
// helper method marks vertex as visited and adds all it's
// edges to priority queue
{
    visited.insert(index);
    for(size_t other : graph.getVertexNeighbors(index))
    {
        pq.push(EdgeWithPriority(index, other, graph));
    }
}

Here, you can replace pq.push(EdgeWithPriority(index, other, graph)); by pq.emplace(index, other, graph);. The function emplace will construct the object directly in the priority_queue with the given parameters.

You could also probably replace visited.insert(index); by visited.emplace(index); but I don't think it will change anything.

---

Graph* result = new Graph(impl->graph.verticesCount());
for(Graph::EdgeKey element : impl->edges)
{
    double weight = impl->graph.distance(element.first, element.second);
    result->connect(element.first, element.second, weight);
}

I don't know what the methods distance and connect do, but depending on what they really do, it could be better to for your for loop to take const references instead of values. But, well... it depends on distance and connect.

---

You should use std::unique_ptr instead of std::shared_ptr to hold the pointer to the implementation. Since std::unique_ptr cannot be copied, that means that PrimGraphMst cannot be copied either, but that's probably fine since std::shared_ptr was not copying your data either but merely doing an alias to the implementation.

You can also improve the constructor of PrimGraphMst by using a constructor initiaization list instead of a late memory allocation:

PrimGraphMst::PrimGraphMst(const Graph& graph):
    impl{ new PrimGraphMstImplementation{graph} }
{}

---

You may have noted it: I used curly braces in the initialization list of the constructor in the previous section of this review. Contrary to plain parenthesis, curly braces prevent any implicit narrowing type conversion. Using them can help to catch the small errors that are sometimes linked to narrowing conversions.

---

Style: your indentation often seems off and makes the code quite difficult to review. You should indent your code evrytime you introduce a new scope.

You are placing the comments of your function right after their point of declaration. Generally speaking, comments about a function are placed right before the function declaration.