Brauche Hilfe Zwischenzustände von Objekt aus rekursiver Methode speichern

[hennskand]

Hallo zusammen,

Ich will mit diesen beiden Methoden einen Algorithmus schreiben der einen Graph aus Knoten(Vertex) und Kanten(Edge) unter bestimmten Bedingungen schrittweise reduziert. Das reduzieren findet in der move.getAfterState() Methode statt. Nach jedem mal reduzieren soll der dadurch entstehende Graph in der ArrayList states gespeichert werden.
Folgende Methoden hab ich dafür geschrieben:

private ArrayList<Move> solve(Graph graph) {
        ArrayList<State> states = new ArrayList<>();
        for (Vertex v : graph.getVertices().stream().filter(element -> graph.getNeighbours(element).size() == 3).collect(Collectors.toCollection(ArrayList::new))) {
            findFastestWay(graph, states, v);
        }
        return null;
    }
    
    
    private Graph findFastestWay(Graph graph, ArrayList<State> states, Vertex v) {
        Graph graph1 = graph;
        states.add(new State(graph, counter++));
            if (graph1.getVertices().size() == 1) {
                return graph1;
            } else {
                if (graph1.getNeighbours(v).size() == 3) {
                    Move move = new Move(graph1, v);
                    findFastestWay(move.getAfterState(), states, v);
                }
            }
        return null;
    }

Der Algorithmus kann zwar den Graphen erfolgreich auf einen Knoten reduzieren aber die states enthält nur x-mal den Endzustand. Beim debuggen ist mir aufgefallen das sobald die move.getAfterState() aufgerufen wird alle einträge der ArrayList mit dem aktuellen Graph (Dem Rückgabe wert von move.getAfterState()) überschrieben werden. Kann mir jemand erklären woran das liegt und wie ich es verhindern kann? Schonmal danke fürs durchlesen und sorry falls ich im falschen sub bin, es ist mein erstes mal hier.

 

[KonradN]

Kanne es sein, dass du nur eine Regerenz auf den Graphen im State speicherst? Dann hast du einfach mehrere Referenzen auf eine Graphen-Instanz.

Du musst natürlich immer eine Kopie erstellen vom Graphen damit du die unterschiedlichen Zustände hast.

 

[hennskand]

Kanne es sein, dass du nur eine Regerenz auf den Graphen im State speicherst? Dann hast du einfach mehrere Referenzen auf eine Graphen-Instanz.

Du musst natürlich immer eine Kopie erstellen vom Graphen damit du die unterschiedlichen Zustände hast.

Stimmt ich hatte nur referenzen erstellt aber ich habe das jetzt geändert und das Problem bleibt bestehen. Hier mal ein screenshot vom Debugger: Die Namen in Gelb sind ja die Referenzen wenn ich das richtig verstehe (benutze Intellij falls das wichtig ist). Da sieht man ja das graph und graph1 eine unterschieliche Referenz haben was ja heißt das es auch im memory verschiedene Adressen für die beiden Graphen gibt oder?
Ich verstehe meinen code so: die Methode kriegt beim ersten Aufruf einen Graphen als Parameter. Dieser graph(graph) wird dann in graph1 gecloned. Auf graph1 werden dann eine Collapse operation aufgerufen und dann wird die Methode wieder mit graph1 aufgerufen. Dadurch wird graph1 dann im zweiten aufruf ja wieder als Parameter, also als Graph graph in graph1 gecloned. So müsste doch jedesmal ein neues Objekt erstellt werden oder?

 

[KonradN]

Wie sieht denn die Klasse Graph aus? Du hast ja in der Klasse Graph auch wieder Referenzen. Was macht die clone Methode im Detail?

 

[hennskand]

Wie sieht denn die Klasse Graph aus? Du hast ja in der Klasse Graph auch wieder Referenzen. Was macht die clone Methode im Detail?

Das ist meine GRaph Klasse:

public class Graph {
    private ArrayList<Vertex> vertices;
    private ArrayList<Edge> edges;

    public Graph() {
        vertices = new ArrayList<>();
        edges = new ArrayList<>();

    }


    public ArrayList<Vertex> getVertices() {
        return vertices;
    }

    public ArrayList<Edge> getEdges() {
        return edges;
    }

    public int numVertices() {
        return vertices.size();
    }


    public boolean readGraphFromFile(String pathToFile) {
        try {
            BufferedReader reader = new BufferedReader(new FileReader(pathToFile));
            String line;

            while ((line = reader.readLine()) != null) {
                if (line.trim().startsWith("node")) {
                    Pattern nodeId = Pattern.compile("id\\s+(\\d+)");
                    Matcher matcher = nodeId.matcher(line);
                    if (matcher.find()) {
                        vertices.add(new Vertex(Integer.valueOf(matcher.group(1))));
                    }
                } else if (line.trim().startsWith("edge")) {
                    Pattern edgeSource = Pattern.compile("source\\s+(\\d+)");
                    Pattern edgeTarget = Pattern.compile("target\\s+(\\d+)");
                    Matcher matcherSource = edgeSource.matcher(line);
                    Matcher matcherTarget = edgeTarget.matcher(line);
                    if (matcherSource.find() && matcherTarget.find()) {
                        edges.add(new Edge(Integer.valueOf(matcherSource.group(1)), Integer.valueOf(matcherTarget.group(1))));
                    }
                }
            }
            reader.close();
            connectEdges();
            return true;
        } catch (Exception e) {
            System.out.println(e.getLocalizedMessage());
            return false;
        }


    }

    private void connectEdges() {
        for (Vertex v : vertices) {
            for (Edge e : edges) {
                if (v.getId() == e.getSource() || v.getId() == e.getTarget()) {
                    v.getEdges().add(e);
                }
            }
        }
    }

    public boolean areNeighbours(Vertex u, Vertex v) {
        boolean neighbours = false;
        for (Edge e : u.getEdges()) {
            for (Edge x : v.getEdges()) {
                if (e.getSource() == x.getSource() && e.getTarget() == x.getTarget() && u.getId() != v.getId()) {
                    neighbours = true;
                }
            }
        }
        return neighbours;
    }

    public ArrayList<Vertex> getNeighbours(Vertex u) {
        ArrayList<Vertex> neighbours = new ArrayList<>();
        for (Vertex v : vertices) {
            if (areNeighbours(u, v)) {
                neighbours.add(v);
            }
        }
        return neighbours;
    }

    public Graph collapseNeighbours(Vertex u)  {
        Graph graph1 = this;
        int uIndex = -1;
        for(Vertex b : this.getVertices()){
            if(b.equals(u)){
                uIndex = this.getVertices().indexOf(b);
            }
        }
        ArrayList<Vertex> neighbours = graph1.getNeighbours(u);
        ArrayList<Edge> edgesToRemove = new ArrayList<>();
        ArrayList<Vertex> verticesToRemove = new ArrayList<>();
        if (neighbours.size() != 3) {
            return graph1;
        } else {
            for (Vertex v : neighbours) {
                if (v.getEdges().size() == 1) {
                    edgesToRemove.addAll(v.getEdges());
                    verticesToRemove.add(v);
                } else {
                    for (Edge e : v.getEdges()) {
                        if (e.getSource() == v.getId() && e.getTarget() != u.getId()) {
                            String source = "source";
                            updateEdges(u, e, graph1, source);
                            edgesToRemove.add(e);

                        } else if (e.getTarget() == v.getId() && e.getSource() != u.getId()) {
                            String target = "target";
                            updateEdges(u, e, graph1, target);
                            edgesToRemove.add(e);
                        } else {
                            edgesToRemove.add(e);
                        }
                    }
                    edgesToRemove.addAll(v.getEdges());
                    verticesToRemove.add(v);
                }
            }
        }
        removeEdges(u, edgesToRemove);

        updateGraph(u, graph1, uIndex, verticesToRemove, edgesToRemove);
        return graph1;
    }

    private void updateGraph(Vertex u, Graph graph1, int uIndex, ArrayList<Vertex> verticesToRemove, ArrayList<Edge> edgesToRemove) {
        graph1.getVertices().set(uIndex, u);
        graph1.getVertices().removeAll(verticesToRemove);
        graph1.getEdges().addAll(u.getEdges());
        graph1.getEdges().removeAll(edgesToRemove);
    }

    private void updateEdges(Vertex u, Edge e, Graph graph1, String string) {
        if (string.equals("source")) {
            Edge e1 = new Edge(u.getId(), e.getTarget());
            Vertex x = graph1.getVertices().stream().filter(element -> element.getId() == e.getTarget()).findFirst().get();
            if (!x.getEdges().contains(e1)) {
                x.getEdges().add(e1);
            }
            x.getEdges().remove(e);
            if (!u.getEdges().contains(e1)) {
                u.getEdges().add(e1);
            }

        } else if (string.equals("target")) {
            Edge e1 = new Edge(u.getId(), e.getSource());
            Vertex x = graph1.getVertices().stream().filter(element -> element.getId() == e.getSource()).findFirst().get();
            if (!x.getEdges().contains(e1)) {
                x.getEdges().add(e1);
            }
            x.getEdges().remove(e);
            if (!u.getEdges().contains(e1)) {
                u.getEdges().add(e1);
            }
        }
    }


    private void removeEdges(Vertex u, ArrayList<Edge> edgesToRemove) {
        for (Edge x : edgesToRemove) {
            u.getEdges().remove(x);
        }

    }
    public Graph clone() {

        Graph clonedGraph = new Graph();
        HashMap<Integer, Vertex> clonedVerticesMap = new HashMap<>();

        for (Vertex v : this.vertices) {
            Vertex clonedVertex = new Vertex(v.getId());
            clonedGraph.getVertices().add(clonedVertex);
            clonedVerticesMap.put(v.getId(), clonedVertex);
        }

        for (Edge e : this.edges) {
            Edge clonedEdge = new Edge(e.getSource(), e.getTarget());
            clonedGraph.getEdges().add(clonedEdge);


            if (clonedVerticesMap.containsKey(e.getSource())) {
                clonedVerticesMap.get(e.getSource()).getEdges().add(clonedEdge);
            }
            if (clonedVerticesMap.containsKey(e.getTarget())) {
                clonedVerticesMap.get(e.getTarget()).getEdges().add(clonedEdge);
            }
        }

        return clonedGraph;
    }


}

innerhalb der Klasse benutze ich nur referenzen was glaube ich auch ok sein sollte? Nur in der findfastestWay() methode will ich ein wirklich neues Objekt mithilfe von graph.clone() erstellen. Ich habe versucht innerhalb der collapse methode auch schon ein neues Objekt graph zu erstellen das dann zurückgegeben wird aber das hat zu ganz neuen Problemen geführt die ich noch nicht verstanden habe

 

[hennskand]

Ich habe das Problem jetzt gelöst indem ich in der findFastestWay() methode nicht mehr

Graph graph1 = graph.clone()

mache sondern stattdessen erst clone wenn ich den graph1 der ArrayList hinzufüge, also:

 Graph graph1 = graph;
 states.add(new State(graph1.clone(), counter++));

Ich verstehe allerdings trotzdem nicht warum es mit der ersten Lösung nicht geklappt hat. Über eine Erklärung würd ich mich freuen 🙂. Aber auf jedenfall schonmal danke für den Hinweis mit den Referenzen. Ich hatte tatsächlich in meiner ganzen Ausbildung+ 1 Semester Studium noch nie eine Situation wo das ein Problem war und wär da wahrscheinlich nicht so schnell drauf gekommen.

 

[KonradN]

Also vom Ablauf her ist es erst einmal logisch, das so zu machen. Du hast einen Zustand und diesen willst Du sichern ehe Du diesen veränderst. Nehmen wir einen Zettel, auf dem Du herum malst und Du willst Zwischenergebnisse sichern: Immer wenn Du ein Zwischenergebnis sichern willst, legst Du den Zettel auf einen Kopierer und machst eine Kopie zur Archivierung, ehe Du dann mit dem Zettel weiter arbeitest.

Prinzipiell funktioniert das andere aber auch, aber Du hast verschobene Backups. Bei dem Vergleich mit dem Zettel:
Du machst erst eine Kopie aber malst dann auf der Kopie herum. Aber beim nächsten Durchlauf machst Du wieder eine Kopie um dann auf der neuen Kopie weiter zu arbeiten.

Also Du hast einmal in dem Array immer die Version, die Du beim Start der Methode hattest. Im ersten Punkt hattest Du immer die Version, die Du nach dem Durchlauf hattest (bis zum nächsten clone Aufruf).