liniengraph

def distanz(self, u: BahnhofElement, v: BahnhofElement, metrik: str) -> Any:
    """
    Distanz zwischen zwei Bahnhöfen

    Es muss eine direkte Kante zwischen den zwei Bahnhöfen bestehen.

    Args:
        u: Erste Betriebsstelle (Bf oder Anst)
        v: Zweite Betriebsstelle (Bf oder Anst)
        metrik: Kantenattribut im Liniengraph:
            fahrzeit_min, fahrzeit_schnitt oder fahrzeit_max.
    """

    try:
        data = self[u][v]
        zeit = data.get('fahrzeit_manuell', 0) or data.get(metrik, 0)
    except KeyError:
        logger.warning(f"Verbindung {u}-{v} nicht im Liniengraph.")
        zeit = 0

    return max(1, zeit)

def export_konfiguration(self) -> Sequence[dict[str, str | int | float | bool]]:
    """
    Streckenmarkierung in Konfigurationsformat exportieren
    """

    result = []
    for e1, e2, data in self.edges(data=True):
        m = data.get('markierung', '')
        z = data.get('fahrzeit_manuell', 0)
        d = {}
        if m:
            d['flags'] = m
        if z > 0:
            d['fahrzeit'] = z
        if d:
            d['station1'] = str(e1)
            d['station2'] = str(e2)
            result.append(d)

    return result

def import_konfiguration(self,
                         streckenmarkierung_konfig: Iterable[dict[str, Any]],
                         bahnhofgraph: BahnhofGraph):
    """
    Streckenmarkierungen aus der Konfiguration übernehmen
    """

    for markierung_kfg in streckenmarkierung_konfig:
        station1 = BahnhofElement.from_string(markierung_kfg['station1'])
        station2 = BahnhofElement.from_string(markierung_kfg['station2'])
        fahrzeit = markierung_kfg.get('fahrzeit', 0)
        markierung = markierung_kfg.get('flags', '')
        if station1 in bahnhofgraph and station2 in bahnhofgraph:
            if station1 not in self:
                self.add_node(station1, typ=station1.typ, name=station1.name, fahrten=0)
            if station2 not in self:
                self.add_node(station2, typ=station2.typ, name=station2.name, fahrten=0)
            self.add_edge(station1, station2)
            if markierung:
                self.edges[station1, station2]['markierung'] = markierung
            if fahrzeit > 0:
                self.edges[station1, station2]['fahrzeit_manuell'] = fahrzeit
        else:
            logger.warning(f"Streckenmarkierung zwischen {station1} und {station2} konnte nicht zugeordnet werden.")

@staticmethod
def label(typ: str, name: str) -> LinienLabelType:
    """
    Das Label vom Liniengraph entspricht dem des BahnsteigGraph, i.d.R. auf Stufe Bf und Anst.
    """
    return LinienLabelType(typ, name)

def linie_eintragen(self,
                    ziel1: ZielGraphNode, bahnhof1: BahnsteigGraphNode,
                    ziel2: ZielGraphNode, bahnhof2: BahnsteigGraphNode):
    """
    Liniengraph erstellen

    Sollte nicht mehr als einmal pro Zug aufgerufen werden, da sonst die Statistik verfälscht werden kann.
    """

    try:
        fahrzeit = ziel2.p_an - ziel1.p_ab
        # beschleunigungszeit von haltenden zuegen
        if ziel1.typ == 'D':
            fahrzeit += 1
    except AttributeError:
        fahrzeit = 2

    bft1 = self.label(bahnhof1.typ, bahnhof1.name)
    bft2 = self.label(bahnhof2.typ, bahnhof2.name)

    try:
        knoten1_daten = self.nodes[bft1]
        assert isinstance(knoten1_daten, LinienGraphNode)
    except KeyError:
        knoten1_daten = LinienGraphNode(typ=bahnhof1.typ, name=bahnhof1.name, fahrten=0)
    try:
        knoten2_daten = self.nodes[bft2]
        assert isinstance(knoten2_daten, LinienGraphNode)
    except KeyError:
        knoten2_daten = LinienGraphNode(typ=bahnhof2.typ, name=bahnhof2.name, fahrten=0)

    knoten1_daten.fahrten += 1
    knoten2_daten.fahrten += 1

    try:
        liniendaten = self[bft1][bft2]
        assert isinstance(liniendaten, LinienGraphEdge)
    except KeyError:
        liniendaten = LinienGraphEdge(fahrzeit_min=self.MAX_FAHRZEIT, fahrzeit_max=0,
                                      fahrten=0, fahrzeit_summe=0., fahrzeit_schnitt=0.)

    liniendaten.fahrzeit_min = min(liniendaten.fahrzeit_min, fahrzeit)
    liniendaten.fahrzeit_max = max(liniendaten.fahrzeit_max, fahrzeit)
    liniendaten.fahrten += 1
    liniendaten.fahrzeit_summe += fahrzeit
    liniendaten.fahrzeit_schnitt = liniendaten.fahrzeit_summe / liniendaten.fahrten

    self.add_edge(bft1, bft2, **liniendaten)
    self.add_node(bft1, **knoten1_daten)
    self.add_node(bft2, **knoten2_daten)

def schleifen_aufloesen(self):
    """
    Schleifen auflösen

    Weil Züge nicht alle Haltestellen bedienen,
    kann es im Liniengraph mehrere Verbindungen zwischen zwei Knoten geben,
    die im Graphen eine Schleife (cycle) bilden.
    Damit eine Strecke möglichst dem tatsächlichen Gleisverlauf folgt,
    löst diese Funktion solche Schleifen auf, indem sie die längste Kante jeder Schleife entfernt.
    Die Länge der Kante ist die minimale Fahrzeit zwischen den Knoten.

    Wenn die längste Kante nicht eindeutig bestimmt werden kann, wird die Schleife nicht aufgelöst.
    Dies kann z.B. der Fall sein, wenn die Fahrzeit zwischen allen Knoten gleich lang ist,
    weil der durchfahrende Zug die Zeit zum Anhalten und Beschleunigen einspart.
    Die Funktion versucht, solche Fälle aufzulösen,
    indem sie Verbindungen zwischen Knoten mit Grad > 2 künstlich verlängert.

    Note:
        Diese Methode entfernt Elemente aus dem Liniengraph, was die Darstellung des Streckenfahrplans behindern kann.
        Bei Anwendungen, die keine Schleifen erlauben, sollte die Methode auf eine private Kopie angewendet werden!
    """

    entfernen = set()

    for schleife in nx.simple_cycles(self):
        kanten = zip(schleife, schleife[1:] + schleife[:1])
        laengste_fahrzeit = 0
        summe_fahrzeit = 0
        laengste_kante = None

        for kante in kanten:
            fahrzeit = max(1, self.edges[kante].get("fahrzeit_min", 0))
            fahrzeit += max(0, self.degree[kante[0]] - 2)
            fahrzeit += max(0, self.degree[kante[1]] - 2)
            if self.degree[kante[0]] > 2 and self.degree[kante[1]] > 2:
                summe_fahrzeit += fahrzeit
                if fahrzeit > laengste_fahrzeit:
                    laengste_fahrzeit = fahrzeit
                    laengste_kante = kante

        if laengste_kante is not None:
            if laengste_fahrzeit > summe_fahrzeit - laengste_fahrzeit - len(schleife):
                entfernen.add(laengste_kante)
            else:
                schleifen_text = ", ".join((str(bst) for bst in schleife))
                logger.debug(f"symmetrische schleife {schleifen_text}")

    for u, v in entfernen:
        try:
            self.remove_edge(u, v)
        except nx.NetworkXError:
            pass

def strecke(self, start: LinienLabelType, ziel: LinienLabelType) -> list[LinienLabelType]:
    """
    Kürzeste Verbindung zwischen zwei Punkten bestimmen.

    Start und Ziel sind die Labels zweier beliebiger Knoten im Liniengraph.
    Die berechnete Strecke ist eine geordnete Liste von Labels.

    Da die Streckenberechnung aufwändig sein kann, werden die Resultate im
    `_strecken_cache` gespeichert. Der Cache muss gelöscht werden, wenn der
    Graph verändert wird.

    Args:
        start: Bahnhof- oder Anschlussname.
        ziel: Bahnhof- oder Anschlussname.

    Returns:
        Liste von befahrenen Gleisgruppen vom Start zum Ziel.
        Die Liste kann leer sein, wenn kein Pfad gefunden wurde.
    """

    try:
        return self._strecken_cache[(start, ziel)]
    except KeyError:
        pass

    try:
        strecke: list[LinienLabelType] = nx.shortest_path(self, start, ziel)
    except nx.NetworkXException:
        strecke: list[LinienLabelType] = []

    self._strecken_cache[(start, ziel)] = strecke
    return strecke

def strecken_vorschlagen(self, min_fahrten: int = 0, min_laenge: int = 2) -> list[list[LinienLabelType]]:
    """
    Strecken aus Liniengraph vorschlagen

    Diese Funktion bestimmt die kürzesten Strecken zwischen allen Kombinationen von Anschlüssen.
    Wenig frequentierte Anschlüsse können ausgeschlossen werden.

    Eine Strecke besteht aus einer Liste von Bahnhöfen inklusive Einfahrt am Anfang und Ausfahrt am Ende.
    Die Elemente sind Knotenlabels des Liniengraphen.

    Args:
        min_fahrten: Minimale Anzahl von Fahrten, die ein Anschluss aufweisen muss,
            um in die Auswahl aufgenommen zu werden.
            Per default (0), werden auch Strecken zwischen unbenutzten Anschlüssen erstellt.

        min_laenge: Minimale Länge (Anzahl Wegpunkte) einer Strecke.
            Kürzere Strecken werden ignoriert.
            Die Defaultlänge 2 liefert auch direkte Strecken zwischen Einfahrt und Ausfahrt.

    Returns:
        Liste von Listen von Liniengraphlabels
    """

    anschluesse = [x for x, d in self.nodes(data=True) if d.get('typ', '?') == 'Anst']
    strecken = []

    for ein, aus in itertools.permutations(anschluesse, 2):
        try:
            fahrten: int = min(self.nodes[ein]['fahrten'], self.nodes[aus]['fahrten'])
        except KeyError:
            fahrten = -1

        if ein != aus and fahrten >= min_fahrten:
            strecke = self.strecke(ein, aus)
            if len(strecke) >= min_laenge:
                strecken.append(strecke)

    return strecken

def strecken_zeitachse(self,
                       strecke: Sequence[BahnhofElement],
                       metrik: str = 'fahrzeit_min',
                       ) -> Sequence[int | float]:
    """
    Distanzen entlang einer Strecke berechnen

    Kumulierte Distanzen der Haltepunkte ab dem ersten Punkt der Strecke berechnen.
    Die Distanz wird als Fahrzeit in Minuten angegeben.

    Als Fahrzeit wird für jeden Abschnitt der erste der folgenden Werte genommen, der grösser als Null ist:
    1. 'fahrzeit_manuell'-Attribut der Liniengraph-Kante (vom Benutzer konfiguriert).
    2. Vom parameter-Argument bezeichnetes Attribut der Liniengraph-Kante.
    3. 1 (default, auch bei fehlender Kante im Liniengraph).

    Args:
        strecke: Liste von Linienpunkten
        metrik: Kantenattribut im Liniengraph:
            fahrzeit_min, fahrzeit_schnitt oder fahrzeit_max.

    Returns: distanz = Fahrzeit in Minuten.
        Die Liste enthält die gleiche Anzahl Elemente wie die Strecke.
        Das erste Element ist 0.
    """

    kanten = zip(strecke[:-1], strecke[1:])
    distanzen = [self.distanz(u, v, metrik) for u, v in kanten]
    return list(itertools.accumulate(distanzen, initial=0))

def add_strecke(self,
                name: str,
                stationen: Iterable[BahnhofElement],
                ordnung: int = DEFAULT_SORT_KEY,
                auto: bool = True,
                ) -> None:
    """
    Strecke definieren
    """

    stationen = list(stationen)
    if len(stationen) < 2:
        return

    self.strecken[name] = list(stationen)
    self.ordnung[name] = ordnung
    self.auto[name] = auto

def clear(self):
    """
    Alle Streckendefinitionen löschen
    """

    self.strecken.clear()
    self.ordnung.clear()
    self.auto.clear()
    self._hauptstrecke = None

def export_konfiguration(self) -> list[dict[str, Any]]:
    """
    Streckendeklaration in Konfigurationsformat exportieren
    """

    konfig: list[dict[str, Any]] = []

    for key in sorted(self.ordnung.keys(), key=self._sort_key):
        stationen: list[str] = [str(station) for station in self.strecken[key]]
        konfig.append({'name': key,
                       'haupt': key == self.hauptstrecke,
                       'ordnung': self.ordnung[key],
                       'auto': self.auto[key],
                       'stationen': stationen})

    return konfig

def import_konfiguration(self,
                         strecken_konfig: Iterable[dict[str, Any]],
                         bahnhofgraph: BahnhofGraph):
    """
    Streckendefinition aus der Konfiguration übernehmen
    """

    strecken: dict[str, Sequence[BahnhofElement]] = {}
    haupt: dict[str, bool] = {}
    ordnung: dict[str, int] = {}
    auto: dict[str, bool] = {}

    for strecke_kfg in strecken_konfig:
        strecke: list[BahnhofElement] = []
        for station in strecke_kfg['stationen']:
            if bahnhofgraph.has_node(node := BahnhofElement.from_string(station)):
                strecke.append(node)
        if len(strecke) < 2:
            continue

        try:
            key: str = strecke_kfg['name']
        except KeyError:
            key: str = "-".join((str(strecke[0]), str(strecke[-1])))

        strecken[key] = strecke
        haupt[key] = strecke_kfg.get('haupt', False)
        ordnung[key] = strecke_kfg.get('ordnung', DEFAULT_SORT_KEY)
        auto[key] = strecke_kfg.get('auto', True)

    for key in ordnung:
        self.strecken[key] = strecken[key]
        self.ordnung[key] = ordnung[key]
        self.auto[key] = auto[key]

    hauptstrecken: list[str] = [k for k, v in haupt.items() if v]
    if hauptstrecken:
        self.hauptstrecke = min(hauptstrecken, key=self._sort_key)
    else:
        self.hauptstrecke = None

def remove_strecke(self, name: str):
    """
    Streckendefinition entfernen
    """

    try:
        del self.strecken[name]
    except KeyError:
        pass
    try:
        del self.ordnung[name]
    except KeyError:
        pass
    try:
        del self.auto[name]
    except KeyError:
        pass
    if self._hauptstrecke == name:
        self._hauptstrecke = None

def streckengraph(self, strecke: str) -> LinienGraph:
    """
    Strecke als Liniengraph darstellen

    Kann nützlich sein, wenn auf Liniengraphdaten für eine Strecke zugegriffen werden soll.
    Das Resultat ist ein View und daher nicht veränderbar.

    Todo: Mir ist noch nicht klar, wie dynamisch der View ist,
    d.h. ob Änderungen am Basisgraph automatisch sichtbar werden.
    Ausserdem: Können Attribute verändert werden?
    """

    def fn(node: BahnhofElement) -> bool:
        return node in self.strecken[strecke]

    def fe(node1: BahnhofElement, node2: BahnhofElement) -> bool:
        return node1 in self.strecken[strecke] and node2 in self.strecken[strecke]

    assert self.liniengraph is not None
    result = nx.subgraph_view(self.liniengraph, filter_node=fn, filter_edge=fe)
    assert isinstance(result, LinienGraph)
    return result

def validate(self, bahnhofgraph: BahnhofGraph):
    """
    Strecken mit Bahnhofgraph abgleichen

    Überprüft die Streckendefinitionen auf korrekte Stationen und
    entfernt nicht vorhandene Stationen. Bei weniger als zwei Stationen
    wird die Strecke gelöscht.
    """

    korrekturen = {}
    for name in self.strecken.keys():
        strecke = self.strecken[name]
        stationen = [station for station in strecke if bahnhofgraph.has_node(station)]
        if len(stationen) != len(strecke):
            korrekturen[name] = stationen

    for name, stationen in korrekturen.items():
        if len(stationen) >= 2:
            self.strecken[name] = stationen
        else:
            self.remove_strecke(name)