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

Diskutiere Untersuchen ob ein Graph nach entfernen einer Kante immer noch zusammenhängend ist im Java Basics - Anfänger-Themen Bereich.
M

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:
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 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]
 
H

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:
Java:
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);
  }
}
 
Zuletzt bearbeitet:
M

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:
Java:
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.
 
H

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

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

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

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

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

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

abc66

Mit Guava geht das recht einfach:
Java:
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());
	}
	
}
 
H

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).
Java:
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));
  }
}
 
Zuletzt bearbeitet:
A

abc66

Sorry nochmal was geändert:
Java:
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));
	}

}
 
M

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

}
 
H

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

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.
Java:
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));
      }
}
 
H

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

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

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:
Java:
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. :)
 
Zuletzt bearbeitet:
M

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
 
H

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.
 
Thema: 

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

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben