2
\$\begingroup\$

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:

  1. Am I applying move semantics in a useful way when I add vertices and edges?
  2. 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;
};
\$\endgroup\$
2
\$\begingroup\$

To be honest I am having a hard time following your code.
So I can't comment on the efficiency.

But as an engineer I will make comments on maintainability (which I think is much more important (because if you understand the code you can optimize the slow parts once you have measured it))

I am not sure I understand the difference between "vertex_type" and "edge_type"?.

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;

Getters are bad OO design. They expose and thus bind your implementation to specific types.

vertex_container getVertexList() const
edge_container   getEdgeList()   const
size_t getNumVerts() const
size_t getNumEdges() const

Also you are returning the result by value (and thus copying) when you could return a const reference achieving the same affect without copying.

I am not sure what Handle is.
In computer science terms a Handle is named resource (thus allowing the resource to be moved and the handle to still refer to the same thing (commonly implemented as a pointer to a pointer to the resource)).

I handle you violate the "DRY" principle:

this code (or simple variations of it) are reeated multiple times.:

    const auto ptr = m_ptr.lock();
    if (ptr)
    {
        return <SIMPLE ACTION>;
    }

    throw std::logic_error(<ERROR MESSAGE>);
\$\endgroup\$
  • \$\begingroup\$ why would vertex be a synonym for edge? \$\endgroup\$ – Janus Troelsen Apr 7 '13 at 17:52
  • \$\begingroup\$ @Ysangkok: Ops. Long time since I did geometry. \$\endgroup\$ – Martin York Apr 7 '13 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.