Нахождение количества ребер и выполнение топографической сортировки в моей реализации графа

Во-первых, для количества ребер было бы проще подсчитать их непосредственно при построении графа (просто добавьте счетчик в свой класс Digraph и увеличивайте его каждый раз, когда добавляете ребро…)

Для топологической сортировки сначала у меня есть вопрос: ваши ребра от предварительных требований к зависимым курсам? То есть у вас есть ссылка A -> B, если A является предпосылкой B? Если это не так, вам нужно инвертировать график.

Обратитесь к основному алгоритму, чтобы построить топологическую сортировку: основанную на простой DFS (http://en.wikipedia.org/wiki/Depth-first_search), а другой опирается на входящие степени (http://en.wikipedia.org/wiki/Directed_graph#Indegree_and_outdegree) ваших вершин (курсов в вашем случае).

Обычно вам нужно убедиться, что ваш график не содержит циклов, что обычно происходит, если ваши данные непротиворечивы.

Давайте рассмотрим алгоритм, основанный на поиске в глубину: поиск в глубину обходит каждую вершину из заданного корня по ребрам по мере их появления. Мы можем легко доказать, что порядок последней встречи вершины образует обратный топологический порядок. Итак, все, что нам нужно, это запихнуть в стек текущую вершину после вызовов ее преемников.

Я сделал для вас быструю и грязную реализацию, снова используя C++11.

Во-первых, добавьте в класс Digraph следующее:

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

Затем идет код:

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";
  }
}

Код компилируется, но я не проверял. Если по каким-либо причинам у вас возникла проблема с рекурсивным алгоритмом (функция Digraph::dfs), его можно декурсифицировать с помощью стека, содержащего родительскую вершину целевой вершины и итератор текущего преемника, итератор достигает конца списка смежности, вы можете поместить родителя в топологическую сортировку.

Другой алгоритм почти так же прост: для каждой вершины нужно подсчитать количество предшественников (в степени), что можно сделать при построении графа. Чтобы вычислить топологическую сортировку, вы ищете первую вершину со степенью входа 0 (без предшествующей), затем вы уменьшаете степень входа всех ее последователей и переходите к следующей вершине с 0. Если граф имеет нет цикла, всегда будет вершина со степенью входа 0 (в начале, конечно, но также во время работы алгоритма по мере ее уменьшения), пока все вершины не будут просмотрены. Порядок встречи вершин образует топологическую сортировку (это связано с алгоритмом кратчайшего пути Беллмана).

Обратите внимание, что эти 2 алгоритма перечислены здесь: http://en.wikipedia.org/wiki/Topological_sorting. Тот, который использует степень входа, описывается в терминах удаления ребер, которые мы просто моделируем, уменьшая степень входа (гораздо менее деструктивный подход…)

Простым способом было бы перебрать все вершины в вашем графе, сложить количество их соседей, а затем разделить на два:

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

Чтобы использовать диапазон, основанный на цикле for, вам нужно использовать С++ 11. С g++ это будет --std=c++11 в командной строке.

EDIT: я только что понял, что у вас есть ориентированный граф, и вы, вероятно, хотите посчитать по одному для каждого направления. В таком случае: не делите на два!

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