Untersuchen ob ein Graph nach entfernen einer Kante immer noch zusammenhängend ist

Nein, momentan sieht bei mir CartesianPoint so aus:
Java: 
public class CartesianPoint<T> {
    private int xCoordinate;
    private int yCoordinate;

    public CartesianPoint(int xCoordinate, int yCoordinate) {
        this.xCoordinate = xCoordinate;
        this.yCoordinate = yCoordinate;
    }

}
Auf welche Weise muss ich hier equals und hashCode überschreiben, denn ich dachte man muss diese nur in Edge überschreiben
 
Mika34 hat gesagt.:
Auf welche Weise muss ich hier equals und hashCode überschreiben
Zum Vergrößern anklicken....
Analog zu Edge, z. B.
Java: 
    @Override
    public boolean equals(Object o) {
        if (o == null || o == this || !(o instanceof CartesianPoint)) {
            return o == this;
        }
        CartesianPoint p = (CartesianPoint) o;
        return xCoordinate == p.xCoordinate && yCoordinate == p.yCoordinate;
    }

    @Override
    public int hashCode() {
        return 57+13*xCoordinate+23*yCoordinate; 
    }
Bzgl. hashCode() wird prinzipiell nur gefordert, dass zwei equals-gleiche Objekte auch den gleichen HashCode liefern. Das Ergebnis sollte für unterschiedliche Objekte zwar möglichst unterschiedlich sein, um unnötige Kollisionen bei z. B. einer HashMap zu vermeiden - ist aber kein Zwang.

Mika34 hat gesagt.:
denn ich dachte man muss diese nur in Edge überschreiben
Zum Vergrößern anklicken....
Nein. Edge verwendet ja die Methoden equals und hashCode (versteckt in den Objects.equals()- und Object.hash()-Aufrufen) von CartesianPoint.

Zwei Kanten a und b sind gleich, gdw. wenn die Punkte a.source und b.source sowie a.dest und b.dest gleich sind. Das ist in Edge#equals() umgesetzt. Diese Definition fußt also auf der Gleichheit zweier Punkte. Wann aber sind zwei Punkte gleich? Dieser Teil des Codes fehlt bei Dir.
 
Ich hab es nun abgeändert und nun erneut für ein simples Programm durchlaufen lassen, jedoch klappt es immer noch nicht. Ich verstehe nicht, wieso hier isConnectAfterRemoving() auf true schlägt wenn man edge2 entfernt. Habt ihr eine Lösung?
Java: 
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class TrackRemover<T> {

    private Map<T, List<T>> edgesBetweenTwoPoints = new HashMap<>();

    public void addEdge(T firstCoordinate, T secondCoordinate) {
        edgesBetweenTwoPoints.computeIfAbsent(firstCoordinate, x -> new ArrayList<T>()).add(secondCoordinate);
        edgesBetweenTwoPoints.computeIfAbsent(secondCoordinate, x -> new ArrayList<T>()).add(firstCoordinate);
    }

    public boolean isConnectedAfterRemoving(Set<Edge<T>> toRemove) {
        Set<T> notVisited = new HashSet<T>(edgesBetweenTwoPoints.entrySet().stream()
                .filter(e -> e.getValue().stream()
                        .filter(d -> !toRemove.contains(new Edge<>(e, d)) && !toRemove.contains(new Edge<>(d, e)))
                        .count() > 0)
                .map(Map.Entry::getKey).collect(java.util.stream.Collectors.toSet()));
        if (notVisited.isEmpty())
            return true;
        visit(notVisited.iterator().next(), notVisited, toRemove);
        return notVisited.isEmpty();
    }

    private void visit(T next, Set<T> notVisited, Set<Edge<T>> toRemove) {
        if (!notVisited.remove(next))
            return;
        for (T t : edgesBetweenTwoPoints.get(next))
            if (!toRemove.contains(new Edge<>(next, t)) && !toRemove.contains(new Edge<>(t, next)))
                visit(t, notVisited, toRemove);
    }

    public static void main(String[] args) {
        TrackRemover<CartesianPoint> g = new TrackRemover<>();
        Set<Edge<CartesianPoint>> setToBeRemovedEdges = new HashSet<>();
        CartesianPoint p1 = new CartesianPoint(1, 1);
        CartesianPoint p2 = new CartesianPoint(5, 1);
        CartesianPoint p3 = new CartesianPoint(8, 1);
        CartesianPoint p4 = new CartesianPoint(10, 1);

        Edge edge1 = new Edge(p1, p2);
        Edge edge2 = new Edge(p2, p3);
        Edge edge3 = new Edge(p3, p4);

        setToBeRemovedEdges.add(edge2);

        System.out.println(g.isConnectedAfterRemoving(setToBeRemovedEdges));
    }
}
 
Habe ich doch gemacht mittels setToBeRemovedEdges.add(edge2); oder vertue ich mich gerade komplett im Moment? Denn ich möchte diese Kante entfernen entfernen und übergebe somit diese als Set der Methode isConnectedAfterRemoving()
 
Ist es auch möglich einen getter für die die Edges zu schreiben? Also für diese Methode einen getter:
Java: 
public void addEdge(T firstCoordinate, T secondCoordinate) {
        edgesBetweenTwoPoints.computeIfAbsent(firstCoordinate, x -> new ArrayList<T>()).add(secondCoordinate);
        edgesBetweenTwoPoints.computeIfAbsent(secondCoordinate, x -> new ArrayList<T>()).add(firstCoordinate);
    }
Denn ich komme gerade schlichtweg einfach nicht an die Kanten, welche in der HashMap EdgesBetweenTwoPoints gespeichert werden.
 
Ja, habe ich gemacht, aber ich wurde daraus nicht schlau. Ich habe nun versucht
Java: 
   public List<CartesianPoint> getPoints() {
        return Collections.unmodifiableList(CartesianPoint);
        }
zu implementieren, bin jedoch daran unter gegangen, da ich nicht an die Punkte rankomme. Denn wenn ich nun zwei Punkte habe von denen ich die Kante zwischen beiden entfernen solle, komme ich nicht an die Kante in EdgesBetweenPoints ran, da ich den Getter dafür nicht hinbekomme
 
Mika34 hat gesagt.:
Denn ich komme gerade schlichtweg einfach nicht an die Kanten, welche in der HashMap EdgesBetweenTwoPoints gespeichert werden.
Zum Vergrößern anklicken....
An die Kanten (zwei Punkte) kommt man leicht. Jeder Key bildet mit jedem Eintrag der Liste (value) eine Kante. Das Problem ist, dass das Modell nicht gut geeignet ist, weil Du ja auch an die Tracks herankommen musst. Daher haben wir das in dem anderen Thread umgestellt.
 
Da hast du Recht. An die Tracks komme ich aber über verschachtelte for-Schleifen, welche ich dann jeweils entfernen kann in der jeweiligen Liste.
Bedeutet das somit, dass meine Modellierung an diesem Punkt dann scheitert oder lässt sich dann noch mittels den Eigenschaften einer Map ein getter schreiben?
 
Ich möchte eine getEdge Methode, welche sich bei [B]private[/B] Map<T, List<T>> edgesBetweenTwoPoints = [B]new[/B] HashMap<>(); die Kante holt. Dabei möchte ich diesen: getEdge(CartesianPoint point1, CartesianPoint point2){} so modellieren, dass er den Eintrag edgesBetweenTwoPoints findet, indem diese beiden Punkte durch eine Kante definiert werden.
Jedoch gestaltet sich das Ganze gerade sehr schwierig. Deshalb habe ich gemeint, ob mein Programm nun nicht zum Scheitern verurteilt ist, bezüglich dieser letzten Methode
 
Meinst Du sowas in der Richtung?
Java: 
public Edge<T> getEdge(T start, T dest) {
    List<T> list = edgesBetweenTwoPoints.get(start);
    if (list != null && list.contains(dest)) {
        return new Edge<>(start, dest);
    }
    return null;
}
 
Ja, das hat nun geklappt, jedoch habe ich nun ein größeres Problem und da habe ich nun, so denke ich, nichts vergessen.
Wenn ich in diesem Bsp. die Kante zwischen p3 und p4 löschen will, dann wirft mir die Methode isConnectedAfterRemoving ein false, obwohl dieser Graph nicht in zwei Einzelteile zerbricht. Also wie z.B.:
A------B----C-----D, wenn ich hier nun C----D entferne.

Weißt du woran es liegen kann?

Java: 
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class TrackRemover<T> {

    private Map<T, List<T>> edgesBetweenTwoPoints = new HashMap<>();

    public void addEdge(T firstCoordinate, T secondCoordinate) {
        edgesBetweenTwoPoints.computeIfAbsent(firstCoordinate, x -> new ArrayList<T>()).add(secondCoordinate);
        edgesBetweenTwoPoints.computeIfAbsent(secondCoordinate, x -> new ArrayList<T>()).add(firstCoordinate);
    }
    
    public Edge<T> getEdge(T start, T dest) {
        List<T> list = edgesBetweenTwoPoints.get(start);
        if (list != null && list.contains(dest)) {
            return new Edge<>(start, dest);
        }
        return null;
    }

    public boolean isConnectedAfterRemoving(Set<Edge<T>> toRemove) {
        Set<T> notVisited = new HashSet<T>(edgesBetweenTwoPoints.entrySet().stream()
                .filter(e -> e.getValue().stream()
                        .filter(d -> !toRemove.contains(new Edge<>(e, d)) && !toRemove.contains(new Edge<>(d, e)))
                        .count() > 0)
                .map(Map.Entry::getKey).collect(java.util.stream.Collectors.toSet()));
        if (notVisited.isEmpty())
            return true;
        visit(notVisited.iterator().next(), notVisited, toRemove);
        return notVisited.isEmpty();
    }

    private void visit(T next, Set<T> notVisited, Set<Edge<T>> toRemove) {
        if (!notVisited.remove(next))
            return;
        for (T t : edgesBetweenTwoPoints.get(next))
            if (!toRemove.contains(new Edge<>(next, t)) && !toRemove.contains(new Edge<>(t, next)))
                visit(t, notVisited, toRemove);
    }
    public Map<T, List<T>> getEdgesBetweenTwoPoints(){
        return this.edgesBetweenTwoPoints;
    }

    public static void main(String[] args) {
        TrackRemover<CartesianPoint> g = new TrackRemover<>();
        Set<Edge<CartesianPoint>> setToBeRemovedEdges = new HashSet<>();
        CartesianPoint p1 = new CartesianPoint(1, 1);
        CartesianPoint p2 = new CartesianPoint(5, 1);
        CartesianPoint p3 = new CartesianPoint(8, 1);
        CartesianPoint p4 = new CartesianPoint(10, 1);

        Edge edge1 = new Edge(p1, p2);
        Edge edge2 = new Edge(p2, p3);
        Edge edge3 = new Edge(p3, p4);

        g.addEdge(p1, p2);
        g.addEdge(p2, p3);
        g.addEdge(p3, p4);

        Terminal.printLine(g.getEdgesBetweenTwoPoints());

        //
        Terminal.printLine(g.getEdgesBetweenTwoPoints().size());
        setToBeRemovedEdges.add(g.getEdge(p3, p4));

        System.out.println(g.isConnectedAfterRemoving(setToBeRemovedEdges));
    }
}
 
Guten Morgen,
Danke, nun hat es endlich geklappt. Jedoch wollte ich fragen, ob es Sinn macht oder eher möglich ist eine Methode einzuführen namens deleteEdge, welche Kanten aus dem Set edgesBetweenPoints löscht.
 
Die Methode prüft vorab, ob ein Entfernen der Kanten möglich wäre. Für das wirkliche Löschen solltest Du natürlich eine Methode haben.

Du kannst natürlich auch auf einer Kopie arbeiten, dort die Kanten tatsächlich entfernen und die Kopie auf Zusammenhang prüfen.
 
Nein, ich meinte ich füge permanent edgesBetweenTwoPoints Kanten hinzu, aber wenn nun isConnectedAfterRemoving true zurückgibt, dann lässt sich die Kante entfernen.
Jetzt muss ich dann aber auch die Kante in edgesBetweenTwoPoints entfernen, damit diese bei einem neuen Vorgang nicht mehr berücksichtigt wird, oder?
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Zusammenhängend Komponente suchen(Graph)
Antworten: 4
Queue-Datenstruktur: nach dem Elementen entfernen, das Ergebnis ist immer noch nicht optimal.
Antworten: 3
Schauen ob ein Kante zwischen Knoten existiert
Antworten: 4
Type mismatch: cannot convert from Graph.Edge to ArrayList<Graph.Edge>
Antworten: 21
2 JTables zusammenhängend füllen
Antworten: 3

Zurück
Oben