Im letzten Kapitel haben wir kürzeste Wege mit einem LP gesucht.

Spezialisierte Algorithmen sind da effizienter

• Dijkstras Algorithmus
• A*

Formal ist ein Graph $G=(V,E)$ ein Tupel aus einer Menge an Knoten (vertices) $V$ und einer Menge an Kanten (edges) $E$.

• Die Knoten sind beliebige Objekte
  $V = \{A,B,C,D\}$
• Kanten sind Tupel von Knoten
  $E = \{(A,B), (A,C), (C,B), (C,D)\}$
  • Wir gehen erst mal von gerichteten Graphen aus.
  • Ungerichtete Graphen funktionieren aber ähnlich.

An jede Kante $e \in E$ können wir Kosten $\color{red} c_e$ schreiben,
z.B. $\color{red} c_{(C, D)} = 4$

In Pythons NetworkX Package können wir beliebige Graphen einfach definieren.

          import networkx as nx

          g = nx.DiGraph()

          # g = nx.Graph() erzeugt einen ungerichteten Graph
        

Wenn wir Kanten erzeugen, werden die Knoten automatisch generiert

          g.add_edge("A", "B")
          g.add_edge("A", "C")
          g.add_edge("C", "B")
          g.add_edge("C", "D")
        

Wir können einer Kante oder einem Knoten beliebige Attribute geben (nachträglich, oder direkt beim erstellen der Kante)

          g.edges["A", "B"]["weight"] = 1
          g.add_edge("A", "C", weight=1)

          g.nodes["A"]["demand"] = 3
        

Es gibt verschiedene Wege, um an die unterschiedlichen Attribute des Graph zu kommen.

          print(list(g.predecessors("C")))
          print(list(g.successors("C")))
        

Wir können unseren Graph plotten:

          pos = nx.spectral_layout(g)
          nx.draw(g, pos=pos, with_labels=True)
          nx.draw_networkx_edge_labels(g, pos=pos)
        

Layouting von großen Graphen ist nicht trivial!

Wir suchen einen kürzesten Weg (minimale Kosten $c$) von einem Knoten $v_\text{source} \in V$ nach $v_\text{sink} \in V$.

Idee von Dijkstras Algorithmus:
Wir erkunden einen Knoten nach dem anderen in der Reihenfolge der Kosten von $v_\text{source}$ ausgehend.

Dijkstras Algorithmus:

• Markiere $v_\text{source}$ als "offen".
• Setze $d_{v_\text{source}} \gets 0$
• Solange $v_\text{sink}$ nicht "erkundet" ist:
  • Wähle "offenen" Knoten $v$ mit kleinstem $d_{v}$.
  • Für alle nicht "erkundeten" Nachfolger von $v'$ von $v$:
    • Markiere $v'$ als "offen"
    • Setze $d_{v'} \gets \min(d_{v'}, d_v + c_{(v,v')})$
  • Markiere $d$ als "erkundet".

https://commons.wikimedia.org/wiki/File:Dijkstras_progress_animation.gif

Ordentlich implementiert hat Dijkstras Algorithmus eine worst case Komplexität von
$O(|E| + |V| \log |V|)$

Sowohl im worst case als auch in der Praxis deutlich schneller, als mit einem LP Solver.

In NetworkX

          import networkx as nx

          g = nx.DiGraph()
          g.add_edge("A", "B", weight=1)
          g.add_edge("A", "C", weight=1)
          g.add_edge("C", "B", weight=3)
          g.add_edge("C", "D", weight=4)

          nx.shortest_path(g, "A", "D", weight="weight")
        

Einschränkung des Dijkstra Algorithmus: Kantenkosten dürfen nicht negativ sein.

Der Bellman-Ford Algorithmus kann auch mit negativen Kanten umgehen.

Der Algorithmus funktioniert ähnlich wie der Dijkstra, führt aber auch Updates für schon erkundete Knoten aus.

Laufzeit: $O(|E||V|)$ (im schlimmsten Fall $O(|V|^3)$).

In NetworkX:

          import networkx as nx

          g = nx.DiGraph()
          g.add_edge("A", "B", weight=1)
          g.add_edge("A", "C", weight=1)
          g.add_edge("C", "B", weight=3)
          g.add_edge("C", "D", weight=4)
          g.add_edge("D", "B", weight=-5)

          nx.shortest_path(g, "A", "B", weight="weight", method="bellman-ford")
        

Wenn es negative Kreise im Graph gibt, schlägt der Bellman-Ford Algorithmus fehlt.

In diesem Fall suchen wir meistens eher den shortest simple path.

Ein simple path ist ein Pfad, der keinen Knoten zweimal besucht.

Das Problem ist NP-schwer.

Was, wenn wir mehrere mögliche Start oder Zielknoten haben?

Beispiel: Ich will zur nächsten Tankstelle fahren, mir ist aber egal welche.

Beispiel: Fahre von A nach entweder C oder D:

Kommen wir jetzt mit dem Graphenalgorithmus nicht mehr weiter?

Idee: Hilfknoten mit kostenlosen Kanten von C und D:

Jetzt können wir wieder von einer Quelle zu einer Senke suchen.

Analog können wir mehrere Quellen mit einer Hilfsquelle verbinden.

Was, wenn wir einen Zwischenstopp einplanen wollen.

Beispiel: Fahre von Bingen nach Alzey über Mainz.

Beispiel: Wir wollen von A nach F über D fahren.

Idee: Berechne einen kürzesten Weg

• von A nach D
• von D nach F

Was, wenn wir mehrere Optionen für den Zwischenstopp haben?

Beispiel: Fahre von Bingen nach Alzey, aber halte zwischendurch bei einer beliebigen Tankstelle.

Beispiel: Wir wollen von A nach E fahren und einen Stopp bei C oder D machen.

Der kürzeste Weg zu einem der Zwischenstopps ist nicht notwendigerweise Teil des insgesamt kürzesten Weges.

Idee: Baue neuen Hilfsgraph.

• Mache eine Kopie des gesamten Graph.
• Für jeden möglichen Zwischenstopp $v$ füge eine Kante $(v, v')$ mit Kosten $\color{red} c_{(v, v')} = 0$ von $v$ zu seiner Kopie $v'$ hinzu.
• Suche kürzesten Weg von der Original Quelle zur Kopie der Senke.

Wir erhalten ein "Stockwerk" für den Teil vor und eines für den Teil nach dem Zwischenstopp.

Für jeden Zwischenstopp brauchen wir eine Kopie des Original-Graphen. Die Komplexität wächst um die Anzahl an Zwischenstopps.

Beispiel: Wir suchen einen kürzesten Weg, die Kantenkosten ändern sich aber mit der Zeit.

In der Rush-Hour kann es sinnvoller sein einen weniger befahrenen Umweg zu nehmen.

Idee: Time Expanded Network

Jeder Knoten bekommt eine Kopie je "Zeiteinheit" (z.B. pro Minute)

Meistens wollen wir noch zwei Hilfsknoten haben um mehrere Quellen und Senken abzubilden.

Hier bekommen wir eine Kopie des Graphen für jede Zeiteinheit.

Tradeoff: Genauigkeit vs Laufzeit.

Nächste Erweiterung: Was, wenn wir den kürzesten Weg von einer Quelle zu jedem anderen Knoten wissen wollen?

Der Dijkstra Algorithmus berechnet auch den kürzesten Weg zu jedem Knoten, der näher an der Quelle liegt, als der Zielknoten.

$\Rightarrow$ Wir lassen den Algorithmus einfach laufen, bis alle Knoten erkundet sind.

Wenn wir den kürzesten Weg von jedem Knoten zu einer Senke wissen wollen, geht das analog, indem wir einfach Quelle und Senke vertauschen, alle Kanten umdrehen und die Pfade am Ende umdrehen.

In NetworkX:

          nx.single_source_shortest_path(g, "A")

          nx.single_target_shortest_path(g, "D")
        

Was, wenn wir den kürzesten Weg von jedem Knoten zu jedem anderen Knoten suchen?

Idee: Wir lassen den Dijkstra einmal von jeder Quelle aus laufen

Laufzeit: $O(|V| |E| + |V|^2 \log |V|)$

In NetworkX:

          list(nx.all_pairs_dijkstra(g))
        

Hier haben wir natürlich wieder Probleme mit negativen Kosten.

Den Bellman-Ford Algorithmus von jeder Quelle laufen zu lassen hätte Laufzeit $O(|V|^2 |E|)$
(im schlimmsten Falle $O(|V|^4)$).

Der Floyd-Warshall Algorithmus findet alle kürzesten Wege in Laufzeit $O(|V|^3)$.

Kann mit negativen Gewichten aber nicht mit negativen Kreisen umgehen.

In NetworkX:

          import networkx as nx

          g = nx.DiGraph()
          g.add_edge("A", "B", weight=1)
          g.add_edge("A", "C", weight=1)
          g.add_edge("C", "B", weight=3)
          g.add_edge("C", "D", weight=4)
          g.add_edge("D", "B", weight=-5)

          nx.floyd_warshall(g)
          # Oder: list(nx.all_pairs_shortest_path(g))
        

Modellierungstricks:

• Hilfknoten für multiple Qullen oder Senken
• Graphenkopie für Zwischenstopps
• Graphenkopie für zeitexandierte Netzwerke

Als nächstes schauen wir uns Algorithmen an, um Flüsse zu berechnen.

Finde den maximalen Fluss von A nach G.

Das Problem kann mit dem Edmonds-Karp Algorithmus (eine Variante der Ford-Fulkerson Methode) gelöst werden.

Grundidee: Für einen schon berechneten Fluss nehmen wir den Graph mit den Restkapazitäten.
Dort suchen wir nach noch existierender Kapazität und erweitern den Fluss.

Laufzeit: $O(|V|^2 |E|)$.

In der Praxis ist das oft genug.
Es gibt aber auch Flussalgorithmen die fast in $O(|E|)$ laufen.

In NetworkX:

          g = nx.DiGraph()

          g.add_edge("A", "B", capacity=5)
          g.add_edge("A", "C", capacity=2)
          g.add_edge("A", "D", capacity=4)
          g.add_edge("B", "E", capacity=3)
          g.add_edge("B", "F", capacity=7)
          g.add_edge("C", "F", capacity=8)
          g.add_edge("D", "F", capacity=3)
          g.add_edge("E", "G", capacity=9)
          g.add_edge("F", "G", capacity=5)

          nx.maximum_flow(g, "A", "G")
        

Wenn wir mehrere Quellen oder Senken haben, können wir das wieder mit Hilfsknoten lösen.

Wenn eine Kante keine Kapazitätseinschränkung hat, können wir die Kapazität auf $\infty$
(bzw. float("inf")) setzen.

Als nächstes suchen wir Min-Cost Flows, also Flüsse mit minimalen Kosten.

Neben Kapazitäten haben wir nun auch Kosten.

Verschiedene Settings:

• Maximaler Fluss von A nach G mit minimalen Kosten.
• Jeder Knoten hat einen Demand und Fluss soll minimale Kosten haben und alle Demands erfüllen.

Die beiden Probleme können ineinander überführt werden.

• Ermittle maximalen Fluss (ohne Kosten) und setze diesen als Demand.
• Füge Hilfsknoten ein. Verbinde diese mit Knoten die Demand haben (Kosten = 0, Kapazität = |Demand|).

Dieses Problem kann mit dem Network Simplex effizient gelöst werden.

Eine spezialisierte Variante des Simplex Algorithmus, welche die Graphenstruktur ausnutzt.

Im Gegensatz zum allgemeinen Simplex gibt es hier Performance Garantien.

Laufzeit $O(|V||E|\log(|V|)\log(|V|C))$
($C$ sind die maximalen Kantenkosten)

(also circa $O(|V||E|)$)

In NetworkX:

          g = nx.DiGraph()
          g.add_edge("A", "B", capacity=5, weight=4)
          g.add_edge("A", "C", capacity=2, weight=1)
          g.add_edge("A", "D", capacity=4, weight=2)
          g.add_edge("B", "E", capacity=3, weight=3)
          g.add_edge("B", "F", capacity=7, weight=1)
          g.add_edge("C", "F", capacity=8, weight=1)
          g.add_edge("D", "F", capacity=3, weight=3)
          g.add_edge("E", "G", capacity=9, weight=4)
          g.add_edge("F", "G", capacity=5, weight=5)
          g.nodes["A"]["demand"] = -8
          g.nodes["G"]["demand"] = 8

          nx.min_cost_flow(g)
        

Modellierungstricks, wie z.B. zeitexpandierte Graphen funktionieren hier analog.

Als nächstes wollen wir wissen, was in bei einem maximalen Fluss der Flaschenhals ist.

Was genau ist ein Flaschenhals in einem Netzwerk?

Ein s-t Cut ist eine Menge an Kanten, ohne die man im Graph nicht von s nach t reisen kann.

Wir suchen also einen minimalen s-t Cut (basierend auf den Kapazitäten).

Ein minimaler s-t Cut entsteht beim berechnen eines maximalen Flusses automatisch.

Alle Kanten des Cuts haben Restkapazität 0.

Es kann mehrere minimale s-t Cuts geben. Wir müssen eventuell aus den Kanten mit Restkapazität 0 auswählen.

In NetworkX:

          g = nx.DiGraph()
          g.add_edge("A", "B", capacity=5)
          g.add_edge("A", "C", capacity=2)
          g.add_edge("A", "D", capacity=4)
          g.add_edge("B", "E", capacity=3)
          g.add_edge("B", "F", capacity=7)
          g.add_edge("C", "F", capacity=8)
          g.add_edge("D", "F", capacity=3)
          g.add_edge("E", "G", capacity=9)
          g.add_edge("F", "G", capacity=5)

          nx.minimum_cut(g, "A", "G")
        

Als nächstes schauen wir uns Probleme an, bei denen wir Knoten paarweise zuordnen wollen (Matchings).

Beispiel: Jeder Knoten ist ein Studierender und wir wollen Studiengruppen von je 2 Personen finden.

Jeder Knoten ist ein Studierender, eine Kante zwischen 2 Studierenden indiziert, dass diese eine Gruppe bilden können.

Hier sind die Kanten des Graphen ungerichtet.

Wir suchen eine möglichst große Menge an Kanten, so dass jeder Knoten in maximal einer gewählten Kante vorkommt.

Beispiel

Es findet nicht notwendigerweise jeder Knoten einen Partner

Je nach Struktur der Kanten ist das maximale Matching auch kleiner als $\lfloor \frac{|V|}{2} \rfloor$.

Ein solches maximales Matching auf einem beliebigen Graphen kann man mit Edmonds's Blossom Algorithm finden.

Idee: Wir starten mit einem Matching. Wenn es einen augmenting path im Graphen gibt, nutzen wir diesen, um das Matching zu vergrößern.

Augmenting path: Ein Pfad der mit einem Knoten ausserhalb des Matchings beginnt und endet, und immer abwechseln eine Kante ausserhalb und innerhalb des Matchings verwendet.

Man kann zeigen, dass es immer einen Augmenting Path gibt, wenn sich das Matching noch verbessern lässt.

Der anspruchsvolle Teil ist, diesen allgemein zu finden.

Laufzeit: $O(|E||V|^2)$

Es gibt einen Algorithmus, der Laufzeit $O(\sqrt{|V|} |E|)$ hat.

In NetworkX:

          g = nx.Graph()

          g.add_edge("A", "B")
          g.add_edge("A", "C")
          g.add_edge("C", "D")
          g.add_edge("A", "D")

          nx.maximal_matching(g)
        

Hier haben wir ein Maximum Cardinality Matching berechnet (maximale Anzahl Kanten).

Wenn die Kanten unterschiedliche Gewichte haben, suchen wir eher ein Maximum Weight Matching.

Beispiel: Die Studierenden geben Präferenzen an, mit wem sie gerne eine Gruppe bilden möchten.

Maximum Weight Matching

In NetworkX:

          g = nx.Graph()

          g.add_edge("A", "B", weight=1)
          g.add_edge("A", "C", weight=2)
          g.add_edge("C", "D", weight=1)
          g.add_edge("A", "D", weight=4)
          g.add_edge("B", "D", weight=1)

          nx.max_weight_matching(g)
        

Maximum Cardinality Maximum Weight Matching

In NetworkX:

          g = nx.Graph()

          g.add_edge("A", "B", weight=1)
          g.add_edge("A", "C", weight=2)
          g.add_edge("C", "D", weight=1)
          g.add_edge("A", "D", weight=4)
          g.add_edge("B", "D", weight=1)

          nx.max_weight_matching(g, maxcardinality=True)
        

Maximum Weight (mit oder ohne Maximum Cardinality) lassen sich auch mit dem Edmonds's Blossom Algorithm finden (in $O(|E||V|^2)$ Laufzeit).

Sehr oft suchen wir nach einem Matching auf einem Bipartiten Graphen.

Ein Graph ist bipartit, wenn sich die Knoten in zwei Teilmengen zerlegen lassen, innerhalb derer es keine Kanten gibt.

Wir haben eine Menge von Kursen, die jeder genau einen Raum bekommen sollen. Manche Kurse passen besser in bestimmte Räume.

Hier macht ein Maximum Cardinality Maximum Matching Sinn.

Ein Bipartites Matching lässt sich auch gut als Flussproblem formulieren:

Viele Matching Probleme sind bipartit.

NetworkX hat spezialisierte Algorithmen für bipartite Graphen.

          g = nx.Graph()

          g.add_edge("K1", "R1", weight=1)
          g.add_edge("K1", "R2", weight=3)
          g.add_edge("K1", "R3", weight=2)
          g.add_edge("K2", "R2", weight=2)
          g.add_edge("K2", "R3", weight=1)

          nx.bipartite.maximum_matching(g, ["K1", "K2"])
        

Beispiel: Wir wollen Studierende zu Tutoriumsgruppen zuordnen. Jede Gruppe kann 3 Studierende aufnehmen.

Wie modellieren wir mit Matchings wo wir immer nur paarweise Zuordnungen machen?

Idee: Wir nehmen einen Knoten für jeden möglichen Slot in einer der Tutoriumsgruppen.

Nächstes Beispiel: Wir haben eine Reihen verschiedener Jobs $j_1, \ldots, j_n$. Jeder Job braucht eine Zeiteinheit zum bearbeiten.

Wir können Jobs parallel bearbeiten.

Manche Jobs können nicht gleichzeitig bearbeitet werden, da sie die gleiche Ressource brauchen.

Wie viele Zeiteinheiten brauchen wir mindestens um alle Jobs zu bearbeiten?

• Wir nehmen einen Knoten für jeden Job.
• Wenn zwei Jobs nicht parallel bearbeitet werden können, verbinden wir sie mit einer Kante
• Wir suchen nun ein Vertex Coloring

Ein Vertex Coloring ist eine Färbung der Knoten, so dass keine verbundenen Knoten die gleiche Farbe haben.

Jede Farbe entspricht einem Zeitschritt.

Wir wollen so wenige Farben wir möglich verwenden.

https://en.wikipedia.org/wiki/File:Petersen_graph_3-coloring.svg

Vertex Coloring ist ein NP-hartes Problem.

Ein heuristischer Ansatz ist Greedy Coloring:

• Für jeden Knoten $v$:
  • Wähle die erste Farbe, die noch kein Nachbar von $v$ hat.

Die Reihenfolge der Knoten hat hier einen großen Einfluss auf das Ergebnis.

Wir können die Knoten so ordnen, dass die mit den meisten Kanten zuerst kommen ("largest first").

Oder nehme den Knoten als nächstes, dessen Nachbarn bereits die meisten Farben verwenden ("saturation largest first").

          import networkx as nx

          g = nx.fast_gnp_random_graph(500, 0.05, 3)

          coloring = nx.coloring.greedy_coloring.greedy_color(g)
          # coloring = nx.coloring.greedy_coloring.greedy_color(g, strategy="saturation_largest_first")

          max(coloring.values())
        

Modifikation unseres Beispiels:

Alle Jobs haben feste Start- und Endzeiten. Eine Maschine kann keine zwei Jobs gleichzeitig bearbeiten.

Interval Graph

https://en.wikipedia.org/wiki/File:Interval_graph.svg

Für Interval Graphen führt Greedy Coloring immer zu einer optimalen Lösung.

Für schwere Probleme ist es oft eine gute Idee zuerst mit einer sehr einfachen Heuristik zu starten, um schnell ein funktionierendes Gesamtsystem zu erhalten
(agiler Ansatz)

Wenn wir eine Menge an Knoten haben, die untereinander vollständig verbunden sind, nennen wir diese eine Clique

https://de.wikipedia.org/wiki/Datei:6n-graf-clique.svg

Bei einem Coloring muss jeder Knoten einer Clique eine andere Farbe bekommen.

Eine Clique maximaler Größe ist also eine untere Schranke für das Vertex Coloring.

Eine Clique maximaler Größe (maximum Clique) zu finden ist leider auch NP-schwer.

Einfacher ist es eine Clique zu finden, die sich nicht mehr vergrößern lässt (maximal Clique)

• Kann eine existierende Clique um einen ihrer Nachbarn erweitert werden?
  • Ja: Füge Knoten zur Clique hinzu.
  • Nein: Die Clique ist maximal.

In NetworkX können wir uns uns mit find_cliques alle maximalen Cliquen enumerieren:

          import networkx as nx

          g = nx.fast_gnp_random_graph(500, 0.2, 3)

          max(len(c) for c in nx.find_cliques(g))
        

Die Anzahl an maximalen Cliquen kann exponentiell mit der Anzahl an Knoten steigen.

Kommt sehr darauf an, wie bösartig der Graph ist.

Bei einer Clique kennt jeder Knoten jeden.

Bei einer Connected Component geht es darum Knoten zu finden, die irgendwie verbunden sind.

https://en.wikipedia.org/wiki/File:Pseudoforest.svg

Connected Components kann man leicht mit Tiefensuche in ungefähr linearer Zeit finden.

Häufig suchen wir Connected Components um ein anderes Problem einfacher zu machen.

Eventuell können wir jede Component einzeln betrachten und so das Problem zerlegen.

Oder wir können die Components in einem folgenden Problem zusammenfassen.

Beispiel: Wir suchen Termine für mehre Meetings

• Anna und Bob können nur gleichzeitig.
• Bob und Carmen können nur gleichzeitig.

Anna, Bob und Carmen können wir zu einer Entität im Terminplanungsproblem zusammenfassen.

Beispiel aus der Bildbearbeitung: Färbe alle Pixel einer Region ein.

Entscheidend ist, ab wann Pixel als verbunden gelten.

https://en.wikipedia.org/wiki/File:Screenshot-Figure_1.png

Wir können die Connected Components mit connected_components finden:

          import networkx as nx

          g = nx.Graph()
          g.add_edge(1, 2)
          g.add_edge(2, 3)
          g.add_edge(4, 5)
          g.add_node(6)
          g.add_edge(1, 7)

          list(nx.connected_components(g))
        

Auf gerichteten Graphen unterscheiden wir zwischen zwei Typen von Connected Components:

• Schwach verbunden: Es gibt einen ungerichteten Pfad von jedem Knoten zu jedem anderen Knoten.
• Stark verbunden: Es gibt einen gerichteten Pfad von jedem Knoten zu jedem anderen Knoten.

          import networkx as nx

          g = nx.DiGraph()

          g.add_edge(1, 2)
          g.add_edge(2, 3)
          g.add_edge(3, 1)
          g.add_edge(2, 4)
          g.add_edge(5, 6)

          print(list(nx.weakly_connected_components(g)))
          print(list(nx.strongly_connected_components(g)))
        

Wenn wir alle Knoten einer strongly connected component kontrahieren, erhalten wir einen directed acyclic graph (DAG)

Mit contracted_nodes können wir Knoten zusammenfassen.

          import networkx as nx

          g = nx.DiGraph()
          g.add_edge(1, 2)
          g.add_edge(2, 3)
          g.add_edge(3, 1)
          g.add_edge(2, 4)
          g.add_edge(2, 5)
          g.add_edge(5, 4)

          components = list(nx.strongly_connected_components(g))
          for component in components:
              if len(component) > 1:
                  component = list(component)
                  for i in range(len(component)-1):
                      nx.contracted_nodes(g, component[-1], component[i], self_loops=False, copy=False)

          print(list(g.edges))
        

Ein DAG ist ein gerichteter Graph, der keine Kreise hat.
Jede strongly connected component hat Größe 1.

https://commons.wikimedia.org/wiki/File:Graph_Condensation.svg

DAGs sind häufig die Grundlage für Scheduling Probleme.

Beispiel: Was ist der kritische Pfad in einem Meilensteinplan?

https://en.wikipedia.org/wiki/File:Pert_chart_colored.svg

Einen längsten Pfad suchen ist allgemein NP-schwer.

In DAGs lässt sich das sehr effizient berechnen.

In diesem Fall entsprechen die Aufgaben den Kanten und die Meilensteine den Knoten.

Wir können mehrere Kanten zwischen den gleichen Knoten haben.

Die passende Klasse in NetworkX ist MultiDiGraph

          import networkx as nx

          g = nx.MultiDiGraph()
          g.add_edge(10, 30, duration=3)
          g.add_edge(10, 20, duration=4)
          g.add_edge(20, 50, duration=3)
          g.add_edge(30, 40, duration=1)
          g.add_edge(30, 50, duration=3)
          g.add_edge(40, 50, duration=3)

          nx.dag_longest_path(g)
        

Eine wichtige Eigenschaft von DAGs ist, dass sie eine topologische Sortierung haben.

Eine topologische Sortierung ist eine Reihenfolge der Knoten, so dass alle Kanten von links nach rechts zeigen.

Eine topologische Sortierung ist nicht eindeutig.

Jede topologische Sortierung gibt uns eine Reihenfolge in der wir z.B. Tasks mit Abhängigkeiten sequenziell bearbeiten können.

          import networkx as nx

          g = nx.MultiDiGraph()
          g.add_edge(10, 30, duration=3)
          g.add_edge(10, 20, duration=4)
          g.add_edge(20, 50, duration=3)
          g.add_edge(30, 40, duration=1)
          g.add_edge(30, 50, duration=3)
          g.add_edge(40, 50, duration=3)

          list(nx.topological_sort(g))
        

Topologische Sortierung ist in $O(|V| + |E|)$ möglich.

Wir können sie auch nutzen um zu prüfen, ob ein Graph ein DAG ist.

Mit der topologischen Sortierung werden oft andere Algorithmen schneller (z.B. longest path und shortest path)

Nächstes Beispiel: Suche einen Weg durch den Graph, der jede Kante genau einmal besucht.

https://de.wikipedia.org/wiki/Datei:HausVomNikolaus.png

Dieses Problem nennt sich Euler Pfad oder Eulerian Path

Wenn der Start- und Zielknoten gleich sind, erhält man einen Euler Kreis (Eulerian Circuit)

          import networkx as nx

          g = nx.Graph()
          g.add_edge(1,2)
          g.add_edge(1,3)
          g.add_edge(1,4)
          g.add_edge(2,3)
          g.add_edge(2,4)
          g.add_edge(3,4)
          g.add_edge(3,5)
          g.add_edge(4,5)

          list(nx.eulerian_path(g))
        

Ein anderes bekanntes Problem ist das Traveling Salesperson Problem (TSP).

Wir suchen eine Route durch den Graph, welche jeden Knoten besucht und am Startknoten endet.

Das TSP ist NP-schwer.

Es gibt aber gute Heuristiken, die in der Praxis gut funktionieren.

Z.B. der Algorithmus von Christofides

Der Christofides Algorithmus garantiert, dass die gefundene Lösung maximale 50% schlechter als das Optimum ist.

Laufzeit: $O(|V|^3)$

In NetworkX: traveling_salesman_problem

Es gibt noch viele andere Algorithmen in NetworkX für diverse Probleme:

• Minimum Spanning Tree
• Dominating Set (NP-schwer)
• Independent Set (NP-schwer)
• Planarity
• ...