signalgraph

def graph_anschluesse_pruefen(g: nx.Graph) -> nx.Graph:
    """
    Kanten von Anschlüssen prüfen und vereinfachen.

    Anschlüsse sollten wenn möglich mit Signalen verbunden sein.
    Direkte Verbindungen zu Bahnsteigen werden entfernt,
    außer es liegen keine Signale in der Nachbarschaft.

    Args:
        g: Ungerichteter Graph.

    Returns:
        Graph `g` mit geänderten Anschlüssen.
    """
    anschl = {n for n, _d in g.nodes.items()
              if _d.get('typ', None) in {Knoten.Typ.EINFAHRT, Knoten.Typ.AUSFAHRT}}
    for a in anschl:
        edges_to_remove = []
        signal_gefunden = False
        nbr = [n for n in g[a]]
        for n in nbr:
            if g.nodes[n]['typ'] == Knoten.Typ.SIGNAL:
                signal_gefunden = True
            else:
                edges_to_remove.append((a, n))
        if signal_gefunden:
            g.remove_edges_from(edges_to_remove)

    return g

def graph_bahnsteigsignale_ersetzen(g: nx.Graph) -> nx.Graph:
    """
    Bahnsteig-Signal-Kombinationen durch Bahnsteige ersetzen.

    Vereinfacht die Gleisanlage, indem Signale in der Nachbarschaft von Bahnsteigen und Haltepunkten entfernt werden.
    Die von den betroffenen Signalen ausgehenden Kanten werden durch direkte Kanten der jeweiligen Partner ersetzt.

    Die Funktion hat zum Zweck, dass in der vereinfachten Gleisanlage Pfade nicht an den Bahnsteigen vorbeiführen.

    Args:
        g: Ungerichteter Graph.

    Returns:
        Graph `g` mit ersetzten Weichen.
    """
    bahnsteige = {n for n, _d in g.nodes.items() if _d.get('typ', None)
                  in {Knoten.Typ.BAHNSTEIG, Knoten.Typ.HALTEPUNKT}}
    for b in bahnsteige:
        nbr = [n for n in g[b]]
        for v in nbr:
            if g.nodes[v]['typ'] == Knoten.Typ.SIGNAL:
                g = nx.contracted_nodes(g, b, v, self_loops=False, copy=False)

    return g

def graph_gleise_zuordnen(g: nx.Graph,
                          gleiszuordnung: dict[str, str],
                          ) -> nx.Graph:
    """
    Gleise in Graph zu Gruppen zusammenfassen.

    Args:
        g: Signalgraph, Gleisgraph oder ähnlicher Graph.
        gleiszuordnung: Mapping Gleisname zu Gruppenname.

    Returns:
        Graph g mit zugeordneten Gleisen.
    """
    g = nx.relabel_nodes(g, gleiszuordnung, copy=False)
    g.remove_edges_from(nx.selfloop_edges(g))
    return g

def graph_mehrdeutige_strecke_abgleichen(g: nx.Graph,
                                         strecke: Sequence[str],
                                         routen: Sequence[Sequence[str]],
                                         ) -> nx.Graph:
    """
    Mehrdeutige Strecke mit Zugrouten abgleichen.

    Wenn die Reihenfolge der Stationen auf einer Strecke nicht eindeutig bestimmt werden kann,
    bleiben im Gleisgraphen Schleifen zurück.
    Diese Funktion versucht, die Reihenfolge anhand von bekannten Zugläufen zu bestimmen.
    Wenn ein Zug alle Stationen der Strecke anfährt, werden diese Kanten im Graphen belassen
    und alle unbedienten in der Nachbarschaft entfernt.

    Args:
        g: Gleisgraph oder ähnlich.
        strecke: Sequenz von Stationen, deren Reihenfolge abgeglichen werden soll.
        routen: Liste von Routen. Jede Route besteht aus einer Sequenz von Stationsnamen im Graphen g.

    Returns:
        Modifizierter Graph g.
    """
    nachbarschaft = set([])
    for k in strecke:
        nachbarschaft.update(g.adj[k])

    edges_to_remove = set([])
    for route in routen:
        match_index = [i for i, n in enumerate(route) if n in nachbarschaft]
        if len(match_index) >= len(nachbarschaft):
            pfad = route[min(match_index):max(match_index)+1]
            rg = nx.Graph(zip(pfad[:-1], pfad[1:]))
            for n in strecke:
                for e in g.edges(n):
                    if e not in rg.edges:
                        edges_to_remove.add(e)
            break

    g.remove_edges_from(edges_to_remove)
    return g

def graph_mehrdeutige_strecken(g: nx.Graph,
                               max_knoten: int = 3,
                               ) -> list[set[str]]:
    """
    Findet mehrdeutige Streckenabschnitte.

    In mehrdeutigen Streckenabschnitten ist die Reihenfolge von Stationen aus dem Signalgraph unklar.
    Im Graphen erscheinen sie als Schleifen, meistens Dreiecke.

    Args:
        g: Signal-Graph, Gleis-Graph oder ähnlicher Graph.
        max_knoten: Filtert Abschnitte mit mehr als einer maximalen Knotenzahl heraus,
            wenn längere Schleifen nicht gemeldet werden sollen.

    Returns:
        Liste von mehrdeutigen Kanten.
    """
    cycles = nx.cycle_basis(g)
    cycles = [c for c in cycles if len(c) <= max_knoten]
    return cycles

def graph_signalpaare_ersetzen(g: nx.Graph) -> nx.Graph:
    """
    Signalpaare kontrahieren.

    Signale, die mit einem anderen Signal verbunden sind, werden durch ein einzelnes ersetzt.

    Args:
        g: Ungerichteter Graph.

    Returns:
        Graph `g` mit ersetzten Signalpaaren.
    """
    while True:
        signale = {n for n, _d in g.nodes.items()
                   if _d.get('typ', None) == Knoten.Typ.SIGNAL}
        for s1 in signale:
            for s2 in g[s1]:
                if g.nodes[s2]['typ'] == Knoten.Typ.SIGNAL:
                    g = nx.contracted_nodes(g, s1, s2, self_loops=False, copy=False)
                    signale.remove(s2)
                    break
            else:
                continue
            break
        else:
            break

    return g

def graph_weichen_ersetzen(g: nx.Graph) -> nx.Graph:
    """
    Weichen durch Kanten ersetzen.

    Vereinfacht die Gleisanlage, indem Weichen durch direkte Kanten der Nachbarknoten ersetzt werden.

    Args:
        g: Ungerichteter Graph.

    Returns:
        Graph `g` mit ersetzten Weichen.
    """
    weichen = {n for n, _d in g.nodes.items()
               if _d.get('typ', None) in {Knoten.Typ.WEICHE_OBEN, Knoten.Typ.WEICHE_UNTEN}}
    for w in weichen:
        for v in g[w]:
            # w wird entfernt
            g = nx.contracted_nodes(g, v, w, self_loops=False, copy=False)
            break

    return g

def graph_zwischensignale_entfernen(g: nx.Graph) -> nx.Graph:
    """
    Einzelne Signale zwischen Bahnsteigen durch Kanten ersetzen.

    Args:
        g: Ungerichteter Graph.

    Returns:
        Graph `g` mit entfernten Signalen.
    """
    signale = {n for n, _d in g.nodes.items()
               if _d.get('typ', None) == Knoten.Typ.SIGNAL}
    while signale:
        s1 = signale.pop()
        for s2 in g[s1]:
            if g.nodes[s2]['typ'] in {Knoten.Typ.BAHNSTEIG, Knoten.Typ.HALTEPUNKT}:
                g = nx.contracted_nodes(g, s2, s1, self_loops=False, copy=False)
                break

    return g