hal.utils.graph_utils¶
best_greedy_mps ¶
best_greedy_mps(G, num_iter=100, seed=None)
Run the randomized greedy MPS extraction multiple times and return the best result.
Parameters: - G: The original graph. - num_iter: Number of iterations to perform. - seed: Optional seed for reproducibility.
Returns: - best_P: The planar subgraph with the maximum number of edges found.
ccw ¶
ccw(A, B, C)
Return True if points A, B, C are in counterclockwise order.
Args: A (tuple[float, float]): First point. B (tuple[float, float]): Second point. C (tuple[float, float]): Third point.
Returns: bool: True if the points are in counterclockwise order.
community_layout ¶
community_layout(g)
Compute the layout for a modular graph.
Arguments:
g -- networkx.Graph or networkx.DiGraph instance graph to plot
partition -- dict mapping int node -> int community graph partitions
Returns:
pos -- dict mapping int node -> (float x, float y) node positions
compute_crossing_pairs ¶
compute_crossing_pairs(G)
Given a graph G with node positions, compute a list of edge pairs that cross. Only consider pairs of edges that do not share a vertex.
Returns: crossing_pairs: a list of tuples (e, f) where each e and f are edges represented as tuples of nodes (with nodes in sorted order).
dash_print ¶
dash_print(message, string_length=50, char='-')
Print a message with dashes around it for emphasis.
Args: message (str): The message to print. string_length (int): The total length of the printed line, including dashes.
generate_tanner_graph ¶
generate_tanner_graph(parity_check_matrix)
Generate a Tanner graph from a parity check matrix.
Args: parity_check_matrix (np.ndarray): Parity check matrix. Assumes he parity check matrix is structured as np.vstack((Hx, Hz)),
Returns: nx.Graph: A bipartite Tanner graph.
get_ordered_edges ¶
get_ordered_edges(G, edge_metric, edge_weights=None)
Calculates a metric for each edge and returns a sorted list of edges.
New metrics added: - "betweenness": Edge betweenness centrality. Measures the edge's importance as a bridge in the graph's shortest paths. - "sum_degrees": The sum of the degrees of an edge's two endpoints. A heuristic for routing in congested areas first. - "angle": The geometric angle of the edge. Useful for routing in a systematic sweeping order.
greedy_mps_random ¶
greedy_mps_random(G, seed=None)
Greedy maximum planar subgraph extraction with randomized ordering of remaining edges.
Parameters: - G: The original graph. - seed: Optional seed for reproducibility.
Returns: - P: A planar subgraph of G.
intersect ¶
intersect(A, B, C, D)
Return True if segments AB and CD intersect.
Args: A, B, C, D (tuple[float, float]): Segment endpoints.
Returns: bool: True if the segments intersect, False otherwise.
parity_check_matrix_to_hx_hz ¶
parity_check_matrix_to_hx_hz(P)
Convert a parity check matrix into Hx and Hz components.
Args: P (np.ndarray): The parity check matrix.
Returns: tuple[np.ndarray, np.ndarray]: The Hx and Hz matrices.
remove_extra_edges ¶
remove_extra_edges(G)
Heuristically reduce node degrees to at most 4 by removing edges.
Args: G (nx.Graph): Graph modified in-place.
Returns: list[tuple]: Edges removed.
tanner_graph_to_parity_check_matrix ¶
tanner_graph_to_parity_check_matrix(G)
Reconstruct Hx and Hz parity check matrices from a Tanner graph, assuming the following node order: - First quarter: Hx check nodes - Second quarter: Hz check nodes - Third quarter: variable nodes for Hx - Fourth quarter: variable nodes for Hz
Args: G (nx.Graph): The Tanner graph.
Returns: np.ndarray : Parity check matrix; vstack of (Hx, Hz).
thickness ¶
thickness(G, ordered_edges, print_progress=True)
Partition edges into planar layers by greedy insertion order.
Args: G (nx.Graph): Original graph (nodes copied to each layer). ordered_edges (list[tuple]): Edge insertion order. print_progress (bool): Show a progress bar.
Returns: list[nx.Graph]: List of planar subgraphs (layers).