Repository: neo4j-labs/graph (language: rust)

Issue:
Use generic graph args for algos (see PageRank)



Discussion / hints:

Fix patch:
diff --git a/crates/algos/src/sssp.rs b/crates/algos/src/sssp.rs
index f2cda820..e002ff21 100644
--- a/crates/algos/src/sssp.rs
+++ b/crates/algos/src/sssp.rs
@@ -35,10 +35,11 @@ impl DeltaSteppingConfig {
     }
 }
 
-pub fn delta_stepping<NI: Idx>(
-    graph: &DirectedCsrGraph<NI, (), f32>,
-    config: DeltaSteppingConfig,
-) -> Vec<AtomicF32> {
+pub fn delta_stepping<NI, G>(graph: &G, config: DeltaSteppingConfig) -> Vec<AtomicF32>
+where
+    NI: Idx,
+    G: Graph<NI> + DirectedNeighborsWithValues<NI, f32> + Sync,
+{
     let start = Instant::now();
 
     let DeltaSteppingConfig { start_node, delta } = config;
@@ -100,14 +101,18 @@ pub fn delta_stepping<NI: Idx>(
     distance
 }
 
-fn process_shared_bin<'bins, NI: Idx>(
+fn process_shared_bin<'bins, NI, G>(
     bins: &'bins mut ThreadLocalBins<NI>,
     curr_bin: usize,
-    graph: &DirectedCsrGraph<NI, (), f32>,
+    graph: &G,
     (frontier, frontier_idx, frontier_len): (&[NI], &AtomicUsize, usize),
     distance: &[AtomicF32],
     delta: f32,
-) -> &'bins mut ThreadLocalBins<NI> {
+) -> &'bins mut ThreadLocalBins<NI>
+where
+    NI: Idx,
+    G: Graph<NI> + DirectedNeighborsWithValues<NI, f32> + Sync,
+{
     loop {
         let offset = frontier_idx.fetch_add(BATCH_SIZE, Ordering::AcqRel);
 
@@ -126,13 +131,17 @@ fn process_shared_bin<'bins, NI: Idx>(
     bins
 }
 
-fn process_local_bins<'bins, NI: Idx>(
+fn process_local_bins<'bins, NI, G>(
     bins: &'bins mut ThreadLocalBins<NI>,
     curr_bin: usize,
-    graph: &DirectedCsrGraph<NI, (), f32>,
+    graph: &G,
     distance: &[AtomicF32],
     delta: f32,
-) -> &'bins mut ThreadLocalBins<NI> {
+) -> &'bins mut ThreadLocalBins<NI>
+where
+    NI: Idx,
+    G: Graph<NI> + DirectedNeighborsWithValues<NI, f32> + Sync,
+{
     while curr_bin < bins.len()
         && !bins.is_empty(curr_bin)
         && bins.bin_len(curr_bin) < BIN_SIZE_THRESHOLD
@@ -158,13 +167,16 @@ fn min_non_empty_bin<NI: Idx>(local_bins: &mut ThreadLocalBins<NI>, curr_bin: us
     next_local_bin
 }
 
-fn relax_edges<NI: Idx>(
-    graph: &DirectedCsrGraph<NI, (), f32>,
+fn relax_edges<NI, G>(
+    graph: &G,
     distances: &[AtomicF32],
     local_bins: &mut ThreadLocalBins<NI>,
     node: NI,
     delta: f32,
-) {
+) where
+    NI: Idx,
+    G: Graph<NI> + DirectedNeighborsWithValues<NI, f32> + Sync,
+{
     for Target { target, value } in graph.out_neighbors_with_values(node) {
         let mut old_distance = distances[target.index()].load(Ordering::Acquire);
         let new_distance = distances[node.index()].load(Ordering::Acquire) + value;
diff --git a/crates/algos/src/triangle_count.rs b/crates/algos/src/triangle_count.rs
index 00ba8f8b..ba839191 100644
--- a/crates/algos/src/triangle_count.rs
+++ b/crates/algos/src/triangle_count.rs
@@ -8,13 +8,21 @@ use std::{sync::atomic::Ordering, time::Instant};
 
 const CHUNK_SIZE: usize = 64;
 
-pub fn relabel_graph<NI: Idx>(graph: &mut UndirectedCsrGraph<NI>) {
+pub fn relabel_graph<NI, G, EV>(graph: &mut G)
+where
+    NI: Idx,
+    G: RelabelByDegreeOp<NI, EV>,
+{
     let start = Instant::now();
     graph.to_degree_ordered();
     info!("Relabeled graph in {:?}", start.elapsed());
 }
 
-pub fn global_triangle_count<NI: Idx>(graph: &UndirectedCsrGraph<NI>) -> u64 {
+pub fn global_triangle_count<NI, G>(graph: &G) -> u64
+where
+    NI: Idx,
+    G: Graph<NI> + UndirectedNeighbors<NI> + Sync,
+{
     let start = Instant::now();
 
     let next_chunk = Atomic::new(NI::zero());
diff --git a/crates/algos/src/wcc.rs b/crates/algos/src/wcc.rs
index 6576340e..365482f5 100644
--- a/crates/algos/src/wcc.rs
+++ b/crates/algos/src/wcc.rs
@@ -96,10 +96,11 @@ pub trait Components<NI> {
 
 /// Computes Wcc by iterating all relationships in parallel and
 /// linking source and target nodes using a disjoint set struct.
-pub fn wcc_baseline<NI: Idx>(
-    graph: &DirectedCsrGraph<NI>,
-    config: WccConfig,
-) -> impl Components<NI> {
+pub fn wcc_baseline<NI, G>(graph: &G, config: WccConfig) -> impl Components<NI>
+where
+    NI: Idx,
+    G: Graph<NI> + DirectedNeighbors<NI> + Sync,
+{
     let node_count = graph.node_count().index();
     let dss = DisjointSetStruct::new(node_count);
 
@@ -119,10 +120,11 @@ pub fn wcc_baseline<NI: Idx>(
 /// Computes Wcc using the Afforest algorithm backed by a disjoint
 /// set struct. The disjoint set struct performans path compression
 /// while searching the set id for a given node.
-pub fn wcc_afforest<NI: Idx + Hash>(
-    graph: &DirectedCsrGraph<NI>,
-    config: WccConfig,
-) -> impl Components<NI> {
+pub fn wcc_afforest<NI, G>(graph: &G, config: WccConfig) -> impl Components<NI>
+where
+    NI: Idx + Hash,
+    G: Graph<NI> + DirectedDegrees<NI> + DirectedNeighbors<NI> + Sync,
+{
     let start = Instant::now();
     let comp = Afforest::new(graph.node_count().index());
     info!("Afforest creation took {:?}", start.elapsed());
@@ -135,10 +137,11 @@ pub fn wcc_afforest<NI: Idx + Hash>(
 /// Computes Wcc using the Afforest algorithm as described in the original
 /// paper (see module description). The backing union find structure can
 /// achieve better cache locality compared to the disjoint set struct variant.
-pub fn wcc_afforest_dss<NI: Idx + Hash>(
-    graph: &DirectedCsrGraph<NI>,
-    config: WccConfig,
-) -> impl Components<NI> {
+pub fn wcc_afforest_dss<NI, G>(graph: &G, config: WccConfig) -> impl Components<NI>
+where
+    NI: Idx + Hash,
+    G: Graph<NI> + DirectedDegrees<NI> + DirectedNeighbors<NI> + Sync,
+{
     let start = Instant::now();
     let dss = DisjointSetStruct::new(graph.node_count().index());
     info!("DSS creation took {:?}", start.elapsed());
@@ -148,9 +151,10 @@ pub fn wcc_afforest_dss<NI: Idx + Hash>(
     dss
 }
 
-fn wcc<NI, UF>(graph: &DirectedCsrGraph<NI>, comp: &UF, config: WccConfig)
+fn wcc<NI, G, UF>(graph: &G, comp: &UF, config: WccConfig)
 where
     NI: Idx + Hash,
+    G: Graph<NI> + DirectedDegrees<NI> + DirectedNeighbors<NI> + Sync,
     UF: UnionFind<NI> + Send + Sync,
 {
     let start = Instant::now();
@@ -175,9 +179,10 @@ where
 }
 
 // Sample a subgraph by looking at the first `NEIGHBOR_ROUNDS` many targets of each node.
-fn sample_subgraph<NI, UF>(graph: &DirectedCsrGraph<NI>, uf: &UF, config: WccConfig)
+fn sample_subgraph<NI, G, UF>(graph: &G, uf: &UF, config: WccConfig)
 where
     NI: Idx,
+    G: Graph<NI> + DirectedNeighbors<NI> + Sync,
     UF: UnionFind<NI> + Send + Sync,
 {
     (0..graph.node_count().index())
@@ -197,9 +202,10 @@ where
 // Sample a subgraph by looking at the first `NEIGHBOR_ROUNDS` many targets of each node.
 // In contrast to `sample_subgraph`, the method calls `compress` for each neighbor round.
 #[allow(dead_code)]
-fn sample_subgraph_afforest<NI>(graph: &DirectedCsrGraph<NI>, af: &Afforest<NI>, config: WccConfig)
+fn sample_subgraph_afforest<NI, G>(graph: &G, af: &Afforest<NI>, config: WccConfig)
 where
     NI: Idx,
+    G: Graph<NI> + DirectedDegrees<NI> + DirectedNeighbors<NI> + Sync,
 {
     let neighbor_rounds = config.neighbor_rounds;
     for r in 0..neighbor_rounds {
@@ -261,13 +267,10 @@ where
 }
 
 // Process the remaining edges while skipping nodes that are in the largest component.
-fn link_remaining<NI, UF>(
-    graph: &DirectedCsrGraph<NI>,
-    uf: &UF,
-    skip_component: NI,
-    config: WccConfig,
-) where
+fn link_remaining<NI, G, UF>(graph: &G, uf: &UF, skip_component: NI, config: WccConfig)
+where
     NI: Idx,
+    G: Graph<NI> + DirectedDegrees<NI> + DirectedNeighbors<NI> + Sync,
     UF: UnionFind<NI> + Send + Sync,
 {
     (0..graph.node_count().index())


Test patch: