Finding the number of edges and performing a topo sort in my graph implementation

Question

I have been working on a graph implementation for the last few days. All of this is really new to me, and I am stuck on two parts of my implementation. I am implementing a digraph of courses from an input file. From the file, I can determine which courses are prereqs for other courses. I then create a digraph with courses as nodes, and edges connecting courses that are prereqs. I also want to find the total number of nodes and edges, and perform a topological sort on the graph (I will later be adding weights to the edges). Here is my implementation.

Digraph.h

class vertex{
public:

    typedef std::pair<int, vertex*> ve;
    std::vector<ve> adjacency;
    std::string course;
    vertex(std::string c){
        course = c;
    }
};

class Digraph{
public:
    void addVertex(std::string&);
    void addEdge(std::string& from, std::string& to, int cost);
    typedef std::map<std::string, vertex *> vmap;
    vmap work;
    int getNumVertices();
    int getNumEdges();
    void getTopoSort(); 

};

Digraph.cpp

void Digraph::addVertex(std::string& course){
    vmap::iterator iter = work.begin();
    iter = work.find(course);
    if(iter == work.end()){
        vertex *v;
        v = new vertex(course);
        work[course] = v;
        return;
    }
}

void Digraph::addEdge(std::string& from, std::string& to, int cost){
    vertex *f = (work.find(from)->second);
    vertex *t = (work.find(to)->second);
    std::pair<int, vertex *> edge = std::make_pair(cost, t);
    f->adjacency.push_back(edge);
}

Finding the number of nodes was easy just return work.size. I have confirmed this is working properly. I am lost on how I would return the number of edges in my graph. It seems it would be simple, but everything I tried doesn't work. Secondly, I am completely lost on how to perform a topological sort on this graph. Any assistance is appreciated.

Answer 1

First, for the number of edges, it would be simpler to count them directly when you build the graph (just add a counter in your Digraph class and increment it each time you add an edge … )

For the topological sort, first I have a question: your edges are from prereqs to dependant courses ? That is you have a link A -> B if A is a prereq of B ? If this not the case, you need to invert your graph.

You to main algorithm in order to build a topological sort: one based on a simple DFS (http://en.wikipedia.org/wiki/Depth-first_search) and the other relying on in-degrees (http://en.wikipedia.org/wiki/Directed_graph#Indegree_and_outdegree) of your vertices (courses in your case.)

Normally, you need to verify that your graph doesn't contain any cycle, which will normally be the case if your data are coherent.

Let's consider the DFS based algorithm: a DFS traverses each vertices from a given root following edges as they appear. We can easily prove that order of last encounter of a vertex forms a reverse topological order. So, all we need is to push in a stack the current vertex after the calls on its successors.

I made a quick and dirty implementation for you, using C++11 again.

First, add the following to the Digraph class:

  typedef std::unordered_set<vertex*> marks_set;
  marks_set marks;
  typedef std::deque<vertex*> stack;
  stack topo;
  void dfs(vertex* vcur);

Then here comes the code:

void Digraph::dfs(vertex* vcur) {
  marks.insert(vcur);
  for (const auto & adj : vcur->adjacency) {
    vertex* suc = adj.second;
    if (marks.find(suc) == marks.end()) {
      this->dfs(suc);
    } // you can detect cycle in the else statement
  }
  topo.push_back(vcur);
}

void Digraph::getTopoSort() {
  // It should be a good idea to separate this algorithm from the graph itself
  // You probably don't want the inner state of it in your graph,
  // but that's your part.

  // Be sure marks and topo are empty
  marks.clear();
  topo.clear();
  // Run the DFS on all connected components
  for (const auto & v : work) {
    if (marks.find(v.second) == marks.end()) {
      this->dfs(v.second);
    }
  }
  // Display it
  for (const auto v : topo) {
    std::cout << v->course << "\n";
  }
}

The code compiles but I haven't tested. If for any reasons you have an issue with the recursive algorithm (the function Digraph::dfs), it can be derecursified using a stack containing the parent of the target vertex and the iterator to the current successor, the iterator reach the end of the adjacency list, you can push the parent in the topological sort.

The other algorithm is almost as simple: for each vertices you need to count the number of predecessor (in-degree) which can be done while building the graph. In order to compute the topological sort, you look for the first vertex with a in-degree of 0 (no predecessor), you then decrease the in-degree of all its successors and continue with the next vertex with 0. If the graph has no cycle, there will always be a vertex with a in-degree of 0 (at beginning of course, but also during the algorithm run as you decrease it) until all vertices have been seen. The order of vertices encounter form a topological sort (this is related to the Bellman shortest-path algorithm.)

Note that these 2 algorithms are listed here: http://en.wikipedia.org/wiki/Topological_sorting. The one using in-degree is described in terms of removing edges which we simply simulate by decreasing the in-degree (a far less destructive approach … )

Answer 2

A simple way would be to iterate through all vertices in your graph, add up their neighbor counts and then divide by two:

int Digraph::getNumEdges(){
     int count = 0;
     for (const auto & v : work) {
         count += v.second->adjacency.size();
     }
     return count / 2;
}

To use the range based for loop, you need to use c++11. With g++ that would be --std=c++11 on the command line.

EDIT: I just realized you have a directed graph, and you probably want to count one for each direction. In such case: don't divide by two!

int Digraph::getNumEdges(){
     int count = 0;
     for (const auto & v : work) {
         count += v.second->adjacency.size();
     }
     return count;
}