I'm implementing Kruskal's algorithm in C++11 and would like feedback on style and performance on my graph data structure and algorithm for educational purposes (for production code, I'd use a pre-existing library). The main design questions I have are:
Is there a better way to implement the handle class for the graph structure?
Did I implement path compression correctly in the UnionFind data structure?
I also have a couple of C++11 specific questions:
- Am I applying move semantics in a useful way when I add vertices and edges?
- Am I taking full advantage of return value optimization and copy elision?
AdjacencyList.h
#include <vector>
#include <memory>
#include <algorithm>
#include <string>
#include "FwdDecl.h"
#include "Handle.h"
#include "Vertex.h"
#include "Edge.h"
class AdjacencyList
{
public:
typedef Vertex vertex_type;
typedef std::string vertex_id_type;
typedef std::vector<std::shared_ptr<vertex_type>> vertex_container;
typedef Handle<vertex_type> vertex_handle;
typedef Edge<vertex_handle> edge_type;
typedef std::vector<std::shared_ptr<edge_type>> edge_container;
typedef Handle<edge_type> edge_handle;
vertex_container getVertexList() const
{
return m_vertices;
}
edge_container getEdgeList() const
{
return m_edges;
}
size_t getNumVerts() const
{
return m_vertices.size();
}
size_t getNumEdges() const
{
return m_edges.size();
}
vertex_handle findVertex(const vertex_type& v) const
{
return findVertexById(v.m_id);
}
vertex_handle findVertexById(const vertex_id_type& id) const
{
const auto vertexIt(std::find_if(begin(m_vertices),
end(m_vertices),
[id](const std::shared_ptr<vertex_type>& v) { return v->m_id == id; } ));
vertex_handle result(std::shared_ptr<vertex_type>(nullptr), 0);
if (vertexIt != end(m_vertices))
{
result = vertex_handle(*vertexIt, std::distance(begin(m_vertices), vertexIt));
}
return result;
}
edge_handle findEdge(const edge_type& e) const
{
return findEdge(e.getStart(), e.getEnd(), e.getWeight());
}
edge_handle findEdge(const vertex_handle& startVertex, const vertex_handle& endVertex, size_t weight) const
{
return findEdge(startVertex->m_id, endVertex->m_id, weight);
}
edge_handle findEdge(const vertex_id_type& startId, const vertex_id_type& endId, size_t weight) const
{
const auto edgeIt(std::find_if(begin(m_edges),
end(m_edges),
[startId, endId, weight](const std::shared_ptr<edge_type>& e)
{ return weight == e->getWeight() &&
startId == e->getStart()->m_id &&
endId == e->getEnd()->m_id;
} ));
edge_handle result(std::shared_ptr<edge_type>(nullptr), 0);
if (edgeIt != end(m_edges))
{
result = edge_handle(*edgeIt, std::distance(begin(m_edges), edgeIt));
}
return result;
}
vertex_handle addVertex(const vertex_type& v)
{
auto existingVertex(findVertex(v));
if (!existingVertex.isValid())
{
m_vertices.push_back(std::make_shared<vertex_type>(v));
existingVertex = vertex_handle(m_vertices.back(), m_vertices.size() - 1);
}
return existingVertex;
}
vertex_handle addVertex(vertex_type&& v)
{
auto existingVertex(findVertex(v));
if (!existingVertex.isValid())
{
m_vertices.push_back(std::make_shared<vertex_type>(std::move(v)));
existingVertex = vertex_handle(m_vertices.back(), m_vertices.size() - 1);
}
return existingVertex;
}
edge_handle addEdge(const edge_type& e)
{
auto existingEdge(findEdge(e));
if (!existingEdge.isValid())
{
m_edges.push_back(std::make_shared<edge_type>(e));
existingEdge = edge_handle(m_edges.back(), m_edges.size() - 1);
}
return existingEdge;
}
edge_handle addEdge(edge_type&& e)
{
auto existingEdge(findEdge(e));
if (!existingEdge.isValid())
{
m_edges.push_back(std::make_shared<edge_type>(std::move(e)));
existingEdge = edge_handle(m_edges.back(), m_edges.size() - 1);
}
return existingEdge;
}
private:
vertex_container m_vertices;
edge_container m_edges;
};
Handle.h
#include <memory>
#include <exception>
template <typename T>
class Handle
{
public:
Handle(const std::shared_ptr<T>& ptr, size_t index)
: m_ptr(ptr)
, m_index(index)
{
}
bool isValid() const
{
return !m_ptr.expired();
}
size_t getIndex() const
{
if (isValid())
{
return m_index;
}
throw std::logic_error("Attempt to get index from invalid handle.");
}
T& operator*()
{
const auto ptr = m_ptr.lock();
if (ptr)
{
return *ptr;
}
throw std::logic_error("Attempt to dereference invalid handle.");
}
const T& operator*() const
{
const auto ptr = m_ptr.lock();
if (ptr)
{
return *ptr;
}
throw std::logic_error("Attempt to dereference invalid handle.");
}
T* operator->()
{
const auto ptr = m_ptr.lock();
if (ptr)
{
return ptr.get();
}
return nullptr;
}
const T* operator->() const
{
const auto ptr = m_ptr.lock();
if (ptr)
{
return ptr.get();
}
return nullptr;
}
private:
std::weak_ptr<T> m_ptr;
size_t m_index;
};
Kruskal.cpp
#include "Kruskal.h"
#include "AdjacencyList.h"
#include "UnionFind.h"
AdjacencyList kruskal(const AdjacencyList& graph)
{
auto edges(graph.getEdgeList());
std::sort(begin(edges),
end(edges),
[](const AdjacencyList::edge_container::value_type& lhs,
const AdjacencyList::edge_container::value_type& rhs)
{
return *lhs < *rhs;
});
UnionFind components(graph.getNumVerts());
AdjacencyList minimumSpanningTree;
for (const auto edgePtr : edges)
{
const auto* edge = edgePtr.get();
const auto startIndex = edge->getStart().getIndex();
const auto endIndex = edge->getEnd().getIndex();
if (!components.sameComponent(startIndex, endIndex))
{
const auto startVertex(minimumSpanningTree.addVertex(*edge->getStart()));
const auto endVertex(minimumSpanningTree.addVertex(*edge->getEnd()));
minimumSpanningTree.addEdge(AdjacencyList::edge_type(startVertex,
endVertex,
edge->getWeight()));
components.merge(startIndex, endIndex);
}
}
return minimumSpanningTree;
}
UnionFind.h
#include <vector>
#include <algorithm>
#include <iterator>
#include <exception>
#include <sstream>
class UnionFind
{
public:
explicit UnionFind(size_t numVerts)
{
m_components.reserve(numVerts);
size_t parentIdx = 0;
std::generate_n(std::back_inserter(m_components),
numVerts,
[&]() { return UnionFindNode(parentIdx++); });
}
bool sameComponent(size_t start, size_t end) const
{
return findRoot(start) == findRoot(end);
}
size_t findRoot(size_t elem) const
{
if (elem < m_components.size())
{
auto prevParent = elem;
auto parentIdx = m_components[prevParent].parentIdx;
while (parentIdx != prevParent)
{
prevParent = parentIdx;
parentIdx = m_components[parentIdx].parentIdx;
}
return parentIdx;
}
std::ostringstream oss;
oss << "Element index " << elem << " is out of range of components buffer (size " << m_components.size() << ").";
throw std::out_of_range(oss.str());
}
void merge(size_t start, size_t end)
{
const auto startRoot(findRoot(start));
const auto endRoot(findRoot(end));
if (startRoot == endRoot)
{
return;
}
const auto startTreeSize = m_components[startRoot].subtreeSize;
const auto endTreeSize = m_components[endRoot].subtreeSize;
if (startTreeSize < endTreeSize)
{
m_components[startRoot].parentIdx = m_components[endRoot].parentIdx;
}
else
{
m_components[endRoot].parentIdx = m_components[startRoot].parentIdx;
}
if (startTreeSize == endTreeSize)
{
m_components[startRoot].subtreeSize += 1;
}
}
private:
struct UnionFindNode
{
explicit UnionFindNode(size_t parent)
: parentIdx(parent)
, subtreeSize(1)
{
}
size_t parentIdx;
size_t subtreeSize;
};
std::vector<UnionFindNode> m_components;
};
