Collections Methode (Knoten hinzufügen) für Graphen

Diskutiere Methode (Knoten hinzufügen) für Graphen im Java Basics - Anfänger-Themen Bereich.
T

TobiCodi

Hallo zusammen!
Folgendes ist mein Problem:
Ich möchte einem Graphen (-> Nachbarschaftsliste) Knoten hinzufügen, und dafür eine Methode schreiben. Diese Methode bekommt einen Key und erstellt einen neuen Knoten mit genau dem übergebenen Key. Dann soll dieser neue Knoten an das Ende der Knotenliste des Graphen eingefügt werden.
Letzteres bereitet mir Schwierigkeiten, so sieht mein Code aktuell aus:

Java:
package graph;

public class Graph<K extends ObjectId, W extends Sum<W> & Comparable<W>> {

    public ListItem<Node<K, W>> head;
   
    public void addNode(K key) {
        Node <K,W> myNode = new Node<K,W>(key);
        //TODO: add myNode zur Knotenliste des Graphen
    }
}
Hier noch ein paar Einzelheiten:
Jeder Graph besitzt einen Verweis auf seinen ersten Knoten (also ähnlich wie LinkedList).
Der Graph soll aus verkettete Liste von Knoten realisiert werden, dafür benutze ich die ListItem-Klasse:
Java:
package graph;

public class ListItem<T> {
    public T key;
    public ListItem<T> next;
   
    public ListItem(T key) {
        this.key = key;
    }
   
    public ListItem(T key, ListItem<T> next) {
        this.key = key;
        this.next = next;
    }
   
}
Jeder Knoten selbst besitzt zusätzlich eine verkettete Liste von Kanten. Dazu habe ich folgende zwei Klassen:
Java:
package graph;

public class Node<K extends ObjectId, W extends Sum<W> & Comparable<W>> {
    public K key;
    public ListItem<Edge<K, W>> headEdges;

    public Node(K key) {
        this.key = key;
    }
}
Man sieht, dass jeder Node (Knoten) einen Key, sowie den Kopf auf seine Kantenliste (headEdges) besitzt.
Jede Kante hingegen besitzt einen Verweis auf den Nachbar (neighbour), sowie das Kantengewicht (weight).
Java:
package graph;

public class Edge<K extends ObjectId, W extends Sum<W> & Comparable<W>> {
   
    public Node<K, W> neighbour;
    public W weight;
   
    public Edge(Node<K, W> neighbour, W weight) {
        this.neighbour = neighbour;
        this.weight = weight;
    }

}
Gerade die Kanten werden bei der Methode public void connectNodes(String idFrom, String idTo, W weight){...} essenziell, da ich hier die Knoten über Kanten verbinden will.
Hier ist mein Plan:
1. Erstelle eine neue Kante newEdge
2. Verweise newEdge auf den Knoten, der die OhektId idTo besitzt (Attribut neighbour)
3. Füge dann newEdge an das Ende der Kantenliste des Knotens mit ObjectId idFrom ein.


Vielen Dank für jede Antwort!!
LG TobiCodi
 
T

TobiCodi

Naja, die Knotenliste ist ja nur eine LinkedList. Geht es jetzt nur darum, den Knoten ans Ende einer verketteten Liste einzufügen?
Ja darum geht es.
Allerdings darf für das einfügen nur die Zeiger, also das Attribut next, der Listenelemente sowie den Kopf der jeweiligen Liste verwendet werden.
 
mihe7

mihe7

OK, wenn die verkettete Liste leer ist, zeigt head noch auf keinen Knoten sondern auf null.
Code:
null
^
|
head
D. h. das Einfügen in eine leere Liste besteht einfach darin, head auf den einzufügenden Knoten, nennen wir ihn mal myNode, zeigen zu lassen. Der neue Knoten hat keinen Nachfolgerknoten, so dass next==null gilt. Es ergibt sich folgendes Bild:

Code:
       next
myNode ----> null
^
|
head
Das Einfügen ist in die leere Liste ist im Code trivial:
Java:
    public void addNode(K key) {
        Node <K,W> myNode = new Node<K,W>(key);
        if (head == null) {
            head = myNode;
            return;
        }
Was ist nun, wenn die Liste nicht leer ist? Natürlich zeigt dann head auf einen Knoten (und nicht auf null) und es kann mehrere Knoten geben, die über next miteinander verknüpft sind. Der letzte Knoten hat keinen Nachfolger, so dass next == null gilt. Bild:
Code:
      next        next        next
node1 ----> node2 ----> node3 ----> null
^
|
head
Zum Einfügen am Ende muss man offensichtlich so lange durch die Knotenliste wandern, bis man an den letzten Knoten (für den next == null gilt) kommt. Der einzufügende Knoten (myNode) wird dann zum Nachfolger des letzten Knotens:

Code:
      next        next        next         next
node1 ----> node2 ----> node3 ----> myNode ----> null
^
|
head
(EDIT: falches Bild reinkopiert, korrigiert)
Wie hangelt man sich nun der Liste entlang? Dafür verwendet man einen "Zeiger", den man zunächst mit head initialisiert, ich nenne diesen mal current:
Code:
      next        next        next
node1 ----> node2 ----> node3 ----> null
^
|
current
D. h. current entspricht dem aktuellen Knoten. Wie kommt man nun zum nächsten Knoten? Naja, indem man current auf seinen Nachfolger, also current.next, setzt.
Code:
      next        next        next
node1 ----> node2 ----> node3 ----> null
             ^
             |
           current
Das wiederholt man natürlich nur so lange, bis es keinen Nachfolger mehr gibt, d. h. current.next == null gilt. Dann entspricht current dem letzten Knoten in der Liste.

Code:
      next        next        next
node1 ----> node2 ----> node3 ----> null
                          ^
                          |
                       current
Jetzt kann man den Nachfolger von current auf den einzufügenden Knoten setzen, also current.next = myNode zuweisen.

Insgesamt ergibt sich folgende Methode:
Java:
    public void addNode(K key) {
        Node <K,W> myNode = new Node<K,W>(key);
        if (head == null) {
            head = myNode;
            return;
        }

        Node<K,W> current = head;
        while (current.next != null) {
            current = curent.next;
        }
        current.next = myNode;
    }
 
T

TobiCodi

Woooow unglaublich stark @mihe7 , vielen vielen Dank :)!
Ich hab das einfügen nun vollständig verstanden, nur noch eine Frage dazu:
Mein head ist doch ein ListItem, siehe hier:
Java:
public ListItem<Node<K, W>> head;
Wenn ich nun einen Zeiger namens current vom Typ Node<K,W> erstelle und mit "head" initialisiere gibt das ein Problem.

Ich hab jetzt mal Node als ListItem gemacht, wie es oben verlangt wird. Damit musste ich aber "key" beim erstellen des myNode casten, ist das so richtig, sieht ziemlich wild aus o_O:D:
Java:
public void addNode(K key) {
        ListItem<Node<K, W>> myNode = new ListItem<Node<K, W>>((Node<K, W>) key);
        if (head == null) {
            head = myNode;
            return;
        }

        ListItem<Node<K, W>> current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = myNode;
    }
 
T

TobiCodi

Die am Anfang schon erwähnte Methode
public void connectNodes(String idFrom, String idTo, W weight)
macht mir nun Probleme.
Grundsätzlich möchte ich mit dieser Knoten über Kanten verbinden.

Folgende Überlegungen habe ich gemacht:
1. Erstelle eine neue Kante "myEdge"
2. Verweise myEdge auf den Knoten, der die ObjectId idTo besitzt. Die ObjectId kann ich mit der gegebenen Methode (String getObjectId()) abfragen.
3. Suche den Knoten, dessen ObjectId == idFrom
4. Gehe in die Kanten(!)-liste von dem gefundenen Knoten und füge myEdge an das Ende ein.

Hier mein z.T. Pseudocode artiges Gebilde :D:
(die kommentierten Zahlen entsprechen den oben aufgezählten Schritten)

Java:
public void connectNodes(String idFrom, String idTo, W weight) {

        // 1.
        ListItem<Edge<K,W>> myEdge = new ListItem<Edge<K,W>>((Edge<K, W>) weight);

        // 2.
        myEdge.key.neighbour = theNodeWith.getObjectId==idTo; 


        // 3. 
        while(bla.getObjectId != idFrom) {
            bla = bla.next;
        }
        bla = blubb;        

        // 4. 
        kantenListeVon_theNodeWith.add(myEdge);
    }
 
mihe7

mihe7

public void connectNodes(String idFrom, String idTo, W weight) {
Warum String? Wo soll der herkommen? Müsste das nicht K sein?

Folgende Überlegungen habe ich gemacht:
Beschreib das ein wenig abstrakter, dann wird es einfacher:

1. Suche im Graphen den Knoten (sourceNode) mit der Quell-ID
2. Suche im Graphen den Knoten (destNode) mit der Ziel-ID
3. Erstelle eine neue Kante (edge) für den Knoten destNode un dem gegebenen Gewicht
4. Füge edge zur Kantenliste von sourceNode hinzu

Offensichtlich brauchst Du an Position 1 und 3 eine Funktion, die den Knoten zu einem Schlüssel aus der Knotenliste liefert.

Java:
private Node<K,W> findNodeById(K id) {
    if (head == null || id == null) {
        return null;
    }    
    ListItem<Node<K,W>> current = head;
    while (current != null) {
        Node<K,W> node = current.key;
        if (id.equals(node.key)) {
            return node;
        }
        current = current.next;
    }
}
Für 4. bietet sich eine Methode in Node an:
Java:
private ListItem<Edge<K,W>> head = null;

public void addEdge(Edge<K,W> edge) {
    ListItem<Edge<K,W>> newItem = new ListItem<>(edge);
    if (head == null) {
        head = newItem;
    }
    
    ListItem<Edge<K,W>> current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = newItem;
}
Der Code ist praktisch identisch zum Hinzufügen eines Nodes. Das ist ein deutliches Zeichen dafür, dass man umstrukturieren sollte. Das mache ich jetzt aber nicht, sonst wird das zu unübersichtlich.

Damit lässt sich nun in Graph schreiben:
Java:
public void connectNodes(K idFrom, K idTo, W weight) {
    Node<K,W> source = findNodeById(idFrom);
    Node<K,W> dest = findNodeById(idTo);
    if (source != null && dest != null) {
        source.addEdge(new Edge<K,W>(dest, weight));
    }
}
Das entspricht fast wörtlich den Punkten 1 bis 4.
 
T

TobiCodi

Warum String? Wo soll der herkommen? Müsste das nicht K sein?
Ja das ist schon richtig. In meiner Aufgabendokumentation steht:
"Wir wollen uns nicht auf einen konkreten Typ für die Knoten eines Graphen festlegen, wir stellen lediglich die Bedingung, dass die Knotenklasse das bereits vorgegebene ObjectId-Interface implementiert. Dieses Interface stellt lediglich nur eine Methode (String getObjectId()) zur Verfügung. Die Rückgabe dieser Methode ist ein String, mit dem man das Objekt eindeutig identifizieren kann."

Und der Methodenkopf
Java:
public void connectNodes(String idFrom, String idTo, W weight) {
ist vorgegeben...
 
T

TobiCodi

Warum String? Wo soll der herkommen? Müsste das nicht K sein?



Beschreib das ein wenig abstrakter, dann wird es einfacher:

1. Suche im Graphen den Knoten (sourceNode) mit der Quell-ID
2. Suche im Graphen den Knoten (destNode) mit der Ziel-ID
3. Erstelle eine neue Kante (edge) für den Knoten destNode un dem gegebenen Gewicht
4. Füge edge zur Kantenliste von sourceNode hinzu

Offensichtlich brauchst Du an Position 1 und 3 eine Funktion, die den Knoten zu einem Schlüssel aus der Knotenliste liefert.

Java:
private Node<K,W> findNodeById(K id) {
    if (head == null || id == null) {
        return null;
    }  
    ListItem<Node<K,W>> current = head;
    while (current != null) {
        Node<K,W> node = current.key;
        if (id.equals(node.key)) {
            return node;
        }
        current = current.next;
    }
}
Für 4. bietet sich eine Methode in Node an:
Java:
private ListItem<Edge<K,W>> head = null;

public void addEdge(Edge<K,W> edge) {
    ListItem<Edge<K,W>> newItem = new ListItem<>(edge);
    if (head == null) {
        head = newItem;
    }
  
    ListItem<Edge<K,W>> current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = newItem;
}
Der Code ist praktisch identisch zum Hinzufügen eines Nodes. Das ist ein deutliches Zeichen dafür, dass man umstrukturieren sollte. Das mache ich jetzt aber nicht, sonst wird das zu unübersichtlich.

Damit lässt sich nun in Graph schreiben:
Java:
public void connectNodes(K idFrom, K idTo, W weight) {
    Node<K,W> source = findNodeById(idFrom);
    Node<K,W> dest = findNodeById(idTo);
    if (source != null && dest != null) {
        source.addEdge(new Edge<K,W>(dest, weight));
    }
}
Das entspricht fast wörtlich den Punkten 1 bis 4.
Stark! Ich arbeite das mal durch.. :)

Bei deiner findNodeById-Methode passt was mit dem return node; nicht, der Compiler meint, dass ein return-statement fehlt.

Außerdem müsste man nach Aufgabenvorgabe hier dann findNodeById(String id) anstatt ...(K id) schreiben, ebenso bei den anderen Methoden oder?

private ListItem<Edge<K,W>> head = null;
Hier sagt der Compiler: "Duplicate field Graph<K,W>.head". Aufgrund von Zeile 5: public ListItem<Node<K, W>> head;.

Liebe Grüße und nochmals tausend Dank für diese unglaubliche Hilfe!
 
Zuletzt bearbeitet:
mihe7

mihe7

der Compiler meint, dass ein return-statement fehlt.
Da hat er recht. Am Ende fehlt ein return null;

Außerdem müsste man nach Aufgabenvorgabe hier dann findNodeById(String id)anstatt ...(K id) schreiben, ebenso bei den anderen Methoden oder?
Ja und jeweils mit getObjectId() vergleichen.

Hier sagt der Compiler: "Duplicate field Graph<K,W>.head". Aufgrund von Zeile 5: public ListItem<Node<K, W>> head;.
Der Spaß gehört in die Klasse Node, da hast Du headEdges geschrieben. Ich habe mit der Zeile nur andeuten wollen, dass das bei mir nur "head" heißen würde :)
 
T

TobiCodi

Okay!
Check!
Ja und jeweils mit getObjectId() vergleichen.
Was meinst du mit getObjectId vergleichen?

Der Spaß gehört in die Klasse Node, da hast Du headEdges geschrieben. Ich habe mit der Zeile nur andeuten wollen, dass das bei mir nur "head" heißen würde
Okay wenn ich also das was bei dir head (in Bezug der Edge) heißt, ich einfach zu headEdges umbenenne passt das. Also so:
Java:
private ListItem<Edge<K,W>> headEdges = null;

    public void addEdge(Edge<K,W> edge) {
        ListItem<Edge<K,W>> newItem = new ListItem<>(edge);
        if (headEdges == null) {
            headEdges = newItem;
        }
        
        ListItem<Edge<K,W>> current = headEdges;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newItem;
    }
(ich darf in meiner Node Klasse nämlich nichts ändern..)

Dann gäbe es noch das Problem, dass in der Zeile
Java:
 source.addEdge(new Edge<K,W>(dest, weight));
aus der connectNode-Methode (hier nochmals ganz):
Java:
public void connectNodes(String idFrom, String idTo, W weight) {
         Node<K,W> source = findNodeById(idFrom);
            Node<K,W> dest = findNodeById(idTo);
            if (source != null && dest != null) {
                source.addEdge(new Edge<K,W>(dest, weight));
            }
    }
Das ".addEdge" rot untermalt ist: "The method addEdge(Edge<K,W>) is undefined for the type Node<K,W>".

VLG und Gute Nacht :)
 
mihe7

mihe7

T

TobiCodi

Hier die ganze Graph-Klasse:

Java:
package graph;

public class Graph<K extends ObjectId, W extends Sum<W> & Comparable<W>> {

    public ListItem<Node<K, W>> head;
    
    public void addNode(K key) {
        ListItem<Node<K, W>> myNode = new ListItem<>(new Node<K, W>(key));
        if (head == null) {
            head = myNode;
            return;
        }

        ListItem<Node<K, W>> current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = myNode;
    }
    
    private Node<K, W> findNodeById(String id) {
        if (head == null || id == null) {
            return null;
        }   
        ListItem<Node<K,W>> current = head;
        while (current != null) {
            Node<K, W> node = current.key;
            if (id.equals(node.key)) {
                return node;
            }
            current = current.next;
        }
        return null;
    }
    
    private ListItem<Edge<K,W>> headEdges = null;

    public void addEdge(Edge<K,W> edge) {
        ListItem<Edge<K,W>> newItem = new ListItem<>(edge);
        if (headEdges == null) {
            headEdges = newItem;
        }
        
        ListItem<Edge<K,W>> current = headEdges;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newItem;
    }
    
    
    public void connectNodes(String idFrom, String idTo, W weight) {
         Node<K,W> source = findNodeById(idFrom);
            Node<K,W> dest = findNodeById(idTo);
            if (source != null && dest != null) {
                source.addEdge(new Edge<K,W>(dest, weight));
            }
    }
}
 
mihe7

mihe7

Der Teil
Java:
    private ListItem<Edge<K,W>> headEdges = null;

    public void addEdge(Edge<K,W> edge) {
        ListItem<Edge<K,W>> newItem = new ListItem<>(edge);
        if (headEdges == null) {
            headEdges = newItem;
        }
        
        ListItem<Edge<K,W>> current = headEdges;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newItem;
    }
gehört nicht in die Klasse Graph, sondern in den Node.
 
T

TobiCodi

Der Teil
Java:
    private ListItem<Edge<K,W>> headEdges = null;

    public void addEdge(Edge<K,W> edge) {
        ListItem<Edge<K,W>> newItem = new ListItem<>(edge);
        if (headEdges == null) {
            headEdges = newItem;
        }
       
        ListItem<Edge<K,W>> current = headEdges;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newItem;
    }
gehört nicht in die Klasse Graph, sondern in den Node.
Achsooo Aber ich darf die Node-Klasse nicht verändern :/ gibts da auch einen anderen Weg?
 
mihe7

mihe7

OK, das heißt in Deiner Node-Klasse ist headEdges public.

In der Methode ist headEdges die Kurzform für this.headEdges, wobei this die Referenz auf das Node-Objekt darstellt, für das die Methode aufgerufen wurde.

Der Code oben ist also nichts anderes als

Java:
    public void addEdge(Edge<K,W> edge) {
        ListItem<Edge<K,W>> newItem = new ListItem<>(edge);
        if (this.headEdges == null) {
            this.headEdges = newItem;
        }
      
        ListItem<Edge<K,W>> current = this.headEdges;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newItem;
    }
Da this einfach eine Referenz auf ein Node-Objekt ist, kannst Du hier auch eine beliebig andere Verwenden, z. B. eine, die Du als Parameter bekommen hast:

Java:
    public void addEdge(Node<K,W> node, Edge<K,W> edge) {
        ListItem<Edge<K,W>> newItem = new ListItem<>(edge);
        if (node.headEdges == null) {
            node.headEdges = newItem;
        }
      
        ListItem<Edge<K,W>> current = node.headEdges;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newItem;
    }
Weil headEdges in Node public ist, kannst Du die Methode dann auch in Graph unterbringen. Aus einem Aufruf node.addEdge(edge); wird dann addEdge(node, edge);.
 
Thema: 

Methode (Knoten hinzufügen) für Graphen

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben