Zusammenhängenden Graphen für Gleisnetz erstellen

[DagobertDuck]

Guten Abend,

meine Frage bezieht sich auf ein ähnliches Problem von Mika34. Jedoch hat mir seine Frage bei meinem Problem nicht ganz weitergeholfen.

Ich bin dabei ein Gleisnetz zu implementieren. Dabei gibt es zwei Typen von Gleisen:
- NormalTrack(int id, Point startPoint, Point endPoint, int length)
- TrackSwitch(int id, Point startPoint, Point endPoint, Point secondEndPoint, int length, boolean switchEnabled)

Eine Weiche (TrackSwitch) kann eine Strecke in zwei Teilstrecken aufteilen. Jedes Gleis (sowohl Weichen als auch normale Gleise) bekommen eine eindeutige ID, daher die Map<Integer, Track> tracks.

Jedoch habe ich keine gescheite Idee, wie ich die addTrack() und addSwitch() Methode implementieren soll. Eventuell macht es auch gar kein Sinn mit den beiden Maps oder generell mit meiner Implementierung...?

public class RailNetwork {
    private Map<Point, List<Point>> edges = new HashMap<>();
    private Map<Integer, Track> tracks;

    // Add edge (two points)
    public void addEdge(Point firstNode, Point secondNode) {
        edges.computeIfAbsent(firstNode, x -> new ArrayList<>()).add(secondNode);
        edges.computeIfAbsent(secondNode, x -> new ArrayList<>()).add(firstNode);
    }

    public void addTrack(NormalTrack track) {
        // TODO
    }
   
    public void addSwitch(TrackSwitch trackSwitch) {
        // TODO
    }
   
    ...
}

Könnte mir jemand bei den beiden Methoden behilflich sein? Ich wäre über jegliche Hilfe sehr dankbar!

Viele Grüße

 

[mihe7]

NormalTrack fügt eine, TrackSwitch zwei Kanten im Graphen ein. Hilft das?

 

[DagobertDuck]

Leider nicht so richtig... Soll ich die Track dann so gesehen in beiden Maps speichern (Punkte der Track in edges und Track in tracks? Das erscheint mir irgendwie etwas ungewöhnlich.
Also irgendwie muss ich die Kanten später ja noch identifizieren können. Außerdem bin ich mir bei der Implementierung der Switch unsicher, wegen der Weichenstellung.

add switch (1,2) -> (2,2),(1,3) erstellt also zwei Kanten. Davon ist allerdings nur die erste befahrbar ((1,2) -> (2,2)). Das wird in dem Attribut switchSetting gespeichert (false). Mit Hilfe des Befehls set switch... kann die Weichenstellung auf den zweiten Punkt gelegt werden. Wie lässt sich die Befahrbarkeit dann später überprüfen? Daher weiß ich auch nicht, ob meine zwei Maps so sinnvoll sind.

Mir ist noch nicht ganz klar wie genau ich die Tracks bzw. Edges speichern soll. Ich wäre dir dankbar, wenn du mir das anhand der Methoden addTrack und addSwitch zeigen würdest.

 

[mihe7]

Soll ich die Track dann so gesehen in beiden Maps speichern (Punkte der Track in edges und Track in tracks? Das erscheint mir irgendwie etwas ungewöhnlich.

Ob Du das sollst, kann ich Dir nicht sagen, ich kenne ja die Aufgabe nicht, die mir im übrigen sehr umfangreich erscheint. Ungewöhnlich ist es aber nicht, entweder weil man verschiedene Modelle, die inhärent zweckgebunden sind, oder verschiedene Zugriffspfade haben will.

Das Speichern des Graphen mit Adjazenzlisten eignet sich z. B. hervorragend, um zu überprüfen, ob der Graph zusammenhängend ist. Die Frage, ob es eine Kante zwischen zwei Knoten gibt, lässt sich dagegen nicht besonders effizient beantworten. Umgekehrt könnte man den Graphen in einer Adjanzenzmatrix darstellen. Dort findet man sehr schnell heraus, ob die Kante zwischen zwei Knoten existiert. Dafür ist die Frage des Zusammenhangs nicht so einfach zu beantworten. Kann man z. B. lösen, wenn man einmal Adjazenzlisten speichert und einmal eine Kantenmenge (HashSet).

Je nachdem, was das Modell leisten soll, kann es auch sinnvoll oder sinnvoller sein, den Graphen nicht explizit zu speichern sondern über den Objektgraphen zu realisieren.

Mit Hilfe des Befehls set switch... kann die Weichenstellung auf den zweiten Punkt gelegt werden. Wie lässt sich die Befahrbarkeit dann später überprüfen? Daher weiß ich auch nicht, ob meine zwei Maps so sinnvoll sind.

Bezogen auf Deinen Code gehe ich mal davon aus, dass mit Point ein Haltepunkt gemeint ist, und 1 eine beispielhafte ID eines solchen Haltepunkts wäre. Track wäre also bereits eine Kante im Graphen und die Map "edges" würde dazu dienen, alle Kanten eines Haltepunkts schnell zu finden, um z. B. den Zusammenhang . Dann könntest Du z. B. statt Map<Point, List<Point>> auch Map<Point, List<Track>> verwenden.

 

[DagobertDuck]

Erstmal vielen Dank für die bisherige Hilfe. Allerdings hat mich das immer noch nicht so richtig weitergebracht.
Ich versuche jetzt mal mein Problem etwas genauer zu beschreiben, damit ihr mein Anliegen besser nachvollziehen könnt.

Hier sind einmal alle benötigten Eigenschaften des Gleisnetzes:

• Zwei Gleistypen: normale Gleise und Gleisweichen.
• Normale Gleise werden durch zwei Punkte im Raum beschrieben (Start- und Endpunkt).
  • Die Koordinaten können beliebig sein, mit der Einschränkung, dass Gleisteile waagerecht oder senkrecht sein müssen. (x1==x2 or y1==y2)
• Mit Ausnahme vom ersten Gleis müssen Start- oder Endpunkt immer an einem Start- oder Endpunkt eines vorhanden Gleises anliegen.
• An einem Punkt an einem Gleis kann immer nur ein anderes Gleis (normales Gleis oder Weiche) angeschlossen werden.
• Jedes Gleis besitzt eine Länge (abhängig von seinen Punkten).
• Gleisweichen teilen eine Strecke in zwei Teilstrecken auf - sie werden durch drei Punkte beschrieben (einen StartPunkt und zwei Endpunkte).
• Gleisweichen speichern zusätzlich ihre Gleisweichenstellung (Grundeinstellung ist der erste Endpunkt). Diese entscheidet über die Befahrbarkeit einer Gleisweiche.
• Die Länge einer Weiche ergibt sich in Abhängigkeit ihrer aktuellen Gleisweichenstellung.

Im Übrigen muss ich anschließend noch den put <trainID> at <point> in direction <x>,<y> und den step <speed> Befehl implementieren. Am Ende sollen sich also auch Züge auf den Tracks befinden können.

Im Folgenden ein Beispiel, wie ein Graph am Ende aufgebaut sein könnte.

add track (1,1) -> (5,1) 1 add switch (5,1) -> (8,1),(5,3) 2 add track (1,1) -> (1,-3) 3 add track (1,-3) -> (10,-3) 4 add track (8,1) -> (10,1) 5 add track (10,1) -> (10,-3) 6 add track (5,3) -> (8,3) 7

(Die Zahl unter dem Befehl ist die zugeordnete ID)



Mit Hilfe des Befehls set switch <trackID> position <point> kann die Weichenstellung geändert werden.

Mein Problem liegt nicht wirklich daran, dass ich nicht weiß, wie ich die bestimmten Eigenschaften implementieren soll, sondern daran, dass ich etwas überwältigt bin von der Menge der Features und ich daher noch keine richtige Idee habe, wie die Struktur der Implementierung am besten auszusehen hat (Klassen, Methoden, Attribute, ...).

@mihe7 Kann man dich auch irgendwie private anschreiben? Leider kann ich dein Profil nicht sehen.

 

[AndiE]

Ich finde die Modellierung so undurchsichtig. Zuerst hast du doch Punkte A,B,C,D... In deinem Beispiel müsstest du nach der 3. Bedingung an Punkt (8,3) anfangen. Gleisweichen mit den Punkten a,b,c( die das A,B,C... bestehen können) können nur zwischen a-b und a-c befahren werden. Der Übergang b-c ist nicht möglich. Ein Gleis verbindet zwei Punkte, eine Weiche drei Punkte. Währen bei einem Gleis die Länge gleich ist, ändert die sich bei einer Weiche nach Weichenstellung.

 

[DagobertDuck]

In deinem Beispiel müsstest du nach der 3. Bedingung an Punkt (8,3) anfangen.

Du hast die dritte Bedingung glaube ich etwas missverstanden. "Start- oder Endpunkt immer an einem Start- oder Endpunkt eines vorhanden Gleises anliegen." - der Graph muss einfach zusammenhängend sein (keine zwei Teilgraphen).

Der Übergang b-c ist nicht möglich.

Wie soll dieser Übergang denn auch möglich sein? Es müsste eine Diagonale Schiene geben, die allerdings nach der Aufgabenstellung nicht erlaubt ist (lediglich waagerechte und horizontale Gleisteile sind valide).

Währen bei einem Gleis die Länge gleich ist, ändert die sich bei einer Weiche nach Weichenstellung.

Das ist richtig. Es macht ja auch Sinn, da die Länge der zwei Weichenteile unterschiedlich sein kann, indem man den ersten bzw. zweiten Endpunkt weiter entfernt setzt.

Ich verstehe nicht so richtig, was an der Modellierung undurchsichtig sein soll. Was ist denn noch genau unklar?

 

[mihe7]

Ich finde, Du kannst mit Deinem Code durchaus anfangen, wenn Du die "edges" Map änderst zu Map<Point, List<Track>>.

Punkt 1: Du kannst den Spaß so modellieren, dass Du typmäßig nicht zwischen Switch und Track nicht zu unterscheiden brauchst. Ein Schienenelement verbindet einen Punkt mit einem oder oder mehreren anderen Punkten im Netz, wobei nur ein Punkt befahrbar ist. Fertig. Element = (id, p0, p1, ..., pn)

Punkt 2: Du brauchst ganz offensichtlich Zugriff auf die Tracks über die Track-ID. Hier bietet sich eine Map an, die Du ja schon hast (tracks).

Punkt 3: Du brauchst auch Zugriff über die Punkte im Netz. Hier bietet sich eine Map an, die Du hast, wenn Du die Map wie o. g. änderst. Die Map liefert zu einem Punkt alle Schienenelemente, die von diesem Punkt ausgehen.

Und mehr ist es erstmal nicht.

 

[DagobertDuck]

Danke, dann bin ich erstmal beruhigt. Wie sehen denn dann Methoden wie isConnectedAfterRemoving(), visit(), visitAndRemove() o. Ä. aus, wenn ich die edges als Map<Point, List<Track>> speichere? Wenn ich beim Hinzufügen einer Track durch die Punkte iterieren soll, dann sollte ich doch als Parameter für NormalTrack und Track besser eine List<Point> benutzen, oder? Inwiefern muss die Edge Methode angepasst werden? Bisher sieht sie ja so aus:

public class Edge {
    private final Point source;
    private final Point dest;

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

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Edge edge = (Edge) o;
        return Objects.equals(source, edge.source) &&
                Objects.equals(dest, edge.dest);
    }

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

Ich bin leider immer noch etwas unbeholfen was die Implementierung der addTrack(Track track) Methode angeht.

 

[mihe7]

Wie sehen denn dann Methoden wie isConnectedAfterRemoving(), visit(), visitAndRemove() o. Ä. aus, wenn ich die edges als Map<Point, List<Track>> speichere?

Vergiss erstmal die Frage, ob der Graph zusammenhängend ist, das lenkt vom eigentlichen Thema nur ab.

Wenn ich beim Hinzufügen einer Track durch die Punkte iterieren soll, dann sollte ich doch als Parameter für NormalTrack und Track besser eine List<Point> benutzen, oder?

Ich sehe aktuell keinen Grund, zwischen NormalTrack und Track unterscheiden zu müssen. Es geht an de Stelle erstmal um die Schnittstelle der Objekte, die muss im Endeffekt zwei Methoden haben: gib mir den Startpunkt und gib mir die Liste der Endpunkte.

Schemenhaft:

public class Track {
    List<Point> points = new ArrayList<>();
    Point switchedTo;

    // erzeugt ein neues Track-Objekt aus einer Liste von Punkten, 
    // wobei der erste Punkt den Startpunkt angibt.
    public Track(Point ... points) {
        if (points == null || points.length < 2) {
            throw new IllegalArgumentException();
        }
        this.points.addAll(Arrays.asList(points));
        switchedTo = this.points.get(1);
    }

    public void switchTo(Point p) {
        int ix = points.indexOf(p);
        if (ix < 1) { // exception? } 
        else {
            switchedTo = this.points.get(ix);
        }
    }

    public Point getActualDestination() { return switchedTo; }
    public Point getStartPoint() { return points.get(0); }
    public List<Point> getEndPoints() { return Collections.unmodifiableList(points.sublist(1)); }

    // equals und hashCode...
}

ich bin leider immer noch etwas unbeholfen was die Implementierung der addTrack(Track track) Methode angeht.

edges.computeIfAbsent(track.getStartPoint(), () -> new ArrayList<Track>()).add(track);
track.getEndPoints().forEach(p -> edges.computeIfAbsent(p, () -> new ArrayList<Track>()).add(track));

Nun erhält man via edges.get(p) eine Liste aller Tracks, die am Punkt p starten oder enden.

 

[DagobertDuck]

Vielen dank! Das mir schon mal um einiges weiter. Wie kann ich bei der switchTo() Methode jetzt noch überprüfen, ob es sich überhaupt um eine Weiche handelt? Bei einem normalen Gleis soll dies ja nicht funktionieren können. Wäre es nicht objekt-orientierter für eine Switch und eine normale Track eine eigene Klasse zu erstellen? So funktioniert es natürlich auch super. Hiermit habe ich bisher geprüft, ob die Schienen horizontal oder waagerecht liegen:

    public boolean isHorizontalOrVertical(Point firstPoint, Point secondPoint) {
        return firstPoint.getFirstComponent() == secondPoint.getFirstComponent()
                || firstPoint.getSecondComponent() == secondPoint.getSecondComponent();
    }

Wie kann ich das jetzt am geschicktesten für zwei oder drei Punkte tun, ohne dies vorher festlegen zu müssen. Als Parameter wäre natürlich List<Point> angebracht und dann benutzt man am besten eine for-each-Schleife. Aber wie sieht das dann konkret aus?

Wie unterscheide ich i. A. zwischen einer Track und einer Switch? Sollte ich mir eine Methode getType() in der Klasse Track erstellen, die die Anzahl der Endpunkte überprüft und dementsprechend einen String zurück gibt ("track" oder "switch")?

Meine remove(Track track) Methode sieht bislang folgendermaßen aus:

public void removeTrack(Track track) {
        // TODO: Remove track/points from Map edges
        this.tracks.remove(track.getId());
    }

Wie funktioniert nun die Entfernung der Punkte/Tracks aus der Map edges...?

 

[mihe7]

Wie kann ich bei der switchTo() Methode jetzt noch überprüfen, ob es sich überhaupt um eine Weiche handelt? Bei einem normalen Gleis soll dies ja nicht funktionieren können.

Theoretisch müsstest Du dort gar nichts einbauen, weil an switchTo ja nur der eine Endpunkt ausgewählt werden kann.

Wie unterscheide ich i. A. zwischen einer Track und einer Switch? Sollte ich mir eine Methode getType() in der Klasse Track erstellen, die die Anzahl der Endpunkte überprüft und dementsprechend einen String zurück gibt ("track" oder "switch")?

Das wäre eine Möglichkeit, Du kannst auch einfach ein boolean zurückgeben (isSwitch o. ä.) oder die Prüfung tatsächlich in switchTo() einbauen und eine Exception werfen.

Wäre es nicht objekt-orientierter für eine Switch und eine normale Track eine eigene Klasse zu erstellen?

Nein, objektorientiert heißt nicht, möglichst viele Klassen und Vererbung einzusetzen, sondern mit geeigneten Abstraktionen zu arbeiten.

Wie kann ich das jetzt am geschicktesten für zwei oder drei Punkte tun, ohne dies vorher festlegen zu müssen. Als Parameter wäre natürlich List<Point> angebracht und dann benutzt man am besten eine for-each-Schleife. Aber wie sieht das dann konkret aus?

Die Methode kannst Du erstmal beibehalten und überladen. Die Frage aber ist, was genau soll geprüft werden? Ob der zweite, dritte, ... Punkt sich horizontal oder vertikal zum ersten befindet? Dann:

public boolean isHorizontalOrVertical(List<Point> points) {
    if (points == null || points.size() < 2) { ... }
    Point start = points.get(0);
    for (Point p : points) {
        if (!isHorizontalOrVertical(start, p)) {
            return false;
        }
    }
    return true
}

funktional gehts etwas kürzer:

public boolean isHorizontalOrVertical(List<Point> points) {
    if (points == null || points.size() < 2) { ... }
    Point start = points.get(0);
    return points.stream()
        .allMatch(p -> isHorizontalOrVertical(start, p));
}

Wie funktioniert nun die Entfernung der Punkte/Tracks aus der Map edges...?

Genauso wie das Hinzufügen, nur mit remove.

 

[DagobertDuck]

OK, das funktioniert jetzt schon mal alles! Den Rest bekomme ich denke ich auch ohne weitere Hilfe gelöst. Ein letztes Problem bereit mir allerdings noch Schwierigkeiten...

    public boolean isConnectedAfterRemoving(Set<Track> toRemove) {
        Set<Point> notVisited = edges.entrySet()
                .stream()
                .filter(e -> e.getValue().stream().anyMatch(d -> !toRemove.contains(new Track(...)) &&
                        !toRemove.contains(new Track(...))))
                .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(Point next, Set<Point> notVisited, Set<Track> toRemove) {
        if (!notVisited.remove(next))
            return;
        for (Track track : edges.get(next))
            if (!toRemove.contains(new Track(...)) &&
                    !toRemove.contains(new Track(...)))
                visit(track, notVisited, toRemove);
    }

Wie müssen diese Methoden nun weiter angepasst werden, sodass sie mit der neuen Map funktionieren...? Darüber hinaus ist mir nicht klar, wie new Track(...) hier funktionieren soll, da die Klasse Track die Parameter id, points, length hat.

 

[mihe7]

Ein letztes Problem bereit mir allerdings noch Schwierigkeiten...

Die Frage ist, ob das Modell für die Feststellung, ob der Graph zusammenhängend ist, geeignet ist oder geändert werden muss.

Da jetzt Tracks verwaltet werden, können wir uns die Edge-Geschichten sparen. Die Menge der noch nicht besuchten Knoten ist sehr einfach festzustellen:

    public boolean isConnectedAfterRemoving(Set<Track> toRemove) {
        Set<Point> notVisited = edges.entrySet()
                .stream()
                .filter(e -> e.getValue().stream().anyMatch(d -> !toRemove.contains(d)))
                .map(Map.Entry::getKey)
                .collect(java.util.stream.Collectors.toSet());
...

Der Rest bleibt gleich.

Bei der Methode visit wird es ein klein wenig komplizierter. Die Methode besucht einen Punkt und alle von diesem Punkt aus (über Tracks) erreichbaren Punkte. Die Map edges liefert zu einem Punkt die Tracks, die an diesem Punkt starten oder enden. Jetzt braucht man nur alle Punkte eines jeden Tracks zu besuchen:

    private void visit(Point next, Set<Point> notVisited, Set<Track> toRemove) {
        if (!notVisited.remove(next))
            return;
        edges.get(next).stream()
            .filter(track -> !toRemove.contains(track)) // betrachtet werden nur die Tracks, die nicht entfernt werden sollen
            .flatMap(track -> track.getPoints().stream()) // auf Punkte abbilden
/* optionale Optimierungen:
            .filter(point -> !point.equals(next)) // der Ausgangspunkt muss nicht nochmal besucht werden
            .distinct() // jeder Punkt muss nur einmal besucht werden
*/
            .forEach(point -> visit(point, notVisited, toRemove));
    }

Hierzu muss in der Klasse Track nur eine Methode

    public List<Point> getPoints() { return Collections.unmodifiableList(points); }

eingebaut werden.

Wenn ich mich nirgends vertan habe, sollte das also funktionieren.