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

M

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

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

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));
    }
}
 
M

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()
 
M

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

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

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

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?
 
M

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

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

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));
    }
}
 
M

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

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

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?
 
mihe7

mihe7

Top Contributor
Jetzt muss ich dann aber auch die Kante in edgesBetweenTwoPoints entfernen, damit diese bei einem neuen Vorgang nicht mehr berücksichtigt wird, oder?
Ja, hab ich doch geschrieben. Erst prüfst Du, ob die Kante entfernt werden kann und dann musst Du sie natürlich noch entfernen.
 
Ä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
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
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
B Umstieg von C# nach Java Java Basics - Anfänger-Themen 18
Ellachen55 Wie nach häufigste Werte im Array suchen? Java Basics - Anfänger-Themen 2
N Wörter und Zahlen nach speziellen Wörtern ausgeben Java Basics - Anfänger-Themen 11
M Werte ändern sich nicht mehr nach Reset Java Basics - Anfänger-Themen 14
B Nach dem kompilieren werden Bilder nicht mehr gefunden Java Basics - Anfänger-Themen 10
X Nach einem Bruch testen ob es eine ganze Zahl ist Java Basics - Anfänger-Themen 6
B String nach erstem Leerzeichen trennen Java Basics - Anfänger-Themen 7
N Speichern von Werten in Variablen nach Schließen des Programms Java Basics - Anfänger-Themen 3
G String wird nach Einlesen aus Datei nicht erkannt Java Basics - Anfänger-Themen 3
UnknownInnocent Best Practice Algorithmus nach jedem Schritt zum Visualisieren pausieren Java Basics - Anfänger-Themen 3
O zwei Arrays nach Werten durchsuchen und zusammenfügen Java Basics - Anfänger-Themen 3
M Double Wert nach n abschneiden ohne zu runden Java Basics - Anfänger-Themen 1
C Erste Schritte Bilder nach Export anzeigen Java Basics - Anfänger-Themen 0
F Input/Output Files von A nach B kopieren Java Basics - Anfänger-Themen 11
B InputStream (PDF) nach Image (PNG / JPG) konvertieren? Java Basics - Anfänger-Themen 2
O compareTo nach mehreren Kriterien Java Basics - Anfänger-Themen 13
R Benutzereingaben als Array abspeichern nach Programmstart Java Basics - Anfänger-Themen 5
S Pane nach speziellen Child Objekten durchsuchen Java Basics - Anfänger-Themen 3
V Neue Ausgabe von toString nach Methodenaufruf Java Basics - Anfänger-Themen 9
L Arrayliste von hinten nach vorne ausgeben Java Basics - Anfänger-Themen 10
F Array nach Objektattribut durchsuchen Java Basics - Anfänger-Themen 6
M Rationale Zahl erkennen - Kurze Frage zum Restwert nach Division Java Basics - Anfänger-Themen 3
O String von vorne nach hinten an einem Zeichen Java Basics - Anfänger-Themen 10
Hanschyo Quicksort sortiert von groß nach klein Java Basics - Anfänger-Themen 3
S suche nach varible POSITION ... fuer das pixel-maennchen Java Basics - Anfänger-Themen 4
A Einträge aus Tupeln nach Regeln in Liste speichern Java Basics - Anfänger-Themen 8
B String nach HTML formatieren Java Basics - Anfänger-Themen 9
Zrebna Compiler-Fehler Java-Compiler wird nach 'javac' keyword-Eingabe nicht gestartet (Erste Übung) Java Basics - Anfänger-Themen 18
UnknownInnocent Klassen JPanel nach Ablauf der Spielzeit neuladen Java Basics - Anfänger-Themen 2
B Umbruch nach bestimmten Wort Java Basics - Anfänger-Themen 5
E Arrays nach best Muster füllen Java Basics - Anfänger-Themen 4
N Arbeitsspeicher nach kompilieren immer voller Java Basics - Anfänger-Themen 6
K String nach bestimmtem Muster parsen Java Basics - Anfänger-Themen 3
S Amazon Produktbeschreibung auslesen und nach Keywords suchen Java Basics - Anfänger-Themen 2
M Scanner-Eingabe nach gewissem Zeitraum überprüfen Java Basics - Anfänger-Themen 2
J variablePathPart ändern nach dem Ordner abgearbeitet worden ist Java Basics - Anfänger-Themen 1
B Wie kann ich die Buchstaben sortieren nach der Höhe der Zahlen Java Basics - Anfänger-Themen 14
J GUI wird direkt nach dem erstellen weiß übermalt Java Basics - Anfänger-Themen 3
L Programm zur Codieren nach Rotx Java Basics - Anfänger-Themen 1
S Nach dem Herüberschieben eines Arrays zwischen 2 Frames öffnet sich das Frame nicht mehr Java Basics - Anfänger-Themen 12
A ArrayList - size() nur nach bestimmtem index anzeigen lassen Java Basics - Anfänger-Themen 13
M Array nach String durchsuchen und zurückgeben Java Basics - Anfänger-Themen 16
W Wie lasse ich meine Ausgabe nach dem Lesen verschwinden ? Java Basics - Anfänger-Themen 1
F Liste nach einer Variablen sortieren Java Basics - Anfänger-Themen 6
S String trennen nach beliebigen Zeichen Java Basics - Anfänger-Themen 3
D Ich suche nach einer Möglickeit den Webseiten Inhalt per Java zu analysieren Automatisch Java Basics - Anfänger-Themen 3
B String: suche nach Wörter und in List<String> speichern Java Basics - Anfänger-Themen 3
O Array nach gleichen Zahlen prüfen und ausgeben Java Basics - Anfänger-Themen 6
K Matrixen berechnen nach Worker Master Paradigma mit Threads Java Basics - Anfänger-Themen 4
K Schlüsselworte Nach Java update findet mdb Datei nicht Java Basics - Anfänger-Themen 6
G nach 9 - stelliger Nummer suchen Java Basics - Anfänger-Themen 7
S Wie verwende ich ne aus einer Schleife nach der Schleife? Java Basics - Anfänger-Themen 9
M BufferedReader neue Zeile nach Knopfdruck Java Basics - Anfänger-Themen 9
E JAvaFX: Verschiedene Panels nach Klick auf Node des TreeView anzeigen Java Basics - Anfänger-Themen 0
D Liste nach 2 gleichen Einträgen suchen Java Basics - Anfänger-Themen 4
J Input/Output Den zweiten Output erst nach Eingabe ausgeben Java Basics - Anfänger-Themen 4
L (Integer) Liste nach aufsteigender Summe der Ziffern sortieren (mit Bedingung) Java Basics - Anfänger-Themen 8
S Dialogfeld nach 5 Sek automatisch öffnen Java Basics - Anfänger-Themen 15
F Alle Objekte einer Klasse nach Eigenschaft durchsuchen Java Basics - Anfänger-Themen 8
S OOP Button erst nach 2x klicken deaktivieren Java Basics - Anfänger-Themen 4
C Compiler-Fehler Wird eine if Bedingung nach einer for-Schleife nach jeder Iteration überprüft? Java Basics - Anfänger-Themen 1
F Koordinaten nach 360° auf 0° setzen Java Basics - Anfänger-Themen 2
N Operatoren Suchen nach einer bestimmten Eingabe (durch Scanner) Java Basics - Anfänger-Themen 7

Ähnliche Java Themen

Anzeige

Neue Themen


Oben