Praktikum Algorithmische Anwendungen

Wintersemester 2003/04

Projekt 5

Gruppe AI A1
Michael Boiman 11027800 ai320
M. Serhat Çinar 11030409 ai440
Mustafa Ekit 11027589 ai336

Index

  • Projekt 5: Flüsse in Netzwerken
  • Aufgabe 1: Verständnis
  • Aufgabe 2: Implementation
  • Dateien und Javadoc
  • Aufgabe 1: Verständnis


    a)
    Erklären Sie die Laufzeit-Problematik des Ford-und-Fulkerson Algorithmus am Beispiel des folgenden Flussgraphen mit Quelle q und Senke s. Diskutieren Sie die Laufzeit für das Beispiel.


    Wenn in diesen Graphen man nach dem Fort und Fulkerson Algorithmus geht, wird der Fluss um den Minimum erhöht was die Kapazität 1 zwischen x und y ist.
    Um den Maximalen Fluss zu erreichen ist dieser schritt aber nicht nötig sonder wird sogar in einen späteren schritt sogar abgezogen so das die Verbindung x-->y später nicht genutzt wird.
    Hier werden unnötige schritte mit dem Fort und Fulkerson Algorithmus verschwendet, besser wäre den kürzesten Weg über den Restgraphen bestimmen.

    b)
    Was ist ein zunehmender Weg? Was ist ein blockierender Fluss?

    b.1)
    Ein Weg von q nach s, auf dem ohne Rücksicht auf die Pfeilrichtungen (ein ungerichteter Weg) der Fluss erhöht werden kann, heißt zunehmender Weg
    (augmenting path) .
    Wenn die Kanten in Flussrichtung sind, muss der Fluss geringer sein um erhöht zu werden.
    Wenn die Kanten entgegengesetzt sind, muss der Fluss grösser 0 sein um verringert werden zu können.

    b.2)
    Ein Fluss, der auf einem zunehmenden Weg nicht mehr zu vergrößern ist, heißt blockierender Fluss.

    c)
    Nach welcher Idee arbeitet der Niveaugraph-Algorithmus (Dinitz)?
    Welche Laufzeitverbesserung wird dadurch erreicht?
    Im Niveaugraph-Algorithmus werden zuerst alle kürzesten Wege einer bestimmten Länge gesucht.
    (Was in Aufgabe 1a den Weg {q,x,y,s} verhindert hätte.
    Durch diese Idee gibt es eine Laufzeitverbesserung, da viele unnötige Knoten weggelassen werden.
    Für den Vorrgang wir die Breitensuche benutzt und die Laufzeit von O(|E|) [--> Die Anzahl der Pfeile im Netzwerk] erreicht.

    d)



    Implementation



    getRestGraph

    Erzeugt für einen übergebenen Flowgraph das Restgraph.

    Das Matrix wird mittels 2 for-Schleifen durchgelaufen. i und j sind Knoten.
    Es gibt 5 Fälle:

  • Fluss und Kapazität sind 0

  • Das bedeutet sie sind nicht verbunden.

  • Kapazität und Fluss sind gleich gross

  • i->j = 0
    j->i = Fluss

  • Kapazität ist grösser der Flusswert(Fluss > 0)

  • i->j = Kapazität - Fluss
    j->i = Fluss

  • Kapazität ist grösser der Flusswert(Fluss = 0)

  • i->j = Kapazität - Fluss
    j->i = 0

  • Sonst

  • i->j = 0

    Fluss -und Kapazitätswerte sind von i nach j.

     

    getNievauGraph

    Erzeugt für einen übergebenen Restgraph das Niveaugraph.

    Dieses Tiefensuchbaum wurde mit einer Queue realisiert. Die Queue enthält unmarkierte Knoten.
    Der Vector "markiert" enthält alle Knoten, die schon fertig sind. Sein erster Wert ist der Startknoten. Die weiteren entnimmt er nach der Reihe aus der Queue. Und der Vector "nachbar" enthält alle unmarkierten Knoten zur zuletzt aus der Warteschlange entnommenen Knoten.

     

    getAugmentedPaths

    Die Funktion kriegt den Restgraphen und verfolgt vom Target Knoten den Graphen zurück um dadurch den kürzesten weg in einen Vector zu sichern.

    public static Vector getAugmentedPaths(IGraph niveaugraph,int source,int target){

    Stack stapel = new Stack();
    //int laenge = niveaugraph.getVertexAmount();
    int i=target;
    stapel.add(new Integer(i));
    int j=-1;
    int knoten=0;
    while (i!=source) {
    while(knoten==0) {
    j++;
    //System.out.println("i="+i+"j="+j);
    knoten = niveaugraph.getValueAt(j,i);
    //System.out.println("Knoten:"+knoten);
    }
    i=j;
    //System.out.println("in den Stapel:"+j);
    stapel.add(new Integer(knoten));
    stapel.add(new Integer(j));
    j=-1;
    knoten=0;
    }

    Vector vec = new Vector();
    while(!stapel.isEmpty()){
    vec.add(stapel.pop());
    }
    return vec;
    }

    raiseFlow

    raiseFlow nutzt die alle Funktionen um den Graph in den nächsten zustand zu überführen.
    Sie holt den Restgraph mit dem Sie den NiveaGraph erzeugen kann und nutzt dann den NiveauGraph um den kürzesten Weg zu finden.
    Dann erhöt Sie den Fluss und benachrichtigt den Observer.
    public void raiseFlow() {
    this.rg = FlowGraphTools.getRestGraph(fg);
    this.ng = FlowGraphTools.getNiveauGraph(rg,fg.getFlowSource());
    this.vec =FlowGraphTools.getAugmentedPaths(ng,fg.getFlowSource(),fg.getFlowTarget());

    Enumeration enum=vec.elements();
    int quell,ziel,cap;
    ziel=((Integer)enum.nextElement()).intValue();
    while(enum.hasMoreElements()){
    quell=ziel;
    cap=((Integer)enum.nextElement()).intValue();
    ziel=((Integer)enum.nextElement()).intValue();
    fg.setFlowAt(quell,ziel,fg.getFlowAt(quell,ziel)+cap);
    //fg.setCapacityAt(quell,ziel,fg.getCapacityAt(quell,ziel)-cap);
    }
    notifyObservers(IFlowGraphOptimizer.NOTIFICATION_RAISED);
    }


    Dateien und Javadoc     top

    Javadoc online
    Online Applet
    Alle Dateien als Zip-Archiv