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

TobiCodi

Mitglied
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
 

mihe7

Top Contributor
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;
    }
 

TobiCodi

Mitglied
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;
    }
 

TobiCodi

Mitglied
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

Top Contributor
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.
 

TobiCodi

Mitglied
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...
 

TobiCodi

Mitglied
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

Top Contributor
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 :)
 

TobiCodi

Mitglied
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

Top Contributor
Okay wenn ich also das was bei dir head (in Bezug der Edge) heißt, ich einfach zu headEdges umbenenne passt das.
Ja.

Java:
Das ".addEdge" rot untermalt ist: "The method addEdge(Edge<K,W>) is undefined for the type Node<K,W>".
Das gibt keinen Sinn, denn das ist ja gerade die Methode
Java:
    public void addEdge(Edge<K,W> edge) {

Vielleicht stellst Du mal den kompletten Code rein.
 

TobiCodi

Mitglied
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

Top Contributor
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.
 

TobiCodi

Mitglied
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

Top Contributor
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);.
 

TobiCodi

Mitglied
Perfekt, verstehe ich :)

Noch eine allgemeinere Frage:
In der Zeile 28 (8. Zeile der findNodeById-Methode) wird (node.key) hellblau unterstrichen, das hatte ich noch nie haha, Compiler sagt "Unlikely argument type for equals(): K seems to be unrelated to String".
Was sagt das mir?

Hier nochmals der ganze (überarbeitete) Code:
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; //die zeile brauch ich ja dann nicht mehr (?)

     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;
        }
    
    
    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) {
                addEdge(source,new Edge<K,W>(dest, weight));
            }
    }
}
 

TobiCodi

Mitglied
Okay danke! Aber wie bereits erwähnt:
Wie genau meinst du "mit getObjectId() vergleichen"?
Ich hätte das mal so gemacht:
(siehe Änderung in der findNodeById-Methode)
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)); //Erstelle neuen Knoten "myNode" mit dem gegebenen key.
        if (head == null) {        //wenn noch kein Knoten existiert, so ist myNode der erste Node.
            head = myNode;
            return;
        }
        ListItem<Node<K, W>> pointerNode = head;    //andernfalls erstelle einen zeiger-node als head.
        while (pointerNode.next != null) {        //iteriere durch alle knoten: solange der jeweils nächste knoten noch exisitert, gehe eins weiter
            pointerNode = pointerNode.next;
        }
        pointerNode.next = myNode;    //ist das ende erreicht, gehe noch eins weiter, füge da dann myNode ein
    }

    private Node<K, W> findNodeById(String id) {    //hier geht es darum, den Knoten zu returnen, dessen id der gesuchten id gleicht.
        if (head == null || id == null) { //Wenn kein Knoten existiert, kann ich kein Knoten finden
            return null;
        }
        ListItem<Node<K, W>> pointerNode = head;    //erstelle einen  zeiger-node, der am anfang head ist, und durch die knoten iteriert
        while(pointerNode != null) {
            Node<K, W> node = pointerNode.key;        //erstelle den gesuchten knoten als den key von pointerNode.
            if (id.equals(node.key.getObjectId())) {                //HIER GETOBJECTID ÄNDERUNG //wenn die gesuchte id, der node-id gleicht, wird diese returnt
                return node;
            }
            pointerNode = pointerNode.next;
        }
        return null;
    }
 
    // private ListItem<Edge<K,W>> headEdges = null; //die zeile brauch ich ja dann nicht mehr (?)

    public void addEdge(Node<K, W> node, Edge<K, W> edge) {     //diese Methode fügt eine Kante und einen Kn
        ListItem<Edge<K, W>> newEdge = new ListItem<>(edge);
        if (node.headEdges == null) {
            node.headEdges = newEdge;
        }
        ListItem<Edge<K, W>> pointerEdge = node.headEdges;
        while (pointerEdge.next != null) {
            pointerEdge = pointerEdge.next;
        }
        pointerEdge.next = newEdge;
    }
    

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

        Node<K, W> startNode = findNodeById(idFrom);
        Node<K, W> finishNode = findNodeById(idTo);
        if (startNode != null && finishNode != null) {
            addEdge(startNode, new Edge<K, W>(finishNode, weight));
        }
    }

    public void disconnectNodes(String idFrom, String idTo) {

        Node<K, W> startNode = findNodeById(idFrom);
        Node<K, W> finishNode = findNodeById(idTo);
        //TODO .......

    }

Sorry für die Kommentare, die sind zwischenzeitlich für mich zum Verständnis drin..
LG
 

TobiCodi

Mitglied
Hallo!
Nun geht es mit diesen beiden Methoden weiter :rolleyes::

1.) "disconnectNodes(String idFrom, String idTo)", bei welcher ich eine Kante zwischen Knoten(mit idFrom) und Knoten (mit idTo) entfernen kann. 2.) "removeNode(String id), bei welcher ich einen Knoten mit der ObjectId id entfernen möchte. Folgendes sind meine (hoffentlich vielversprechende) Ansätze ;).

Java:
public void removeNode(String id) {

        // 1) Wenn head der zu löschende Knoten ist, so wird dieser einfach übersprungen
        if(head.key.key.getObjectId()==id) {
            head = head.next;
        }
        
        // 2) Wenn nicht, dann ist (vlt) der Knoten irgendwo mitten in der Liste
        //    Dafür: Erstelle Pointer, dieser bleibt ein Element vor dem zu suchenden Element stehen (dessen .next wird zu .next.next)
        ListItem<Node<K, W>> pointerNode = head;
        while(pointerNode.next.key.key.getObjectId() != id) { //Solange der Knoten nach dem Knoten nicht der zu löschende Knoten ist: gehe eins weiter
            pointerNode = pointerNode.next;
        }
        pointerNode.next = pointerNode.next.next;
        pointerNode = head;
        
        // 3) Lösche alle Kanten, die auf diesen Knoten verweisen (-> disconnectNodes(idFrom, idTo)):
        disconnectNodes(null, id);
    }
und noch für die Methode, die Kanten zwischen zwei Knoten entfernen soll:

Java:
public void disconnectNodes(String idFrom, String idTo) {
        
        Node<K, W> startNode = findNodeById(idFrom); //Finde den Knoten, von dem die Kante ab geht.
        
        while(startNode.headEdges.next.key.toString() != idTo) { //Durchsuche alle vom startNode abgehende Kanten nach der Kante, die zum Knoten (mit idTo) geht.
            startNode.headEdges = startNode.headEdges.next;
        }
        startNode.headEdges.next = startNode.headEdges.next.next; //Überspringe dann genau diese gesuchte Kante in der Liste.
        
    }

Wichtig ist hierbei, dass nach dem Aufruf dieser Methode der Zugriff auf alle anderen Kanten der jeweiligen Kantenlisten immer noch möglich sein soll. Ebenso übrigens mit der Methode, die Knoten entfernt:
Nach dem Aufruf der Methode soll der Zugriff auf alle anderen Knoten sowie Kanten immer noch möglich sein.

Viele liebe Grüße!!
 

mihe7

Top Contributor
Nun geht es mit diesen beiden Methoden weiter :rolleyes::
Hier wird man aber von nichts verschont ;)

Ok, ernsthaft: die Überlegungen sind gar nicht schlecht. Es fehlt noch die Behandlung des Falls, dass removeNode mit einer id aufgerufen wird, die in keinem Knoten vorkommt. Bei disconnectNodes gibt findNodeById keinen Sinn - Du hast ja keine ID (null). Tatsächlich brauchst Du hier nur über alle Knoten in der Knotenliste iterieren und für jeden Knoten die Verbindung zum Zielknoten entfernen.
 

TobiCodi

Mitglied
Hier wird man aber von nichts verschont ;)
Hahahah jaa das stimmt wohl..
Es fehlt noch die Behandlung des Falls, dass removeNode mit einer id aufgerufen wird, die in keinem Knoten vorkommt
Dieser Fall muss ich laut Aufgabendokumentation nicht behandeln :).
Bei disconnectNodes gibt findNodeById keinen Sinn - Du hast ja keine ID (null)
Das verstehe ich nicht ganz. Du meinst hier die disconnectNodes-Methode, und nicht den disconnectNodes-Aufruf in der removeNode-Methode gell?
Ich soll ja hier genau die Kante von Knoten A (hat ObjectId = idFrom) nach Knoten B (hat ObjectId = idTo) entfernen. Warum dann für JEDEN Knoten die Verbindung zum Zielknoten entfernen. Das würde ja ALLE Kanten entfernen oder bin ich grad blind?

Würde ich es nun stur nach dir machen sähe die disconnectNodes-Methode so aus:
Code:
public void disconnectNodes(String idFrom, String idTo) {
ListItem<Node<K, W>> pointerNode = head; // Mein Zeiger, der über alle Knoten laufen soll
        while(pointerNode.next != null) {          // Lässt den Zeiger über alle Knoten laufen
            
            //TODO: Verbindung zum Zielknoten entfernen (wie ohne findNodeById ?)
            
            pointerNode = pointerNode.next;
        }
        
    }

Bedenke: Ich hab genau diese Ids (idFrom, idTo) durch Parameter fix im Methodenkopf gegeben.
 

mihe7

Top Contributor
Das verstehe ich nicht ganz. Du meinst hier die disconnectNodes-Methode, und nicht den disconnectNodes-Aufruf in der removeNode-Methode gell?
Jein, es geht eigentlich um die Kombination. Du rufst disconnectNodes(null, id); auf, also ist idFrom == null. Dann gibt der Aufruf von findNodeById(idFrom) keinen Sinn.

Du könntest die Schleife in removeNode reinnehmen und dann disconnectNodes aufrufen:

Java:
        pointerNode = head; // Mein Zeiger, der über alle Knoten laufen soll      
        while(pointerNode != null) {          // Lässt den Zeiger über alle Knoten laufen
            String idFrom = pointerNode.key.key.getObjectId();
            disconnectNodes(idFrom, id);           
            pointerNode = pointerNode.next;
        }
 

TobiCodi

Mitglied
Du könntest die Schleife in removeNode reinnehmen und dann disconnectNodes aufrufen:
Sehr gut! Ja okay macht natürlich Sinn, ich kam mir schon komisch vor.

Damit wäre dann removeNode fertig, bleibt noch disconnectNodes. Wie sieht es damit aus?
Java:
public void disconnectNodes(String idFrom, String idTo) {
ListItem<Node<K, W>> pointerNode = head; // Mein Zeiger, der über alle Knoten laufen soll
        while(pointerNode.next != null) {          // Lässt den Zeiger über alle Knoten laufen
            
            //TODO: Verbindung zum Zielknoten entfernen (wie ohne findNodeById ?)
            
            pointerNode = pointerNode.next;
        }
        
    }
Oder doch besser wie davor (siehe diesen Beitrag:)
public void disconnectNodes(String idFrom, String idTo) { Node<K, W> startNode = findNodeById(idFrom); //Finde den Knoten, von dem die Kante ab geht. while(startNode.headEdges.next.key.toString() != idTo) { //Durchsuche alle vom startNode abgehende Kanten nach der Kante, die zum Knoten (mit idTo) geht. startNode.headEdges = startNode.headEdges.next; } startNode.headEdges.next = startNode.headEdges.next.next; //Überspringe dann genau diese gesuchte Kante in der Liste. }

VLG!
 

TobiCodi

Mitglied
Falls du grad nix zu tun hast hier eine Beschäftigung o_O:

Ich möchte aus meinem gesamten Graphen den Kürzesten Pfad (Pfad mit geringstem Kantengewicht) zwischen zwei Knoten berechnen.
Der Methodenkopf sieht so aus und darf nicht verändert werden:
Java:
String getShortestPath(String idStart, String idTarget)
Wie bereits bei den letzten Methoden ist idStart die Objectid (aufrufbar über .getObjectId() ) des Startknotens, idTarget die id des Zielknotens.

1.) Existiert kein Pfad zwischen den Knoten: return null; :)

2.) Existiert mindestens ein Pfad, so wird der kürzeste Pfad im folgenden Schema als String zurückgegeben: "N1 -> N2 -> ... -> Nk". Die Kanten eines Pfades werden durch den String " -> " angegeben. Die Knoten werden durch ihre zugehörige ObjectId angegeben. Die Methode .sum(T other) summiert. Ich kann also z.B. so aufgerufen:
head.key.headEdges.key.weight.sum(head.next.key.headEdges.key.weight); Was das Kantengewicht der ersten Kante, die vom Head-Knotens weg zeigt, mit dem Gewicht der kante, die vom head.next-knotens weg zeigt, summiert.

TIPP: Nutze den Dijkstra's algorithm (-> Wikipedia). ;)

Hier mal ein Beispiel für folgenden Graphen:
12905

Der Aufruf getShortestPath( "B", "A") soll folgenden Pfad (String) zurückgeben:

"B -> D -> A"

Es wäre sooo gut wenn du mir da helfen könntest. Mir geht jetzt echt die Zeit aus, und ich hab leider keinen Code wie das geht..... Hast du zufällig sowas schonmal gemacht? Wenn ja, wäre es super, falls nicht: Auch nicht schlimm!

Viele liebe Grüße! ;)
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
S Binärbaum - Klasse Knoten - Methode Suchen Java Basics - Anfänger-Themen 5
T Rekursive Methode Java Basics - Anfänger-Themen 13
Ü Methode soll Quadrat aus der Summer zurückgeben Java Basics - Anfänger-Themen 10
P Objekt einer Methode eines anderen Objektes übergeben Java Basics - Anfänger-Themen 5
Leyla Spezifischte Methode Java Basics - Anfänger-Themen 16
M Methode zielnah zeigt das gewünschte Ausgabe nicht an Java Basics - Anfänger-Themen 3
L Variablenwerte aus einer Methode übergeben Java Basics - Anfänger-Themen 2
T Methode soll etwas ausrechnen und zurückgeben (klappt nd) hat wer eine Idee? Java Basics - Anfänger-Themen 11
P Main Methode scheint Constructor aufzurufen, ohne dass es so gecoded ist Java Basics - Anfänger-Themen 2
T Aufruf der Methode einer Oberklasse, wenn sie in der Unterklasse überschrieben ist. Polymorphie. Java Basics - Anfänger-Themen 2
C Zugriff auf Methode Java Basics - Anfänger-Themen 2
M Datentypen While-Schleife eine Java Methode erstellen Java Basics - Anfänger-Themen 3
T Methode akzeptiert String nicht Java Basics - Anfänger-Themen 18
M Methode sperren bis ein Kriterium erfüllt wurde Java Basics - Anfänger-Themen 3
D Switch Case Methode aufrufen Java Basics - Anfänger-Themen 3
C Unbekannte Methode add bei Klasse die JTree erweitert Java Basics - Anfänger-Themen 14
M methode aufrufen ohne parameter Java Basics - Anfänger-Themen 1
marcelnedza Finde meinen Fehler in einer Methode nicht, Java Karol Java Basics - Anfänger-Themen 15
monsterherz einfache Methode mit Fehler den ich nicht finde Java Basics - Anfänger-Themen 21
Ostkreuz Wieso wird die Methode nochmal aufgerufen? Java Basics - Anfänger-Themen 5
G Variable aktualisiert sich nicht in rekursiver Methode Java Basics - Anfänger-Themen 4
MoxMorris Wie macht man String[] = String[] aus einer anderer Methode? Java Basics - Anfänger-Themen 18
Say super.methode / super.variable und super(variable) Java Basics - Anfänger-Themen 2
B Wie kann ich folgende Klasse/Methode per Button ausführen? Java Basics - Anfänger-Themen 1
D Interface Methode wird ungewollt in der Subklasse überschrieben Java Basics - Anfänger-Themen 5
L Methoden Eine Methode um zu testen ob es ein Nachbar gibt Java Basics - Anfänger-Themen 10
til237 Iterative Methode in rekursive Methode umschreiben Java Basics - Anfänger-Themen 4
M Daten aus errechneter Methode in Datenbank(SQLite) schreiben Java Basics - Anfänger-Themen 60
D next() Methode mehrfach verwenden Java Basics - Anfänger-Themen 1
Ostkreuz Methoden Von Dezimal zu Hexadezimal Methode toHex Java Basics - Anfänger-Themen 2
I Entity Objekt nicht gefunden -> Webhook empfangen in der gleichen Methode (Transaktion) Java Basics - Anfänger-Themen 37
N Throw an Main Methode übergeben Java Basics - Anfänger-Themen 7
M Methoden Methode 'wiederhole' nicht gefunden (Uebersetzungsfehler) Java Basics - Anfänger-Themen 1
H Zu langen String aufteilen - bequeme Methode? Java Basics - Anfänger-Themen 14
_user_q Wie eine Methode/Funktion aus einer Klasse mit Constructor aufrufen? Java Basics - Anfänger-Themen 20
S Array mit Methode löschen Java Basics - Anfänger-Themen 2
J Java To String Methode, Array mit For-Schleife Java Basics - Anfänger-Themen 2
T Variable von Objekten in einer Methode überprüfen Java Basics - Anfänger-Themen 26
M Anzahl Kommandozeilenparamter mittels Methode Java Basics - Anfänger-Themen 11
D Methode: Array Reihenfolge tauschen Java Basics - Anfänger-Themen 3
julian0507 Array aus Methode in anderer Methode sichtbar machen Java Basics - Anfänger-Themen 10
frager2345 Problem mit Methode Java Basics - Anfänger-Themen 4
J Die statische Main-Methode ändert Instanzvariable? Java Basics - Anfänger-Themen 10
D Methode aus dem Aufrufer aufrufen Java Basics - Anfänger-Themen 1
T IOStreams read(byte[]b) methode Java Basics - Anfänger-Themen 2
frager2345 Java Singleton Muster -> Methode für Konstruktor mit Parametern Java Basics - Anfänger-Themen 3
U Beispiel Methode size() vom "Collection"-interface... Wie kann man sichtbar machen, was die Methode unter der Haube macht? Java Basics - Anfänger-Themen 8
D Warum kann ich hier nicht auf die Methode zugreifen? Java Basics - Anfänger-Themen 5
M generate Methode für Streams Java Basics - Anfänger-Themen 6
M Methoden Zweidimensionaler Array mit Setter Methode ändern Java Basics - Anfänger-Themen 4
I Optionaler Parameter bei Methode, der nur optional ist? Java Basics - Anfänger-Themen 6
berserkerdq2 Wozu benötigt man den BiPredicate, kann ich nicht einfach eine normale Methode nutzen, statt BiPredicate? Java Basics - Anfänger-Themen 3
T Linked List set-Methode Java Basics - Anfänger-Themen 2
D Arrays an replaceAll-Methode übergeben Java Basics - Anfänger-Themen 12
B Attribute eines Objekts einer Klasse durch statische Methode einer 2. Klasse ändern? Java Basics - Anfänger-Themen 32
berserkerdq2 Habe eine Klasse, welche public ist, diese hat eine public Methode, die nicht static ist. Wenn ich nun versuche aufzurufen Probleme? Java Basics - Anfänger-Themen 8
viktor1 Methoden Methode schreiben static void readText (String filename) {...} zu WordHistogramSample.java Java Basics - Anfänger-Themen 13
W Equals-Methode überschreiben bei composition Java Basics - Anfänger-Themen 20
V Hilfe bei Implementierung einer boolean Methode Java Basics - Anfänger-Themen 6
T Methode, die prüft ob in einem Int-Array maximal 2 Zahlen enthalten sind, die größer als ihr Vorgänger sind Java Basics - Anfänger-Themen 5
V Methoden printChar Methode mit Rückgabetyp void Java Basics - Anfänger-Themen 26
F Graph Tiefensuche Methode Java Basics - Anfänger-Themen 7
Jambolo Methode, welche die 3 letzten Parameter Werte speichert Java Basics - Anfänger-Themen 20
berserkerdq2 wie funktioniert contenthandler, was muss ich bei der Methode startElement und endElement tun? Java Basics - Anfänger-Themen 11
M Warum return die Methode den Wert nicht Java Basics - Anfänger-Themen 5
berserkerdq2 Wann soll ich den Stream schließen, wenn ich das in einer Methode habe? Java Basics - Anfänger-Themen 8
berserkerdq2 Ich gebe eine ArrayList als List zurück per MEthode, wie kann ich nun aber die ArrayList speichern? Java Basics - Anfänger-Themen 46
S Methode Java Basics - Anfänger-Themen 4
M Eine Methode die erkennt ob die ein gegebene zahl größer oder kleiner sein muss Java Basics - Anfänger-Themen 2
U Methode wird genutzt, ohne dass ich die aufrufe? Java Basics - Anfänger-Themen 4
F nach Methode Programm nicht beenden Java Basics - Anfänger-Themen 9
Liroyd Methode mit Objektvariabel rechnen? Java Basics - Anfänger-Themen 6
H Mit setter-Methode JLabel in einer andern Klasse ändern. Java Basics - Anfänger-Themen 40
D Methode um mögliche Rezepte auszugeben Java Basics - Anfänger-Themen 12
U Warum kann ich die Methode in der ENUM Klasse nicht aufrufen? Und warum geht die Switch nicht? Java Basics - Anfänger-Themen 8
J Hallo zusammen , was macht diese Methode hier genau? Java Basics - Anfänger-Themen 3
D Array in Main Methode aus anderer Klasse aufrufen Java Basics - Anfänger-Themen 3
H Eine Methode über Actionlistener beenden Java Basics - Anfänger-Themen 8
G jButton führt Main Methode nicht richtig aus Java Basics - Anfänger-Themen 3
G Main Methode wird beim ersten Aufruf nicht richtig ausgeführt Java Basics - Anfänger-Themen 1
C60 Methoden Main-Methode erkennt meine Arrays nicht. Java Basics - Anfänger-Themen 7
A Ein Array bearbeiten und in einer anderen Methode nutzen Java Basics - Anfänger-Themen 6
A Ergebnis einer Methode bei einer anderen verwenden Java Basics - Anfänger-Themen 13
L Iteratorform und Methode mit variabler Parameterzahl Java Basics - Anfänger-Themen 31
F Methode ArrayList mit Eingabewert Java Basics - Anfänger-Themen 2
M Wie kann eine Methode für ein vorhandenes "Array von char" einen Index-Wert zurückliefern? Java Basics - Anfänger-Themen 3
M Wie kann die Implementation einer Methode den Wert eines Attributs vermindern? Java Basics - Anfänger-Themen 3
Csircc Rekursive Methode Stack Overflow Java Basics - Anfänger-Themen 10
M Wie kann eine Methode (string) eine andere Methode (void) mit zufälligen int-Werten aufrufen? Java Basics - Anfänger-Themen 4
M Wie verknüpfe ich eine Bedingung mit einer Methode ohne if-Verzweigung & Bedingungsoperator? Java Basics - Anfänger-Themen 2
M Wie kann eine Methode eine andere Methode um Werte wie z.B. 1 erhöhen? Java Basics - Anfänger-Themen 6
schredder Strings und reguläre Ausdrücke - Methode mit return string.matches Java Basics - Anfänger-Themen 5
D mehrere Berechnungen in einer Methode Java Basics - Anfänger-Themen 9
H String Repräsentation eines Rechtecks mit Instanz-Methode Java Basics - Anfänger-Themen 8
M Wie kann ich eine Methode aus einem Interface in eine Klasse implementieren, so dass sie ihre Funktion ausführt? Java Basics - Anfänger-Themen 7
J ArrayList add methode selbst programmieren Java Basics - Anfänger-Themen 10
X Methoden Methode zur Punktezählung in Blackjack Java Basics - Anfänger-Themen 2
W Methode ändern Java Basics - Anfänger-Themen 65
M Wie kann ich in einem Konstruktor die Methode eines anderen Interfaces mit den jeweiligen Parametern aufrufen? Java Basics - Anfänger-Themen 8
W Methode, die mit einem Datum arbeitet? Java Basics - Anfänger-Themen 22

Ähnliche Java Themen

Neue Themen


Oben