Datenstruktur für Fahrplan einer Buslinie

[Schorschilein]

Hallo,

ich suche nach einer Möglichkeit in einer Klasse Fahrplan, welche den Fahrplan einer Bus/Zugline für eine Haltestelle bereithalten soll, eine Abfahrtszeit sowie einen Abfahrtstag einzulagern und bei Bedarf zu einem übergebenen Tag/Uhrzeit die nächste mögliche Abfahrtzeit ausspuckt:

	public final static int Montag = 0;
	public final static int Dienstag = 1;
        // [...]

       public Fahrplanzeiten getZeit(int tag, int uhrzeit);

Tage sind in diesem Fall Integer (0-6) für Montage, ..., Sonn- und Feiertage. Uhrzeit ist ebenfalls ein Integer (830 für 8:30, 2230 für 22:30)

Ich wollte das zuerst mit verketteten Listen machen, denke aber das dies nicht gerade die eleganteste Lösung ist. Stellt Java irgendwelche Klassen bereit mit denen man so etwas am besten realisieren kann? Wichtig ist das die Methode getZeit() sehr schnell arbeitet. Auf diese wird ein Dijkstra-Algorithmus zugreifen der in einem gewichteten Graphen nachher die schnellste Verbindung suchen wird. Bei ca. 3000 Knoten die abgebildet werden bedeutet dies, dass auch getZeit() 3000 mal aufgerufen wird und zum übergebenen Tag und Uhrzeit die nächste mögliche Verbindung ausgeben muss.

Vielen Dank schon mal!

Gruß

Schorsch

 

[mic_checker]

Wie speicherst du denn bisher den Graphen ? (Also den eigentlichen Plan) ? Bzw. was hast du schon gemacht ?

Hab den Dijkstra auch mal programmiert, der einfachheitshalber anfangs mit ner adjazenzmatrix, danach mal mit adjazenzlisten.

Im Prinzip kannst du die einzelnen Abfahrts/Ankunftszeiten ja schon in ner Liste speichern, solange du sie sortierst....das müsstest du dann einmal machen - da wohl kaum neue Haltestellen dazu kommen.

 

[bygones]

ich würde dir raten nicht das Rad neuzuerfinden... such im netz nach bestehenden Graph und Graphalgorithmen Libraries. Es gibt viele und verdammt gute....

 

[Schorschilein]

Servus,

derzeit nutze ich Adjazenzlisten. Den Dijkstra habe ich auch schon implementiert. Die Gewichte der Kanten (Minuten) werden vom Dijkstra via getMinuten() geholt, derzeit sind dies feste Werte. In dieser getMinuten() möchte ich jetzt dynamisch auf die nächste mögliche Abfahrtzeit zugreifen.

@deathbyaclown
Richtig. Allerdings mache ich dies im Rahmen meiner Studienarbeit. Ich weiß nicht wie mein Prof. darauf reagieren wird wenn ich was kopiere. Das ich den Dijkstra mehr oder weniger Abtippe (von C++ nach Java übersetzt) ist ja klar, da werde ich nix neues erfinden. Aber der ganze Rest sollte schon von mir sein.

Meine erste Idee waren wie gesagt verkettete Listen.

	static class Fahrplanzeiten implements Cloneable{
		int tag;		
		int uhrzeit;
		Fahrplanzeiten next = null;
		
		public Fahrplanzeiten(int tag, int uhrzeit) {
			this.tag = tag;
			this.uhrzeit = uhrzeit;
		}
		
		public Object clone() {
			try {
						Fahrplanzeiten n = (Fahrplanzeiten) super.clone();
						return n;
			} catch ( CloneNotSupportedException ex ) {
						return null;
			}
		}
	}

Beim einfügen würde ich halt die Liste durchgehen und das neue Element an passender Stelle einfügen und beim auslesen einfach die Liste durchwandern.

Gruß

Schorsch

 

[DP]

..oder nen container mit dem streckenplan und einen zeiger, welche station gerade angefahren wird...

 

[mic_checker]

Also wenns für ne Studienarbeit ist würde ich es soweit selbst implementieren oder halt Rücksprache halten inwiefern du auf was zurückgreifen darfst. Andererseits ist die Implementierung einer Adjazenzliste etc. nun auch nicht das schwerste.

Ich wüsste nicht was gegen das Vorgehen sprechen sollte....In der einen Liste speicherst du die einzelnen Standorte, also die jeweiligen Stationen.

Wobei du dann für die einzelnen "nächst-möglichen-stationen" wiederrum ne liste brauchst, da du ja verschiedene fahrzeiten hast....

 

[Newlukai]

Wenn ich die Aufgabenstellung richtig verstanden habe, willst Du zu EINER Linie an EINER Haltestelle sämtlich Abfahrtstage und Abfahrtszeiten, oder?
Wie wär's denn in dem Fall mit einem (oder mehreren, für jeden Tag einen) Suchbaum?

 

[Schorschilein]

Nicht ganz....ich will zu einer Station die kürzeste Fahrtzeit zu einer anderen Station. An jeder Station können mehrere Linien zu unterschiedlichen Zeiten fahren.

Es scheint allerdings so als hätte sich das ganze schon erledigt. Dies ganze wird eine Gruppenarbeit und der Datenbanken-Mensch ;-) hat anscheined parallel ebenfalls eine Klasse für Stationen und Fahrpläne entwickelt. Er arbeitet bei den Fahrplänen wohl mit einer LinkedList. Ich muss mir mal angucken was der da gemacht und ob ich das verwenden kann. Danke für eure Hilfe.

Gruß

Schorsch