5
\$\begingroup\$

Please review the implementation of Kruskal 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();
};

Kruskal's Implementation:

class CompareEdge {
public:
    bool operator() (const boost::shared_ptr<Edge> & e1, const boost::shared_ptr<Edge> & e2) const{
        if(e1->cost == e2->cost)
            return e1.get() < e2.get();  //similar to default comparator less<T>

        return e1->cost < e2->cost;
    }
};

typedef std::map<boost::shared_ptr<Vertex>, boost::shared_ptr<Vertex>> ParentMap;

// A utility function to find the subset of an element i
boost::shared_ptr<Vertex> find(const ParentMap& parentMap, const boost::shared_ptr<Vertex>& vertex)
{
    ParentMap::const_iterator iter = parentMap.find(vertex);
    if (!(iter->second).get())
        return vertex;
    return find(parentMap, iter->second);
}

// A utility function to do union of two subsets 
void Union(ParentMap& parentMap, const boost::shared_ptr<Vertex>& x, const boost::shared_ptr<Vertex>& y)
{
    const boost::shared_ptr<Vertex> xset = find(parentMap, x);
    const boost::shared_ptr<Vertex> yset = find(parentMap, y);
    parentMap[x] = y;
}


// The main function to check whether a given graph contains cycle or not
bool isCycle(const VerticesList& verticesList, const EdgeList& allEdgeList)
{
    // Allocate memory for creating V subsets
    ParentMap parent;

    for(boost::shared_ptr<Vertex> vertex : verticesList) {
        parent.insert(std::make_pair(vertex, nullptr));
    }

    // Iterate through all edges of graph, find subset of both
    // vertices of every edge, if both subsets are same, then there is
    // cycle in graph.
    for(boost::shared_ptr<Edge> edge : allEdgeList)
    {
        boost::shared_ptr<Vertex> x = find(parent, (edge->srcVertex).lock());
        boost::shared_ptr<Vertex> y = find(parent, (edge->dstVertex).lock());

        if (x.get() == y.get())
            return true;

        Union(parent, x, y);
    }
    return false;
}

void Graph::kruskalMST() {
    //set to hold all edges in increasing order of edge cost
    std::set<boost::shared_ptr<Edge>, CompareEdge> allEdgeList;
    for(boost::shared_ptr<Vertex> vertex : _verticesList) {
        EdgeList& vertexEdgeList = vertex->edgeList;
        allEdgeList.insert(vertexEdgeList.begin(), vertexEdgeList.end());
    }

    EdgeList mstEdgeList;
    for(boost::shared_ptr<Edge> edge : allEdgeList) {
        if(mstEdgeList.size() == _verticesList.size() - 1) break;
        mstEdgeList.push_front(edge);
        if(isCycle(_verticesList, mstEdgeList)) {
            //Remove the edge from MST
            mstEdgeList.pop_front();
        }
    }

    // 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\$
  • Since Vertex just has public members, it can just be a struct.

    In addition, you don't need to set bVisited to false in two places. It just needs to be done in the constructor. You could also make it an initializer list instead, which is more proper when setting default values for data members.

  • In Graph, you can omit both the constructor and destructor if you're not overriding them. But if you need to keep the constructor anyway, then use C++11's default constructor`.

    Graph() = default;
    
  • With C++11, you can replace typedefs:

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

    with type aliases:

    using VerticesList = std::list<boost::shared_ptr<Vertex>>;
    using DataVertexMap = std::map<int, VerticesList::const_iterator>;
    
\$\endgroup\$

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.