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

Mika34

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

mihe7

Top Contributor
Auf welche Weise muss ich hier equals und hashCode überschreiben
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.

denn ich dachte man muss diese nur in Edge überschreiben
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.
 

Mika34

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

Mika34

Bekanntes Mitglied
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()
 

Mika34

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

Mika34

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

mihe7

Top Contributor
Denn ich komme gerade schlichtweg einfach nicht an die Kanten, welche in der HashMap EdgesBetweenTwoPoints gespeichert werden.
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.
 

Mika34

Bekanntes Mitglied
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?
 

Mika34

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

mihe7

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

Mika34

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

Mika34

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

mihe7

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

Mika34

Bekanntes Mitglied
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?
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Bitmap untersuchen, etc. Java Basics - Anfänger-Themen 1
M Matrix auf 4 Elemente untersuchen mit offenen Enden Java Basics - Anfänger-Themen 8
L String auf bestimmte zeichen untersuchen Java Basics - Anfänger-Themen 9
Y String auf allgemein Zeichen untersuchen Java Basics - Anfänger-Themen 3
M Aus Datei auslesen und untersuchen ob diese Zeile schon vorhanden ist Java Basics - Anfänger-Themen 3
G 2 dimensionales Array spaltenweise untersuchen. Java Basics - Anfänger-Themen 2
H Spiel Kniffel: Gesamtes Array untersuchen. Java Basics - Anfänger-Themen 15
B Array rekursiv untersuchen Java Basics - Anfänger-Themen 21
M string arraylist untersuchen frage Java Basics - Anfänger-Themen 6
S String auf Sonderzeichen untersuchen Java Basics - Anfänger-Themen 6
L Textzeilen nach 2 Wörtern untersuchen wenn vorhanden Zeile in neuen Text ausgeben wenn nicht löschen Java Basics - Anfänger-Themen 10
G Mit Java Quelltext auf Element untersuchen. Java Basics - Anfänger-Themen 5
Q Tiefensuche Graph -> Schulprojekt Java Basics - Anfänger-Themen 1
F Graph Tiefensuche Methode Java Basics - Anfänger-Themen 7
S Längster Pfad zwischen zwei Vertices in einem Graph Java Basics - Anfänger-Themen 3
danieldemetry Java - Graph Komponenten - Ausgabe Java Basics - Anfänger-Themen 0
O ADT Graph nach größe Abfragen Java Basics - Anfänger-Themen 42
N gerichteter Graph aus einer Datei einlesen Java Basics - Anfänger-Themen 21
Z Graph einlesen Java Basics - Anfänger-Themen 2
S Ungerichteter Graph in Java Java Basics - Anfänger-Themen 1
M int double int double Graph Java Basics - Anfänger-Themen 3
A Tiefensuche in Graph Java Basics - Anfänger-Themen 4
N gerichteten Graph abspeichern Java Basics - Anfänger-Themen 2
Luk10 Frage zu Graph Tiefensuche Java Basics - Anfänger-Themen 4
S Methoden Wegsuche in einem Graph Java Basics - Anfänger-Themen 6
F Zusammenhängend Komponente suchen(Graph) Java Basics - Anfänger-Themen 4
F Kanten in Graph Java Basics - Anfänger-Themen 3
M Wth? übernimmt nichtübergebenen Wert (Graph) Java Basics - Anfänger-Themen 4
T Wie kann ich einem Graph in nem JPanel eine fixe Größe geben? Java Basics - Anfänger-Themen 6
H gerichteter Graph Java Basics - Anfänger-Themen 9
B Graph aus 2dim-Array Java Basics - Anfänger-Themen 3
D Map<String, Integer> sortieren und der reinfolge nach die Glieder abfragen Java Basics - Anfänger-Themen 3
S nach Import von jars (PLC4x) in Eclipse kann nicht mehr compiliert werden Java Basics - Anfänger-Themen 9
S Java: Wie sortiere ich eine ArrayList benutzerdefinierter Objekte nach einem bestimmten Attribut? Java Basics - Anfänger-Themen 2
M Queue-Datenstruktur: nach dem Elementen entfernen, das Ergebnis ist immer noch nicht optimal. Java Basics - Anfänger-Themen 3
N Hey Leute und zwar versuche ich gerade ein 2D Spiel zu Programmieren aber die Figur will sich nicht nach links oder rechts bewegen :( Java Basics - Anfänger-Themen 12
H Liste nach String-Länge sortieren Java Basics - Anfänger-Themen 1
I Bild richtig speichern / Hochkant im File Explorer, nach Upload vertikal Java Basics - Anfänger-Themen 9
D Wie kann man in Java nach Arrays auf Duplikate prüfen Java Basics - Anfänger-Themen 12
C Probleme mit Byte konvertieren nach int Java Basics - Anfänger-Themen 10
T sortierung der eingabe nach größe Java Basics - Anfänger-Themen 5
G Bei dynamischer Arrayliste nach jeder Auswahl Zahl entfernen Java Basics - Anfänger-Themen 3
ptcho Werte/Position nach dem Funktionsaufruf tauschen? Java Basics - Anfänger-Themen 1
K Warum wird mir hier nach dem ersten Durchlauf zwei mal "welchen Datentyp wollen sie übergeben?" ausgegeben ? Java Basics - Anfänger-Themen 1
H Cast von Float nach String klappt nicht Java Basics - Anfänger-Themen 12
W LocalDate toString und nach Split falsch "erkannt"? Java Basics - Anfänger-Themen 8
B Array nach Elementwerten sortieren? Java Basics - Anfänger-Themen 1
S Größte Zahl nach Eingabe der Zahl 0 ausgeben Java Basics - Anfänger-Themen 6
I Java Mail Timeout erst nach rund 5 Minuten? Java Basics - Anfänger-Themen 9
FireHorses Einen Command erst nach einer Chateingabe aktivieren Java Basics - Anfänger-Themen 1
izoards Sortier Algorithmus für Bounding Box Elememte Links nach Rechts und von Oben nach Unten Java Basics - Anfänger-Themen 33
Jambolo Karten sortieren nach Rang und Farbe Java Basics - Anfänger-Themen 5
Lion.King Subtraktion nach Eingabe im Terminal Java Basics - Anfänger-Themen 7
D Programmieren nach UML Java Basics - Anfänger-Themen 2
rosima26 Java nach letzter Ziffer sortieren Java Basics - Anfänger-Themen 19
H Kompliziertes Sortieren einer ArrayList mit Objekten(Sortieren nach X und Y) Java Basics - Anfänger-Themen 11
H Erste Schritte Nach einer Zahl n soll n Mal der String untereinander ausgegeben werden Java Basics - Anfänger-Themen 3
volcanos List & ArrayList nach Familiennamen abfragen Java Basics - Anfänger-Themen 57
sserio Wie kann man nach einer Klasse fragen? Java Basics - Anfänger-Themen 12
S Java Client-je nach Heap Size Größe startet Applikation oder nicht Java Basics - Anfänger-Themen 4
A String split funktioniert nicht, wenn mehr als 1 Ziffer vor dem Zeichen steht nach dem er trennen soll? Java Basics - Anfänger-Themen 4
F Suche nach betreuender Person für eine Jahresarbeit der 12. Klasse. Java Basics - Anfänger-Themen 6
F nach Methode Programm nicht beenden Java Basics - Anfänger-Themen 9
E Umlaute und Sonderzeichen werden nach der Build Project nicht richtig angezeigt Java Basics - Anfänger-Themen 2
M Bei nach oben scrollen soll Seite aktualisiert werden (Userscript mit Javascript) Java Basics - Anfänger-Themen 10
K log4j nach log4j2 überführen Java Basics - Anfänger-Themen 0
javapingu Jeglichen Inhalt einer Textdatei nach Zeile n löschen Java Basics - Anfänger-Themen 8
J Nach dem Exportieren funktioniert mein Programm nicht mehr Java Basics - Anfänger-Themen 8
P Datei einlesen, nach Begriff filtern und in Datei ausgeben. Problem Standardausgabe über Konsole Java Basics - Anfänger-Themen 19
B Array nach Wert prüfen rekursiv Java Basics - Anfänger-Themen 5
CptK For-Schleife in Thread nach jedem Durchlauf pausieren Java Basics - Anfänger-Themen 35
D Primzahlen Rechner nach Eratostenes von Kyrene Algorithmus Java Basics - Anfänger-Themen 2
rafi072001 Sortieren einer HashMap nach Values Java Basics - Anfänger-Themen 2
L Zahlungen nach Monat filtern Java Basics - Anfänger-Themen 2
J Jtable Eingabe nach Klick ausserhalb der Tabelle übernehmen Java Basics - Anfänger-Themen 6
I String nach Wort suchen Java Basics - Anfänger-Themen 6
C ArrayList sortieren nach bestimmten Buchstaben in den Wörtern Java Basics - Anfänger-Themen 13
javaluke Erste Schritte Array nach Datentyp sortieren Java Basics - Anfänger-Themen 16
D Methoden nach einer bestimmten Reihenfolge ausführen. Java Basics - Anfänger-Themen 20
idontknow707 Matrix nach z.B. Variable durchsuchen Java Basics - Anfänger-Themen 4
O 2D-Array nach einer Spalte sortieren Java Basics - Anfänger-Themen 22
I Liste gruppieren nach Monat? Java Basics - Anfänger-Themen 5
P Ein Objekt nach einem String durchsuchen? Java Basics - Anfänger-Themen 7
M Nach einer erstmaligen Eingabe, eine zweite Eingabe nur noch gegen bestätigung möglich Java Basics - Anfänger-Themen 2
D Input/Output fehlerhafter Algorithmus zum Ersetzen von Array-Werten nach logischem Schema Java Basics - Anfänger-Themen 1
C Meldung einer Klasse nach "oben" Java Basics - Anfänger-Themen 6
B Nach eingefügtem Code erkennt Compiler keine Instanzvar und meldet SyntaxError Java Basics - Anfänger-Themen 2
newcomerJava Nach doppelter Zahl eine Ausgabe Java Basics - Anfänger-Themen 10
M Anzahl Schleifendurchgänge nach x Sekunden anzeigen Java Basics - Anfänger-Themen 2
C Lotto 3, 4, 5, 6 Richtige nach x Ziehungen ermittelt.. Java Basics - Anfänger-Themen 7
G Primzahlen von Rekursiv nach Iterativ Java Basics - Anfänger-Themen 6
F JMenuItem Kann nicht nach einem String benannt werden... Java Basics - Anfänger-Themen 11
R JDK installieren Durcheinander nach installation von SE 14.02 Java Basics - Anfänger-Themen 6
P Sortieren von Listen nach Attributen Java Basics - Anfänger-Themen 3
B DateTimeFormatter nach LocalDateTime, wenn dd.MM.yyyy oder dd.MM.yyyy mm:hh Java Basics - Anfänger-Themen 5
1 main-Methode erweitern, Nachfrage nach wiedeholung Java Basics - Anfänger-Themen 2
G unklares Verhalten nach Instanzierung neuer Klasse Java Basics - Anfänger-Themen 3
S Wohin kommt das „abstract“? Vor oder nach „public“/ „private“ /... Java Basics - Anfänger-Themen 3
S Datenbank Befehl nach Login Java Basics - Anfänger-Themen 5
N Operatoren Schreibtischtest der Reihen-Suche nach Aufschluss in die Basics Java Basics - Anfänger-Themen 1

Ähnliche Java Themen

Neue Themen


Oben