adjacency_list/sparse_nodes/
mod.rs

1use graph_types::{
2    errors::GraphError,
3    placeholder::{PlaceholderEdgeIterator, PlaceholderNodeIterator},
4    Edge, EdgeDirection, EdgeInsertID, EdgeQuery, GraphEngine, GraphKind, IndeterminateEdge, MutableGraph, NodeID,
5    NodeRangeVisitor, NodesVisitor,
6};
7use std::collections::BTreeMap;
8
9type EdgeID = u32;
10type StartNodeID = u32;
11type EndNodeID = u32;
12
13#[doc = include_str!("AdjacencyNodeList.html")]
14#[derive(Debug)]
15pub struct AdjacencyNodeList {
16    head_nodes: BTreeMap<StartNodeID, NodeNeighbors>,
17    last_edge: EdgeID,
18}
19
20#[derive(Debug)]
21struct NodeNeighbors {
22    end_nodes: BTreeMap<EdgeID, EndNodeID>,
23}
24
25impl Default for AdjacencyNodeList {
26    fn default() -> Self {
27        Self { head_nodes: BTreeMap::new(), last_edge: 0 }
28    }
29}
30
31impl<'a> GraphEngine<'a> for AdjacencyNodeList {
32    type NeighborIterator = PlaceholderNodeIterator;
33    type BridgeIterator = PlaceholderEdgeIterator;
34    type NodeTraverser = PlaceholderNodeIterator;
35    type EdgeTraverser = PlaceholderNodeIterator;
36    type BridgeTraverser = PlaceholderEdgeIterator;
37
38    fn graph_kind(&self) -> GraphKind {
39        todo!()
40    }
41
42    fn get_node(&self, node: NodeID) -> Result<NodeID, GraphError> {
43        todo!()
44    }
45
46    fn all_nodes(&self) -> Self::NodeTraverser {
47        todo!()
48    }
49
50    fn all_neighbors(&'a self, node: NodeID) -> Self::NeighborIterator {
51        todo!()
52    }
53
54    fn get_edge(&self, edge: graph_types::EdgeID) -> Result<graph_types::EdgeID, GraphError> {
55        todo!()
56    }
57
58    fn all_edges(&self) -> Self::EdgeTraverser {
59        todo!()
60    }
61
62    fn get_bridge(&self, edge: graph_types::EdgeID) -> Result<IndeterminateEdge, GraphError> {
63        todo!()
64    }
65
66    fn get_bridges(&'a self, from: NodeID, goto: NodeID) -> Self::BridgeIterator {
67        todo!()
68    }
69
70    fn all_bridges(&self) -> Self::BridgeIterator {
71        todo!()
72    }
73}
74
75impl MutableGraph for AdjacencyNodeList {
76    fn insert_node(&mut self, node_id: usize) -> bool {
77        let id = node_id as u32;
78        self.head_nodes.entry(id).or_insert_with(|| NodeNeighbors { end_nodes: BTreeMap::new() });
79        node_id < (u32::MAX as usize)
80    }
81
82    fn create_node(&mut self) -> usize {
83        todo!()
84    }
85
86    fn remove_node_with_edges(&mut self, node_id: usize) {
87        self.head_nodes.remove(&(node_id as u32));
88    }
89
90    fn insert_edge_with_nodes<E: Edge>(&mut self, edge: E) -> EdgeInsertID {
91        let lhs = edge.lhs() as u32;
92        let rhs = edge.rhs() as u32;
93        match edge.direction() {
94            EdgeDirection::Disconnect => EdgeInsertID::Nothing,
95            EdgeDirection::Forward => {
96                let e1 = self.insert_directed_edge(lhs, rhs);
97                EdgeInsertID::OneEdge(e1)
98            }
99            EdgeDirection::Reverse => {
100                let e1 = self.insert_directed_edge(rhs, lhs);
101                EdgeInsertID::OneEdge(e1)
102            }
103            EdgeDirection::TwoWay => {
104                let e1 = self.insert_directed_edge(lhs, rhs);
105                let e2 = self.insert_directed_edge(rhs, lhs);
106                EdgeInsertID::TwoEdges(e1, e2)
107            }
108            EdgeDirection::Indeterminate => {
109                todo!()
110            }
111        }
112    }
113
114    fn remove_edge<E>(&mut self, edge: E)
115    where
116        E: Into<EdgeQuery>,
117    {
118        match edge.into() {
119            EdgeQuery::EdgeID(v) => {
120                let edge_id = v as u32;
121                for (_, node) in self.head_nodes.iter_mut() {
122                    node.end_nodes.remove(&edge_id);
123                    // edge id is unique in the graph
124                    break;
125                }
126            }
127            EdgeQuery::Directed(v) => {
128                let start_node_id = v.lhs() as u32;
129                let end_node_id = v.rhs() as u32;
130                if let Some(node) = self.head_nodes.get_mut(&start_node_id) {
131                    // notice that there are multiple edges between two nodes
132                    node.end_nodes.retain(|_, &mut v| v != end_node_id);
133                }
134            }
135            EdgeQuery::Undirected(v) => {
136                panic!("remove undirected edge {v} is not supported in directed graph");
137            }
138            EdgeQuery::Dynamic(_) => {
139                todo!()
140            }
141        }
142    }
143}
144
145impl AdjacencyNodeList {
146    /// The low level interface for inserting a directed edge
147    pub(crate) fn insert_directed_edge(&mut self, from: u32, goto: u32) -> usize {
148        self.last_edge += 1;
149        let new_edge_id = self.last_edge;
150        let from_node = self.head_nodes.entry(from).or_insert_with(|| NodeNeighbors { end_nodes: BTreeMap::new() });
151        from_node.end_nodes.insert(new_edge_id, goto);
152        new_edge_id as usize
153    }
154}
adjacency_list/sparse_nodes/mod.rs

adjacency_list/sparse_nodes/
mod.rs
