ereignisgraph

@abstractmethod
def add_to_graph(self):
    """
    Knoten und Kanten zum Ereignisgraphen hinzufügen.

    Die Methode fügt die vom Builder verantworteten Knoten und internen Kanten dem EreignisGraph hinzu.
    Die Methode darf nur beim ersten Aufruf eine Wirkung zeigen.
    """
    self.ausgefuehrt = True

def edge_info(self, u: EreignisLabelType, v: EreignisLabelType) -> str:
    """
    Information zu Ereigniskante für Log
    """

    try:
        data = self.edges[(u, v)]
    except KeyError:
        return f"Kante {u},{v} nicht im Ereignisgraph."

    result = (f"Kante {u}, {v}: {data.get('typ', '?')}, {data.get('quelle', '?')}, "
              f"ds = {data.get('ds', '-')}, "
              f"dt_min = {data.get('dt_min', '-')}, "
              f"dt_max = {data.get('dt_max', '-')}, "
              f"dt_fdl = {data.get('dt_fdl', '-')}")

    return result

def next_ereignis(self, label: EreignisLabelType, typ: Optional[str] = None) -> Optional[EreignisLabelType]:
    """
    Nächstes Ereignislabel eines Zuges

    Diese Methode gibt das nächste Ereignis des Zuges bzw. (bei Ersatz oder Kupplung) des Folgezuges zurück.
    Wenn das typ-Argument gesetzt ist, wird das Ereignis nur zurückgegeben, wenn der Typ übereinstimmt.

    Vorsicht: Diese Methode sucht nicht nach einem bestimmten Ereignis!

    Args:
        label: Label des Ereignisnodes.
        typ: Ereignistyp (EreignisGraphNode.typ).

    Returns:
        Label des gefundenen Ereignisses oder None.
    """

    try:
        start_typ = self.nodes[label]['typ']
    except KeyError:
        start_typ = None

    for n in self.successors(label):
        if (n.zid == label.zid or
                (start_typ == 'E' and self.edges[(label, n)]['typ'] == 'H') or
                self.nodes[n]['typ'] == 'K'):
            if typ is None or self.nodes[n]['typ'] == typ:
                return n

    return None

def node_info(self, node: EreignisLabelType) -> str:
    """
    Information zu Ereignisknoten für Log
    """

    try:
        data = self.nodes[node]
    except KeyError:
        return f"Ereignisknoten {node} nicht im Ereignisgraph."

    result = (f"Ereignisknoten {node}: {data.get('typ', '?')}, {data.get('plan', '?')}, {data.get('quelle', '?')}, "
              f"t_plan = {format_minutes(data.get('t_plan', 0))}, "
              f"t_prog = {format_minutes(data.get('t_prog', 0))}, "
              f"t_mess = {format_minutes(data.get('t_mess', 0))}")

    return result

def prev_ereignis(self, label: EreignisLabelType, typ: Optional[str] = None) -> Optional[EreignisLabelType]:
    """
    Vorheriges Ereignislabel eines Zuges

    Diese Methode gibt das vorherige Ereignis des Zuges bzw. (bei Ersatz oder Flügelung) des Vorgängerzuges zurück.
    Wenn das typ-Argument gesetzt ist, wird das Ereignis nur zurückgegeben, wenn der Typ übereinstimmt.

    Vorsicht: Diese Methode sucht nicht nach einem bestimmten Ereignis!

    Args:
        label: Label des Ereignisnodes.
        typ: Ereignistyp (EreignisGraphNode.typ).

    Returns:
        Label des gefundenen Ereignisses oder None.
    """

    for n in self.predecessors(label):
        if n.zid == label.zid or self.nodes[n]['typ'] in {'E', 'F'}:
            if typ is None or self.nodes[n]['typ'] == typ:
                return n

    return None

def prognose(self):
    """
    Zeitprognose durchführen

    Für jeden nicht fixierten Knoten wird die erwartete Zeit berechnet.
    Die Zeit wird anhand der Fahrplanzeit und
    von aggregierten Minimal- und Maximalzeiten der einlaufenden Kanten bestimmt.

    Wenn die Fahrplanzeit zwischen Minimal- und Maximalzeit liegt, wird sie unverändert übernommen.
    Ansonsten wird sie auf das Maximum reduziert, wenn sie grösser als das Maximum ist,
    und auf das Minimum erhöht, wenn sie kleiner als das Minimum ist.
    Die resultierende Zeit ist in jedem Fall grösser oder gleich der Minimalzeit.

    Mit diesem Algorithmus können folgende Fälle abgebildet werden:

    1. Normaler Halt:
       dt_min ist die minimale Aufenthaltszeit für den Fahrgastwechsel oder andere Betriebsvorgänge.
       dt_max wird nicht definiert.
    2. Halt mit vorzeitiger Abfahrt:
       dt_min ist die minimale Aufenthaltszeit für den Fahrgastwechsel oder andere Betriebsvorgänge.
       dt_max wird deklariert, wenn der Zug vorzeitig abfahren soll.
    3. Durchfahrt:
       dt_min ist 0.
       dt_max wird nicht definiert.
    4. Abwarten eines anderen Ereignisses:
       dt_min definiert die zusätzliche Wartezeit zum vorausgehenden Ereignis.
       dt_max wird nicht definiert.
    5. Vorzeitige Abfahrt um einem anderen Zug auszuweichen:
       dt_max ist negativ und definiert wie viel früher der Zug abfahren soll.
       dt_min wird nicht definiert.

    """

    self._schleifen_aufbrechen()
    try:
        nodes = nx.topological_sort(self)
    except nx.NetworkXUnfeasible as e:
        logger.error("Fehler beim Sortieren des Zielgraphen")
        logger.exception(e)
        return

    for zielnode in nodes:
        ziel_data = self.nodes[zielnode]
        if ziel_data.get("t_mess") is not None:
            continue

        ziel_zeit = -math.inf
        if ziel_data.typ in {'Ab'}:
            if zielnode.zeit == MIN_MINUTES:
                # einfahrt
                ziel_zeit = ziel_data.get("t_mess") or ziel_data.get("t_fdl") or ziel_data.get("t_prog") or ziel_data.get("t_plan") or ziel_zeit
            else:
                ziel_zeit = ziel_data.get("t_fdl") or ziel_data.get("t_plan") or ziel_zeit

        zeit_min = -math.inf
        zeit_max = math.inf
        for startnode in self.pred[zielnode]:
            start_data = self.nodes[startnode]
            edge = (startnode, zielnode)
            edge_data = self.edges[edge]
            dt_min = edge_data.get("dt_min", 0)
            dt_max = edge_data.get("dt_max", 0)
            dt_fdl = edge_data.get("dt_fdl", 0)

            start_zeit = start_data.get("t_mess") or start_data.get("t_fdl") or start_data.get("t_prog") or start_data.get("t_plan")
            if start_zeit is None:
                continue
            if edge_data.get("typ", "P") == "D":
                ziel_zeit = start_zeit

            zeit_min = max(zeit_min, start_zeit + dt_min + dt_fdl)

            # das analoge für dt_max ist problematisch: was ist der defaultwert von dt_max?
            # zeit_max = min(zeit_max, start_zeit + edge_data.get("dt_max", math.inf) + min(0, edge_data.get("dt_fdl", 0)))

            # lösungsvorschlag:
            if dt_max > 0:
                zeit_max = min(zeit_max, start_zeit + dt_max)
            if dt_fdl < 0:
                zeit_max = min(zeit_max, ziel_zeit + dt_fdl)

        result = ziel_zeit
        result = min(result, zeit_max)
        result = max(result, zeit_min)
        if not math.isinf(result):
            ziel_data.t_prog = result
        else:
            logger.warning(f"Keine Zeitprognose möglich für Ereignis {zielnode}")

def rueckpfad(self,
              zid: int,
              start: EreignisLabelType | None = None,
              stop: EreignisLabelType | None = None,
              ersatz: bool = False,
              fluegeln: bool = False,
              kuppeln: bool = False,
              ) -> Generator[EreignisLabelType, None, None]:
    """
    Rückwärts laufender Generator für die Ereignisse eines Zuges

    Beginnend mit dem Startknoten liefert der Generator die Ereignis-IDs eines Zuges
    entgegen der Reihenfolge ihres Auftretens.

    Das Verhalten des Generators bei Ersatz/Flügeln/Kuppeln kann mit Flags angepasst werden.

    Args:
        zid: Zug-ID
        start: Knoten-ID des ersten Knotens.
            Falls None (default) der letzte Knoten des Zuges.
        stop: Knoten-ID des ersten nicht mehr gelieferten Knotens.
            Falls None (default) werden die Knoten bis einschliesslich des letzten des Zuges geliefert.
        ersatz: Wenn True, fährt der Generator bei Ersatz mit dem Stammzug fort.
            Ansonsten stoppt der Generator nach dem Abfahrtsknoten des Folgezuges.
        fluegeln: Wenn True, fährt der Generator mit dem Stammzug fort.
            Ansonsten stoppt der Generator nach dem Abfahrtsknoten des Folgezuges.
        kuppeln: Wenn False (default), läuft der Generator durchgehend über den Stammzug.
            Wenn True, läuft der Generator über den endenden Zug.
    Returns:
        Generator von Knoten-IDs.
    """

    aktuell = self.zugenden[zid]
    if not self.has_node(aktuell):
        logger.debug(f"EreignisGraph.rueckpfad(zid={zid}, start={start}, stop={stop}), node {aktuell} fehlt.")
        return

    while aktuell is not None:
        if aktuell == start:
            start = None
        if aktuell == stop:
            return
        if start is None:
            yield aktuell

        for vorher in self.predecessors(aktuell):
            knoten_typ = self.nodes[vorher]['typ']
            kanten_typ = self.edges[(vorher, aktuell)]['typ']
            if self.nodes[aktuell]['typ'] == 'K' and kuppeln:
                if kanten_typ == 'K':
                    aktuell = vorher
                    zid = vorher.zid
                    break
                else:
                    continue
            elif vorher.zid == zid:
                aktuell = vorher
                break
            elif ersatz and knoten_typ == 'E':
                aktuell = vorher
                zid = vorher.zid
                break
            elif fluegeln and knoten_typ == 'F' and kanten_typ == 'H':
                aktuell = vorher
                zid = vorher.zid
                break
        else:
            aktuell = None

def sim_ereignis_ersatz(self, ereignis: Ereignis):
    """
    Ersatz verarbeiten

    Das Ersatzereignis kommt aus dem Polling vom Pluginclient (stsplugin.PluginClient.request_zugliste),
    nicht vom Simulator!
    Es kann u.U. erst nach dem Abfahrtsereignis ankommen.

    ereignis.zid bezeichnet den Stammzug.
    Unser E-Ereignisknoten gehört zum Stammzug, der Ab-Knoten zum Folgezug.
    """

    prev_label = self.zugpositionen.get(ereignis.zid) or self.zuganfaenge.get(ereignis.zid)
    print("ersatz", ereignis.zid, ereignis.plangleis, prev_label)
    try:
        cur_label = self.zug_ereignis_suchen(start=prev_label, plan=ereignis.plangleis, typ="E")
    except (AttributeError, ValueError, KeyError) as e:
        print("*** ersatzereignis nicht gefunden ***")
        print(e)
        print(f"    prev_label: {self.node_info(prev_label)}")
        print(f"    prev_plan: {self.zugplangleise.get(ereignis.zid)}")
    else:
        self._sim_ereignis_messzeit(cur_label, ereignis)

        # folgezug aktualisieren, wenn das abfahrtsereignis noch nicht gemeldet wurde
        for next_label in self.successors(cur_label):
            if self.edges[(cur_label, next_label)]['typ'] == 'H':
                if next_label.zid not in self.zugpositionen:
                    self.zugpositionen[next_label.zid] = cur_label
                    self.zugplangleise[next_label.zid] = ereignis.plangleis
                    self.zugplanereignisse[next_label.zid] = next_label

                    # print(f"    prev_label: {self.node_info(prev_label)}")
                    # print(f"    cur_label: {self.node_info(cur_label)}")
                    # print(f"    next_label: {self.node_info(next_label)}")
                    # print(f"    edge(p,c): {self.edge_info(prev_label, cur_label)}")
                    # print(f"    edge(c,n): {self.edge_info(cur_label, next_label)}")

    try:
        del self.zugpositionen[ereignis.zid]
        del self.zugplangleise[ereignis.zid]
        del self.zugplanereignisse[ereignis.zid]
    except KeyError:
        pass

def sim_ereignis_fluegeln(self, ereignis: Ereignis):
    """
    Flügeln verarbeiten

    ereignis.zid bezeichnet den Stammzug.
    Unser F-Ereignisknoten gehört zum (durchgehenden) Stammzug.
    """

    prev_label = self.zugpositionen.get(ereignis.zid) or self.zuganfaenge.get(ereignis.zid)
    print("flügeln", ereignis.zid, ereignis.plangleis, prev_label)
    try:
        cur_label = self.zug_ereignis_suchen(start=prev_label, plan=ereignis.plangleis, typ="F")
    except (AttributeError, ValueError, KeyError) as e:
        print("*** flügelnereignis nicht gefunden ***")
        print(e)
        print(f"    prev_label: {self.node_info(prev_label)}")
        print(f"    prev_plan: {self.zugplangleise.get(ereignis.zid)}")
        return
    else:
        self._sim_ereignis_messzeit(cur_label, ereignis)
        for next_label in self.successors(cur_label):
            if self.edges[(cur_label, next_label)]['typ'] == 'H':
                self.zugpositionen[next_label.zid] = cur_label
                self.zugplangleise[next_label.zid] = ereignis.plangleis
                self.zugplanereignisse[next_label.zid] = next_label

def sim_ereignis_kuppeln(self, ereignis: Ereignis):
    """
    Kuppeln verarbeiten

    ereignis.zid bezeichnet den endenden Zug.
    Unser K-Ereignisknoten gehört zum durchgehenden Zug.
    """

    prev_label = self.zugpositionen.get(ereignis.zid) or self.zuganfaenge.get(ereignis.zid)
    print("kuppeln", ereignis.zid, ereignis.plangleis, prev_label)
    try:
        cur_label = self.zug_ereignis_suchen(start=prev_label, plan=ereignis.plangleis, typ="K")
    except (AttributeError, ValueError, KeyError) as e:
        print("*** kuppelnereignis nicht gefunden ***")
        print(e)
        print(f"    prev_label: {self.node_info(prev_label)}")
        print(f"    prev_plan: {self.zugplangleise.get(ereignis.zid)}")
    else:
        self._sim_ereignis_messzeit(cur_label, ereignis)
    try:
        del self.zugpositionen[ereignis.zid]
        del self.zugplangleise[ereignis.zid]
        del self.zugplanereignisse[ereignis.zid]
    except KeyError:
        pass

def sim_ereignis_rothalt(self, ereignis: Ereignis):
    """
    Betriebshalt verarbeiten

    Es gibt zwei Arten von Betriebshalten:

    1. Der Betriebshalt erfolgt statt Durchfahrt.
        Das letzte Ereignis war eine Ankunft,
        die ausgehende Kante ist vom Typ "B",
        die Quelle der nächsten Abfahrt ist "fdl".
        In diesem Fall ist hier nichts zu tun,
        die Ankunft wurde bereits registriert,
        die Abfahrt wird in "wurdegruen" verarbeitet.
    2. Der Betriebshalt erfolgt zwischen an einem Gleis, das nicht im Fahrplan steht.
        Das letzte Ereignis war eine Abfahrt,
        die darauf folgenden zwei Ereignisse sind vom "fdl"
        und durch eine Kante vom Typ "B" verbunden.
        Wir wissen nicht, wo der Zug genau steht.
        Dieser Fall wird aktuell nicht ausgewertet.
    """

    # Phantomzug
    if not ereignis.sichtbar:
        return

    prev_label = self.zugpositionen.get(ereignis.zid)
    if prev_label is None:
        return
    next_label = cur_label = None

    if prev_label.typ == "An":
        cur_label = self.next_ereignis(prev_label, "Ab")
        try:
            if self.edges[(prev_label, cur_label)]['typ'] == "B":
                print("Betriebshalt statt Durchfahrt")
        except KeyError:
            pass

    elif prev_label.typ == "Ab":
        cur_label = self.next_ereignis(prev_label, "An")
        next_label = self.next_ereignis(cur_label, "Ab")
        try:
            if self.edges[(cur_label, next_label)]['typ'] == "B":
                print("Betriebshalt auf Strecke?")
                # self.messzeit_setzen(cur_label, ereignis)
                # self.zugpositionen[ereignis.zid] = cur_label
        except KeyError:
            pass

    # print("rothalt")
    # print(f"    prev_label: {self.node_info(prev_label)}")
    # print(f"    cur_label: {self.node_info(cur_label)}")
    # print(f"    next_label: {self.node_info(next_label)}")
    # print(f"    edge(p,c): {self.edge_info(prev_label, cur_label)}")
    # print(f"    edge(c,n): {self.edge_info(cur_label, next_label)}")

    self.zugplangleise[ereignis.zid] = ereignis.plangleis

def sim_ereignis_uebernehmen(self, ereignis: Ereignis):
    """
    Daten von einem Sim-Ereignis übernehmen.

    Aktualisiert die Verspätung und Status-Flags anhand eines Ereignisses im Simulator.

    Aktualisiert werden die folgenden Attribute:

    - zugpositionen
    - zugplangleise
    - zugplanereignisse
    - t_mess der Ereignisknoten

    Phantomzüge:

    Nach gewissen Nummernwechseln (mit Richtungsänderung?) schickt der Sim weiterhin Ereignisse
    unter der Nummer des nun unsichtbaren Zuges.
    Das sichtbar-Attribut des Ereignisarguments ist dabei False.
    Ausser bei den Ereignisarten 'Ausfahrt', 'Ersatz' sollten solche Ereignisse nicht beachtet werden.

    Args:
        ereignis: Ereignis-objekt vom PluginClient
    """

    # keine Rangierfahrten
    if ereignis.zid <= 0:
        return

    try:
        meth = getattr(self, "sim_ereignis_" + ereignis.art)
    except AttributeError:
        pass
    else:
        meth(ereignis)

def sim_ereignis_wurdegruen(self, ereignis: Ereignis):
    """
    Betriebshalt verarbeiten

    Es gibt zwei Arten von Betriebshalten:

    1. Der Betriebshalt erfolgt statt Durchfahrt.
        Das letzte Ereignis war eine Ankunft,
        die ausgehende Kante ist vom Typ "B",
        die Quelle der nächsten Abfahrt ist "fdl".
        In diesem Fall registrieren wir die Abfahrtszeit.
    2. Der Betriebshalt erfolgt zwischen an einem Gleis, das nicht im Fahrplan steht.
        Das letzte Ereignis war eine Abfahrt,
        die darauf folgenden zwei Ereignisse sind vom "fdl"
        und durch eine Kante vom Typ "B" verbunden.
        Wir wissen nicht, wo der Zug genau steht.
        Dieser Fall wird aktuell nicht ausgewertet.
    """

    # Phantomzug
    if not ereignis.sichtbar:
        return

    prev_label = self.zugpositionen.get(ereignis.zid)
    if prev_label is None:
        return
    next_label = cur_label = None

    print("wurdegruen", ereignis.zid, ereignis.plangleis)
    if prev_label.typ == "An":
        cur_label = self.next_ereignis(prev_label, "Ab")
        try:
            if self.edges[(prev_label, cur_label)]['typ'] == "B":
                print("Abfahrt von Betriebshalt")
                self._sim_ereignis_messzeit(cur_label, ereignis)
                self.zugpositionen[ereignis.zid] = cur_label
        except KeyError:
            pass

    next_label = self._sim_ereignis_update_planereignis(ereignis, prev_label, cur_label, 'An')

def verspaetungen_nach_zielgraph(self, zg: ZielGraph):
    """
    Schreibt die berechneten Verspätungen in den Zielgraphen.

    Die Verspätungen werden aus der Differenz zwischen den t_eff- und t_plan-Feldern der An- und Ab-Knoten berechnet.

    Args:
        zg: Zielgraph
    """

    for ereignis_node, ereignis_data in self.nodes(data=True):
        try:
            ziel_data = zg.nodes[ereignis_data.fid]
        except (AttributeError, KeyError):
            continue

        try:
            v = ereignis_data.t_eff - ereignis_data.t_plan
        except (AttributeError, TypeError):
            logger.warning(f"Unvollständige Zeitinformation für Verspätungsberechnung: {ereignis_data}")
            continue

        if ereignis_data.typ == 'Ab':
            if ziel_data.typ in {'H', 'D', 'B'}:
                ziel_data.v_ab = v
        elif ereignis_data.typ == 'An':
            if ziel_data.typ in {'H', 'D', 'A'}:
                ziel_data.v_an = v
            if ziel_data.typ in {'D', 'A'}:
                ziel_data.v_ab = v

def zielgraph_importieren(self,
                          zg: ZielGraph,
                          clean: bool = False,
                          quelle: str = 'sts',
                          ) -> None:
    """
    Zielgraph importieren

    Der Ereignisgraph wird anhand eines vollständigen Zielgraphs aufgebaut oder aktualisiert.

    Fahrplanhalte werden in Ankunfts- und Abfahrtsereignisse aufgelöst,
    Betriebsvorgänge werden in entsprechende graphische Muster übersetzt.

    Die Methode arbeitet mit EreignisNodeBuilder- und EreignisEdgeBuilder-Objekten.
    In einem ersten Schritt werden alle Zielknoten in ZielEreignisNodeBuilder übersetzt.
    Im zweiten Schritt werden die Zielkanten in ZielEreignisEdgeBuilder übersetzt und ausgeführt.
    Bei der Ausführung der Builder werden die Zielelemente dem Ereignisgraphen hinzugefügt.

    Die gestaffelte Übersetzung von Knoten und Kanten in Builders bietet die notwendige Flexibilität
    in den folgenden Situationen:

    - Es gibt keine eindeutige Zuordnung von Zielknoten zu Ereignisknoten,
      jedoch im Verlauf dieser Methode eine Zuordnung von Zielknoten zu ZielEreignisNodeBuilder.
    - Die Labels von Ereignisknoten können nicht aus Zielknoten abgeleitet werden.
      Es wird eine fortlaufende Nummer eingesetzt.
      Lediglich der erste Ereignisknoten eines Zuges wird mit der Nummer 0 markiert.
    - Zielpunkte im Zielgraph ergeben je nach Typ eines oder zwei Ereignisse.
    - Betriebsvorgänge sind im Zielgraph im Kantentyp dargestellt, im Ereignisgraph durch die Topologie.
    - Beim Iterieren über Kanten kommen Knoten mehrmals vor.
      Knoten dürfen aber nur einmal in den Graphen eingesetzt werden,
      weil es keine eindeutige Zuordnung von Zielknoten zu Ereignisknoten gibt.

    Args:
        zg: Zielgraph enthält die Ursprungsdaten
        clean: Ereignisgraph vollständig neu aufbauen (True)
            oder nur neue Züge hinzufügen (False, default).
            Bei True gehen Änderungen an den Attributen verloren, bei False werden sie beibehalten.
        quelle: Name der Datenquelle oder des Autors.
            Wird in die Ereignisnodes geschrieben.
    """

    if clean:
        self.clear()
        self.zuege = set()

    node_builders = {}
    for zg1, zg1_data in zg.nodes(data=True):
        builder = ZielEreignisNodeBuilder(self)
        builder.import_ziel(zg, zg1_data)
        builder.quelle = quelle
        node_builders[zg1] = builder

    edge_builders = {}
    for zg1, zg2, zge_data in zg.edges(data=True):
        builder = None

        if zge_data.typ == 'P':
            builder = PlanfahrtEdgeBuilder(self)
        elif zge_data.typ == 'E':
            builder = ErsatzEdgeBuilder(self)
        elif zge_data.typ == 'F':
            builder = FluegelungEdgeBuilder(self)
        elif zge_data.typ == 'K':
            builder = KupplungEdgeBuilder(self)
        else:
            logger.warning(f"Unbekannter Zielkantentyp {zge_data.typ}")

        if builder is not None:
            builder.set_edge(node_builders[zg1], node_builders[zg2])
            builder.quelle = quelle
            edge_builders[(zg1, zg2)] = builder

    for builder in node_builders.values():
        builder.add_to_graph()
    for builder in edge_builders.values():
        builder.add_to_graph()

    self._import_validieren()
    self._zuganfaenge_suchen()
    self._zugenden_suchen()

def zug_ereignis_suchen(self,
                        zid: int | None = None,
                        start: EreignisLabelType | None = None,
                        **kwargs,
                        ) -> EreignisLabelType:
    """
    Ereignis mit gegebenen Attributen im Zugpfad suchen.

    Suche im Zugpfad ab einem wählbaren Startpunkt nach einem Ereignis mit den gegebenen Attributen.
    Die Suche folgt der Richtung des Graphen,
    läuft über durch E/F/K-Ereignisse verbundene Folgezüge
    und endet am Knoten, der keine Nachfolger hat.

    Args:
        zid: Gesuchte Zug-ID.
            Das gesuchte Ereignis muss diese Zug-ID haben.
            zid kann sich von start.zid unterscheiden,
            muss dann aber ein Folgezug von start.zid bezeichnen.
            Mindestens eines der Argumente zid und start muss angegeben werden.
        start: Startnode.
            Die Suche startet an diesem Knoten (inklusiv).
            Wenn kein Start angegeben ist, beginnt die Suche am Zuganfang.
            Mindestens eines der Argumente zid und start muss angegeben werden.
        kwargs: Gesuchte Attributwerte.
            Die Keys müssen Attributnamen von EreignisGraphNode entsprechen.
            Bei float-Attributen gilt eine Toleranz von 0.0001.

    Raises:
        KeyError: Zug wird nicht gefunden.
        ValueError: Attributwerte werden nicht gefunden.
    """

    if start is None:
        start_zid = zid
    else:
        start_zid = start.zid
        if zid is not None:
            kwargs['zid'] = zid

    for label in self.zugpfad(start_zid, ersatz=True, kuppeln=True):
        if start is not None:
            if label == start:
                start = None
            else:
                continue

        data = self.nodes[label]
        for kw, arg in kwargs.items():
            if kw in {'t_mess', 't_plan', 't_prog', 's'}:
                if abs(arg - data.get(kw)) > 0.0001:
                    break
            elif data.get(kw) != arg:
                break
        else:
            return label

    raise ValueError(f"Suche nach {kwargs} im Pfad von {start or zid} fehlgeschlagen.")

def zugpfad(self,
            zid: int,
            start: EreignisLabelType | None = None,
            stop: EreignisLabelType | None = None,
            ersatz: bool = False,
            kuppeln: bool = False,
            fluegeln: bool = False,
            ) -> Generator[EreignisLabelType, None, None]:
    """
    Generator für die fortlaufenden Ereignisse eines Zuges

    Beginnend mit dem Startknoten liefert der Generator die Ereignis-IDs eines Zuges
    in der Reihenfolge ihres Auftretens.

    Das Verhalten des Generators bei Ersatz/Flügeln/Kuppeln kann mit Flags angepasst werden.

    Args:
        zid: Zug-ID
        start: Knoten-ID des ersten Knotens.
            Falls None (default) der erste Knoten des Zuges mit ID (zid, 0).
        stop: Knoten-ID des ersten nicht mehr gelieferten Knotens.
            Falls None (default) werden die Knoten bis einschliesslich des letzten des Zuges geliefert.
        ersatz: Wenn True, fährt der Generator bei Ersatz mit dem Folgezug fort.
            Ansonsten stoppt der Generator nach dem Ankunftsknoten des Stammzuges.
        kuppeln: Wenn True, fährt der Generator beim Kuppeln mit dem Folgezug fort.
            Ansonsten stoppt der Generator nach dem Ankunftsknoten des endenden Zuges.
        fluegeln: Wenn False (default), läuft der Generator durchgehend über den Stammzug.
            Wenn True, läuft der Generator über den geflügelten Zug.

    Returns:
        Generator von Knoten-IDs.
    """

    aktuell = self.zuganfaenge[zid]
    if not self.has_node(aktuell):
        logger.debug(f"EreignisGraph.zugpfad(zid={zid}, start={start}, stop={stop}), node {aktuell} fehlt.")
        return

    while aktuell is not None:
        if aktuell == start:
            start = None
        if aktuell == stop:
            return
        if start is None:
            yield aktuell

        for nachher in self.successors(aktuell):
            knoten_typ = self.nodes[aktuell]['typ']
            kanten_typ = self.edges[(aktuell, nachher)]['typ']

            if knoten_typ == 'F' and fluegeln:
                if nachher.zid == zid:
                    # stamm ignorieren
                    continue
                elif kanten_typ == 'H':
                    # fluegel
                    aktuell = nachher
                    zid = nachher.zid
                    break
            elif nachher.zid == zid:
                aktuell = nachher
                break
            elif ersatz and knoten_typ == 'E' and kanten_typ == 'H':
                aktuell = nachher
                zid = nachher.zid
                break
            elif kuppeln and kanten_typ == 'K' and self.nodes[nachher]['typ'] == 'K':
                aktuell = nachher
                zid = nachher.zid
                break
        else:
            aktuell = None

@abstractmethod
def add_to_graph(self):
    """
    Knoten und Kanten zum Ereignisgraphen hinzufügen.

    Die Methode fügt die von dem Builder verantworteten Knoten und internen Kanten dem EreignisGraph hinzu.
    Die Methode darf nur beim ersten Aufruf eine Wirkung zeigen.
    """
    self.ausgefuehrt = True

@abstractmethod
def first_label(self) -> EreignisLabelType:
    """
    Label des ersten erstellten Ereignisses.

    Das Ereignislabel wird von einlaufenden Kanten referenziert.
    Das Label ist erst nach Ausführen der add_to_graph-Methode gültig!
    """
    return None

@abstractmethod
def last_label(self) -> EreignisLabelType:
    """
    Label des letzten erstellten Ereignisses.

    Das Ereignislabel wird von auslaufenden Kanten referenziert.
    Das Label ist erst nach Ausführen der add_to_graph-Methode gültig!
    """
    return None