zwei adjazenzlisten für jeden knoten eines graphen sinnvoll?

[0x7F800000]

Hey Leute!

Eine kleine theoretische Frage hätte ich hier an euch.
Zum Hintergrund: Ich musste vor kurzem eine allzweck-graphenklasse für allgemeine "experimente" erstellen. Hab da ohne lange zu überlegen mich für die Implementierung mit einer Adjazenzenliste entschieden, für jeden Knoten wird einfach gespeichert, zu welchen anderen knoten eine gerichtete Kante führt.
Das hat zwar einigermaßen akzeptabel funktioniert, allerdigs gefällt mir daran nicht, dass es so aufwendig ist, eingehende kanten zu finden. Dazu muss ich ja alle anderen einträge bei allen anderen Knoten (also im prinzip den gesammten Graphen) durchgehen, nur um paar doofe eingehende kanten zu finden.

Wozu das gut sein soll, eingehende kanten zu suchen, sei erstmal dahingestellt. Zum beispiel ist mir keine bessere Möglichkeit eingefallen, einen gerichteten Graphen auf schwachen wegzusammenhang zu testen (oder geht's ohne?).
Ferner sollte es imho möglich sein, den Graphen ohne jeglichen Aufwand auf die "ungerichtete" Perspektive umzustellen (wie soll ich zB sonst die Wege für ego-shooter bots darstellen, die sich plötzlich levitationsbonus geschnappt haben, und jetzt alle wände hochkommen, von den man sonst nur runterfallen kann?)

Fragen:
Ist es sinnvoll, für jeden Knoten statt den ausgehenden sowohl ausgehende als auch eingehende verbindungen zu speichern? Dann wäre zwar jede Kante zwei mal drin, aber irgendwie wäre es imho wesentlich leichter zweischen der gerichteten und der ungerichteten Perspektive umzuschalten.
Bei Kanten die in beide Richtungen verlaufen wäre es aber dann wiederum total bescheuert: ein und dieselbe Verbindung müsste schon 4 mal gespeichert werden. 🙁

Soll ich evtl nicht direkte Referenzen auf nachbarknoten, sondern referenzen auf kanten abspeichern?

Oder gibt es eine bessere Möglichkeit, auf die ich bisher nicht gekommen bin?

Vielen Dank im voraus.
greetz, Andrey

 

[0x7F800000]

also, nur um das etwas anschaulicher zu machen:

Momentan tendiere ich am ehesten zur folgenden Darstellung meines Graphen:

class Graph<T>{
   
   //jeder vertex speichert alle eingehende und ausgehende referenzen zu nachbarvertices
   private class Vertex{
      public Set<Vertex> incomingEdges, outcomingEdges;
   }

   //graph speichert einen haufen Vertices, die mit irgendeinem Objekt von Typ T identifiziert werden
   Map<T,Vertex> adjacency$List$; //wobei "List" absolut fehl am Platze ist
}

also, mir erscheint diese Konstruktion nicht zu sinnfrei, aber irgendwie weicht die doch recht stark von den "klassischen & üblichen" Ansätzen mit Adjazenzmatrizen/Adjazenzlisten ab, deswegen kommt mir diese meine Idee so suspekt vor ???:L

 

[0x7F800000]

nee, wenn ich mir noch vorstelle, dass ich irgendwann auch kantengewichte oder Alphabet-Symbole für Automaten mitspeichern muss, erscheint mir meine zweite idee mit referenzierten kanten sogar noch sinnvoller:

class Graph<VertexContent,EdgeContent>{
   private class Edge{
      EdgeContent content; //gewicht, symbole, namen, länge, whatever
      Vertex a,b;  //gejointe Knoten
      boolean fromAtoB, fromBtoA;   //Richtung
   }

   private class Vertex{
      VertexContent content; //name der Stadt, Typ der egoshooter-waffe, Automatenzustand
      int inDeg,outDeg,totalDeg; //nützliche infos für suche von eulerpfaden u.ä.
      HashSet<Edge> edges; //eingehende und ausgehende kanten zusammen
   }

   HashSet<Vertex> vertices; //knoten des graphen als member-variable des Graphen
}

Aber das da weicht schon sowas von stark von den Klassischen Ansätzen ab, dass ich jetzt noch verunsicherter bin 😳

 

[hdi]

Wenn du es mit einer Adjazenzmatrix machen willst, dann wieso diese nicht als stinknormales 2d-array in der Klasse Graph:

 int[][] adjMatrix

Oder willst du da mit den Knoten irgendwelche Kunststücke machen, die das updaten des Arrays dann zu aufwendig machen? Ansonsten für jeden Knoten eine Map <Knotennummer,Kantenkapazität> von Nachbarn, und ganz simpel:
Ist Kapazität <0 ist das eine eingehende Kante, ist sie >=0 eine ausgehende

 

[0x7F800000]

Hey hdi.
Danke für die Antwort erstmal.
Adjazenzmatrix kommt imho nicht in Frage, zumindest nicht als int[][] Array, weil das ein gigantischer Speicheraufwand für sehr wenige kanten wäre. Wenn man sich Karten von Städten und Ländern anschaut, dann sieht man ja auch sofort, dass die Graphen sehr dünn besetzt sind. Wenn zB jeder Knoten ~5 Kanten berührt, dann bräuchte ich bei 1000 Knoten grad mal 5000 einträge. Bei einer Adjazenzmatrix wären das aber schon 1000000 Einträge, das ist meistens nicht akzeptabel 😉

Wenn man aber mit irgendwelchen sparse-matrizen herumhantiert, dann ist bei den die zugriffszeit auch nur in zeilen gut, aber nicht wenn man "irgendwas aus der Spalte x" haben will. Dann steht man vor demselben problem, das nur anders umbenannt ist.


Der zweite vorschlag ist schon wesentlich näher an meiner idee, das ist im prinzip genau das was ich gemeint habe: JEDER knoten speicher alle eingehenden UND ausgehenden kanten, und markiert die irgendwie entsprechend. Da ich jedoch nicht nur "gewicht" der Kante, sondern evtl was ganz anderes speichern will, werde ich wohl eine separate kanten-klasse brauchen. Wenn mir bis 20:00 nicht besseres einfällt, implementiere ich das dann genau so 🙂

 

[hdi]

Das ist mal ne geile Herangehensweise 😛

Na dann viel Glück, T-minus 54

 

[Marco13]

Ja, hatte da vor einiger Zeit auch mal was gebastelt. Wie schon hier http://www.java-forum.org/de/viewtopic.php?t=80871&highlight= unten angedeutet, schien mir bei Ungerichteten/Gerichteten Graphen immer das Problem aufzutreten, dass das Liskov'sche Substitutionsprinzip verletzt wird (und nicht nur in philosophisch-throretischem Sinne, sondern so, dass irgendwas tatsächlich nicht funktioniert....)

Am Ende habe ich mich für eine Implementierung entschieden, bei der ich die wenigsten Bauchschmerzen hatte, und die eine API hervorgebracht hat, die erschreckend ähnlich zu http://www.jgrapht.org/javadoc/org/jgrapht/Graph.html ist. Effektiv ist das (nicht nicht genau SO, aber sinngemäß (hatte das noch ein bißchen aufgedröselt)) bei mir jetzt sowas wie

class Graph
{
    Map<Vertex, Set<Edge>> outgoing =...
    Map<Vertex, Set<Edge>> incoming =...
}

Das kann man ganz vernünftig verwalten, und es wird nur gespeichert, was gespreichert werden muss. (Es ist jetzt also eine Adjazenzliste, die nach eingehenden/ausgehenden Kanten getrennt ist - aber Graph ist nur ein Interface, d.h. Alternativimplementierungen mit einer Adjazenzmatrix wären natürlich möglich - die sind aber für Mehrfachkanten nicht so toll...), und bei der direkten Implementierung mit den Maps und Sets hat man hat O(1)-Zugriff auf die eingehenden, oder ausgehenden, oder alle Kanten eines Vertex.

Dass man manchmal einen gerichteten Graphen als ungerichtet ansehen will, und umgekehrt, hatte mich auch ein bißchen ins Schleudern gebracht. Die Verwandlung ist ja nicht immer eineindeutig möglich. Man kann kann zwar
ungerichtet -> gerichtet -> ungerichtet -> gerichtet...
umwandeln sooft man will, aber wenn man mit einem gerichteten Graphen anfängt, kommt bei
gerichtet -> ungerichtet -> gerichtet
ggf. ein anderer Graph raus, als am Anfang. Deswegen macht es IMHO nur Sinn, eine ungerichtete Ansicht auf den Originalgraphen abzuliefern (den Originalgraphen aber unverändert zu lassen). Aber ich glaube, egal, wie man es macht: Man kann immer etwas "kaputtmachen". (Wenn man einen gerichteten Graphen ungerichtet macht, und dort eine (ungerichtete) Kante einfügt, was soll dann passieren? :autsch: (Das kann man beliebig komplizierter machen....)). Das geht dann bis hin zu solchen Fragen, wie "wann sind zwei Edges 'equal'?" (Z.B. ist (a,b) bei einem ungerichteten Graphen eigentlich equal zu (b,a) - sowas sauber einfließen zu lassen, ist schwierig... man kann dann ggf. getrennte Klassen machen (Arc oder Edge), aber das macht das ganze an anderen Stellen wieder unflexibel und unnötig kompliziert...)

 

[0x7F800000]

Hallo Marco13!

Das was du an code hier gepostet hast ist für mich ein wenig mysteriös: was genau ist "Vertex" in deinem code? Ist es das, was der benutzer von draußen kennt, etwa "Zustand eines Automaten" ? Oder ist das irgendeine innere klasse?
Falls es der erste Fall ist: wo speicherst du dann die ganzen (nützlichen?) rein graphentheoretischen zusatzinformationen ab?
Falls es der zweite Fall ist: wie suchst du in deiner Map nach demjenigen Vertex<X> der zum von draußen übergebenen argument x vom Typ X passt?

Danke für die Erinnerung an mehrfachkanten: das muss ich auch noch irgendwie ins modell reinbekommen, hab gar nicht dran gedacht :###

Deswegen macht es IMHO nur Sinn, eine ungerichtete Ansicht auf den Originalgraphen abzuliefern (den Originalgraphen aber unverändert zu lassen)

joah, hatte ich auch vor. Nichts an internen Informationen über das "wahre Wesen" des Graphen geht dadurch verloren. Die andere Richtung erscheint mir irgendwie Sinnfrei, da ich intern ja eh alles gerichtet abspeichern will.

Was das einfügen von ungerichteten/gerichteten kanten angeht, da werde ich mir noch was überlegen müssen. wahrscheinlich werde ich solche sachen an die interne implementierung anpassen und alles als gerichtet betrachten, oder evtl. einen boolean-flag hinzufügen, wo das explizit angegeben werden kann.

 

[0x7F800000]

Gibt's eigentlich irgendwo eine Haschende Datenstruktur, die keine Schlüssel mitspeichert, oder muss ich mir jetzt selbst eine schreiben? ???:L

 

[hdi]

Meinst du jetzt sowas wie Buckets?

 

[0x7F800000]

hmm, nein.
Was ich gerne hätte wäre eine Datenstruktur speziell für "Wrapper mit Extra-Informationen"
Am Beispiel Knoten:

class Vertex<VertexContent>{
   private int additionalInfo;
   private VertexContent content;
   public VertexContent getContent(){...}
}

//ich will jetzt knoten in einer art "hash-map ohne schlüsseln" abspeichern
//sodass ich diese dort anhand des Inhaltes raussuchen kann. 
//Dazu muss man dieser Datenstruktur erzählen, 
//wie aus dem Vertex der Schlüssel herauszubekommen ist d.h irgendsowas in der Art:

UnknownStructure<VertexContent,Vertex> s=new UnknownStructure<VertexContent,Vertex(100,
   new KeyGetter<VertexContent,Vertex>(){
      VertexContent getKey(Vertex v){
         return v.getContent();
      }
   }
);

//der schlüssel vom typ VertexContent wird in den knoten gepackt
VertexContent c=...irgendwoher von draußen
Vertex v=new Vertex(c); //<---- c ist nun hier drin schon enthalten


//jetzt kann ich dadrin die knoten putten (Ohne schlüssel anzugeben, der ist ja IM KNOTEN DRIN)

s.put(v);

//aber rausholen will ich die immer noch anhand des schlüssels c vom typ VertexContent

s.get(c); //soll mir v rausspucken

Also, zu implementieren wär's nicht schwieriger als eine stinknormal HashMap, aber irgendwie scheint es das nicht zu geben, und ich hab grad leider nicht genug zeit um's selbst standardkonform zu bauen. :?

Irgendwelche Vorschläge? 😉

 

[didjitalist]

wenn dein Vertex im grunde nur meta informationen zu einem VertexContent mitschleppen soll, dann überschreib hashCode und equals von Vertex doch so, dass es an die äquivalenten methoden von VertexContent delegiert.

 

[0x7F800000]

und weiter? :bahnhof: gibt es etwa irgendeine Struktur, die ein befehl a'la "gib mir ein Objekt x, das diesem Objekt y gleich ist" bereitstellt? ???:L

 

[didjitalist]

nö, weil so eine struktur reichlich sinnfrei wäre 😉

halte deine idee mit der öffentlichen entkopplung von knoten und inhalt für nicht ganz ausgereift. diverse knoten können ja durchaus dasselbe objekt referenzieren. und spätestens dann rennst du in probleme.

wenn du eine allgemeine klasse gestalten willst, dann verwende ein am besten ein Vertex interface oder eine abstrakte klasse. nur so kannst du gewährleisten, dass eine anständige entkopplung von knoten und nutzlast möglich ist.

 

[0x7F800000]

nö, weil so eine struktur reichlich sinnfrei wäre 😉

joah, da hast du irgendeinen hack an einer nicht existierenden datenstruktur vorgeschlagen 😉

diverse knoten können ja durchaus dasselbe objekt referenzieren. und spätestens dann rennst du in probleme.

Wieso das? Knoten ist der Content mit extrainformationen. Derselbe Content => derselbe Knoten. Sehe da keine schwierigkeiten.

wenn du eine allgemeine klasse gestalten willst, dann verwende ein am besten ein Vertex interface oder eine abstrakte klasse. nur so kannst du gewährleisten, dass eine anständige entkopplung von knoten und nutzlast möglich ist.

Du meinst ich soll die vertex classe für den Benutzer nach außen freigeben, damit er "draußen" selbst an Vertices rumbasteln darf? Das wäre zwar eine Lösung, aber imho eine nicht allzu schöne und ziemlich unsicher. Bei LinkedList o.ä. darf der benutzer ja auch nicht an listenelementen rumfummeln, das ist dann auch gut so, und irgendwelche "Listenelement-Interfaces" sind d doch auch nicht drin, wenn ich mich recht erinnere.


So wie es aussieht muss ich mir die Struktur einfach selber basteln. Halb so wild, aber das verschieb ich mal auf morgen 🙂

 

[Marco13]

was genau ist "Vertex" in deinem code? Ist es das, was der benutzer von draußen kennt, etwa "Zustand eines Automaten" ?

Ja. Alles kann als Vertex betrachtet werden.

Falls es der erste Fall ist: wo speicherst du dann die ganzen (nützlichen?) rein graphentheoretischen zusatzinformationen ab?

Jetzt wirst DU mysteriös: Welche "Zusatzinformationen" hat ein Vertex in einem Graphen, die NICHT aus der Menge der eingehenden/ausgehenden Kanten hervorgeht? (D.h. bei mir werden alle "Zusatzinformationen" mit Hilfe einer Map im Graphen selbst gespeichert - was im Moment NUR die Kantenmengen sind)

Deswegen macht es IMHO nur Sinn, eine ungerichtete Ansicht auf den Originalgraphen abzuliefern (den Originalgraphen aber unverändert zu lassen)

joah, hatte ich auch vor. Nichts an internen Informationen über das "wahre Wesen" des Graphen geht dadurch verloren. Die andere Richtung erscheint mir irgendwie Sinnfrei, da ich intern ja eh alles gerichtet abspeichern will.

Hm - es gibt aber schon Situationen, wo man eine gerichtete Ansicht auf einen ungerichteten Graphen haben will...

Was das einfügen von ungerichteten/gerichteten kanten angeht, da werde ich mir noch was überlegen müssen. wahrscheinlich werde ich solche sachen an die interne implementierung anpassen und alles als gerichtet betrachten, oder evtl. einen boolean-flag hinzufügen, wo das explizit angegeben werden kann.

Ja, egal wie man es macht, irgendwo stolpert man :? An einigen Stellen hatte ich da was gebastelt, um die Stolpersteine zu minimieren, aber ganz ausräumen kann man sie IMHO kaum. (Einige der Punkte sind da z.B. die Interface-mäßige Trennung zwischen "ImmutableGraph" und "MutableGraph", und eine explizite Bereitstellung der Topologie-Information in einer "TopologyInfo", die keine Modifikationen zuläßt, und nur eine Ansicht auf die Daten im eigentlichen Graphen ist, und Methoden zum "Umschalten" zwischen gerichteter/ungerichteter Ansicht bietet, ...)

 

[0x7F800000]

Jetzt wirst DU mysteriös: Welche "Zusatzinformationen" hat ein Vertex in einem Graphen, die NICHT aus der Menge der eingehenden/ausgehenden Kanten hervorgeht?

hmmm. Naja, den ein- und ausgangsgrad kannst du natürlich direkt an den kantenlisten abfragen. Aber für die anzahl der tatsächlich vorhandenen nachbarknoten müsste man schon wieder die listen durchgehen und schauen, wo die kanten herkommen, das dauert und ist ätzend :roll: Oder wenn man zum beispiel ein paar flags mitspeichern will, ob etwa der Graph zerfällt, wenn der knoten entfernt wird (ich bin ein böser bot, will nachschub abschneiden: lohnt es sich eine Bombe auf die Brücke XY abzuwerfen, oder kommt der feind auch ohne diese bestens zurecht?) Das ist eine imho durchaus wichtige rein graphentheoretische eigenschaft, die sich nicht in O(1) aus der anzahl der ausgehenden kanten berechnen lässt.

Hm - es gibt aber schon Situationen, wo man eine gerichtete Ansicht auf einen ungerichteten Graphen haben will...

Ich verstehe überhaupt nicht was es sein soll. Intern will ich doch eh alles in gerichteter form abspeichern, d.h. für jede ungerischtete gibts zwei gerichtete. Wenn das einer sehen will: bitte sehr.

Ja, egal wie man es macht, irgendwo stolpert man :? An einigen Stellen hatte ich da was gebastelt, um die Stolpersteine zu minimieren, aber ganz ausräumen kann man sie IMHO kaum. (Einige der Punkte sind da z.B. die Interface-mäßige Trennung zwischen "ImmutableGraph" und "MutableGraph", und eine explizite Bereitstellung der Topologie-Information in einer "TopologyInfo", die keine Modifikationen zuläßt, und nur eine Ansicht auf die Daten im eigentlichen Graphen ist, und Methoden zum "Umschalten" zwischen gerichteter/ungerichteter Ansicht bietet, ...)

Mir wird immer klarer, dass es da doch mehr zu basteln gibt, als mir nach der implementierung der ersten version vorkam :roll:

 

[Marco13]

Aber für die anzahl der tatsächlich vorhandenen nachbarknoten müsste man schon wieder die listen durchgehen und schauen, wo die kanten herkommen, das dauert und ist ätzend :roll:

Hmja - ich bin da unrsprünglich ziemlich ... distanziert und pragmatisch rangegangen: Es gibt verschiedenen Operationen, die (für verschiedene Graphenalgorithmen) zeitkritisch sind. Und die allgemeinste zeitkritische Operation ist: Iteriere über alle Kanten zu einem gegebenen Vertex. (Prinzipiell, ganz abstrakt, würde nichts dagegen sprechen, dort über alle Kanten zu iterieren, und es dem Aufrufer die Überprüfung zu überlassen, ob das eine engehende oder ausgehende Kante ist - alles andere ist nur für die Bequemlichkeit, weil man eben "oft" NUR die ausgehenden Kanten braucht...). Die Operation "Iteriere über alle Nachbarknoten eines Vertex" ist in diesem Sinne schon wieder "speziell". Wenn man nur EINEN speziellen Graphen implementieren will, auf dem EIN spezieller Algorithmus läuft, dessen Laufzeit crucial davon abhängt, dass man zu einem Knoten alle Nachbarknoten findet, dann könnte man natürlich eine spezielle Implementierung verwenden

class SpecialGraph
{
    private Set neighbors[] = ...

    public Set getNeighbors(Vertex vertex)
    {
        return neighbors[vertex.getIndex()]; // Indiziert - ist ja speziell, und soll schnell sein....
    }

aber für den allgemeinen Fall würde man das eben nachbauen

class SpecialGraph extends DefaultGraph
{
    public Set getNeighbors(Vertex vertex)
    {
        Set result = new HashSet();
        for (Edge edge : incoming(vertex)) { result.add(edge.getVertex(0)); }
        for (Edge edge : outging(vertex)) { result.add(edge.getVertex(1)); }
        return result;
    }

Oder allgemeiner gesprochen: Es gibt zumindest sicher keine "Silver Bullet"-Implementierung, die für ALLE denkbaren Anwendungen optimal ist... (auch wenn obige "getNeighbors"-Methode zumindest "gut" ist, in dem Sinne, dass die Laufzeit "nur" vom Knotengrad abhängt, und nicht etwa von der Menge ALLER vertices oder edges...)

Oder wenn man zum beispiel ein paar flags mitspeichern will, ob etwa der Graph zerfällt, wenn der knoten entfernt wird (ich bin ein böser bot, will nachschub abschneiden: lohnt es sich eine Bombe auf die Brücke XY abzuwerfen, oder kommt der feind auch ohne diese bestens zurecht?) Das ist eine imho durchaus wichtige rein graphentheoretische eigenschaft, die sich nicht in O(1) aus der anzahl der ausgehenden kanten berechnen lässt.

Ja, diese "assoziierten" Informationen... Da gibt es natürlich verschiedene Möglichkeiten. Entweder, der Algorithmus, der diese Information berechnet oder benötigt ist NUR für Graphen anwendbar, die die speziellen vertices enthalten

void computeBombTargets(Graph<? extends VertexWithFlag> graph)
{
    for (VertexWithFlag vertexWithFlag : graph.vertices()) vertexWithFlag.setFlag(true);
    ....
}

oder man speichert solche zusätzlichen Informationen wieder in einer Map. Z.B. hatte ich etwa für die Maximum-Flow Berechnung (sinngemäß!!!) sowas gemacht wie

float computeMaxFlow(Graph<Object> graph, Map<Edge, Float> flowValues)
{
    ....
        flowValues.put(currentEdge, currentFlow);
}

aber damit bin ich auch nocht nicht 100% zufrieden :? (Diese allgemeine Graphensache hatte ich eigentlich nur in spezieller Form für ein spezielles Problem gebraucht, aber dabei (aus Prinzip :wink: ) schon versucht, das möglichst allgemein zu halten, damit ich das dann wirklich als universelle Graphenbibliothek verwenden kann. Für den speziellen Fall ist der aktuelle Stand OK, und damit habe ich jetzt (am speziellen Problem) weitergearbeitet, aber "fertig" (und "bis zum Ende durchdacht") ist diese allgemeine Graphenbibliothek natürlich noch nicht...)

Ich verstehe überhaupt nicht was es sein soll. Intern will ich doch eh alles in gerichteter form abspeichern, d.h. für jede ungerischtete gibts zwei gerichtete. Wenn das einer sehen will: bitte sehr.

Hmja, aber wenn bei einem ungerichteten Graphen für jede Kante praktisch zwei gerictete Kanten existieren, stellen sich auch wieder viele Fragen. Z.B. ist der Knotengrad dann ja abhängig davon, ob man den Graphen gerade als gerichteten oder als ungerichteten Graphen betrachtet. Eigentlich ist es nur eine Kante, es werden aber zwei gespeichert - der Knotengrad ist also eigentlich 1, aber wenn der Aufrufer den Graphen als gerichteten Graphen ansieht, ist er doch 2 ... oder?... :? (es ist wirklich nicht leicht...)

Mir wird immer klarer, dass es da doch mehr zu basteln gibt, als mir nach der implementierung der ersten version vorkam :roll:

Ja, wie schon angedeutet: Wenn man was spezielles macht, ist es einfach. Wenn man bestimmte "Verhaltensweisen" des Graphen (beim Verändern, bei der Directed/Undirected-Sache, bei Knotengraden und den ganzen anderen Detailfragen) schlicht in der API postuliert, kann man auch schnell was zusammenbasteln. Aber wenn es theoretisch sauber und praktisch (universell!) verwendbar sein soll, wird es IMHO sehr schnell sehr kompliziert...