T
Hat eine Weile gedauert, bis ich es hinbekommen habe. Mir scheint das Programm nun halbwegs debugged zu sein. Beim vereinen zweier Pfade bin ich nicht die 'visited'-flags entlanggelaufen, sondern habe mich fuer deren 'inner_product' entschieden, weil ich so auch Pfade wie 0-1-5 und 0-3-5 zu 5-1-0-3 vereinen kann (siehe Kommentare im Text). Falls sich jemand die Muehe machen moechte, den Code anzuschauen, habe ich gegen Kommentare nichts auszusetzen Jetzt muss ich dass allerdings erst auf mein eigentliches Problem anpassen und dort sehen, ob nicht doch die Befuerchtung von jester@loggedoff zutrifft und das ganze einfach zu gross und aufwendig wird. Dann werde ich die Wege noch 'vorsieben' muessen.
Fuer den Code moechte ich mich entschuldigen, die Benennung der Variablen und Funktionen ist weder kreativ noch konsistent. Ob mit oder ohne Kommentare: vielen Dank fuer Eure Unterstuetzung.
#include <vector>
#include <list>
#include <iostream>
#include <numeric>
const int numNodes = 8;
const char graph[numNodes*numNodes] = {
0, 1, 1, 1, 0, 0, 0, 0,
1, 0, 0, 0, 1, 1, 0, 0,
1, 0, 0, 0, 0, 1, 1, 0,
1, 0, 0, 0, 0, 1, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
};
/*
const char graph[numNodes*numNodes] = {
0, 1, 0, 1, 0,
1, 0, 0, 0, 1,
0, 0, 0, 0, 0,
1, 0, 0, 0, 1,
0, 1, 0, 1, 0
};
*/
struct Path {
std::list<int> nodes;
std::vector<char> visited;
};
std::vector<Path> paths;
/* merge to paths */
Path conditionalMerge(const Path& weg1, const Path& weg2);
/* print nodes and 'visited' flags of a path */
void printPath(const Path& weg);
/* recursion through graph */
int einSchrittTiefer (Path weg)
{
int current = weg.nodes.back();
std::vector<int> stack;
std::vector<int>::const_iterator it ;
/* collect children of current last node in 'weg' */
for (int i = 0; i < numNodes; ++i)
{
if ( graph [ i + current*numNodes ] && ! weg.visited[i] )
stack.push_back(i);
}
/* is this a leaf? Then finish recursion */
if (stack.empty()) {
paths.push_back(weg);
return 0;
}
/* otherwise recursively check child nodes */
else {
for (it = stack.begin(); it != stack.end(); ++it)
{
int node = *it;
/* add node to current path and flag as used */
weg.nodes.push_back(node);
weg.visited[node] = 1;
/* recursion */
einSchrittTiefer(weg);
/* once finish release node back into pool */
weg.nodes.pop_back();
weg.visited[node] = 0;
}
}
return -1;
}
int main()
{
std::vector<Path>::iterator it1, it2;
int root = 0;
Path weg;
weg.visited = std::vector<char> (numNodes, 0);
weg.nodes.push_back(root);
weg.visited[root] = 1;
std::vector<Path> alleWege;
std::vector<Path>::const_iterator it;
einSchrittTiefer(weg);
for (it = paths.begin(); it != paths.end(); ++it)
{
std::cout << "Path Number " << it - paths.begin() << ": ";
printPath(*it);
}
/* For merging set flag of initial node to 0 */
std::cout << "---> Merging paths.\n";
for (it1 = paths.begin(); it1 != paths.end(); ++it1)
{
for (it2 = paths.begin(); it2 != paths.end(); ++it2)
{
if (it1 == it2) continue;
alleWege.push_back(conditionalMerge(*it1, *it2));
}
}
for(it = alleWege.begin(); it != alleWege.end(); ++it)
{
if (it->nodes.empty()) continue;
std::cout << "Path Nummer " << it-alleWege.begin() << ": ";
printPath(*it);
}
return 0;
}
Path conditionalMerge(const Path& weg1, const Path& weg2)
{
Path joint (weg1);
int check;
check = std::inner_product(weg1.visited.begin(), weg1.visited.end(), weg2.visited.begin(), 0);
/* possibilities of inner product:
* = 1: only root-node in common -> merge
* > 2: more than two nodes in common -> do not merge
* = 2: if last nodes are the same: remove from joint and merge, otherwise:
* do not merge.
*/
if (check > 2) return Path();
if (check == 2) {
if (weg1.nodes.back() != weg2.nodes.back())
/* common node which is not the end-point */
return Path();
else (joint.nodes.pop_back());
}
/* if the last node is the same, remove that one, too */
joint.nodes.reverse();
joint.nodes.pop_back();
joint.nodes.insert(joint.nodes.end(), weg2.nodes.begin(), weg2.nodes.end());
/* printing result for debugging */
std::cout << "Merging ";
printPath(weg1);
std::cout << " and ";
printPath(weg2);
std::cout << "Result: ";
printPath(joint);
return joint;
}
void printPath(const Path& weg)
{
std::list<int>::const_iterator itw;
std::vector<char>::const_iterator itf;
std::cout << "- Nodes: ";
for(itw = weg.nodes.begin(); itw != weg.nodes.end(); ++itw)
{
std::cout << *itw << " ";
}
std::cout << "- Flags: ";
for (itf = weg.visited.begin(); itf != weg.visited.end(); ++itf)
{
std::cout << int(*itf) << " ";
}
std::cout << std::endl;
}
P.S.: Mir ist bewusst, dass die 'visited'-flags nach dem Mergen nicht mehr stimmen. Muss mir erst noch ueberlegen, ob ich die danach noch benoetige, bevor ich das korrigiere.
