Das Digraph-Paket

mit Algorithmen für gerichtete Graphen

q r s u t

Funktionsübersicht

.random .complete .plot .degree .degree_in .degree_out .incidence_matrix .adjacency_matrix .is_simple .is_connected .shortest_path .distance .max_flow

Beschreibung

Das Digraph-Paket stellt ausgewählte Funktionen der Graphentheorie bereit. Ein Graph wird dabei insbesondere durch seine Kantenmenge definiert, wobei im Digraph-Paket ausschließlich gerichtete Graphen behandelt werden. Neben einer Funktion zur Darstellung von Digraphen sowie Abfragen zur Prüfung der Eigenschaften beinhaltet das Paket auch grundlegende Algorithmen beispielsweise zum Finden kürzester Wege oder maximalen Flüssen.

Beispiel

Im folgenden Beispiel wird ein zufälliger Graph mit 5 Knoten erzeugt. Anschließend wird ein maximaler Fluss von Knoten 0 zu Knoten 4 berechnet, welcher die Gewichtung der Kanten berücksichtigt. Die Ergebnisse werden graphisch dargestellt.

<!DOCTYPE html>
<html>
<head>
  <script src="taramath.js"></script>
</head>
<body>
<div id="plot1" style="display:inline-block;"></div>
<div id="plot2" style="display:inline-block;"></div>
<script>

var G = Digraph.random(5);
var F = Digraph.max_flow(G.E, 0, 4, G.w);

Digraph.plot("plot1", G.E, G.w, "large", 300);
Digraph.plot("plot2", F.E, F.w, "large", 300);

</script>
</body>
</html>

Vorschau aktualisieren

Impressum und Kontakt

Datenschutzerklärung

Rechtliche Hinweise