bigraph/algo/
walk_cover.rs

1use crate::algo::mark_edge_and_mirror;
2use crate::interface::static_bigraph::StaticEdgeCentricBigraph;
3use crate::interface::BidirectedData;
4use crate::traitgraph::index::GraphIndex;
5use bitvector::BitVector;
6use traitgraph::walks::VecEdgeWalk;
7
8/// Computes a set of biwalks covering the graph, without any further guarantees.
9pub fn arbitrary_biwalk_cover<
10    EdgeData: BidirectedData + Eq,
11    Graph: StaticEdgeCentricBigraph<EdgeData = EdgeData>,
12>(
13    graph: &Graph,
14) -> Vec<VecEdgeWalk<Graph>> {
15    let mut used_edges = BitVector::new(graph.edge_count());
16    let mut walks = Vec::new();
17
18    for edge_index in graph.edge_indices() {
19        if used_edges.contains(edge_index.as_usize()) {
20            continue;
21        }
22        //println!("Starting new cycle with edge {}", edge_index.as_usize());
23
24        let mut walk = Vec::new();
25
26        //println!("Start edge {}", start_edge_index.as_usize());
27        // Extend backwards first
28        mark_edge_and_mirror(&mut used_edges, graph, edge_index);
29        walk.push(edge_index);
30        let mut current_node = graph.edge_endpoints(edge_index).from_node;
31
32        let mut has_neighbor = true;
33        while has_neighbor {
34            //println!("Expanding node {}", current_node.as_usize());
35            has_neighbor = false;
36            for neighbor in graph.in_neighbors(current_node) {
37                if !used_edges.contains(neighbor.edge_id.as_usize()) {
38                    walk.push(neighbor.edge_id);
39                    mark_edge_and_mirror(&mut used_edges, graph, neighbor.edge_id);
40                    current_node = neighbor.node_id;
41                    has_neighbor = true;
42                    break;
43                }
44            }
45        }
46
47        walk.reverse();
48
49        // Extend forwards
50        has_neighbor = true;
51        current_node = graph.edge_endpoints(edge_index).to_node;
52        while has_neighbor {
53            //println!("Expanding node {}", current_node.as_usize());
54            has_neighbor = false;
55            for neighbor in graph.out_neighbors(current_node) {
56                if !used_edges.contains(neighbor.edge_id.as_usize()) {
57                    walk.push(neighbor.edge_id);
58                    mark_edge_and_mirror(&mut used_edges, graph, neighbor.edge_id);
59                    current_node = neighbor.node_id;
60                    has_neighbor = true;
61                    break;
62                }
63            }
64        }
65
66        walks.push(walk);
67    }
68
69    walks
70}
bigraph/algo/walk_cover.rs

bigraph/algo/
walk_cover.rs
