Einfache Graph-Search-Algorithmus in SQL (PostgreSQL)

Habe ich implementiert, die ein graph von Knoten in PostgreSQL (kein Baum)

sich die Struktur der Tabelle ist in diesem format

id | node1  | node2 
--------------------
1  |   1    |   2
2  |   1    |   3
3  |   4    |   1
4  |   5    |   1
5  |   1    |   6

Diese zeigt die Beziehungen zwischen den Knoten 1 und dem Knoten verbunden ist.

Mein Problem

...ist, dass ich brauche eine Funktion oder eine Methode zu finden, die einen bestimmten Knoten Pfad in sql.

Möchte ich nennen eine Funktion wie SELECT getGraphPath(startnode,targetnode) und zeigt den Pfad in irgendeiner form(Zeilen, oder Zeichenfolgen)

Z. B. WÄHLEN Sie getGraphPath(1,18) gibt:

[1]-->[3]-->[17]-->[18]
[1]-->[4]-->[10]-->[18]

oder sogar Zeilen:

Result  |
--------
1
3
17
18

Ich würde auch gerne wissen, wie man Durchlaufen Sie das Diagramm mit Breite-zuerst-Suche-und depth-first-Suche.

  • Ich bin mir nicht sicher, wie Sie Ihre Probe-Ausgabe bezieht sich auf deine sample-Daten. Ich kann nicht sehen, ein 3 -> 17 oder a 4 -> 10 in deinem Beispiel-Daten...
InformationsquelleAutor J146 | 2010-11-02
  1. 11

    Etwas wie dieses:

    with recursive graph_cte (node1, node2, start_id) 
as
( 
  select node1, node2, id as start_id
  from graphs
  where node1 = 1 -- alternatively elect the starting element using where id = xyz
  union all
  select nxt.node1, nxt.node2, prv.start_id
  from graphs nxt
    join graph_cte prv on nxt.node1 = prv.node2
)
select start_id, node1, node2
from graph_cte
order by start_id;

    (erfordert PostgreSQL 8.4 oder höher)

    • MySQL und MariaDB können dies nun auch.
    InformationsquelleAutor a_horse_with_no_name
  2. 6

    SQL ist nicht am besten geeignet, um die Manipulation von Graphen und das finden von Pfaden. Wahrscheinlich sind Sie besser laden Sie die Grafik in eine prozedurale Sprache und mit der Floyd-Warshall-Algorithmus oder Johnson ' s Algorithmus, einen Weg zu finden zwischen den Knoten.

    Jedoch, wenn Sie wirklich müssen die SQL verwenden, dann schlage ich Sie abholen eine Kopie der Joe Celko ' s SQL for Smarties, die hat ein ganzes Kapitel gewidmet, um Graphen in SQL.

    InformationsquelleAutor Tony
  3. 2

    Können Sie graph-Datenbank direkt um Ihr problem zu lösen:
    https://launchpad.net/oqgraph -> Diagramm als mysql-storage-engine

    InformationsquelleAutor aris
  4. 0

    Dies ist nicht gerade Speicher-optimal, aber funktioniert mit zyklischen Graphen zu:

    with recursive graph_cte (node1, node2, path) 
as
( 
  select node1, node2, ARRAY[node1] as path
  from graph
  where node1 = 4 -- start node
  union all
  select nxt.node1, nxt.node2, array_append(prv.path, nxt.node1)
  from graph nxt, graph_cte prv
  where nxt.node1 = prv.node2
  and nxt.node1 != ALL(prv.path)
)
select array_append(path, node2)
from graph_cte
where node2 = 6 -- goal node
limit 1;

    Beruht auf eine zuvor akzeptierte Antwort, sondern hält den Pfad. Es sollte aufhören zu suchen, sofort findet er die Ziel-Knoten.

    InformationsquelleAutor Gorgi Kosev
Schreibe einen Kommentar