Algorithmen: Schleifen von außen zugänglich machen

[Naryxus]

Hallo,

ich belege gerade eine Vorlesung zu effizienten Graphenalgorithmen.

Wir haben zu jedem Algorithmus eine Beschreibung, wie dieser abstrakt funktioniert und zusätzlich eventuelle Implementationshinweise.
Bei vielen Algorithmen steht dabei, dass diese sinnvoll als Iterator (nicht unbedingt im Sinne der Java-Iterator-API) implementiert werden können. Zusätzlich dazu wird empfohlen, dass die Schleife "von außen zugänglich" gemacht werden soll, dass der Aufrufende also zusätzlichen Code dem Algorithmus hinzufügen kann.

Ich denke da an folgendes Beispiel (für denjenigen, der ein wenig Erfahrung mit Graphen-Algorithmen hat):
Der Ford-Fulkerson zum Finden des maximalen Flusses eines Fluss-Netzwerks verwendet intern eine Depth-First-Search. Die Bedingung, dass ein Knoten bei der Depth-First-Search gesehen wird, ist, dass das Ziel der aktuell betrachteten ausgehenden Kante eines Knotens noch nicht gesehen wurde.
Für den Ford-Fulkerson muss aber beispielsweise die Depth-First-Search dahingehend verändert werden, dass ein Knoten nur dann gesehen werden darf, wenn der Fluss auf der Kante noch erhöht werden kann.

Um redundanten Code zu vermeiden, suche ich jetzt nach einer Möglichkeit dem Basis-Algorithmus Depth-First-Search "von außen" also vom Algorithmus Ford-Fulkerson aus die Bedingung hinzuzufügen, dass er einen Knoten nur dann sehen soll, wenn die Kapazität der Kante zwischen den Knoten größer als der Fluss dieser Kante ist.

Momentan implementiert meine Depth-First-Search das Interface Iterator<Node>. Liefert also immer den als nächsten gesehenen Knoten zurück. Ein erster Gedanke von mir war gewesen, die gerade traversierte Kante zurückzuliefern und dann darauf zu entscheiden, ob die Kante tatsächlich traversiert wird. Das funktioniert aber dahingehend nicht, dass der Endknoten dieser Kante ja dann schon auf den Stack gelegt wurde und zwangsläufig behandelt wird. Und jetzt dann noch auf den Stack zuzugreifen und den Knoten wieder vom Stack zu löschen, halte ich auch nicht für die beste Lösung.

Vielleicht habt ihr ja eine Idee,
Naryxus

 

[JCODA]

Klingt für mich nach einer Anwendung von Interfaces. An allen Stellen, die flexibel sein sollen, rufst du eine Methode eines Interfaces auf.
Für ein Spezialfall implementiert dann eine Klasse dieses Interface.

Ich kann dir genauer helfen, wenn du Code bereitstellst, und markierst, wo was flexibel sein soll. Ggf. auch zwei Varianten, einmal nur DFS und einmal FF-Algo.

 

[Tobse]

Ich habe keine Erfahrung mit Graphenalgorithmen; aber von dem was du schreibst sieht für mich nach einem Anwendungsfall für java.util.Predicate aus. Wenn du das in die Depth-First-Search integrierst könnte ein Predicate, welches im Ford-Fulkerson-Algorithmus definiert ist, weitere Bedingungen für die Auswahl von Knoten definieren. Tatsächliche "Logik" lässt sich so dem Algorithmus aber nicht hinzufügen (und ich bezweifle auch, dass das abstrakt möglich ist).

 

[AndyJ]

Dieser Thread ist zwar schon etwas alt, aber vielleicht ist es ja noch interessant: man kann durchaus Code in einen Algorithmus einfuegen, das ganze ist bekannt als Template-Method Pattern: http://www.oodesign.com/template-method-pattern.html
Eine Superklasse definiert abstrakte Methoden und implementiert einen Algorithmus der diese Methoden an den Einfuegepunkten aufruft. Eine Subclass muss dann nur noch den gewuenschten, individuallen Part einfuegen.
Andy

 

[Naryxus]

Hey, entschuldigt bitte, dass ich mich erst jetzt wieder melde. Ich hatte die letzten Tage doch einiges zu tun.

aber von dem was du schreibst sieht für mich nach einem Anwendungsfall für java.util.Predicate aus.

Ja, das ist keine schlechte Idee, um zumindest die Auswahl von Knoten zu steuern. Vielleicht mal ein kleines Code-Beispiel (ganz rudimentäre Depth-first search):

private Stack<Node> stack;

//private int minimum = Integer.MAX_VALUE

public Node next() {
   Node v = this.stack.peek();
   DirectedEdge edge = this.nextEdge(v); //Markierung 1

   if(edge == null) {
      v.finish();
      this.stack.pop();
   } else {
      edge.walk();
      if(edge.to().notSeen()) { //Markierung 2
         //this.minimum = Math.min(this.minimum, edge.weighting());
         edge.to().see();
         this.stack.push(edge.to());
      }
   }
   return v;
}

Hier wurde jetzt schon die API des Iterators von Java verwendet (es fehlt natürlich die hasNext()-Methode).
Bei Markierung 1 könnte dann prinzipiell das Predicate übergeben werden, um die Auswahl der nächsten ausgehenden Kante eines Knotens zu bestimmen.

Allerdings wäre es jetzt beispielsweise für einen anderen Algorithmus wichtig in der Bedingung bei Markierung 2 eine Gewichtung der Kante zu speichern, um das Minimum dieser Gewichtungen für alle erreichbaren Knoten herauszufinden. Das heißt der auskommentierte Ausdruck müsste in dieser "modifizierten" Depth-first search eingefügt werden.

man kann durchaus Code in einen Algorithmus einfuegen, das ganze ist bekannt als Template-Method Pattern: http://www.oodesign.com/template-method-pattern.html

Wenn ich Andy und das Pattern auf die schnelle richtig verstanden habe, würde das gehen, indem ich den vorigen Code in einer abstrakten Oberklasse schreiben würde und für den auskommentierten Ausdruck eine Methode "doForUnseenNode()" abstrakt definieren würde und den auskommentierten Ausdruck dann in dieser Methode implementieren würde?

Dann stellt sich mir gleich die nächste Frage: In der Basisversion sind diese zusätzlichen Methoden alle "leer". Würde ich dann für den Basisalgorithmus eine statische Factory-Methode schreiben, die mir eine Instanz dieses Algorithmus mit leeren Methoden zurückliefert? Ansonsten müsste ich mir ja doppelte Arbeit machen, wenn ich tatsächlich nur die Standardversion haben möchte. Dann würde ich den Algorithmus abstrakt schreiben und dann eine konkrete Klasse davon erben lassen? Ich hoffe, das war halbwegs verständlich...

Grüße,
Naryxus

 

[mrBrown]

Wenn ich Andy und das Pattern auf die schnelle richtig verstanden habe, würde das gehen, indem ich den vorigen Code in einer abstrakten Oberklasse schreiben würde und für den auskommentierten Ausdruck eine Methode "doForUnseenNode()" abstrakt definieren würde und den auskommentierten Ausdruck dann in dieser Methode implementieren würde?

Man kann anstatt abstrakte Methoden einzuführen, den Algorithmus genau so lassen, und nur an der markierten Stelle eine zusätzliche Methode aufrufen, die dann zB die Kante übergeben bekommt. In der Basisversion ist die dann einfach leer.
Extendende Klassen können dann, wenn sie's brauchen, diese eine Methode überschreiben (und darin dann zB das Gewicht speichern).

Bei Markierung eins kann man #nextEdge auch überschreibbar machen. Ford-Fulkerson überschreibt dann diese Methode, dass nur den Fluss-verbessernde zurückgegeben werden.

Dann stellt sich mir gleich die nächste Frage: In der Basisversion sind diese zusätzlichen Methoden alle "leer". Würde ich dann für den Basisalgorithmus eine statische Factory-Methode schreiben, die mir eine Instanz dieses Algorithmus mit leeren Methoden zurückliefert? Ansonsten müsste ich mir ja doppelte Arbeit machen, wenn ich tatsächlich nur die Standardversion haben möchte. Dann würde ich den Algorithmus abstrakt schreiben und dann eine konkrete Klasse davon erben lassen? Ich hoffe, das war halbwegs verständlich...

Wenn man's so macht wie oben ist die Basisklasse auch konkret (nämlich normale DFS), die extendenden fügen dann nur zusätzliches hinzu

 

[Tobse]

man kann durchaus Code in einen Algorithmus einfuegen, das ganze ist bekannt als Template-Method Pattern: http://www.oodesign.com/template-method-pattern.html

@AndyJ und @mrBrown Ja, das kann man so machen IMHO ist das hier aber unangebracht, da Komposition Vererbung fast immer vorgezogen werden sollte.

Allerdings wäre es jetzt beispielsweise für einen anderen Algorithmus wichtig in der Bedingung bei Markierung 2 eine Gewichtung der Kante zu speichern, um das Minimum dieser Gewichtungen für alle erreichbaren Knoten herauszufinden. Das heißt der auskommentierte Ausdruck müsste in dieser "modifizierten" Depth-first search eingefügt werden.

Was soll denn mit dem Minimum dann passieren? Prinzipiell könntest du hier einen Consumer<Node> mitgeben:

private List<Consumer<Node>> onNoteSeenListeners = new LinkedList<>();

// ...
public Node next(){
   Node v =this.stack.peek();
   DirectedEdge edge =this.nextEdge(v);//Markierung 1

   if(edge ==null){
      v.finish();
     this.stack.pop();
   }else{
      edge.walk();
     if(edge.to().notSeen()){//Markierung 2
         edge.to().see();
         onNodeSeenListeners.forEach(l -> l.consume(edge));
         this.stack.push(edge.to());
     }
   }
   return v;
}

Aber ohne den Verwendungszweck vom Minimum zu kennen kann man das schwer sagen.


Ich denke gerade auch:
Wenn du den Algorithmus so stark aufbohrst, dass man ihn an allen Ecken und Enden konfigurieren kann, entstehen dir zwei deftige Nachteile:

• der Algorithmus ist nicht mehr performant, weil dauernd Methoden aufgerufen und Daten hin- und her geschoben werden
• der Code für die spezifischen Algorithmen wird sehr komplex

Da ist es IMHO das geringere Übel, 2-3 Variationen des selben Algorithmus zu pflegen.

 

[Naryxus]

Man kann anstatt abstrakte Methoden einzuführen, den Algorithmus genau so lassen, und nur an der markierten Stelle eine zusätzliche Methode aufrufen, die dann zB die Kante übergeben bekommt. In der Basisversion ist die dann einfach leer.

Danke schonmal für deine Antwort.
Je nach dem, wie sich der Thread noch so weiter entwickelt, werde ich den Ansatz mal testen.

Was soll denn mit dem Minimum dann passieren?

Naja schaut man sich zum Beispiel den Algorithmus Ford-Fulkerson an (ich weiß nicht, inwieweit dir Graphenalgorithmen geläufig sind) sucht man für den fluss-erhöhenden Pfad das minimum aller residualen Kapazitäten auf diesem Pfad. Und um zu verhindern, dass man später noch einmal über die Kanten auf diesem Pfad iterieren muss, könnte man schon während der Tiefensuche Buch über die Kapazitäten führen.
Das mit dem Minimum soll aber eigentlich auch nur ein Beispiel dafür sein, was ich gerne von den Implementierungen meiner Algorithmen hätte.

Prinzipiell könntest du hier einen Consumer<Node> mitgeben:

private List<Consumer<Node>> onNoteSeenListeners = new LinkedList<>();
[...]
         onNodeSeenListeners.forEach(l -> l.consume(edge));
[...]

Würde das nicht aber die Komplexität des Algorithmus sprengen? Weil ich dann zusätzlich in einer nochmal über alle gesehenen Knoten iterieren würde, was im worst-case O(|V|) ist und dementsprechend die Komplexität der Schleife O(|V|*|A|) ist?

Ich denke gerade auch:
Wenn du den Algorithmus so stark aufbohrst, dass man ihn an allen Ecken und Enden konfigurieren kann, entstehen dir zwei deftige Nachteile:

• der Algorithmus ist nicht mehr performant, weil dauernd Methoden aufgerufen und Daten hin- und her geschoben werden
• der Code für die spezifischen Algorithmen wird sehr komplex

Da ist es IMHO das geringere Übel, 2-3 Variationen des selben Algorithmus zu pflegen.

Ja in der realen Laufzeit magst du da recht haben, dass das ständige Aufrufen die tatsächliche Laufzeit (Dauer) verlängert. Aber wenn man davon ausgeht, dass die einzelnen "offenen" Code-Teile eine Komplexität von O(1) haben, wird wenigstens die Komplexität des Algorithmus nicht verändert.

Mit den Variationen des Algorithus arbeite ich momentan. Natürlich geht das. Allerdings hatte ich zuvor gedacht, dass es (wahrscheinlich subjektiv) schöner ist, wenn man möglichst wenig redundanten Code hat. Vor allem vor dem Hintergrund, dass ich den Code in einem knappen Monat präsentieren muss.

Grüße

 

[mrBrown]

Würde das nicht aber die Komplexität des Algorithmus sprengen? Weil ich dann zusätzlich in einer nochmal über alle gesehenen Knoten iterieren würde, was im worst-case O(|V|) ist und dementsprechend die Komplexität der Schleife O(|V|*|A|) ist?

Wie du selbst schon sagst, das wird gegen O(1) gehen Für größere Graphen gibts ja nicht mehr Consumer, die den grad besuchten Knoten wissen wollen.

wird wenigstens die Komplexität des Algorithmus nicht verändert.

Die für den Programmierer allerdings schon

Mit den Variationen des Algorithus arbeite ich momentan. Natürlich geht das. Allerdings hatte ich zuvor gedacht, dass es (wahrscheinlich subjektiv) schöner ist, wenn man möglichst wenig redundanten Code hat. Vor allem vor dem Hintergrund, dass ich den Code in einem knappen Monat präsentieren muss.

Naja, wenn dein Code grundsätzlich schon läuft, probier einfach mal beide Methoden aus, verlieren kannst du ja dann nichts

 

[Tobse]

Würde das nicht aber die Komplexität des Algorithmus sprengen? Weil ich dann zusätzlich in einer nochmal über alle gesehenen Knoten iterieren würde, was im worst-case O(|V|) ist und dementsprechend die Komplexität der Schleife O(|V|*|A|) ist?

Nein; in der Praxis ist onNodeSeenListeners ja maximal 1-2 Elemente groß; das forEach ist von der mathematischen Komplexität des Algorithmus her in jedem Fall ein O(1).

Mit den Variationen des Algorithus arbeite ich momentan. Natürlich geht das. Allerdings hatte ich zuvor gedacht, dass es (wahrscheinlich subjektiv) schöner ist, wenn man möglichst wenig redundanten Code hat.

Das stimmt auf jeden Fall.

Naja, wenn dein Code grundsätzlich schon läuft, probier einfach mal beide Methoden aus, verlieren kannst du ja dann nichts

+1 - @TE: Wenn die mega modulare Variante nicht zu langsam ist, kannst du sie ja nehmen, auch wenn optimierte Versionen schneller wären.