Java: Weighted Directed Graph, wo die Vertices OBJEKTE sind

Question

Ich muss einen gewichteten Digraph erstellen. Die Implementierungen, die ich gesehen habe, stellen die Scheitelpunkte als einfache Ganzzahlen dar, und die Kanten werden mit Adjazenzlisten dargestellt. Allerdings brauche ich Scheitelpunkte, die durch Objekte einer benutzerdefinierten Klasse dargestellt werden. Mit diesem Graphen muss ich typische Operationen durchführen (speziell Dijkstra).

Meine Idee war, die Objekte irgendwie als Ganzzahlen darzustellen, aber ich würde nicht wissen, wie man mit einer Hash-Funktion kommt, die beide Wege (d. H. Vertex zu int und int zu Vertex) konvertiert werden kann.

Answer 1

Wenn Sie Scheitelpunkte wirklich als (eindeutige) Ganzzahlen im Diagramm darstellen möchten, können Sie eine ArrayList verwenden, um von Scheitelpunkten zu Ihren Objekten zu mappen, und eine HashMap<MyObject, Integer>, um zurück zu mappen. Sie könnten dieses Paar in Ihre eigene Klasse einpacken, indem Sie getIndex() und getElement() (wie unten angegeben) angeben, was die Lesbarkeit verbessern könnte.

Das sagte, warum nicht einfach http://jgrapht.org oder eine ähnliche Bibliothek verwenden?

public class IndexMap<T> { 
    private List<T> elements = new ArrayList<>(); 
    private Map<T, Integer> indices = new HashMap<>(); 

    public int add(T element) { 
    int index = elements.size(); 
    elements.add(element); 
    indices.put(element, index); 
    return index; 
    } 

    public int getIndex(T element) { 
    Integer index = indices.get(element); 
    return index == null ? -1 : index; 
    } 

    public T getElement(int index) { 
    return elements.get(index); 
    } 

Wenn Sie nicht brauchen (wieder) verwenden, um eine vorbestehende integer-basierte grafische Darstellung und kann nicht eine Bibliothek verwenden, könnten Sie alternativ Ihre eigene Vertex-Klasse als speichert ein Objekt implementieren:

class Vertex<T> { 
    T element; 
    List<Vertex<T>> edges = new ArrayList<>(); 

    Vertex(T element) { 
    this.element = element; 
    } 

    void addEdge(Vertex<t> to) { 
    edges.add(to); 
    } 

    ... 
}