Ketten in Graph

tim_g

Hallo,
ich suche einen Algorithmus, der mir alle alle Ketten in einem Graph berechnet, die ein bestimmtes Element enthalten.
ausgehend von n Elementen A_i baue ich mir eine (symmetrische) n x n -Matrix M , bei der ein Eintrag 1 bei M[t]ij[/t] bedeutet, dass A[t]i[/t] und A[t]j[/t] verbunden sind.
Ich suche nun einen Algorithmus, der mir alle Ketten liefert, die ein bestimmtes Element A[t]r[/t] enthaelt, wobei eine Kette kein Element doppelt enthalten darf.
Selbst per "brute-force" wuesste ich nicht, wie ich das (in C++) implementieren muesste, von daher hoffe ich auf Hinweise, welche Algorithmen ich dazu benutzen muss.

Wie extrahiere ich aus M die Untermatrix, die den zusammenhaengenden Graphen darstellt, der A[t]r[/t] enthaelt? Ist das ueberhaupt erstmal der richtige Ansatz?
Wenn ich den mit A[t]r[/t] zusammenhaengenden Graphen habe, wie finde ich dann eine Kette (ist "Kette" ueberhaupt die graphentheoretisch korrekte Bezeichnung?)?
Wie kann ich dann alle Ketten finden, die A[t]r[/t] enthalten?
Ich habe nur rudimentaere Kenntnisse ueber Graphen - sollten diese Fragen banal sein, wuerde ich mit ueber einen Hinweis auf ein Buch oder Skript oder auch die richtigen Stichworte, mit denen ich bei google mehr Glueck habe, freuen.

Christoph

tim_g schrieb:

ist "Kette" ueberhaupt die graphentheoretisch korrekte Bezeichnung?

Nein, der Begriff ist mir zumindest nicht bekannnt. Könntest du kurz definieren, was eine "Kette" ist?

edit: Interessant wär auch zu wissen, ob dein Graph gerichtet oder ungerichtet ist. Momentan klingt es nach einem gerichtetem Graphen, ist das richtig? Ich frage, weil "zusammenhängender Graph" bei gerichteten Graphen wieder anders definiert ist als bei ungerichteten. Bei gerichteten Graphen gibt es "stark zusammenhängend" und "schwach zusammenhängend".

volkard

Nur so eine Idee:

Ich würde sagen, du verfolgst per Tiefensuche von A[t]r[/t] aus alle Wege, die mit A[t]r[/t] beginnen und kein Element doppelt haben. Dazu ein Bitfeld mit n Bits mitführen, was schon besucht wurde.

struct Weg
{
   vector<int> weg;
   vector<bool> schonBesucht;
   ...
}
vector<Weg> alleWegeVonArAus;

Ich denke, der Zeitbedarf ist dafür minimal (im Sinne von schbneller gehts nicht).
Dann

foreach w1 in alleWegeVonArAus
   foreach w2 in alleWegeVonArAus
      if((w1.schonBesucht & w2.schonbesucht)==nix)
      ergebnis.hängeZweiWegeAneinander(w1,reverse(w2))

volkard

Christoph schrieb:

tim_g schrieb:

ist "Kette" ueberhaupt die graphentheoretisch korrekte Bezeichnung?

Nein, der Begriff ist mir zumindest nicht bekannnt. Könntest du kurz definieren, was eine "Kette" ist?

Eigentlich kenne ich Ketten als
http://de.wikipedia.org/wiki/Ordnungsrelation

Aber als
http://home.f1.fhtw-berlin.de/scheibl/algor/index.htm?./Graph/Theorie.htm
kann ich sie auch essen.

tim_g

Christoph schrieb:

Nein, der Begriff ist mir zumindest nicht bekannnt. Könntest du kurz definieren, was eine "Kette" ist?

"Weg" ist das richtige Wort, wie ich mittlerweile herausgefunden habe. Nein, der Graph ist ungerichtet. Steckt das nicht darin, dass M symmetrisch ist?

tim_g

volkard schrieb:

Nur so eine Idee:

Ich würde sagen, du verfolgst per Tiefensuche von A[t]r[/t] aus alle Wege, die mit A[t]r[/t] beginnen und kein Element doppelt haben. Dazu ein Bitfeld mit n Bits mitführen, was schon besucht wurde.

A[t]r[/t] darf auch mitten im Weg liegen, ich moechte also quasi in "zwei Richtungen" von A aus laufen. Aber ich muss mir Deinen Vorschlag noch anschauen, ob er nicht vielleicht trotzdem gueltig ist.

volkard

tim_g schrieb:

volkard schrieb:

Nur so eine Idee:

Ich würde sagen, du verfolgst per Tiefensuche von A[t]r[/t] aus alle Wege, die mit A[t]r[/t] beginnen und kein Element doppelt haben. Dazu ein Bitfeld mit n Bits mitführen, was schon besucht wurde.

A[t]r[/t] darf auch mitten im Weg liegen, ich moechte also quasi in "zwei Richtungen" von A aus laufen.

Deswegen das

ergebnis.hängeZweiWegeAneinander(w1,reverse(w2))

, was ich zugegebenermaßen jetzt erst reineditier habe.

tim_g

Ja, ich verstehe die Idee, das muesste klappen. Dann lese ich mich bei Wikipedia mal in Tiefensuche ein.
Danke erstmal!
Gibt es einen tatsaechlichen Operator oder eine Abkuerzung fuer den "&" Operator in "schonBesucht" in C++ zum Vergleichen zweier bool-Vektoren, oder gehe ich vergleiche ich sie einfach paarweise? (Zumindest beschwert sich mein g++ darueber).

volkard

tim_g schrieb:

Ja, ich verstehe die Idee, das muesste klappen. Dann lese ich mich bei Wikipedia mal in Tiefensuche ein.
Danke erstmal!

Bitte berichte dann, wie es gelaufen ist!

tim_g schrieb:

Gibt es einen tatsaechlichen Operator oder eine Abkuerzung fuer den "&" Operator in "schonBesucht" in C++ zum Vergleichen zweier bool-Vektoren, oder gehe ich vergleiche ich sie einfach paarweise? (Zumindest beschwert sich mein g++ darueber).

Das gibt es alles nicht. Ich wollte mir nicht die Mühe machen, es auszuprogrammieren. Und vector<bool> würde ich da auch nie verwenden, sondern vector<char>. Oder einen selbergebauten, wo ich "&" noch schneller implementiere. Aber das dürfte alles egal sein, wenn ich recht abschätze, sind die Kosten für operator new in diesem Programm viel größer als alles andere, soll heißen, für jedes Ergebnis zahlst Du 200 Takte für das Speicher-Besorgen (bei nur 1GHz immerhin 5Mio/Sekunde), die Vergleiche und so gehen da auch bei schäbiger Implementierung vermutlich unter.

tim_g

Ich wuerde spontan an einen int schonBesucht denken, den ich beim Ablaufen von Knoten i mit

if ( 1<<i & schonBesucht ) /* naechster, ist schon im Weg */
else {
schonBesucht += 1<<i;
/* i in Weg aufnehmen */
}

hochsetzen wuerde - dann kann ich tatsaechlich "&" benutzen. Gibt es Gruende, das nicht so zu machen, wie z.B. evtl. Fehlerquellen?

volkard

tim_g schrieb:

Ich wuerde spontan an einen int schonBesucht denken, den ich beim Ablaufen von Knoten i mit
if ( 1<<i & schonBesucht ) /* naechster, ist schon im Weg */
else {
schonBesucht += 1<<i;
/* i in Weg aufnehmen */
}
hochsetzen wuerde - dann kann ich tatsaechlich "&" benutzen. Gibt es Gruende, das nicht so zu machen, wie z.B. evtl. Fehlerquellen?

Nur die Beschränkung auf nur 32 Knoten im Graphen. Willst Du die Beschränkung haben?

hast du eine bestimmte anwendung im sinn? im allgemeinen gibt es nämlich furchtbar viele solche wege. wenn du also nicht so wichtige ausschliessen kannst wuerde das enorm helfen.

tim_g

@volkard: stimmt, dass es dann nur 32 Knoten sein koennen, habe ich nicht bedacht. Weswegen wuerdest Du eher einen vector aus char und nicht aus bool nehmen? Ist das schneller?
@jester@loggedoff:
Die Zahl der Knoten koennte schon relativ hoch werden, allerdings denke ich, durch eine Vorauswahl die Anzahl der Kanten eher klein halten zu koennen. Falls das an seine Grenze stoesst, werde ich nochmal drueber nachdenken, aber im Moment muesste es so gehen.

volkard

tim_g schrieb:

@volkard: stimmt, dass es dann nur 32 Knoten sein koennen, habe ich nicht bedacht. Weswegen wuerdest Du eher einen vector aus char und nicht aus bool nehmen? Ist das schneller?

Ja. vector<bool> ist kein echter vector, sondern ein Ding, das sich nur so ähnlich wie ein vector anfühlt, aber innendrin keine echten bools verwaltet, sondern speichereffizient nur ein Bit pro "bool" benutzt. Das Umrechnen und shiften immer kostet eine winzige Kleinigkeit.

tim_g

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.