Routinen für komprimierte spärliche Graphen (scipy.sparse.csgraph)#

Schnelle Graph-Algorithmen basierend auf spärlichen Matrixdarstellungen.

Inhalt#

connected_components(csgraph[, directed, ...])

Analysiert die Zusammenhangskomponenten eines spärlichen Graphen

laplacian(csgraph[, normed, return_diag, ...])

Gibt den Laplace-Operator eines gerichteten Graphen zurück.

shortest_path(csgraph[, method, directed, ...])

Führt eine kürzeste Pfad-Graphsuche auf einem positiven gerichteten oder ungerichteten Graphen durch.

dijkstra(csgraph[, directed, indices, ...])

Dijkstra-Algorithmus mit Prioritätswarteschlange

floyd_warshall(csgraph[, directed, ...])

Berechnet die Längen der kürzesten Pfade mit dem Floyd-Warshall-Algorithmus

bellman_ford(csgraph[, directed, indices, ...])

Berechnet die Längen der kürzesten Pfade mit dem Bellman-Ford-Algorithmus.

johnson(csgraph[, directed, indices, ...])

Berechnet die Längen der kürzesten Pfade mit Johnsons Algorithmus.

yen(csgraph, source, sink, K, *[, directed, ...])

Yens K-kürzeste-Pfade-Algorithmus auf einem gerichteten oder ungerichteten Graphen.

breadth_first_order(csgraph, i_start[, ...])

Gibt eine Breitensuche-Reihenfolge zurück, beginnend mit dem angegebenen Knoten.

depth_first_order(csgraph, i_start[, ...])

Gibt eine Tiefensuche-Reihenfolge zurück, beginnend mit dem angegebenen Knoten.

breadth_first_tree(csgraph, i_start[, directed])

Gibt den Baum zurück, der durch eine Breitensuche erzeugt wurde

depth_first_tree(csgraph, i_start[, directed])

Gibt einen Baum zurück, der durch eine Tiefensuche erzeugt wurde.

minimum_spanning_tree(csgraph[, overwrite])

Gibt einen minimalen Spannbaum eines ungerichteten Graphen zurück

reverse_cuthill_mckee(graph[, symmetric_mode])

Gibt das Permutationsarray zurück, das eine spärliche CSR- oder CSC-Matrix in umgekehrter Cuthill-McKee-Reihenfolge ordnet.

maximum_flow(csgraph, source, sink)

Maximiert den Fluss zwischen zwei Knoten in einem Graphen.

maximum_bipartite_matching(graph[, perm_type])

Gibt eine Paarung eines bipartiten Graphen zurück, deren Kardinalität mindestens so groß ist wie die jeder gegebenen Paarung des Graphen.

min_weight_full_bipartite_matching(biadjacency)

Gibt die minimale Gewichts-Vollpaarung eines bipartiten Graphen zurück.

structural_rank(graph)

Berechnet den strukturellen Rang eines Graphen (Matrix) mit einem gegebenen Sparsity-Muster.

NegativeCycleError([message])

construct_dist_matrix(graph, predecessors[, ...])

Konstruiert die Distanzmatrix aus einer Vorgängermatrix

csgraph_from_dense(graph[, null_value, ...])

Konstruiert einen spärlichen Graphen im CSR-Format aus einer dichten Matrix.

csgraph_from_masked(graph)

Konstruiert einen Graphen im CSR-Format aus einem maskierten Array.

csgraph_masked_from_dense(graph[, ...])

Konstruiert eine maskierte Array-Graphdarstellung aus einer dichten Matrix.

csgraph_to_dense(csgraph[, null_value])

Konvertiert eine spärliche Graphdarstellung in eine dichte Darstellung

csgraph_to_masked(csgraph)

Konvertiert eine spärliche Graphdarstellung in eine maskierte Array-Darstellung

reconstruct_path(csgraph, predecessors[, ...])

Konstruiert einen Baum aus einem Graphen und einer Vorgängerliste.

Graphdarstellungen#

Dieses Modul verwendet Graphen, die in Matrixform gespeichert sind. Ein Graph mit N Knoten kann durch eine (N x N) Adjazenzmatrix G dargestellt werden. Wenn eine Verbindung von Knoten i zu Knoten j besteht, dann ist G[i, j] = w, wobei w das Gewicht der Verbindung ist. Für Knoten i und j, die nicht verbunden sind, hängt der Wert von der Darstellung ab

  • für dichte Array-Darstellungen werden Nicht-Kanten durch G[i, j] = 0, Unendlich oder NaN dargestellt.

  • für dichte maskierte Darstellungen (vom Typ np.ma.MaskedArray) werden Nicht-Kanten durch maskierte Werte dargestellt. Dies kann nützlich sein, wenn Graphen mit Null-Gewicht-Kanten gewünscht sind.

  • für spärliche Array-Darstellungen werden Nicht-Kanten durch Nicht-Einträge in der Matrix dargestellt. Diese Art von spärlicher Darstellung erlaubt auch Kanten mit Null-Gewichten.

Als konkretes Beispiel stellen wir uns vor, dass wir den folgenden ungerichteten Graphen darstellen möchten

      G

     (0)
    /   \
   1     2
  /       \
(2)       (1)

Dieser Graph hat drei Knoten, wobei Knoten 0 und 1 durch eine Kante mit Gewicht 2 verbunden sind, und Knoten 0 und 2 durch eine Kante mit Gewicht 1 verbunden sind. Wir können die dichten, maskierten und spärlichen Darstellungen wie folgt konstruieren, unter Berücksichtigung, dass ein ungerichteter Graph durch eine symmetrische Matrix dargestellt wird

>>> import numpy as np
>>> G_dense = np.array([[0, 2, 1],
...                     [2, 0, 0],
...                     [1, 0, 0]])
>>> G_masked = np.ma.masked_values(G_dense, 0)
>>> from scipy.sparse import csr_array
>>> G_sparse = csr_array(G_dense)

Dies wird schwieriger, wenn Null-Kanten bedeutsam sind. Betrachten Sie zum Beispiel die Situation, in der wir den obigen Graphen leicht modifizieren

     G2

     (0)
    /   \
   0     2
  /       \
(2)       (1)

Dies ist identisch mit dem vorherigen Graphen, außer dass die Knoten 0 und 2 durch eine Kante mit Gewicht Null verbunden sind. In diesem Fall führt die obige dichte Darstellung zu Mehrdeutigkeiten: wie können Nicht-Kanten dargestellt werden, wenn Null ein sinnvoller Wert ist? In diesem Fall muss entweder eine maskierte oder spärliche Darstellung verwendet werden, um die Mehrdeutigkeit zu beseitigen

>>> import numpy as np
>>> G2_data = np.array([[np.inf, 2,      0     ],
...                     [2,      np.inf, np.inf],
...                     [0,      np.inf, np.inf]])
>>> G2_masked = np.ma.masked_invalid(G2_data)
>>> from scipy.sparse.csgraph import csgraph_from_dense
>>> # G2_sparse = csr_array(G2_data) would give the wrong result
>>> G2_sparse = csgraph_from_dense(G2_data, null_value=np.inf)
>>> G2_sparse.data
array([ 2.,  0.,  2.,  0.])

Hier haben wir eine Hilfsroutine aus dem csgraph-Untermodul verwendet, um die dichte Darstellung in eine spärliche Darstellung zu konvertieren, die von den Algorithmen im Untermodul verstanden wird. Durch Betrachten des Datenarrays können wir sehen, dass die Nullwerte explizit im Graphen kodiert sind.

Gerichtet vs. ungerichtet#

Matrizen können entweder gerichtete oder ungerichtete Graphen darstellen. Dies wird im gesamten csgraph-Modul durch ein boolesches Schlüsselwort angegeben. Graphen werden standardmäßig als gerichtet angenommen. In einem gerichteten Graphen kann eine Traversierung von Knoten i zu Knoten j über die Kante G[i, j] erfolgen, jedoch nicht über die Kante G[j, i]. Betrachten Sie den folgenden dichten Graphen

>>> import numpy as np
>>> G_dense = np.array([[0, 1, 0],
...                     [2, 0, 3],
...                     [0, 4, 0]])

Wenn directed=True ist, erhalten wir den Graphen

  ---1--> ---3-->
(0)     (1)     (2)
  <--2--- <--4---

In einem ungerichteten Graphen kann eine Traversierung von Knoten i zu Knoten j über G[i, j] oder G[j, i] erfolgen. Wenn beide Kanten nicht null sind und die beiden ungleiche Gewichte haben, wird das kleinere der beiden verwendet.

Für denselben Graphen erhalten wir, wenn directed=False ist, den Graphen

(0)--1--(1)--3--(2)

Beachten Sie, dass eine symmetrische Matrix einen ungerichteten Graphen darstellt, unabhängig davon, ob das Schlüsselwort 'directed' auf True oder False gesetzt ist. In diesem Fall führt die Verwendung von directed=True im Allgemeinen zu einer effizienteren Berechnung.

Die Routinen in diesem Modul akzeptieren als Eingabe entweder scipy.sparse-Darstellungen (csr, csc oder lil-Format), maskierte Darstellungen oder dichte Darstellungen mit Nicht-Kanten, die durch Nullen, Unendlichkeits- und NaN-Einträge gekennzeichnet sind.