Найти число ребер и выполнить топографическую сортировку в моей реализации графа
Я работал над реализацией графа в течение последних нескольких дней. Все это действительно ново для меня, и я застрял на двух частях моей реализации. Я реализую диграф курсов из входного файла. Из файла я могу определить, какие курсы являются предварительными для других курсов. Затем я создаю орграф с курсами в виде узлов и ребер, соединяющих курсы, которые являются предварительными требованиями. Я также хочу найти общее количество узлов и ребер и выполнить топологическую сортировку на графике (позже я добавлю веса к ребрам). Вот моя реализация.
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);
}
Найти количество узлов было просто, просто верните work.size, Я подтвердил, что это работает правильно. Я заблудился о том, как бы вернуть количество ребер в моем графике. Кажется, все будет просто, но все, что я пробовал, не работает. Во-вторых, я совершенно заблудился о том, как выполнить топологическую сортировку на этом графике. Любая помощь приветствуется.
Решение
Во-первых, для количества ребер было бы проще подсчитать их непосредственно при построении графика (просто добавьте счетчик в свой класс Digraph и увеличивайте его каждый раз, когда добавляете ребро…)
Для топологической сортировки сначала у меня есть вопрос: ваши ребра от предварительных требований до зависимых курсов? То есть у вас есть ссылка A -> B, если A является обязательным условием B? Если это не так, вам нужно инвертировать ваш график
Вы в основном алгоритм для построения топологической сортировки: один на основе простой DFS (http://en.wikipedia.org/wiki/Depth-first_search) а другой полагается на градусы (http://en.wikipedia.org/wiki/Directed_graph#Indegree_and_outdegree) из ваших вершин (курсы в вашем случае.)
Обычно вам нужно убедиться, что ваш график не содержит циклов, что обычно бывает, если ваши данные согласованы.
Давайте рассмотрим алгоритм, основанный на DFS: DFS пересекает каждую вершину от заданного корня после ребер по мере их появления. Легко доказать, что порядок последнего столкновения вершины образует обратный топологический порядок. Итак, все, что нам нужно, это вставить в стек текущую вершину после вызова ее преемников.
Я сделал быструю и грязную реализацию для вас, снова используя 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), это может быть derecursified используя стек, содержащий родителя целевой вершины и итератор для текущего преемника, итератор достигает конца списка смежности, вы можете поместить родителя в топологическую сортировку.
Другой алгоритм почти такой же простой: для каждой вершины нужно посчитать количество предшественников (в-степени), что можно сделать при построении графика. Чтобы вычислить топологическую сортировку, вы ищете первую вершину с степенью 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;
}
Чтобы использовать диапазон, основанный на цикле, вам нужно использовать c ++ 11. С g ++ это было бы --std=c++11 в командной строке.
РЕДАКТИРОВАТЬ:
Я только что понял, что у вас есть ориентированный граф, и вы, вероятно, хотите посчитать один для каждого направления. В таком случае: не делите на два!
int Digraph::getNumEdges(){
int count = 0;
for (const auto & v : work) {
count += v.second->adjacency.size();
}
return count;
}