dijkstra.py

import heapq
import networkx as nx
import numpy as np
import concurrent.futures

def dijkstra_base_rho(g_weighted, start, threshold, max_nodes_to_visit=None):
    """Dijkstra using current rho weights with threshold pruning."""
    distances = {start: 0.0}
    default_dist = float('inf')
    preds = {}
    heap = [(0.0, start)]
    visited_count = 0
    
    while heap:
        current_dist, u = heapq.heappop(heap)
        if current_dist > distances.get(u, default_dist): continue
        
        if max_nodes_to_visit is not None and visited_count >= max_nodes_to_visit: break
        visited_count += 1

        if u not in g_weighted: continue
        for v in g_weighted.neighbors(u):
            weight = g_weighted.get_edge_data(u, v, default={'weight': default_dist})['weight']
            if weight == default_dist: continue
            new_dist = current_dist + weight
            if new_dist < distances.get(v, default_dist):
                 distances[v] = new_dist
                 preds[v] = u
                 heapq.heappush(heap, (new_dist, v))
    return distances, preds

def find_violated_cycles_F_adapted(graph, rho_map, violation_threshold, start_node):
    """
    Finds violated cycles starting Dijkstra from start_node, using rho weights.

    Args:
        graph: Original graph structure.
        rho_map: Current rho values as edge weights.
        violation_threshold: p-length must be < this value.
        start_node: Node to start Dijkstra from.

    Returns:
        List of tuples: [(cycle_frozenset, p_length), ...] found from this start node.
    """
    violated_cycles = []
    found_cycle_sets = set()  # Avoid duplicates from the same start node

    # 1. Create weighted graph for Dijkstra
    g_weighted = nx.Graph()
    default_dist = float('inf')
    for u, v in graph.edges():
         edge = tuple(sorted((u,v)))
         rho = max(rho_map.get(edge, 0.0), 1e-12)  # Epsilon for Dijkstra stability
         g_weighted.add_edge(u, v, weight=rho)

    # 2. Run Dijkstra from start_node (using modified Dijkstra)
    # We pass the full threshold to potentially explore further
    distances, preds = dijkstra_base_rho(g_weighted, start_node, violation_threshold * 2)  # Explore wider
    nodes_reached = set(distances.keys())

    # 3. Check edges for potential cycle closures
    edges_to_check = set()
    # Consider edges where *both* endpoints were reached by Dijkstra from start_node
    for u in nodes_reached:
        for v in graph.neighbors(u):
             # Check if v was also reached and the edge exists in the original graph
            if v in nodes_reached and graph.has_edge(u, v):
                # Avoid checking trivial cases or edges already in Dijkstra tree path directly
                if u != v and preds.get(u) != v and preds.get(v) != u:
                     edges_to_check.add(tuple(sorted((u,v))))

    # 4. Calculate p-length and check violation
    for edge_uv in edges_to_check:
        u, v = edge_uv
        # Ensure distances are finite (should be if in nodes_reached)
        if distances[u] == default_dist or distances[v] == default_dist: continue

        rho_uv = max(rho_map.get(edge_uv, 0.0), 0.0)  # Use actual rho for length
        p_length = distances[u] + distances[v] + rho_uv

        # Check if it violates threshold and is non-zero
        if 1e-9 < p_length < violation_threshold:
            # --- Reconstruct Cycle Edges ---
            # Path from start_node to u
            path_u_nodes = [u]; curr = u
            while curr != start_node and curr in preds: path_u_nodes.append(preds[curr]); curr = preds[curr]
            if curr != start_node: continue  # Path didn't reach start? Should not happen
            path_u_nodes.reverse()

            # Path from start_node to v
            path_v_nodes = [v]; curr = v
            while curr != start_node and curr in preds: path_v_nodes.append(preds[curr]); curr = preds[curr]
            if curr != start_node: continue
            path_v_nodes.reverse()

            # Find LCA index (last common node in paths from start)
            lca_idx = 0
            max_common_len = min(len(path_u_nodes), len(path_v_nodes))
            while lca_idx < max_common_len and path_u_nodes[lca_idx] == path_v_nodes[lca_idx]:
                lca_idx += 1
            lca_idx -= 1  # Index of the LCA node itself

            # Combine paths: path(LCA->u) + edge(u,v) + path(v->LCA) reversed
            cycle_nodes = path_u_nodes[lca_idx:] + path_v_nodes[lca_idx+1:][::-1]

            # Validate constructed cycle
            if len(cycle_nodes) >= 3:
                cycle_edges = set()
                valid_recon = True
                for i in range(len(cycle_nodes)):
                    n1 = cycle_nodes[i]; n2 = cycle_nodes[(i + 1) % len(cycle_nodes)]
                    edge = tuple(sorted((n1, n2)))
                    # Crucially check against original graph structure
                    if graph.has_edge(n1, n2): cycle_edges.add(edge)
                    else: valid_recon = False; break

                # Ensure the closing edge was the one we checked, size>=3, no duplicate edges
                if valid_recon and edge_uv in cycle_edges and len(cycle_edges) >= 3:
                     cycle_fset = frozenset(cycle_edges)
                     if cycle_fset not in found_cycle_sets:
                         violated_cycles.append((cycle_fset, p_length))
                         found_cycle_sets.add(cycle_fset)

    return violated_cycles

def parallel_worker_F_adapted(args):
    """ Wraps find_violated_cycles_F_adapted for ProcessPoolExecutor. """
    graph, rho_map, violation_threshold, start_node, _ = args
    try:
        return find_violated_cycles_F_adapted(graph, rho_map, violation_threshold, start_node)
    except Exception as e:
        print(f"Error in parallel worker (node {start_node}): {e}")
        return []  # Return empty list on error