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

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));
            }
    }
}
 
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
 
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!!
 
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.
 
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.
 
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;
        }
 
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!
 
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! ;)
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben