3
\$\begingroup\$

Please review the implementation of Prim algorithm. Points on which I have doubt:

  1. My Graph doesn't have any ID for nodes. Nodes are accessed based on their data. Is there any general approach in that? Should nodes be referenced by an ID as that will also make these algo somewhat easier to implement by using id as index into arrays.

  2. With current graph representation, are there any issue in the algo implementation?

  3. Are there any issues in method of accessing vertex and edges shared_ptr? Should weak_ptr be used at some places? Any shared_ptr validity issue?

  4. Anything that you can suggest to improve will be helpful.

Vertex:

class Vertex {
public:
    Vertex() {
        bVisited = false;
    }
    int data = 0;
    EdgeList edgeList;
    bool bVisited = false; 
};

Edge:

struct Edge {
    int cost;
    boost::weak_ptr<Vertex> srcVertex;
    boost::weak_ptr<Vertex> dstVertex;
};

Graph:

typedef std::list<boost::shared_ptr<Vertex>> VerticesList;
typedef std::map<int, VerticesList::const_iterator> DataVertexMap;
class Graph {

    VerticesList _verticesList;
    DataVertexMap _dataVertexMap;

    //TODO: Need some design to have this function internal only and not exposed to client
    boost::shared_ptr<Vertex> addAndGetVertex(int data);
public:
    Graph();
    ~Graph();

    bool isEmpty() const;
    //We don't check for duplicate vertex
    void addVertex(int data);
    void addEdge(int srcData, int dstData, int cost);
    int getCostForEdge(int srcData, int dstData);
    void displayGraph();
    void dfsTraversal();
    void bfsTraversal();

    void findShortestPath(int srcData, int dstData);
    void kruskalMST();
    void primMST();
};

Prim's implementation:

 //return min cost edge
 boost::shared_ptr<Edge> getMinEdge(const EdgeList& edgeList) {
    int min = INFINITY;
    boost::shared_ptr<Edge> minEdge;
    for(boost::shared_ptr<Edge> edge : edgeList) {
        if(edge->cost < min) {
            min = edge->cost;
            minEdge = edge;
        }
    }

    return minEdge;
}

void Graph::primMST() {
    EdgeList mstEdgeList;
    EdgeList potentialEdgeList;

    //insert edges for first vertex 
    boost::shared_ptr<Vertex> firstVertex = _verticesList.front();
    potentialEdgeList.insert(potentialEdgeList.begin(), firstVertex->edgeList.begin(), firstVertex->edgeList.end());

    while(mstEdgeList.size() < _verticesList.size() - 1) {
        boost::shared_ptr<Edge> minEdge = getMinEdge(potentialEdgeList);
        mstEdgeList.push_front(minEdge);
        potentialEdgeList.remove(minEdge);
        //Mark the vertices visited so that edge having them as destination are not again included
        (minEdge->srcVertex).lock()->bVisited = true;
        (minEdge->dstVertex).lock()->bVisited = true;
        EdgeList& dstVertexEdgeList = (minEdge->dstVertex).lock()->edgeList;
        for(boost::shared_ptr<Edge> edge : dstVertexEdgeList) {
            if(!(edge->dstVertex).lock()->bVisited)
                potentialEdgeList.push_front(edge);
        }
    }

    //TODO: set all bVisited false

    // print the contents of result[] to display the built MST
    printf("Following are the edges in the constructed MST\n");
    for (boost::shared_ptr<Edge> edge : mstEdgeList)
        printf("%d -- %d == %d\n", (edge->srcVertex).lock()->data, (edge->dstVertex).lock()->data,
               edge->cost);
    return;
}
\$\endgroup\$
3
\$\begingroup\$

I try some review, although I don't know the Prim algorithm until now, so there are mostly general things here. Hope it is helpful nevertheless. The following points are in random order:


Regarding the language:

  • In your Vertex() {} class, you can omit the bVisited = false; as it is already initialized in the declaration. Otherwise, it's better to use an initializer list, Vertex() : bVisited(false) {}.

  • In C++11 (which you tagged) I would rather use the standard-library smart pointers and not the boost stuff. So, I would add an #include<memory> and replace all boost:: namespaces by std::.

  • Your function getMinEdge can be replaced by an single-line STL algorithm:

    auto getMinEdge(const EdgeList& edgeList) -> boost::shared_ptr<Edge>
    {
        return *std::min_element(edgeList.begin(),edgeList.end()
                               , [](boost::shared_ptr<Edge> const& a
                                  , boost::shared_ptr<Edge> const& b)
                                   { return a->cost < b->cost; });
    }
    
  • When using range-based for loops

     for(boost::shared_ptr<Edge> edge : dstVertexEdgeList) 
    

    I would rather use auto instead of explicitly stating the type. Moreover, as copying a shared_ptr is not an unexpensive operation (as the memory manager must increase its reference count), here I would use auto& or better auto const& and pass the shared_ptr by reference.

    The same holds for statements like boost::shared_ptr<Edge> minEdge = getMinEdge(potentialEdgeList); or EdgeList& dstVertexEdgeList = (minEdge->dstVertex).lock()->edgeList;. Better use auto or auto&, resp.


Regarding the design:

  • Regarding the storage scheme: The std::list<std::shared_ptr<Vertex> > you chose is probably the safest option, but probably also not the most performant. As an alternative you could for instance use std::shared_ptr<std::list<Vertex> >. It's rather fast and advantageous imo if vertices are more or less constant, such that you do not make changes in copies of the class -- because these would affect the original list. Further I would also consider whether a simple std::list<Vertex> is sufficient for you, as that is surely the easiest choice (--then you could then forget about all the smart-pointer stuff). Much here depends on the size of the pointed-to objects. The smaller they are, probably the less appropriate is the overhead of a shared_ptr.

    The same holds for EdgeList. Here, you seem to make some copies and change these, such that std::shared_ptr<std::list<Edge> > doesn't make much sence (as you would change the original list). However, as edge is a rather small object, again a simple std::list could be more efficient.

    But these are fundamental design questions which affect "only" the performance. I leave them up to you and will go on with the implementation as it is.

  • Rather than a std::list, you can also consider using a std::set or a sorted std::vector (as you already using boost, the latter corresponds to a flat_set). This gives you better performance for the search (logarithmic vs. linear for a list) but an increased effort for insertion and deletion (logarithmic vs. constant for a list).

  • The weak_ptr in the Edge class is ok, though it might not exactly be what you want. At the moment it works like this: an Edge connects two vertices. If now one vertex is removed from the graph, the Edge remains, but when you want to go along it the shared_ptr from weak_ptr initialization will fail and implicitly tell you that it is a dead end. I don't know whether this is desired.

    Instead, the graph object should know that it has to automatically remove this Edge once the Vertex is destroyed. This obviously would require some corresponding logic in the Graph class. As an alternative, you could also create a closer coupling between the two classes (e.g. maybe hold an EdgeList for each vertex).

    Further, when you go for a weak_ptr and .lock() it, you must keep track that it still points to something which is alive. Otherwise, access to variables of the pointed-to class fails. If you not check for existence and simply rely on it due to your code, a raw pointer would be sufficient.


So, that's it for now, hope it helps. When I get to know the Prim algorithm itself, I'll maybe make an update.

\$\endgroup\$
  • \$\begingroup\$ Thanks. Well explained. Do you have any comment on my point 1. \$\endgroup\$ – technophile Nov 25 '14 at 17:04

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.