Java: Wie stellt man Graphen dar?

Question

Ich implementiere einige Algorithmen, um mich selbst über Graphen zu unterrichten und wie man damit arbeitet. Was würden Sie empfehlen, ist der beste Weg, das in Java zu tun? Ich dachte etwas in der Art:

public class Vertex { 

    private ArrayList<Vertex> outnodes; //Adjacency list. if I wanted to support edge weight, this would be a hash map. 

    //methods to manipulate outnodes 
} 

public class Graph { 
    private ArrayList<Vertex> nodes; 
    //algorithms on graphs 
} 

Aber ich habe im Grunde nur das erfunden. Gibt es einen besseren Weg?

Außerdem möchte ich es in der Lage sein, Variationen auf Vanille Graphen zu unterstützen wie Digraphe, gewichtete Kanten, Multigraphen usw.

Answer 1

Wenn Sie gewichtete Kanten und Multigraphen benötigen, könnten Sie eine andere Klasse Rand hinzufügen möchten .

Ich würde auch empfehlen, Generics zu verwenden, um die Angabe zu ermöglichen, welche Unterklasse von Vertex und Edge derzeit verwendet werden. Zum Beispiel:

public class Graph<V extends Vertex> { 
List<V> vertices; 
... 
} 

Wenn es um die Graphenalgorithmen Implementierung könnten Sie auch Schnittstellen für Ihre Graphenklassen definieren, auf denen die Algorithmen arbeiten können, so dass Sie mit unterschiedlichen Implementierungen der tatsächlichen Diagrammdarstellung rumspielen können . Zum Beispiel, einfache Grafiken, die gut verbunden sind, könnten besser durch einen adjacency matrix, spärlicher Graphen realisiert werden könnten durch adjacency lists dargestellt werden - es hängt alles ...

BTW Der Aufbau solcher Strukturen effizient eine ziemliche Herausforderung, Könntest du uns vielleicht ein paar Details darüber geben, für welche Art von Job du sie benutzen möchtest? Für komplexere Aufgaben schlage ich vor, dass Sie sich die verschiedenen Java-Graph-Bibliotheken anschauen, um sich inspirieren zu lassen.

Answer 2

Werfen Sie einen Blick auf die http://jung.sourceforge.net/doc/index.html Grafikbibliothek. Sie können immer noch üben, Ihre eigenen Algorithmen zu implementieren (vielleicht zuerst die erste oder die erste Tiefensuche), aber Sie müssen sich keine Gedanken über die Erstellung der Diagrammstruktur machen.

Answer 3

Vor einiger Zeit hatte ich das gleiche Problem und habe meine eigene Implementierung. Was ich dir vorschlage ist, eine andere Klasse zu implementieren: Edge. Dann wird ein Vertex eine Liste von Kanten haben.

public class Edge { 
    private Node a, b; 
    private directionEnum direction;  // AB, BA or both 
    private int weight; 
    ... 
} 

Es funktionierte für mich. Aber vielleicht ist das so einfach. Es gibt diese Bibliothek, die Ihnen vielleicht helfen kann, wenn Sie in den Code schauen: http://jgrapht.sourceforge.net/

Answer 4

Ich würde graphviz hoch empfehlen, wenn Sie an den Punkt kommen, an dem Sie Ihre Graphen darstellen möchten.

Und seine Begleiter: Werfen Sie einen Blick auf Laszlo Szathmary's GraphViz class, zusammen mit notugly.xls.

Answer 5

Schon zur Zeit dieser Frage, vor mehr als 3 Jahren, existierte Sage (was völlig kostenlos ist) und war ziemlich gut in der Graphentheorie. Aber im Jahr 2012 handelt es sich um das beste Graphentheorie-Tool, das es gibt. So hat Sage bereits eine riesige Menge an graphischem Material eingebaut, einschließlich anderer freier und Open-Source-Sachen, die da draußen sind. Es ist also einfach, mit verschiedenen Dingen herumzuspielen, um mehr zu lernen, da keine Programmierung erforderlich ist.

Und wenn Sie sich auch für den Programmierteil interessieren, ist Sage Open Source, so dass Sie jeden Code sehen können, der bereits existiert.Und zweitens können Sie jede gewünschte Funktion neu programmieren, wenn Sie wirklich üben wollen, oder Sie können der Erste sein, der etwas programmiert, das noch nicht existiert. In letzterem Fall können Sie sogar diese neue Funktionalität einreichen und Sage für alle anderen Benutzer verbessern.

Zu diesem Zeitpunkt ist diese Antwort möglicherweise nicht so nützlich für das OP (seit es 3 Jahre), aber hoffentlich ist es nützlich für jeden, der diese Frage in der Zukunft sieht.

Answer 6

Warum nicht die Dinge einfach halten und eine adjacency matrix oder eine adjacency list verwenden?

Answer 7

Adjazenzliste Die Implementierung von Graph eignet sich zur Lösung der meisten graphenbezogenen Probleme.

Java-Implementierung der gleichen ist here auf meinem Blog.

Answer 8

class Graph<E> { 
    private List<Vertex<E>> vertices; 

    private static class Vertex<E> { 
     E elem; 
     List<Vertex<E>> neighbors; 
    } 
} 

Answer 9

class Vertex { 
    private String name; 
    private int score; // for path algos 
    private boolean visited; // for path algos 
    List<Edge> connections; 
} 

class Edge { 
    private String vertex1Name; // same as Vertex.name 
    private String vertex2Name; 
    private int length; 
} 

class Graph { 
    private List<Edge> edges; 
} 

Answer 10

Jeder Knoten eindeutig benannt und weiß, wer an sie angeschlossen ist. Die Liste der Verbindungen ermöglicht die Verbindung eines Knotens mit einer beliebigen Anzahl anderer Knoten.

Jede Verbindung ist gerichtet, hat einen Anfang und ein Ende und ist gewichtet.

public class Edge { 
    public Node start; 
    public Node end; 
    public double weight; 
} 

Ein Diagramm ist nur Ihre Sammlung von Knoten. Anstelle von List<Node> betrachten Map<String, Node> für schnelle Suche nach Namen.

public class Graph { 
    List<Node> nodes; 
} 

Answer 11

Eine einfache Darstellung geschrieben von 'Robert Sedgwick' und 'Kevin Wayne' ist bei http://algs4.cs.princeton.edu/41graph/Graph.java.html

Erläuterung erhältlich von der oben genannten Seite kopiert.

Die Graph-Klasse repräsentiert ein ungerichteter Graph von Vertices genannt 0 bis V - 1.

Es unterstützt die folgenden zwei Hauptoperationen: eine Kante des Graphen hinzuzufügen iterieren über alle der Scheitelpunkte neben einem Scheitelpunkt. Es bietet auch Methoden für die Rückgabe der Anzahl der Scheitelpunkte V und die Nummer der Kanten E. Parallele Kanten und Eigenschleifen sind erlaubt. Vereinbarungs eine Selbstschleife v-v erscheint in der Adjazenzliste von v zweimal und trägt zwei in dem Maße von v.

Diese Implementierung verwendet eine Adjazenzlisten-Repräsentation, die ist ein vertex-indexiertes Array von Bag-Objekten. Alle Operationen benötigen konstante Zeit (im schlimmsten Fall), mit Ausnahme von Iteration über die Scheitelpunkte neben einem gegebenen Scheitelpunkt, was Zeit proportional zur Anzahl solcher Scheitelpunkte dauert.