Problem in der Modellierung

Mika34

Bekanntes Mitglied
Schönen Abend an Alle,

Ich sitze gerade etwas verdutzt seit nun einer Stunde vor einer Modellierungsfrage vor mir und ich weiß gerade noch nicht so recht, ob mein Lösungsansatz richtig ist oder es komplett in die falsche Richtung geht. Da es etwas Background brauch, habe ich mich leider nicht kürzer fassen können und entschuldige mich im Vorhinein... Sorry

Nun zu meinem Problem: Ich möchte eine Modelleisenbahnstrecke bauen, welche man sich als einen Graphen mit Knoten und Kanten vorstellen kann. Die Knoten dürfen nur senkrecht oder waagrecht zueinander sein und werden durch ein Tupel von zwei Int Werten beschrieben. Auf den Kanten fahren dann die Modelleisenbahnen. Nun bin ich gerade besorgt, ob meine Modellierung Sinn ergibt oder nicht und bitte euch um Rat...
Momentan habe ich eine Liste von Tupeln, in welcher einzelne Gleise gespeichert sind. Ein Gleis besteht aus einem Startpunkt-Tupel und einem Endpunkt-Tupel. Jetzt habe ich aber das Problem, das ich diese Tupel in keine Relation zueinander stellen kann. Denn wenn ich ein Gleis entfernen möchte, dann geht das nur, wenn am Ende alle Gleisstücke nach dem Entfernen von Einem immer noch miteinander verbunden sind. Also es darf kein Gleis existieren, welches nicht in Relation zu einem Anderen steht. Mein Ansatz wäre über eine Tiefensuche über Start- und Endknoten gegangen, jedoch bin ich mir nicht sicher, ob meine Modellierung bis zum Status Quo überhaupt richtig ist.

Ich bin über jede Hilfe tierisch dankbar :)

Liebe Grüße
 

MoxxiManagarm

Top Contributor
Du musst doch nur von Start und Ende schauen, ob diese noch ein anderes Gleis haben, oder verstehe ich was falsch? Also angenommen du hast das Netz

Code:
A-B
| |
C-D

Dann kannst du das Gleis zwischen C und D entfernen, Weil C noch ein Gleis zu A und D noch ein Gleis zu B hat. Das der Rest vom Netz noch zusammenhängt wird vorausgesetzt.


Im übrigen ähnelt die Beschreibung noch dem Spiel Bridges (heißt das so?). Du weißt schon, das Rätsel mit den Zahlenkreisen und den Brücken dazwischen. Vielleicht hilft dir das.
 

mihe7

Top Contributor
Spontan würde ich sagen, dass sich eine Kante genau dann entfernen lässt, wenn ihre beiden Knoten sich auf einem Kreis befinden. EDIT: was aber auch auf die Tiefensuche rausläuft.
 

Mika34

Bekanntes Mitglied
Guten Morgen,

Ja, genau. Hier geht es darum, das am Ende ein immer noch ein zusammenhängender Graph vorhanden sein muss, wenn man eine Kante entfernt. Also es ist am Ende immer noch ein zusammenhängender Graph und nicht zwei unabhängige Graphen, welche getrennt voneinander sind.
Aber in welchem Zusammenhang lässt sich dies modellieren?
 

LimDul

Top Contributor
Ich verstehe jetzt nicht ganz, wo das Problem ist. Kante entfernen, Tiefensuche oder Breitensuche von einem beliebigen Startknoten aus. Wenn Menge der gefunden Punkte = Gesamtmenge aller Punkte ist der Graph noch zusammenhängend.
 

Mika34

Bekanntes Mitglied
Ich glaube meine Formulierung war etwas unglücklich. Ich verstehe noch nicht ganz wie ich das insgesamt modellieren soll. Momentan habe ich ein zweidimensionales Array, in welchem ich Kanten von einem Knoten zu einem anderen Knoten so modelliert habe, dass alle Elemente im Array zwischen diesen beiden Knoten mit einem Objekt gefüllt sind (zum Beispiel einem Gleis). Somit gewährleiste ich, das diese Kanten auch tatsächlich als Wege genutzt werden können.
Wenn ich nun eine Kante entferne, dann entferne ich auch alle Elemente des zweidimensionalen Arrays, die sich auf dieser Kante befinden.
Nun verstehe ich aber nicht, wie ich nun über Breitensuche oder Tiefensuche prüfen soll, ob die Menge der gefundenen Punkte = Gesamtmenge aller Punkt sind.
 

LimDul

Top Contributor
Wirf die Arrays weg. Arrays sind dumme Datenobjekte. Du versucht deine Informationen (wer mit wem verbunden ist) durch Array-Positionen abzubilden. Das ist nicht Objektorentiert.

Simples Beispiel, wie man machen könnte:

Java:
public class Gleis {
   private Set<Gleis> verbundeneGleise = new HashSet<>();

   protected void removeVerbindungInternal(Gleis gleis) {
     verbundeneGleise.remove(gleis);
   }

   public void removeVerbindung(Gleis gleis) {
      removeInternal(gleis);
      gleis.removeInternal(this);
   }

  protected void addVerbindungInternal(Gleis gleis) {
    verbundeneGleise.add(gleis);
  }

  public void addVerbindung(Gleis gleis) {
    addVerbindungInternal(gleis);
    gleis.addVerbindungInternal(this);
  }
}

Und dann kannst du auf der Objektstruktur eine simple Tiefen oder Breitensuchen laufen lassen.
 

LimDul

Top Contributor
Oh doch. Arrays sind sehr wohl Objekte innerhalb der Objektorientierung - wenn man sie denn sinnvoll einzusetzen weiß.

Stichworte zum Einstieg sind hier Adjazenzmatrizen und (vs.) Adjazenzlisten.
Ja, Arrays sind Datenobjekte - allerdings kann ich einem Array keine Logik beibringen. In einem Array speichere ich Daten, wenn die Daten quasi direkt ein Array sind. Aber sobald ich Logik brauche oder zusätzliche Attribute, ist ein Array schnell raus. Ich kann Array gerne in einem Objekt als Member verwenden, wenn es für die Daten entsprechend passt. Aber wie hier, wo ich Gleise und Verbindungen zwischen diesen habe, diese Fachlichkeit durch Arrays abzubilden ist eben nicht mehr objektorientiert. Ich verliere die Möglichkeit zusätzliche Informationen zu speichern. Es sei denn ich packe sie in die Objetke - aber dann muss ich sicherstellen, dass Änderungen am Objekt und an der Array Befüllung synchron sind. Und an der Stelle komme ich mit Arrays nicht mehr weit.
 

Blender3D

Top Contributor
Oh doch. Arrays sind sehr wohl Objekte innerhalb der Objektorientierung - wenn man sie denn sinnvoll einzusetzen weiß.

Stichworte zum Einstieg sind hier Adjazenzmatrizen und (vs.) Adjazenzlisten.
Stimmt treffend.
Die Repräsentation eines Graphen als Matrix erlaubt den Einsatz von Methoden der linearen Algebra. Die Anwendung und Untersuchung solcher Methoden bildet ein zentrales Thema in der spektralen Graphentheorie. Es bildet damit eine Schnittstelle zwischen Graphentheorie und linearer Algebra.
Insbesondere bei sehr vielen Kanten ist eine Speicherung der Verbindung als nxn-Matrix sinnvoll.

Aber wie hier, wo ich Gleise und Verbindungen zwischen diesen habe, diese Fachlichkeit durch Arrays abzubilden ist eben nicht mehr objektorientiert.
Jedes Objekt baut auf primitiven Datentypen auf. --> Eine Klasse die ein Array als Adjazenzmatrix nutzt ist immer objektorientiert.
 

Mika34

Bekanntes Mitglied
Erstmal vielen Dank für die Hilfe und die Anregungen. :)
Wenn ich jetzt auf Basis von diesem HashSet meine Methoden in soweit verändern möchte, dass zum Beispiel nur waagrechte oder senkrechte Gleise hinzugefügt werden dürfen, dann implementiere ich diese Bedingungen hier in den Methoden, oder doch nicht?
Ich bin mit Hash Sets leider nicht all zu vertraut und wäre hier wirklich über einen zweidimensionalen Array gegangen, in dem ich die Gleise an den jeweiligen Stellen im Array hinzugefügt hätte
 

abc66

Top Contributor
@Mika34 hier stellen sich zunächst viele Fragen. Ist der Graph zusammenhängend, gerichtet/ungerichtet, gewichtet/ungewichtet, bi- oder "multi"-directional usw.
Vereinfacht: können alle Knoten erreicht werden, gibt es Hinweg und/oder Rückweg, kostet "jede Verbindung" das gleiche, und gibt es mehrere gleiche "Verbindungen" usw.
 

mihe7

Top Contributor
Nun verstehe ich aber nicht, wie ich nun über Breitensuche oder Tiefensuche prüfen soll, ob die Menge der gefundenen Punkte = Gesamtmenge aller Punkt sind.
Beispiel:
Java:
import java.util.*;

public class Graph<T> {
    private Map<T, List<T>> edges = new HashMap<>();

    public void addEdge(T u, T v) {
        edges.computeIfAbsent(u, x -> new ArrayList<T>());
        edges.get(u).add(v);
        edges.computeIfAbsent(v, x -> new ArrayList<T>());
        edges.get(v).add(u);
    }

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

    public boolean isConnected() {
        if (edges.isEmpty()) { return true; }
        Set<T> nodes = new HashSet<>(edges.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);
            }
        }
    }

    // ------- Test -------
    public static void main(String[] args) {
        Graph<String> g = new Graph<>();
        g.addEdge("Köln", "Hamburg");
        g.addEdge("Köln", "Düsseldorf");
        System.out.println(g.isConnected());
        g.addEdge("Berlin", "München");
        System.out.println(g.isConnected());
        g.addEdge("Hamburg", "Berlin");
        System.out.println(g.isConnected());
    }
}
 

Mika34

Bekanntes Mitglied
Hi mihe7,
Das hat mir richtig weitergeholfen. Ich habe mich von der Idee mit dem zwei dimensionalem Array verabschiedet und bin über eine Hash-Map gegangen, in welcher die Id der jeweiligen Gleise als Keys verwendet werden. :)
 

Mika34

Bekanntes Mitglied
Beispiel:
Java:
import java.util.*;

public class Graph<T> {
    private Map<T, List<T>> edges = new HashMap<>();

    public void addEdge(T u, T v) {
        edges.computeIfAbsent(u, x -> new ArrayList<T>());
        edges.get(u).add(v);
        edges.computeIfAbsent(v, x -> new ArrayList<T>());
        edges.get(v).add(u);
    }

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

    public boolean isConnected() {
        if (edges.isEmpty()) { return true; }
        Set<T> nodes = new HashSet<>(edges.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);
            }
        }
    }

    // ------- Test -------
    public static void main(String[] args) {
        Graph<String> g = new Graph<>();
        g.addEdge("Köln", "Hamburg");
        g.addEdge("Köln", "Düsseldorf");
        System.out.println(g.isConnected());
        g.addEdge("Berlin", "München");
        System.out.println(g.isConnected());
        g.addEdge("Hamburg", "Berlin");
        System.out.println(g.isConnected());
    }
}
Könntest Du mir bitte aber noch erklären, was das T, u und v bei dir im Code bedeuten?
 

mihe7

Top Contributor
T ist ein Typparameter, damit der Spaß mit verschiedenen Typen (wie z. B. String) typsicher funktioniert. Naja und u und v sind ganz normale Parameter. Du kannst sie auch node1 und node2 nennen.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
K Verständnis Problem bei Server/Client Java Basics - Anfänger-Themen 2
I WildFily - unterschiedliche Libs im Projekt verursachen Problem Java Basics - Anfänger-Themen 11
imocode Vererbung Problem mit Vererbung Java Basics - Anfänger-Themen 2
L Taschenrechner Problem Java Basics - Anfänger-Themen 4
I Applikationsserver (WildFly) - Zugriff auf Ressourcen.. Problem mit Pfade Java Basics - Anfänger-Themen 10
A ScheduledExecutorService problem Java Basics - Anfänger-Themen 7
marcelnedza Problem mit Weltzuweisung, JavaKarol Java Basics - Anfänger-Themen 13
XWing Methoden rückgabe Problem? Java Basics - Anfänger-Themen 6
M Erste Schritte Collatz Problem max int Java Basics - Anfänger-Themen 3
M Problem bei verschachtelter for-Schleife bei zweidimensionalen Arrays Java Basics - Anfänger-Themen 3
C GLOOP Problem beim Erstellen der Kamera Java Basics - Anfänger-Themen 9
nelsonmandela Problem bei Ausgabe einer Switch - Case Funktion Java Basics - Anfänger-Themen 5
frager2345 Problem mit Methode Java Basics - Anfänger-Themen 4
L Problem bei Rechnung mit Math.pow Java Basics - Anfänger-Themen 13
A Thread-Schreibe-Lese-Problem Java Basics - Anfänger-Themen 4
SUPERTJB return Problem Java Basics - Anfänger-Themen 3
sserio BigInteger Problem Java Basics - Anfänger-Themen 4
JordenJost Taschenrechner problem Java Basics - Anfänger-Themen 5
K Problem mit "Random" Java Basics - Anfänger-Themen 5
S Datei anlegen Problem! Groß- und Kleinschreibung wird nicht unterschieden Java Basics - Anfänger-Themen 4
sserio Problem beim Anzeigen Java Basics - Anfänger-Themen 5
xanxk Problem For-Schleife mit Charakter Java Basics - Anfänger-Themen 2
L Unbekanntes Problem mit 2d Array Java Basics - Anfänger-Themen 6
sserio Liste erstellt und ein Problem mit dem Index Java Basics - Anfänger-Themen 8
sserio Schwimmen als Spiel. Problem mit to String/ generate a card Java Basics - Anfänger-Themen 4
J Schleife Problem Java Basics - Anfänger-Themen 2
D Problem mit der Erkennung von \n Java Basics - Anfänger-Themen 2
milan123 das ist meine aufgabe ich hab das problem das bei mir Wenn ich die Richtung der Linien verändern will und drei davon sind richtig, verändere ich die 4 Java Basics - Anfänger-Themen 3
M Verständins Problem bei Aufgabe Java Basics - Anfänger-Themen 4
HeiTim Problem mit der Kommasetzung an der richtigen stelle Java Basics - Anfänger-Themen 59
Temsky34 Problem mit dem Code Java Basics - Anfänger-Themen 17
P Problem mit Calendar.getDisplayName() Java Basics - Anfänger-Themen 8
C Problem mit mehreren Methoden + Scanner Java Basics - Anfänger-Themen 5
P Datei einlesen, nach Begriff filtern und in Datei ausgeben. Problem Standardausgabe über Konsole Java Basics - Anfänger-Themen 19
M Problem mit Klassenverständnis und Button Java Basics - Anfänger-Themen 8
EchtKeineAhnungManchmal hallo habe ein Problem mit einer Datei -> (Zugriff verweigert) Java Basics - Anfänger-Themen 4
H Problem mit Verzweigungen Java Basics - Anfänger-Themen 6
H Problem mit Rückgabewert Java Basics - Anfänger-Themen 7
josfe1234 JAVA FX problem Java Basics - Anfänger-Themen 3
A Code Problem Java Basics - Anfänger-Themen 6
Henri Problem von Typen Java Basics - Anfänger-Themen 7
J Problem mit "ArrayIndexOutOfBoundsException" Java Basics - Anfänger-Themen 11
K jackson Mapping - Problem mit Zeitzonen Java Basics - Anfänger-Themen 10
B Threads Problem mit mehreren Threads Java Basics - Anfänger-Themen 38
I Output BigDecimal anstatt double / Problem beim Rechnen Java Basics - Anfänger-Themen 16
D Schleifen Problem Java Basics - Anfänger-Themen 2
H So viele Fehlermeldungen, dass ich nicht weiß wo das Problem ist. Java Basics - Anfänger-Themen 6
J JAVA-Problem blockiert MEDIATHEKVIEW Java Basics - Anfänger-Themen 13
T Problem mit Lehrzeichen und String bei einfacher Chiffre Java Basics - Anfänger-Themen 8
J extends Problem Java Basics - Anfänger-Themen 2
C Polymorphie-Problem Java Basics - Anfänger-Themen 3
Kalibru Problem bei Ausgabe von Objekt Java Basics - Anfänger-Themen 1
I Format Problem mit Wert - bekomme 0,10 anstatt 10,00 Java Basics - Anfänger-Themen 6
J Problem mit einer Methode die gewissen Inhalt einer Array löschen soll Java Basics - Anfänger-Themen 9
J Problem mit einer Methode, die beliebig viele Objekte in Array speichern soll Java Basics - Anfänger-Themen 6
J Allgemeines Problem mit Klassen Java Basics - Anfänger-Themen 5
U Problem mit dem initialisieren meines Strings in einer Schleife Java Basics - Anfänger-Themen 5
amgadalghabra algorithmisches Problem Java Basics - Anfänger-Themen 19
J Traveling Salesman Problem [Arrays] Java Basics - Anfänger-Themen 9
R ArrayList Problem Java Basics - Anfänger-Themen 6
InfinityDE Problem mit Datenübergabe an Konstruktor Java Basics - Anfänger-Themen 7
C RegEx Problem Java Basics - Anfänger-Themen 4
J Anfänger TicTacToe, Problem bei Gewinnoption, sowohl Unentschieden Java Basics - Anfänger-Themen 8
E Taschenrechner GUI Problem mit Fehlerhandling Java Basics - Anfänger-Themen 6
M Input/Output Fallunterscheidung Problem Java Basics - Anfänger-Themen 17
P Problem beim Überschreiben einer vererbten Methode Java Basics - Anfänger-Themen 4
M Problem bei Ausgabe Java Basics - Anfänger-Themen 7
Splayfer Java Array Problem... Java Basics - Anfänger-Themen 2
G Problem bei der Ausgabe einer Main Claase Java Basics - Anfänger-Themen 7
F Problem mit KeyListener in kombination mit dem ActionListener Java Basics - Anfänger-Themen 4
G Subset sum problem mit Backtracking Java Basics - Anfänger-Themen 18
N Problem mit Scanner Java Basics - Anfänger-Themen 2
J Klassen Problem Java Basics - Anfänger-Themen 8
A Out.format problem. Java Basics - Anfänger-Themen 3
J Problem bei der Programmierung eines Tannenbaums Java Basics - Anfänger-Themen 9
A Array problem Java Basics - Anfänger-Themen 16
2 Taschenrechner mit GUI Problem bei der Berechnung Java Basics - Anfänger-Themen 8
W Remote Method Invocation RMI - Problem Java Basics - Anfänger-Themen 0
I Ich habe ein Problem Java Basics - Anfänger-Themen 3
A Problem bei returnen eines Wertes Java Basics - Anfänger-Themen 6
M Regex Erstellung Problem Java Basics - Anfänger-Themen 2
D Input/Output Problem bei der Benutzereingabe eines Befehls Java Basics - Anfänger-Themen 14
M (Sehr großes Problem) Listen als static in anderen Klassen verwendet Java Basics - Anfänger-Themen 12
F Habe ein problem mit dem ActionListener Java Basics - Anfänger-Themen 3
C Regex-Problem Java Basics - Anfänger-Themen 4
J Problem beim vergleich von zwei Integer Java Basics - Anfänger-Themen 3
W Wo ist das URL-Problem ? Java Basics - Anfänger-Themen 1
S Generics-Problem: Class, Class<?>, Class<Object> Java Basics - Anfänger-Themen 4
D FileWriter / FileReader Problem Java Basics - Anfänger-Themen 10
G Problem beim Speichern von Objekten in einer Datei Java Basics - Anfänger-Themen 7
S Compiler-Fehler Exception in thread "main" java.lang.Error: Unresolved compilation problem: Java Basics - Anfänger-Themen 6
J Problem mit Array: 2 Klassen Java Basics - Anfänger-Themen 2
S Collections funktionale Listen (ListNode<E>) review und problem beim clone Java Basics - Anfänger-Themen 0
W OOP Vererbung und Problem bei Zählschleife in einer Methode Java Basics - Anfänger-Themen 10
C Problem mit If Else If und Überprüfung eines Counters Java Basics - Anfänger-Themen 3
F Problem mit Listen Java Basics - Anfänger-Themen 5
I wieder mit einer Umwandelung habe ich Problem (diesmal von char Array zu char) Java Basics - Anfänger-Themen 1
J Problem bei Umrechnung von Hex in Bin Java Basics - Anfänger-Themen 4
W Problem bei Programmierung von Monte-Carlo-Integration Java Basics - Anfänger-Themen 12
C Java Methoden "Parameter" Problem Java Basics - Anfänger-Themen 16

Ähnliche Java Themen

Neue Themen


Oben