Важность постановки задачи
Неясно, что подсчитывается.
- Установлен ли начальный узел все узлы, для которых имеется хотя бы один исходящий фронт, или есть определенные критерии начального узла?
- Является ли конечный узел набором всех узлов, для которых имеются нулевые исходящие ребра, или может ли любой узел, для которого есть хотя бы один входящий ребро, быть возможным конечным узлом?
Определите вашу проблему, чтобы не было двусмысленности.
Оценка
Оценки могут быть отклонены на порядки, если они рассчитаны для произвольно построенных ориентированных графов, и граф является очень статистически искаженным или систематическим по своей конструкции. Это типично для всех процессов оценки, но особенно ярко выражено на графиках из-за их потенциальной сложности экспоненциальной структуры.
Два оптимизирующих пункта
Модель std :: bitset будет медленнее, чем значения bool для большинства архитектур процессоров, из-за механики набора команд для тестирования бита с определенным смещением бита. Набор битов более полезен, когда объем памяти, а не скорость, является критическим фактором.
Важно исключить случаи или уменьшить с помощью вычетов. Например, если есть узлы, для которых имеется только один исходящий фронт, можно рассчитать количество путей без него и добавить к числу путей в подграфе количество путей от узла, на который он указывает.
Использование кластеров
Проблема может быть выполнена в кластере путем распределения по начальному узлу. Некоторые проблемы просто требуют суперкомпьютеров. Если у вас есть 1 000 000 начальных узлов и 10 процессоров, вы можете разместить 100 000 начальных узлов на каждом процессоре. Вышеупомянутые исключения и сокращения случая должны быть сделаны до распределения случаев.
Типичная первая глубина рекурсии и как ее оптимизировать
Вот небольшая программа, которая сначала обеспечивает базовую глубину, ациклический обход от любого узла к любому узлу, который можно изменить, поместить в цикл или распределить. Список можно поместить в статический собственный массив, используя шаблон с размером в качестве одного параметра, если известен максимальный размер набора данных, что сокращает время итерации и индексации.
#include <iostream>
#include <list>
class DirectedGraph {
private:
int miNodes;
std::list<int> * mnpEdges;
bool * mpVisitedFlags;
private:
void initAlreadyVisited() {
for (int i = 0; i < miNodes; ++ i)
mpVisitedFlags[i] = false;
}
void recurse(int iCurrent, int iDestination,
int path[], int index,
std::list<std::list<int> *> * pnai) {
mpVisitedFlags[iCurrent] = true;
path[index ++] = iCurrent;
if (iCurrent == iDestination) {
auto pni = new std::list<int>;
for (int i = 0; i < index; ++ i)
pni->push_back(path[i]);
pnai->push_back(pni);
} else {
auto it = mnpEdges[iCurrent].begin();
auto itBeyond = mnpEdges[iCurrent].end();
while (it != itBeyond) {
if (! mpVisitedFlags[* it])
recurse(* it, iDestination,
path, index, pnai);
++ it;
}
}
-- index;
mpVisitedFlags[iCurrent] = false;
}
public:
DirectedGraph(int iNodes) {
miNodes = iNodes;
mnpEdges = new std::list<int>[iNodes];
mpVisitedFlags = new bool[iNodes];
}
~DirectedGraph() {
delete mpVisitedFlags;
}
void addEdge(int u, int v) {
mnpEdges[u].push_back(v);
}
std::list<std::list<int> *> * findPaths(int iStart,
int iDestination) {
initAlreadyVisited();
auto path = new int[miNodes];
auto pnpi = new std::list<std::list<int> *>();
recurse(iStart, iDestination, path, 0, pnpi);
delete path;
return pnpi;
}
};
int main() {
DirectedGraph dg(5);
dg.addEdge(0, 1);
dg.addEdge(0, 2);
dg.addEdge(0, 3);
dg.addEdge(1, 3);
dg.addEdge(1, 4);
dg.addEdge(2, 0);
dg.addEdge(2, 1);
dg.addEdge(4, 1);
dg.addEdge(4, 3);
int startingNode = 0;
int destinationNode = 1;
auto pnai = dg.findPaths(startingNode, destinationNode);
std::cout
<< "Unique paths from "
<< startingNode
<< " to "
<< destinationNode
<< std::endl
<< std::endl;
bool bFirst;
std::list<int> * pi;
auto it = pnai->begin();
auto itBeyond = pnai->end();
std::list<int>::iterator itInner;
std::list<int>::iterator itInnerBeyond;
while (it != itBeyond) {
bFirst = true;
pi = * it ++;
itInner = pi->begin();
itInnerBeyond = pi->end();
while (itInner != itInnerBeyond) {
if (bFirst)
bFirst = false;
else
std::cout << ' ';
std::cout << (* itInner ++);
}
std::cout << std::endl;
delete pi;
}
delete pnai;
return 0;
}