fast_graph_reduce#

Fast graph reduction for degree-2 vertices.

This module provides a Cython implementation for finding chains formed by degree-2 vertices.

The logic is as follows: - Identify Potential Start Edges: For each edge (v1, v2):

If exactly one endpoint is degree-2 and the other is not degree-2, this edge can be a starting point for a chain. If this edge is not visited, start building a chain from this edge.

  • Chain Construction:

    Suppose (v1, v2) is such an edge, and v1 is degree-2, v2 is not degree-2. Mark this edge visited. Initialize chain_edges = [this_edge] and chain_vertices = [v2, v1]. Then, while the current vertex has degree-2:

    Find the other edge at current vertex (not back to prev_vertex and not visited). Mark that new edge visited, append to chain_edges, and set current_vertex to the other end of that edge.

    Once you exit, you have a maximal chain from v2 to a new non-degree-2 vertex.

cy_reduce(source, sink, idx_stack, offsets, reducer_fn, num_threads=10)#

Parallel reducer over ragged slices of arr:

Parameters:

  • source (np.ndarray) – The array to reduce.

  • idx_stack (np.ndarray) – The index stack that defines the slices.

  • offsets (np.ndarray) – The offsets that define the slices in idx_stack.

  • reducer_fn (callable) – The function to apply to each slice. Must be a numpy function that can release the GIL, e.g. np.sum, np.mean, np.max, np.min.

  • num_threads (int) – The number of threads to use for parallel reduction (in the case of standard Cython reducers).

Warning

if reduction function is sum, sink must be of type float64

Note

slice i == arr[idx_stack[offsets[i]:offsets[i+1]]]

Returns

bool

True if the reduction was successful, False if an unknown reducer function was provided.

find_degree2_branches(edges_array, end_edge_ids, vertex_degs, print_step=10)#
Find chains formed by degree-2 vertices. Returns a list of tuples:

(edge_ids_list, vertex_ids_list)

Warning

We make 3 important assumptions: - there are no pure degree2 loops in the graph (i.e. the graph is a largest component) - the vertices in the graph are monotonic with unit step (from 0) - the edge ids are reindexed prior to this function

Steps: - Compress vertex IDs and build adjacency. - Start from edges that connect a degree-2 vertex to a non-degree-2 vertex. - Follow chains from these edges.