Update
I've posted some updated code and included the definition of Vertex and Edge to try to answer as many questions as I could. To summarize what's changed:
- I've followed the advice here to reduce the amount of code duplication arising from enabling move semantics as much as I can.
- Handle has been renamed to ItemIndexPair. I need to label vertices with a total ordering to implement the UnionFind data structure as an array, not a tree.
- I've removed the non-const overload of operator* and operator-> to reduce code duplication.
- The getters/setters for AdjacencyList have been removed. In its place, I've changed kruskal() to be a function template taking an edge list and the number of vertices in the graph and provided a member function that forwards to this helper (in case I ever decide to implement AdjacencyMatrix).
Edge and vertex definitions
template <typename VertexPointer>
class Edge
{
public:
Edge(VertexPointer start, VertexPointer end, size_t weight)
: m_start(std::move(start))
, m_end(std::move(end))
, m_weight(weight)
{
}
VertexPointer getStart() const
{
return m_start;
}
VertexPointer getEnd() const
{
return m_end;
}
size_t getWeight() const
{
return m_weight;
}
private:
VertexPointer m_start;
VertexPointer m_end;
size_t m_weight;
};
template <typename VertexPointer>
bool operator<(const Edge<VertexPointer>& lhs, const Edge<VertexPointer>& rhs)
{
return lhs.getWeight() < rhs.getWeight();
}
template <typename VertexPointer>
bool operator>(const Edge<VertexPointer>& lhs, const Edge<VertexPointer>& rhs)
{
return rhs < lhs;
}
template <typename VertexPointer>
bool operator<=(const Edge<VertexPointer>& lhs, const Edge<VertexPointer>& rhs)
{
return !(lhs > rhs);
}
template <typename VertexPointer>
bool operator>=(const Edge<VertexPointer>& lhs, const Edge<VertexPointer>& rhs)
{
return !(lhs < rhs);
}
class Vertex
{
public:
explicit Vertex(std::string id)
: m_id(std::move(id))
{
}
std::string getId() const
{
return m_id;
}
private:
std::string m_id;
};
ItemIndexPair.h
#include <memory>
#include <exception>
template <typename T>
class ItemIndexPair
{
public:
ItemIndexPair(const std::shared_ptr<T>& ptr, size_t index)
: m_itemIndex(std::make_pair(std::weak_ptr<T>(ptr), index))
{
}
bool isValid() const
{
return !m_itemIndex.first.expired();
}
size_t getIndex() const
{
if (isValid())
{
return m_itemIndex.second;
}
throw std::logic_error("Attempt to get index from invalid handle.");
}
T* get() const
{
const auto ptr(m_itemIndex.first.lock());
return ptr.get();
}
T& operator*() const
{
auto* ptr(get());
if (ptr)
{
return *ptr;
}
throw std::logic_error("Attempt to dereference invalid handle.");
}
T* operator->() const
{
return get();
}
private:
std::pair<std::weak_ptr<T>, size_t> m_itemIndex;
};
AdjacencyList.h
#include <vector>
#include <memory>
#include <algorithm>
#include <string>
#include "FwdDecl.h"
#include "ItemIndexPair.h"
#include "Vertex.h"
#include "Edge.h"
#include "Kruskal.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 ItemIndexPair<vertex_type> vertex_pointer;
typedef Edge<vertex_pointer> edge_type;
typedef std::vector<std::shared_ptr<edge_type>> edge_container;
typedef ItemIndexPair<edge_type> edge_pointer;
size_t getNumVertices() const
{
return m_vertices.size();
}
size_t getNumEdges() const
{
return m_edges.size();
}
AdjacencyList kruskal() const
{
return ::kruskal<AdjacencyList>(m_edges, m_vertices.size());
}
vertex_pointer findVertex(const vertex_type& v) const
{
return findVertex(v.getId());
}
vertex_pointer findVertex(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->getId() == id; } ));
vertex_pointer result(std::shared_ptr<vertex_type>(nullptr), 0);
if (vertexIt != end(m_vertices))
{
result = vertex_pointer(*vertexIt, std::distance(begin(m_vertices), vertexIt));
}
return result;
}
edge_pointer findEdge(const vertex_pointer& startVertex, const vertex_pointer& endVertex, size_t weight) const
{
return findEdge(startVertex->getId(), endVertex->getId(), weight);
}
edge_pointer findEdge(vertex_id_type startId, 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()->getId() &&
endId == e->getEnd()->getId();
} ));
edge_pointer result(std::shared_ptr<edge_type>(nullptr), 0);
if (edgeIt != end(m_edges))
{
result = edge_pointer(*edgeIt, std::distance(begin(m_edges), edgeIt));
}
return result;
}
vertex_pointer 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_pointer(m_vertices.back(), m_vertices.size() - 1);
}
return existingVertex;
}
edge_pointer addEdge(vertex_pointer start, vertex_pointer end, size_t weight)
{
auto existingEdge(findEdge(start, end, weight));
if (!existingEdge.isValid())
{
m_edges.push_back(std::make_shared<edge_type>(std::move(start), std::move(end), weight));
existingEdge = edge_pointer(m_edges.back(), m_edges.size() - 1);
}
return existingEdge;
}
private:
vertex_container m_vertices;
edge_container m_edges;
};
Kruskal.h
#include "Kruskal.h"
#include "AdjacencyList.h"
#include "UnionFind.h"
template <typename GraphType, typename EdgeSequence>
GraphType kruskal(EdgeSequence edges, size_t numVertices)
{
std::sort(
begin(edges),
end(edges),
[](const typename EdgeSequence::value_type& lhs,
const typename EdgeSequence::value_type& rhs)
{
return *lhs < *rhs;
});
UnionFind components(numVertices);
GraphType minimumSpanningTree;
for (const auto edgePtr : edges)
{
const auto* edge = edgePtr.get();
const auto startVertex(edge->getStart());
const auto endVertex(edge->getEnd());
const auto startIndex = startVertex.getIndex();
const auto endIndex = endVertex.getIndex();
if (!components.sameComponent(startIndex, endIndex))
{
const auto mstStartVertex(minimumSpanningTree.addVertex(*startVertex));
const auto mstEndVertex(minimumSpanningTree.addVertex(*endVertex));
minimumSpanningTree.addEdge(mstStartVertex, mstEndVertex, edge->getWeight());
components.merge(startIndex, endIndex);
}
}
return minimumSpanningTree;
}
Original post
AdjacencyList.h AdjacencyList.h
Handle.h Handle.h
Kruskal.cpp Kruskal.cpp
UnionFind.h UnionFind.h
