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

[Mika34]

Hallo an alle,

Ich melde mich heute wieder zu später Stunde, um euch nach einen Rat zu fragen. Ich habe vor zwei Tagen eine ähnliche Frage gehabt, in der ich mit der Modellierung von einer Breiten -und Tiefensuche Probleme hatte.
Jetzt erschließt sich mir ein weiteres Problem.
Ich habe den Code soweit durch eure Hilfe mir zusammenbauen können, jedoch stoße ich an die nächste Wand, wo ich nicht weiter komme.
Der Code sieht momentan so aus:

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 ConstructionWorker<T> {
    private Map<T, List<T>> edgesBetweenTwoPoints = new HashMap<>();

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

    public List<T> getEdges(T node) {
        return Collections.unmodifiableList(edgesBetweenTwoPoints.get(node));
    }

    public boolean isConnected() {
        if (edgesBetweenTwoPoints.isEmpty()) { return true; }
        Set<T> nodes = new HashSet<>(edgesBetweenTwoPoints.keySet());
        Iterator<T> it = nodes.iterator();
        if (it.hasNext()) {
            visitAndRemove(nodes, it.next());
        }
        return nodes.isEmpty();
    }

    private void visitAndRemove(Set<T> nodes, T node) {
        if (nodes.contains(node)) {
            nodes.remove(node);
            List<T> nextNodes = getEdges(node);
            for (T next : nextNodes) {
                visitAndRemove(nodes, next);
            }
        }
    }
}

Hierbei habe ich jedoch ein Problem, dass ich die Methoden nicht insofern verändern kann, dass beispielsweise der skizzierte Graph über die Knoten
A----B----C------D---E
verbunden ist und wenn man nun den Knoten D entfernt, dass der Graph dann nicht mehr zusammenhängend ist.
Hat jemand von euch eine Idee oder eine Richtung, wie sich dies implementieren lässt?
Wie immer bin ich tierisch dankbar über jede Hilfe! [/CODE]

 

[httpdigest]

Deine Implementierung ist eigentlich korrekt, so wie sie ist.

Hierbei habe ich jedoch ein Problem, dass ich die Methoden nicht insofern verändern kann, dass beispielsweise der skizzierte Graph über die Knoten verbunden ist und wenn man nun den Knoten D entfernt, dass der Graph dann nicht mehr zusammenhängend ist.

Du hast in deinem Satz leider viele Verneinungen verwendet, so dass ich gar nicht weiß, was genau du eigentlich möchtest, bzw. was nun genau nicht funktioniert.
Ich denke, das Problem wird sein, wie du denn eigentlich Knoten aus dem Graph genau entfernst. Das fehlt leider in deinem Code.

EDIT: Das Entfernen von Kanten und auch Knoten müsste in etwa so aussehen:

public void removeEdge(T fst, T snd) {
  edgesBetweenTwoPoints.getOrDefault(fst, Collections.emptyList()).remove(snd);
  edgesBetweenTwoPoints.getOrDefault(snd, Collections.emptyList()).remove(fst);
}
public void removeVertex(T v) {
  edgesBetweenTwoPoints.remove(v);
  for (List<T> dest : edgesBetweenTwoPoints.values()) {
    dest.remove(v);
  }
}

 

[Mika34]

Deine Implementierung ist eigentlich korrekt, so wie sie ist.

Du hast in deinem Satz leider viele Verneinungen verwendet, so dass ich gar nicht weiß, was genau du eigentlich möchtest, bzw. was nun genau nicht funktioniert.
Ich denke, das Problem wird sein, wie du denn eigentlich Knoten aus dem Graph genau entfernst. Das fehlt leider in deinem Code.

EDIT: Das Entfernen von Kanten und auch Knoten müsste in etwa so aussehen:

public void removeEdge(T fst, T snd) {
  edgesBetweenTwoPoints.getOrDefault(fst, Collections.emptyList()).remove(snd);
  edgesBetweenTwoPoints.getOrDefault(snd, Collections.emptyList()).remove(fst);
}
public void removeVertex(T v) {
  edgesBetweenTwoPoints.remove(v);
  for (List<T> dest : edgesBetweenTwoPoints.values()) {
    dest.remove(v);
  }
}

Ja, genau. Mein Problem war es, wie ich überhaupt die Knoten aus meinem Graphen entfernt bekomme.
Aber mit der Methode "removeVertex" entferne ich nun den Knoten im Graphen und im gleichen Schritt, dann auch die dazugehörigen Kanten, welche damit verbunden sind. Unter der Annahme, das ich deinen Code richtig gelesen habe.
Oder verstehe ich das falsch?
Aber dann wird mir nicht ersichtlich, wieso es dann noch eine "removeEdge" Methode geben muss, wenn man diese ohnehin mit der "removeVertex" Methode tun kann.

 

[httpdigest]

removeEdge() ist dann wichtig, wenn du eben nur eine Kante entfernen möchtest, und nicht gleich den ganzen Knoten. Das ist sinnvoll, wenn ein Knoten mehr als nur eine Kante zu anderen Knoten hat.

 

[Mika34]

Achso, so erschließt es sich.
Dabei ist mir gerade ein anderes Problem aufgefallen an der Implementierung. Wenn ich prüfen will, ob der Graph nach dem Entfernen eines Knotens streng zusammenhängend ist, dann muss ich
1.)den Knoten zwischenspeichern
2.)dann den Knoten entfernen
3.)dann prüfen, ob er immer noch zusammenhängend ist
Falls er nun noch zusammenhängend ist, dann kann ich die momentane Situation so belassen. Aber falls der Graph nicht mehr zusammenhängend ist, dann muss ich den gezwischenspeicherten Wert wieder in den Graphen einfügen.

Ist das der Weg, den man mittels dieser Implementierung verfolgen sollte oder könnte man das strukturierter und sinnvoller implementieren?

 

[httpdigest]

Um zu prüfen, ob ein beliebiger Graph zusammenhängend ist (egal, wie viele Knoten und Kanten du vorher oder nachher hinzugefügt oder entfernt hast), musst du das machen, was du bereits tust:
1. suche dir irgendeinen der Knoten im Graphen aus
2. führe eine Tiefensuche oder Breitensuche von diesem Knoten ausgehend durch den Graphen aus
3. merke dir alle durch diese Suche erreichten Knoten in einer Menge
Wenn diese Menge dieselbe ist wie die der aktuell im Graphen gespeicherten Knoten, dann ist der Graph zusammenhängend.

 

[Mika34]

Aber dann muss ich einen Knoten zunächst entfernen, um an die Zweite Menge zu kommen, was ohne nicht möglich wäre. Oder wie ist das zu verstehen?

 

[httpdigest]

Ach so, ich glaube, ich verstehe jetzt erst, was deine eigentlich Frage ist. Wenn du prüfen möchtest, ob ein Graph, der zum aktuellen Zeitpunkt noch zusammenhängend ist, auch nach dem hypothetischen Entfernen einer Kanten immer noch zusammenhängend sein würde, dann musst du einfach nur deine Tiefensuche entsprechend anpassen, dass sie eben nicht über die hypothetisch zu entfernende Kante traversiert. Du benötigst streng genommen also eine neue Methode, die die hypothetisch zu entfernende Kante als Parameter bekommt und als Rückgabewert einen boolean zurückliefert, der angibt, ob nach Entfernen dieser Kante der Graph noch zusammenhängend wäre (so er es denn schon vorher war).

 

[Mika34]

Ja genau. Also die Ausgangslage ist ein zusammenhängender Graph. Und nun soll ich prüfen, ob das Entfernen einer Kante aus dem zusammenhängenden Graphen einen nicht Zusammenhängenden macht.
Und wenn das eintritt, genau dann darf keine Kante entfernt werden. Also das ist mein Problem, wo ich gerade einfach nicht weiter komme und nicht verstehe, wie das auf Grundlage meiner bisherigen Implementierung umzusetzen ist.

 

[abc66]

Mit Guava geht das recht einfach:

import java.util.ArrayList;
import java.util.HashSet;
import com.google.common.graph.MutableValueGraph;
import com.google.common.graph.ValueGraphBuilder;

public class Test {
	
	public static void main(String[] args) {
		MutableValueGraph<String, Float> graph = ValueGraphBuilder.directed().build();
		graph.addNode("Hamburg");
		graph.addNode("Berlin");
		graph.addNode("Dresden");
		graph.addNode("München");
		graph.addNode("FFM");
		graph.addNode("Essen");
		graph.putEdgeValue("Hamburg", "Essen", 372.3f);
		graph.putEdgeValue("Hamburg", "Berlin", 288.8f);
		graph.putEdgeValue("Berlin", "Dresden", 193.2f);
		graph.putEdgeValue("Dresden", "Berlin", 193.2f);
		graph.putEdgeValue("Dresden", "München", 459.7f);
		graph.putEdgeValue("FFM", "Essen", 250.0f);

		ArrayList<String> set1 = new ArrayList<String>();
		set1.add("Hamburg"); // Wähle ersten node
		HashSet<String> set2 = new HashSet<String>(graph.nodes());
		while (!set1.isEmpty()) {
			String s = set1.remove(0);
			if (set2.remove(s)) {
				for (String t : graph.adjacentNodes(s)) {
					if (graph.hasEdgeConnecting(s, t)) {
						set1.add(t);
					}
				}
			}
		}
		System.out.println(set1);
		System.out.println(set2);
		System.out.println(set2.isEmpty());
	}
	
}

 

[httpdigest]

Also das ist mein Problem, wo ich gerade einfach nicht weiter komme und nicht verstehe, wie das auf Grundlage meiner bisherigen Implementierung umzusetzen ist.

Wenn du prüfen möchtest, ob ein Graph, der zum aktuellen Zeitpunkt noch zusammenhängend ist, auch nach dem hypothetischen Entfernen einer Kanten immer noch zusammenhängend sein würde, dann musst du einfach nur deine Tiefensuche entsprechend anpassen, dass sie eben nicht über die hypothetisch zu entfernende Kante traversiert. Du benötigst streng genommen also eine neue Methode, die die hypothetisch zu entfernende Kante als Parameter bekommt und als Rückgabewert einen boolean zurückliefert, der angibt, ob nach Entfernen dieser Kante der Graph noch zusammenhängend wäre (so er es denn schon vorher war).

Spoiler

import java.util.*;
public class Graph<T> {
  private final Map<T, List<T>> es = new HashMap<>();

  public void addEdge(T fst, T snd) {
    es.computeIfAbsent(fst, x -> new ArrayList<T>()).add(snd);
    es.computeIfAbsent(snd, x -> new ArrayList<T>()).add(fst);
  }
  public boolean isConnectedAfterRemoving(T fst, T snd) {
    if (es.isEmpty())
      return true;
    Set<T> notVisited = new HashSet<T>(es.keySet());
    visit(es.keySet().iterator().next(), notVisited, fst, snd);
    return notVisited.isEmpty();
  }
  private void visit(T next, Set<T> notVisited, T fst, T snd) {
    if (!notVisited.remove(next))
      return;
    for (T t : es.get(next))
      if ((next != fst || t != snd) && (next != snd || t != fst))
        visit(t, notVisited, fst, snd);
  }
  // Test
  public static void main(String[] args) {
    Graph<Integer> g = new Graph<>();
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
    System.out.println(g.isConnectedAfterRemoving(2, 3));
    System.out.println(g.isConnectedAfterRemoving(3, 4));
  }
}

 

[abc66]

Sorry nochmal was geändert:

import java.util.ArrayList;
import java.util.HashSet;

import com.google.common.graph.MutableValueGraph;
import com.google.common.graph.ValueGraphBuilder;

public class Test {

	static boolean isStronglyConnectedComponent(MutableValueGraph<String, Float> g) {
		for (String n : g.nodes()) {
			ArrayList<String> list1 = new ArrayList<String>();
			list1.add(n); // Wähle ersten node
			HashSet<String> set2 = new HashSet<String>(g.nodes());
			while (!list1.isEmpty()) {
				String s = list1.remove(0);
				if (set2.remove(s)) {
					for (String t : g.adjacentNodes(s)) {
						if (g.hasEdgeConnecting(s, t)) {
							list1.add(t);
						}
					}
				}
			}
			if (!set2.isEmpty()) {
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		MutableValueGraph<String, Float> graph = ValueGraphBuilder.directed().build();
		graph.addNode("Hamburg");
		graph.addNode("Berlin");
		graph.addNode("Dresden");
		graph.addNode("München");
		graph.addNode("FFM");
		graph.addNode("Essen");
		graph.putEdgeValue("Essen", "Hamburg", 372.3f);
		graph.putEdgeValue("Hamburg", "Essen", 372.3f);
		graph.putEdgeValue("Hamburg", "Berlin", 288.8f);
		graph.putEdgeValue("Berlin", "Dresden", 193.2f);
		graph.putEdgeValue("Dresden", "Berlin", 193.2f);
		graph.putEdgeValue("Dresden", "München", 459.7f);
		graph.putEdgeValue("FFM", "Essen", 250.0f);
		graph.putEdgeValue("Essen", "FFM", 250.0f);
		System.out.println(isStronglyConnectedComponent(graph));
		graph.putEdgeValue("München", "FFM", 392.1f);
		System.out.println(isStronglyConnectedComponent(graph));
	}

}

 

[Mika34]

Schönen Mittag nochmal,

Ich habe gestern Abend es versucht zu implementieren, jedoch sitze ich bis jetzt immer noch dran, weil es nicht funktioniert wie es soll.
Mein Problem ist momentan, dass ich Koordinaten entfernen möchte, bzw. hinzufügen möchte und dies mir gerade höllisch Probleme bereitet. Bis jetzt, sieht die Modellierung wie folgt aus, in Abwandlung zu httpdigest seinem Code

public class CartesianPoint <T>{
    private int xCoordinate;
    private int yCoordinate;
    private boolean isConnected;
    
    public CartesianPoint(int xCoordinate, int yCoordinate) {
        this.xCoordinate = xCoordinate;
        this.yCoordinate = yCoordinate;
    }
    
   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(T fst, T snd) {
        if (edgesBetweenTwoPoints.isEmpty())
          return true;
        Set<T> notVisited = new HashSet<T>(edgesBetweenTwoPoints.keySet());
        visit(edgesBetweenTwoPoints.keySet().iterator().next(), notVisited, fst, snd);
        return notVisited.isEmpty();
      }
    
    private void visit(T next, Set<T> notVisited, T fst, T snd) {
        if (!notVisited.remove(next))
          return;
        for (T t : edgesBetweenTwoPoints.get(next))
          if ((next != fst || t != snd) && (next != snd || t != fst))
            visit(t, notVisited, fst, snd);
      }

}

 

[httpdigest]

Du bringst hier glaube ich in der Modellierung etwas durcheinander: Dein Graph ist kein kartesicher Punkt, sondern er enthält Punkte, bzw. er enthält Kanten zwischen jeweils zwei Punkten.
Dementsprechend würde ich stattdessen eine Klasse "Graph<T>" schreiben und eine separate Klasse "CartesianPoint". Dann kannst du für T im Graph die Klasse CartesianPoint verwenden. Du hast dann also ein "Graph of CartesianPoint(s)".

 

[Mika34]

Du bringst hier glaube ich in der Modellierung etwas durcheinander: Dein Graph ist kein kartesicher Punkt, sondern er enthält Punkte, bzw. er enthält Kanten zwischen jeweils zwei Punkten.
Dementsprechend würde ich stattdessen eine Klasse "Graph<T>" schreiben und eine separate Klasse "CartesianPoint". Dann kannst du für T im Graph die Klasse CartesianPoint verwenden. Du hast dann also ein "Graph of CartesianPoint(s)".

Ok, das habe ich nun gemacht, das war aber auch sehr schwachsinnig. Aber nun habe ich das Problem, dass die Methode isConnected nicht dahingehend funktioniert, dass sie erkennt wenn ein Graph so aufgebaut ist:
A-----B-----C----D
Wenn man hier nun die Kante von C nach D entfernt, dann ist der Graph trotzdem noch streng zusammenhängend, jedoch gibt mir die Methode durchgehend ein false zurück, dass dieser nicht mehr zusammenhängend ist. Denn wenn ich hier die Kante entferne, entferne ich automatisch auch den Knoten D. Ich hab das in einem Beispiel ausprobiert und meine Modellierung angepasst.

public class Graph <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(T fst, T snd) {
        if (edgesBetweenTwoPoints.isEmpty())
          return true;
        Set<T> notVisited = new HashSet<T>(edgesBetweenTwoPoints.keySet());
        visit(edgesBetweenTwoPoints.keySet().iterator().next(), notVisited, fst, snd);
        return notVisited.isEmpty();
      }
    
    private void visit(T next, Set<T> notVisited, T fst, T snd) {
        if (!notVisited.remove(next))
          return;
        for (T t : edgesBetweenTwoPoints.get(next))
          if ((next != fst || t != snd) && (next != snd || t != fst))
            visit(t, notVisited, fst, snd);
      }
    
    
    public static void main(String[] args) {
        TrackRemover<CartesianPoint> g = new TrackRemover<>();
        CartesianPoint p1 = new CartesianPoint(1,1);
        CartesianPoint p2 = new CartesianPoint(5,1);
        CartesianPoint p3 = new CartesianPoint(8,1);
        CartesianPoint p4 = new CartesianPoint(10,1);

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

        System.out.println(g.isConnectedAfterRemoving(p3, p4));
      }
}

 

[httpdigest]

Wenn man hier nun die Kante von C nach D entfernt, dann ist der Graph trotzdem noch streng zusammenhängend, jedoch gibt mir die Methode durchgehend ein false zurück, dass dieser nicht mehr zusammenhängend ist. Denn wenn ich hier die Kante entferne, entferne ich automatisch auch den Knoten D.

Für die Methode gilt ein Knoten nicht automatisch als entfernt, nur weil du die letzte Kante zu ihm entfernt hast. Das ist dann auch Definitionssache. Ein Knoten kann ja auch ohne Kante in einem Graphen existieren. Wenn du das nicht möchtest, musst du die Methoden isConnectedAfterRemoving() und visit() noch etwas anpassen, dass sie den bzw. die entfernten Knoten nicht mehr berücksichtigen.

 

[Mika34]

Für die Methode gilt ein Knoten nicht automatisch als entfernt, nur weil du die letzte Kante zu ihm entfernt hast.

Ich habe den Knoten in einer anderen Map gelöscht, in dem ich Objekte gespeichert habe, jedoch komme ich nicht an die Knoten in der Klasse Graph dran, da diese gar nicht in der Modellierung vorkommen.
In meiner anderen Map, sind diese durch startX und startY Koordinaten bestimmt. Hier habe ich auf die keinen Zugriff, wodurch sich dieser nicht entfernen lässt.

 

[httpdigest]

Ich habe den Knoten in einer anderen Map gelöscht, in dem ich Objekte gespeichert habe, jedoch komme ich nicht an die Knoten in der Klasse Graph dran, da diese gar nicht in der Modellierung vorkommen.
In meiner anderen Map, sind diese durch startX und startY Koordinaten bestimmt. Hier habe ich auf die keinen Zugriff, wodurch sich dieser nicht entfernen lässt.

Wovon redest du? Meine Aussage war nur, dass aktuell die Methode isConnectedAfterRemoving() nicht berücksichtigt, dass Knoten komplett aus dem Graph entfallen, wenn sie nur noch eine Kante zu anderen Knoten besitzen und diese Kante gelöscht werden würde.
Um das zu berücksichtigen, kann man die Methode wie folgt anpassen:

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

EDIT: Kleinen Bug gefixed.

 

[Mika34]

Oh je, ich glaube ich bringe hier ziemlich viel durcheinander.
Wenn ich einen Graphen habe der so aussieht:
A-----B-----C----D
und ich entferne die Kante C----D, dann bleibt dies übrig
A-----B-----C
Jedoch verstehe ich nicht wie sich das implementieren lässt oder, ob das überhaupt möglich ist unter gegebener Modellierung meinerseits

 

[httpdigest]

Jedoch verstehe ich nicht wie sich das implementieren lässt oder, ob das überhaupt möglich ist unter gegebener Modellierung meinerseits

Ist möglich. Siehe Code oben. Du brauchst einfach nur zu prüfen, ob ein Knoten keine Kante mehr besitzen würde, nachdem die zu entfernende Kante entfernt werden würde.

 

[Mika34]

Oh, Herr *facepalm*, du hast vollkommen Recht. Vielen Dank *erneutes facepalm*.
Jedoch habe ich noch eine kleine Verständnisfrage, falls es in Ordnung für dich ist.
Angenommen wir haben so einen Graphen:

A----B----C----D
          |
          |
          E
Und man entferne nun gleichzeitig die Kanten: C-----D und C
                                                         |
                                                         |
                                                         E

Wenn man nun auf die gleiche Frage prüft, ob der Graph nach dem gleichzeitigen Entfernen von diesen beiden Kanten immer noch zusammenhängend ist, geht man wie oben in deinem Code vor, oder wäre hier besondere Obacht geboten?

 

[mihe7]

Oh je, ich glaube ich bringe hier ziemlich viel durcheinander.
Wenn ich einen Graphen habe der so aussieht:
A-----B-----C----D
und ich entferne die Kante C----D, dann bleibt dies übrig
A-----B-----C
Jedoch verstehe ich nicht wie sich das implementieren lässt oder, ob das überhaupt möglich ist unter gegebener Modellierung meinerseits

In der Map würde das so aussehen:

A->[B]
B->[A,C]
C->[B,D]
D->[C]

Die Schlüssel (links) bilden die Knotenmenge, also {A,B,C,D}. Jetzt beginnst Du mit dem Besuch eines beliebigen Knotens. Zum Beispiel B. Wenn Du einen Knoten besuchst, merkst Du Dir als erstes, dass Du diesen bereits besucht hast. Das ist wichtig, um Zyklen zu erkennen. Dann werden alle Kanten betrachtet und dabei die noch nicht besuchten Knoten besucht. Wenn am Ende die gesamte Knotenmenge besucht wurde, ist der Graph zusammenhängend.

Statt sich zu merken, welche Knoten man besucht hat, kann man sich auch merken, welche Knoten man noch nicht besucht hat (das macht der Algorithmus aus dem Eröffnungspost).

Wenn Du die Kante C-D entfernst, ändert sich die Map wie folgt:

A->[B]
B->[A,C]
C->[B]
D->[]

Es gibt nun keine Verbindung mehr von/zu D, was von dem Algorithmus erkannt werden würde -> nicht zusammenhängend.

Statt die Verbindung tatsächlich aus der Map zu entfernen, musst Du lediglich dafür sorgen, dass die betreffenden Kanten (C->D und D->C) nicht verarbeitet werden.

Was die Frage

Wenn man nun auf die gleiche Frage prüft, ob der Graph nach dem gleichzeitigen Entfernen von diesen beiden Kanten immer noch zusammenhängend ist, geht man wie oben in deinem Code vor, oder wäre hier besondere Obacht geboten?

beantworten dürfte

 

[Mika34]

Natürlich macht das total Sinn, da dies im Grunde auch nur eine Suche danach ist. Jedoch komme ich nicht auf den Weg, inwiefern man vorzugehen habe, wenn zwei Kanten auf einmal zu entfernen seien. Dies ist mir im Moment noch nicht total schlüssig geworden auf der Grundlage des Codes. Mein Ansatz wäre, dass man diesen Algorithmus zwei mal durchlaufen lässt und dann jeweils zwei booleans miteinander vergleicht und wenn beide auf true zeigen, hat sich die Sache erledigt und man kann beide entfernen.
Ist dies ein primitivier Ansatz oder gibt es einen Weg, welcher dies effizienter lösen würde?

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

 

[mihe7]

Mein Ansatz wäre, dass man diesen Algorithmus zwei mal durchlaufen lässt und dann jeweils zwei booleans miteinander vergleicht und wenn beide auf true zeigen, hat sich die Sache erledigt und man kann beide entfernen.

Das liefert i. A. falsche Ergebnisse, weil beim zweiten Durchlauf die erste Kante wieder im Graph vorhanden ist.

gibt es einen Weg, welcher dies effizienter lösen würde?

Sicher, Du musst lediglich eine Menge von Kanten an die Methode übergeben und die betreffenden Kanten rausfiltern.

 

[Mika34]

Ich habe mich nun daran versucht, jedoch prüft die Methode nicht richtig, das heißt es wird durchweg ein falscher Wert zurückgegeben, mit dem ich nicht auf das gewünschte Ergebnis komme.
Ist mein Ansatz falsch oder geht es nur über einen anderen Weg?

   public boolean isConnectedAfterRemovingWithThree(T fst, T snd, T thrd) {
        if (edgesBetweenTwoPoints.isEmpty())
          return true;
        Set<T> notVisited = new HashSet<T>(edgesBetweenTwoPoints.entrySet().stream()
            .filter(e -> e.getValue().stream()
                .filter(d -> !d.equals(fst) && !d.equals(snd) && !d.equals(thrd))
                .count() > 0)
            .map(e -> e.getKey())
            .collect(java.util.stream.Collectors.toSet()));
        visitThreeEdges(notVisited.iterator().next(), notVisited, fst, snd, thrd);
        return notVisited.isEmpty();
      }

 private void visitThreeEdges(T next, Set<T> notVisited, T fst, T snd, T thrd) {
        if (!notVisited.remove(next))
          return;
        for (T t : edgesBetweenTwoPoints.get(next))
            if ((!next.equals(fst) || !t.equals(snd)) && (!next.equals(snd) || !t.equals(fst))&& (!next.equals(thrd) || !t.equals(fst))
                    && (!next.equals(fst) || !t.equals(thrd))&& (!next.equals(thrd) || !t.equals(snd))&& (!next.equals(snd) || !t.equals(thrd)))
                visitThreeEdges(t, notVisited, fst, snd, thrd);
      }

 

[httpdigest]

Du musst dir erstmal im Klaren darüber werden, was es genau ist, das du aus dem Graphen entfernen möchtest. Möchtest du nun Kanten oder Knoten entfernen? Meine ursprüngliche Methode `isConnectedAfterRemoving(T fst, T snd)` ging davon aus, dass du die Kante zwischen den beiden Knoten `fst` und `snd` entfernen möchtest. Das führt nicht notwendigerweise zum Entfernen von `fst` oder `snd` als Knoten.
Unter dieser Annahme macht deine Erweiterung der Methode mit drei Parametern keinen Sinn.

 

[Mika34]

Doch ich möchte die Kante zwischen zwei Knoten entfernen, wie in diesem Beispiel:
A-----B-----C----D
ich entferne die Kante C----D, dann bleibt dies übrig
A-----B-----C
Der Kernaspekt, welchen ich verfolge ist, dass aus einem Graphen, welcher zusammenhängend ist, nicht zwei Teilgraphen entstehen, wie in diesem Beispiel. Hier dürfte man nicht eine Kante entfernen, da man dann zwei Graphen hat, ausgehend von einem Graphen, der zusammenhängend war:
A-----B-----C----D-----E----F
ich entferne die Kante C----D, dann bleibt dies übrig
A-----B-----C D----E-----F

Dabei bin ich dann ins Grübeln gekommen, wenn man zwei Kanten entfernen möchte, ausgehend von einem Knoten, ob man hier prüfen kann, ob nach dem Entfernen immer noch ein zusammenhängender Graph übrig bleibt und nicht zwei unabhängige Graphen wie im letzten Beispiel

 

[httpdigest]

Doch ich möchte die Kante zwischen zwei Knoten entfernen, wie in diesem Beispiel:

Du möchtest also die Kante zwischen zwei Knoten entfernen, indem du drei Knoten angibst... das ergibt keinen Sinn.
Und wenn du hier meintest, dass du zwei Kanten testen/entfernen möchtest, dann werden zwei Kanten nicht durch drei Knoten definiert, sondern durch vier. Es sei denn natürlich, dass einer der Knoten von den beiden Kanten gemeinsam genutzt wurde.
By the way: Was du erreichen möchtest, ist mir schon klar, das hast du bereits dreimal ausführlich erklärt.
Mein Punkt ist nur, dass es keinen Sinn macht, zwei Kanten durch drei Knoten anzugeben.

 

[Mika34]

In meiner Modellierung kann ich Kanten nur senkrecht oder waagrecht setzen. Jeder Anfangspunkt und jeder Endpunkt einer Kante sind Knoten. Hierbei dürfen Kanten nur von einem anderen Anfangspunkt/Endpunkt einer anderen Kante beginnen bzw. aufhören. Deshalb möchte ich zwei Kanten durch drei Knoten modellieren, da ein Knoten, dann von zwei Kanten genutzt wird.
Das ist der Grund, weshalb ich drei Kanten durch zwei Knoten angebe.
Und hierbei bin ich noch auf keine eindeutige Lösung gekommen, wie man das richtig in die Tat umsetzen soll, bezogen auf das gleichzeitige Entfernen von zwei Kanten ausgehend von einem Knoten.

 

[LimDul]

In meiner Modellierung kann ich Kanten nur senkrecht oder waagrecht setzen. Jeder Anfangspunkt und jeder Endpunkt einer Kante sind Knoten. Hierbei dürfen Kanten nur von einem anderen Anfangspunkt/Endpunkt einer anderen Kante beginnen bzw. aufhören. Deshalb möchte ich zwei Kanten durch drei Knoten modellieren, da ein Knoten, dann von zwei Kanten genutzt wird.
Das ist der Grund, weshalb ich drei Kanten durch zwei Knoten angebe.
Und hierbei bin ich noch auf keine eindeutige Lösung gekommen, wie man das richtig in die Tat umsetzen soll, bezogen auf das gleichzeitige Entfernen von zwei Kanten ausgehend von einem Knoten.

Das verstehe ich nicht? Ein Knoten ist keine Kante. Modelliere das als getrennte Objekte, dann wird es mit Sicherheit viel einfacher.

 

[Mika34]

Das verstehe ich nicht? Ein Knoten ist keine Kante. Modelliere das als getrennte Objekte, dann wird es mit Sicherheit viel einfacher.

Also so sollte ein Beispielgraph aussehen:

https://imgur.com/a/Sxp3knO

.
Eine Kante darf nur auf einem Start bzw. Endpunkt einer anderen Kante beginnen und demnach wird ein Knoten zwei Kanten zugeordnet. Und wenn ich nun eine Kante entferne, sollen keine zwei Teilgraphen aus diesem entstehen. Das ist momentan die Modllierungsfrage

 

[LimDul]

Dann hast du 12 Knoten Objekte (Jeweils mit x/y-Koordinate) und 13 Kanten-Objekte (jeweils mit 2 Knoten Objekten als Referenz)

Und dann kann man darauf all das vorher gesagt anwenden.

 

[Mika34]

Dann hast du 12 Knoten Objekte (Jeweils mit x/y-Koordinate) und 13 Kanten-Objekte (jeweils mit 2 Knoten Objekten als Referenz)

Und dann kann man darauf all das vorher gesagt anwenden.

Ja, genau. Diese Methode funktioniert auch schon, mit der Hilfe von httpdigest.

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

Jedoch hapert es noch an der Stelle bei mir, wenn eine Weiche entfernt wird, sprich zwei Kanten auf einmal. Denn dann ist zu prüfen, ob der Graph nach dem Entfernen von zwei Kanten nicht in zwei Teilgraphen zerfällt.

 

[Mika34]

Nochmal schönen Abend an die, die noch wach sind.
Ich versuche mich nun seit Stunden an der besagten Methode, die zwei Kanten simultan entfernen soll, jedoch will es einfach nicht klappen. Er schaltet einfach nicht wie er soll.
Hat jemand von Euch eine Idee, wie ich dies implementieren kann, da meine Implementierung nur den Bach untergeht.
Darüber wäre ich tierisch dankbar.

 

[mihe7]

Erstmal Kanten modellieren:

import java.util.*;

class Edge<T> {
    private final T source;
    private final T dest;

    public Edge(T source, T dest) {
        this.source = source;
        this.dest = dest;
    }

    @Override
    public boolean equals(Object o) {
        if (o == null || o == this || !(o instanceof Edge)) {
            return o == this;
        }

        Edge<?> edge = (Edge<?>) o;
        return Objects.equals(source, edge.source) &&
               Objects.equals(dest, edge.dest);
    }

    @Override
    public int hashCode() {
        return Objects.hash(source, dest);
    }
}

Und dann die Methoden anpassen:

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

Achtung: der Spaß ist ungetestet.

 

[Mika34]

Erstmal Kanten modellieren:

import java.util.*;

class Edge<T> {
    private final T source;
    private final T dest;

    public Edge(T source, T dest) {
        this.source = source;
        this.dest = dest;
    }

    @Override
    public boolean equals(Object o) {
        if (o == null || o == this || !(o instanceof Edge)) {
            return o == this;
        }

        Edge<?> edge = (Edge<?>) o;
        return Objects.equals(source, edge.source) &&
               Objects.equals(dest, edge.dest);
    }

    @Override
    public int hashCode() {
        return Objects.hash(source, dest);
    }
}

Und dann die Methoden anpassen:

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

Achtung: der Spaß ist ungetestet.

Aber dann wird in deiner Modellierung der Fall gar nicht aufgegriffen, wenn zwei Kanten zur gleichen Zeit entfernt werden oder habe ich ein riesiges Brett vor der Stirn

 

[mihe7]

Aber dann wird in deiner Modellierung der Fall gar nicht aufgegriffen, wenn zwei Kanten zur gleichen Zeit entfernt werden oder habe ich ein riesiges Brett vor der Stirn

Du übergibst an isConnectedAfterRemoving eine Menge von Kanten, so dass Du prüfen kannst, ob der Graph nach der Entfernung einer beliebigen Anzahl von Kanten noch zusammenhängend wäre.

 

[DagobertDuck]

@mihe7 Wenn man für ein Projekt als Kantentyp z. B. nur <Point> braucht, sollte man dann auch als Typ-Parameter <Point> nehmen, oder ist es besserer Programmierstil, wenn man <T> nimmt, sodass es später ggf. noch angepasst werden kann?

 

[DagobertDuck]

Oder z. B. private Map<Point, List<Point>> edgesBetweenTwoPoints = new HashMap<>(); anstatt private Map<T, List<T>> edgesBetweenTwoPoints = new HashMap<>(); .

 

[mihe7]

T kannst Du nur nehmen, wenn die Klasse einen Typparameter T hat.

class X<T> {
   private Map<T, List<T>> edges;
}

 

[Mika34]

Erstmal Kanten modellieren:

import java.util.*;

class Edge<T> {
    private final T source;
    private final T dest;

    public Edge(T source, T dest) {
        this.source = source;
        this.dest = dest;
    }

    @Override
    public boolean equals(Object o) {
        if (o == null || o == this || !(o instanceof Edge)) {
            return o == this;
        }

        Edge<?> edge = (Edge<?>) o;
        return Objects.equals(source, edge.source) &&
               Objects.equals(dest, edge.dest);
    }

    @Override
    public int hashCode() {
        return Objects.hash(source, dest);
    }
}

Und dann die Methoden anpassen:

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

Achtung: der Spaß ist ungetestet.

@mihe7 Was bedeutet hier das Object?

    @Override
    public boolean equals(Object o) {
        if (o == null || o == this || !(o instanceof Edge)) {
            return o == this;
        }

        Edge<?> edge = (Edge<?>) o;
        return Objects.equals(source, edge.source) &&
               Objects.equals(dest, edge.dest);
    }

    @Override
    public int hashCode() {
        return Objects.hash(source, dest);
    }

 

[temi]

Was bedeutet hier das Object?

Das ist die Java Klasse Object, von der alle Klassen in Java implizit erben.

Wenn du dir auf der o.g. Seite die Methode equals() anschaust, dann wirst du erkennen, dass deren Signatur ein Object als Parameter fordert. Das ist auch sinnvoll, denn du möchtest ja auch jede Art von Objekt vergleichen können.

Etwas weiter unten findest du auch die Anforderungen, welche die Methode equals() erfüllen sollte.

 

[Mika34]

Oh, ich dachte ich habe die Implementierung nur verrafft. Alles klar
Jetzt habe ich aber noch eine Frage. In @mihe7 existiert keine Methode addEdge. Ist diese dann von der vorherigen Imlementierung mittels

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

zu implementieren?

 

[Mika34]

@mihe7 Es gibt ein Problem. Ich komme momentan bei deiner Modellierung dort nicht weiter.
Wenn ich:
A----B----C----D habe und nun die Kante von B-----C entferne, dann sagt er, das der Graph zusammenhängend ist, aber eigentlich ist er in zwei Teile zerbrochen. Hast du eine Idee, was da falsch läuft?

 

[mihe7]

Hast du eine Idee, was da falsch läuft?

Wenn Du ausführbaren Beispielcode hast, kann ich mir das gerne anschauen.

Aber: Euren Beiträgen nach zu urteilen, bearbeitest Du die gleiche Aufgabe wie @DagobertDuck. Hier im Thread ging es allgemein um einen Graphen. Wenn Du ein Modell willst, das für die Aufgabe geeigneter ist, dann schau mal hier https://www.java-forum.org/thema/zusammenhaengenden-graphen-fuer-gleisnetz-erstellen.187364/ rein.

 

[abc66]

Hm dürft ihr wohl https://github.com/google/guava/wiki/GraphsExplained verwenden? Das hatte ich in einem der vielen Graph Themen auch schonmal erwähnt.

 

[abc66]

/e Oh oh, shit shit shit, das war ja in diesem Thema.

 

[Mika34]

Mein Code sieht momentan so aus. Jedoch bin ich mir nicht sicher, ob es so in Ordnung geht oder ob ich die addEdge Methode in der EdgeRemover Klasse doch implementieren muss. Könnt ihr mich aufschließen?

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 EdgeRemover<T> {

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

 

    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);
    }
}
[B]import[/B] java.util.Objects;





[B]class[/B] Edge<CartesianPoint> {


    [B]private[/B] [B]final[/B] CartesianPoint source;


    [B]private[/B] [B]final[/B] CartesianPoint dest;





    [B]public[/B] Edge(CartesianPoint source, CartesianPoint dest) {


        [B]this[/B].source = source;


        [B]this[/B].dest = dest;


    }





    @Override


    [B]public[/B] [B]boolean[/B] equals(Object o) {


        [B]if[/B] (o == [B]null[/B] || o == [B]this[/B] || !(o [B]instanceof[/B] Edge)) {


            [B]return[/B] o == [B]this[/B];


        }





        Edge<?> edge = (Edge<?>) o;


        [B]return[/B] Objects.[I]equals[/I](source, edge.source) &&


               Objects.[I]equals[/I](dest, edge.dest);


    }





    @Override


    [B]public[/B] [B]int[/B] hashCode() {


        [B]return[/B] Objects.[I]hash[/I](source, dest);


    }


}

 

[Mika34]

Da die Edge Klasse falsch formatiert wurde, hier die richtig Formatierte

import java.util.Objects;

class Edge<CartesianPoint> {
    private final CartesianPoint source;
    private final CartesianPoint dest;

    public Edge(CartesianPoint source, CartesianPoint dest) {
        this.source = source;
        this.dest = dest;
    }

    @Override
    public boolean equals(Object o) {
        if (o == null || o == this || !(o instanceof Edge)) {
            return o == this;
        }

        Edge<?> edge = (Edge<?>) o;
        return Objects.equals(source, edge.source) &&
               Objects.equals(dest, edge.dest);
    }

    @Override
    public int hashCode() {
        return Objects.hash(source, dest);
    }
}

 

[mihe7]

Hast Du in CartesianPoint auch equals und hashCode überschrieben?