Găsirea căilor într-un grafic nedirecționat

Luați în considerare următorul grafic:

dummy graph

Reprezentată de următoarea structură de matrice:

$graph = array
(
    'a' => array(),
    'b' => array('a'),
    'c' => array('a', 'b'),
    'd' => array('a'),
    'e' => array('d'),
    'f' => array('a', 'b', 'c', 'd'),
    'g' => array('d'),
    'h' => array('c'),
    'i' => array('c', 'g'),
    'j' => array(),
);

Care este algoritmul cel mai eficient de a găsi căile toate (nu doar cele mai scurte) de la nodul X la nodul Y în ambele direcții fără a se repeta nodurile ? De exemplu, căile care conduc de la nodul C la nodul A sunt:

C --> A
C --> B --> A
C --> F --> A
C --> F --> B --> A
C --> F --> D --> A
C --> I --> G --> D --> A

Găsirea tuturor căilor folosind nodurile părinte ale nodului X ( A și B ) este trivial, dar am un timp foarte dificil de a traversa nodurile într-o direcție descendent/hibrid.

Poate cineva să mă ajute?


UPDATE: Following @JackManey advice, I tried to port IDDFS (Iterative Deepening Depth-First Search) based on the Wikipedia pseudo-code and this is more or less what my code looks like:

$graph = directed2Undirected($graph);

function IDDFS($root, $goal) {
    $depth = 0;

    while ($depth <= 2) {//2 is hard-coded for now
        $result = DLS($root, $goal, $depth);

        if ($result !== false) {
            return $result;
        }

        $depth++;
    }
}

function DLS($node, $goal, $depth) {
    global $graph;

    if (($depth >= 0) && ($node == $goal)) {
        return $node;
    }

    else if ($depth > 0) {
        foreach (expand($node, $graph) as $child) {
            return DLS($child, $goal, $depth - 1);
        }
    }

    else {
        return false;
    }
}

Și aici sunt funcțiile ajutoare utilizate de el:

function directed2Undirected($data) {
    foreach ($data as $key => $values) {
        foreach ($values as $value) {
            $data[$value][] = $key;
        }
    }

    return $data;
}

function expand($id, $data, $depth = 0) {
    while (--$depth >= 0) {
        $id = flatten(array_intersect_key($data, array_flip((array) $id)));
    }

    return array_unique(flatten(array_intersect_key($data, array_flip((array) $id))));
}

function flatten($data) {
    $result = array();

    if (is_array($data) === true) {
        foreach (new RecursiveIteratorIterator(new RecursiveArrayIterator($data)) as $value) {
            $result[] = $value;
        }
    }

    return $result;
}

Apelarea rezultatelor de mai sus prezintă rezultate ciudate sau incomplete:

var_dump(IDDFS('c', 'a'));//a -- only 1 path?
var_dump(IDDFS('c', 'd'));//NULL -- can't find this path?!

Cred că am trecut peste ceva din codul pseudo-cod, dar nu sunt sigur ce este.


I also tried this DFS class that was recommended in another question, although it seems to always find one path from node X to node Y, I can't get it to return all paths (demo for C -> A and C -> D).


Deoarece nu trebuie să știu calea efectivă luată, numai câte trasee există care necesită n numărul de pași pentru a ajunge de la nodul X la nodul Y, am venit cu această funcție (utilizează directed2Undirected de mai sus):

$graph = directed2Undirected($graph);

function Distance($node, $graph, $depth = 0) {
    $result = array();

    if (array_key_exists($node, $graph) === true) {
        $result = array_fill_keys(array_keys($graph), 0);

        foreach (expand($node, $graph, $depth - 1) as $child) {
            if (strcmp($node, $child) !== 0) {
                $result[$child] += $depth;
            }
        }

        $result[$node] = -1;
    }

    return $result;
}

function expand($id, $data, $depth = 0) {
    while (--$depth >= 0) {
        $id = flatten(array_intersect_key($data, array_flip((array) $id)));
    }

   //no array_unique() now!
    return flatten(array_intersect_key($data, array_flip((array) $id)));
}

Pentru Distanța ('c', $ graph, 0) , Distanța ('c', $ graf, 1) și Distanța ('c', $ graph, 3) ( și mai mare ) începe repetarea nodurilor și returnează rezultate greșite:

Array
(
    [a] => 12
    [b] => 9
    [c] => -1
    [d] => 9
    [e] => 3
    [f] => 12
    [g] => 3
    [h] => 3
    [i] => 6
    [j] => 0
)

Indicele a ar trebui să fie doar 6 (3 + 3), deoarece singurele metode pe care le pot obține de la C

C --> F --> B --> A
C --> F --> D --> A

Cu toate acestea, se pare că au în vedere două (numai?) Căi suplimentare care repetă noduri:

C --> A --> C --> A
C --> B --> C --> A
C --> F --> C --> A
C --> H --> C --> A
C --> I --> C --> A

Desigur, indexul a nu este singurul greșit. Problema pare să fie expand() , dar nu știu cum să o rezolv, array_diff (extindeți ('c', $ graph, $ i) $ graph, $ i - 2)) pare să remedieze această eroare specială, dar aceasta nu este o soluție corectă ... Ajutor?


dummy graph again again, so you don't have to scroll

9
@danielrsmith: Îmi pare rău pentru asta, am vrut să adaug săgeți în ambele direcții, dar am uitat să fac asta. Pentru a clarifica, graficul este nedirecționat și neweighted . =)
adăugat autor Alix Axel, sursa
@chris: În principiu, da - dar voi limita distanța de la nodul de origine la maximum 3 pași sau așa (în funcție de cât de repede se va efectua).
adăugat autor Alix Axel, sursa
Chiar vrei cai toate intre doua noduri? Acesta poate fi un număr destul de mare de căi, chiar și cu restricția că o cale poate conține orice nod dat un maxim de o dată. De exemplu, dacă graficul a fost complet (o margine între oricare dintre cele două vârfuri) și avea 10 vârfuri, dacă nu m-am înșelat, ar fi 9! căi între oricare două noduri.
adăugat autor goat, sursa
Imaginea și tabloul dvs. arată un grafic "direcționat". Ați sugerat probabil un grafic "neimpozitat"?
adăugat autor danielrsmith, sursa
PHP România, Moldova
PHP România, Moldova
173 participanți

Vorbim despre Yii, Laravel, Symphony, MySQL, PgSQL, WP, OpenCart... Pentru confort, opriți notificările. Parteneri: https://ciupacabra.com @js_ro @node_ro @python_ro @seo_ro @Romania_Bot Offtop: @holywars_ro Joburi: @php_job @Grupuri_IT