raphtory 0.17.0

raphtory, a temporal graph library
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

//! # Single Source Shortest Path (SSSP) Algorithm
//!
//! This module provides an implementation of the Single Source Shortest Path algorithm.
//! It finds the shortest paths from a given source node to all other nodes in a graph.
use crate::{
    core::entities::{nodes::node_ref::AsNodeRef, VID},
    db::{
        api::state::{ops::Const, GenericNodeState, Index, NodeStateOutputType, TypedNodeState},
        graph::{node::NodeView, nodes::Nodes},
    },
    prelude::*,
};
use serde::{Deserialize, Serialize};
use std::{collections::HashMap, mem};

#[derive(Clone, PartialEq, Serialize, Deserialize, Debug, Default)]
pub struct PathState {
    pub path: Vec<VID>,
}

#[derive(Clone, Debug)]
pub struct TransformedPathState<'graph, G, GH = G>
where
    G: GraphViewOps<'graph>,
    GH: GraphViewOps<'graph>,
{
    pub path: Nodes<'graph, G, GH>,
}

impl PathState {
    pub fn node_transform<'graph, G>(
        state: &GenericNodeState<'graph, G>,
        value: Self,
    ) -> TransformedPathState<'graph, G>
    where
        G: GraphViewOps<'graph>,
    {
        TransformedPathState {
            path: Nodes::new_filtered(
                state.base_graph.clone(),
                state.base_graph.clone(),
                Const(true),
                Some(Index::from_iter(value.path)),
            ),
        }
    }
}

/// Calculates the single source shortest paths from a given source node.
///
/// # Arguments
///
/// - `g: &G`: A reference to the graph. Must implement `GraphViewOps`.
/// - `source: T`: The source node. Must implement `InputNode`.
/// - `cutoff: Option<usize>`: An optional cutoff level. The algorithm will stop if this level is reached.
///
/// # Returns
///
/// Returns an `AlgorithmResult<String, Vec<String>>` containing the shortest paths from the source to all reachable nodes.
///
pub fn single_source_shortest_path<'graph, G: GraphViewOps<'graph>, T: AsNodeRef>(
    g: &G,
    source: T,
    cutoff: Option<usize>,
) -> TypedNodeState<'graph, PathState, G, TransformedPathState<'graph, G>> {
    let mut paths: HashMap<VID, Vec<VID>> = HashMap::new();
    if let Some(source_node) = g.node(source) {
        let node_internal_id = source_node.node;
        let mut level = 0;
        let mut nextlevel = vec![node_internal_id];
        paths.insert(node_internal_id, vec![node_internal_id]);
        let mut thislevel = vec![];

        while !nextlevel.is_empty() {
            if Some(level) == cutoff {
                break;
            }
            mem::swap(&mut thislevel, &mut nextlevel);
            nextlevel.clear();
            for v in thislevel.iter() {
                let node = NodeView::new_internal(g, *v);
                for w in node.neighbours() {
                    if !paths.contains_key(&w.node) {
                        let mut new_path = paths.get(v).unwrap().clone();
                        new_path.push(w.node);
                        paths.insert(w.node, new_path);
                        nextlevel.push(w.node);
                    }
                }
            }
            level += 1;
        }
    }
    TypedNodeState::new_mapped(
        GenericNodeState::new_from_map(
            g.clone(),
            paths,
            |path| PathState { path },
            Some(HashMap::from([(
                "path".to_string(),
                (NodeStateOutputType::Nodes, None),
            )])),
        ),
        PathState::node_transform,
    )
}