weavatrix_graph/algo/network/
structure.rs

1use super::adjacency::{SlotAdjacency, adjacency};
2use crate::algo::traversal::Direction;
3use crate::{IndexGraphView, Vec};
4use alloc::collections::{BinaryHeap, VecDeque};
5use core::cmp::Reverse;
6
7#[must_use]
8pub fn k_core_numbers<G>(graph: &G) -> Vec<(G::Node, usize)>
9where
10    G: IndexGraphView,
11{
12    let adjacent = adjacency(graph, Direction::Both);
13    let mut degree = adjacent.neighbors.iter().map(Vec::len).collect::<Vec<_>>();
14    let mut removed = vec![false; graph.node_bound()];
15    let mut core = vec![0; graph.node_bound()];
16    let mut queue = BinaryHeap::new();
17    for &node in &adjacent.nodes {
18        let slot = G::node_slot(node);
19        queue.push(Reverse((degree[slot], slot)));
20    }
21    let mut level = 0;
22    while let Some(Reverse((candidate, slot))) = queue.pop() {
23        if removed[slot] || degree[slot] != candidate {
24            continue;
25        }
26        removed[slot] = true;
27        level = level.max(candidate);
28        core[slot] = level;
29        for &neighbor in &adjacent.neighbors[slot] {
30            if !removed[neighbor] {
31                degree[neighbor] = degree[neighbor].saturating_sub(1);
32                queue.push(Reverse((degree[neighbor], neighbor)));
33            }
34        }
35    }
36    adjacent
37        .nodes
38        .iter()
39        .copied()
40        .map(|node| (node, core[G::node_slot(node)]))
41        .collect()
42}
43
44/// Returns a deterministic fundamental cycle basis of the undirected projection.
45#[must_use]
46pub fn cycle_basis<G>(graph: &G) -> Vec<Vec<G::Node>>
47where
48    G: IndexGraphView,
49{
50    let adjacent = adjacency(graph, Direction::Both);
51    let bound = graph.node_bound();
52    let mut parent = vec![None; bound];
53    let mut depth = vec![usize::MAX; bound];
54    let mut tree_edges = Vec::new();
55    for &root_node in &adjacent.nodes {
56        let root = G::node_slot(root_node);
57        if depth[root] != usize::MAX {
58            continue;
59        }
60        depth[root] = 0;
61        let mut queue = VecDeque::from([root]);
62        while let Some(node) = queue.pop_front() {
63            for &neighbor in &adjacent.neighbors[node] {
64                if depth[neighbor] == usize::MAX {
65                    depth[neighbor] = depth[node] + 1;
66                    parent[neighbor] = Some(node);
67                    tree_edges.push(ordered_pair(node, neighbor));
68                    queue.push_back(neighbor);
69                }
70            }
71        }
72    }
73    tree_edges.sort_unstable();
74    let mut edges = Vec::new();
75    for &node in &adjacent.nodes {
76        let source = G::node_slot(node);
77        for &target in &adjacent.neighbors[source] {
78            if source < target {
79                edges.push((source, target));
80            }
81        }
82    }
83    edges.sort_unstable();
84    edges.dedup();
85    edges
86        .into_iter()
87        .filter(|edge| tree_edges.binary_search(edge).is_err())
88        .filter_map(|(source, target)| {
89            fundamental_cycle(&adjacent, source, target, &parent, &depth)
90        })
91        .collect()
92}
93
94fn fundamental_cycle<Node>(
95    adjacent: &SlotAdjacency<Node>,
96    mut left: usize,
97    mut right: usize,
98    parent: &[Option<usize>],
99    depth: &[usize],
100) -> Option<Vec<Node>>
101where
102    Node: Copy,
103{
104    let mut left_path = vec![left];
105    let mut right_path = vec![right];
106    while depth[left] > depth[right] {
107        left = parent[left]?;
108        left_path.push(left);
109    }
110    while depth[right] > depth[left] {
111        right = parent[right]?;
112        right_path.push(right);
113    }
114    while left != right {
115        left = parent[left]?;
116        right = parent[right]?;
117        left_path.push(left);
118        right_path.push(right);
119    }
120    right_path.pop();
121    left_path.extend(right_path.into_iter().rev());
122    left_path
123        .into_iter()
124        .map(|slot| adjacent.node(slot))
125        .collect()
126}
127
128const fn ordered_pair(left: usize, right: usize) -> (usize, usize) {
129    if left < right {
130        (left, right)
131    } else {
132        (right, left)
133    }
134}
weavatrix_graph/algo/network/structure.rs

weavatrix_graph/algo/network/
structure.rs
