graph_algo_ptas/utils/
convert.rs

1use arboretum_td::graph::{HashMapGraph, MutableGraph};
2use petgraph::{stable_graph::StableGraph, visit::EdgeRef, Undirected};
3
4pub type UndirectedGraph = StableGraph<(), (), Undirected>;
5
6pub fn to_hash_map_graph(petgraph: &UndirectedGraph) -> HashMapGraph {
7    let mut hash_map_graph = HashMapGraph::new();
8
9    for v in petgraph.node_indices() {
10        hash_map_graph.add_vertex(v.index());
11    }
12
13    for v in petgraph.node_indices() {
14        for e in petgraph.edges(v) {
15            hash_map_graph.add_edge(e.source().index(), e.target().index());
16        }
17    }
18
19    hash_map_graph
20}
21
22#[cfg(test)]
23mod tests {
24    use crate::utils::convert::{to_hash_map_graph, UndirectedGraph};
25    use arboretum_td::graph::BaseGraph;
26
27    #[test]
28    fn isolated() {
29        let mut petgraph = UndirectedGraph::default();
30        let u = petgraph.add_node(());
31        let v = petgraph.add_node(());
32        let w = petgraph.add_node(());
33
34        let hash_map_graph = to_hash_map_graph(&petgraph);
35        assert!(hash_map_graph.order() == petgraph.node_count());
36        assert!(hash_map_graph.has_vertex(u.index()));
37        assert!(hash_map_graph.has_vertex(v.index()));
38        assert!(hash_map_graph.has_vertex(w.index()));
39    }
40
41    #[test]
42    fn single_edge() {
43        let mut petgraph = UndirectedGraph::default();
44        let u = petgraph.add_node(());
45        let v = petgraph.add_node(());
46        petgraph.add_edge(u, v, ());
47
48        let hash_map_graph = to_hash_map_graph(&petgraph);
49        assert!(hash_map_graph.order() == petgraph.node_count());
50        assert!(hash_map_graph.has_edge(u.index(), v.index()));
51    }
52
53    #[test]
54    fn triangle() {
55        let mut petgraph = UndirectedGraph::default();
56        let u = petgraph.add_node(());
57        let v = petgraph.add_node(());
58        let w = petgraph.add_node(());
59        petgraph.add_edge(u, v, ());
60        petgraph.add_edge(v, w, ());
61        petgraph.add_edge(w, u, ());
62
63        let hash_map_graph = to_hash_map_graph(&petgraph);
64        assert!(hash_map_graph.order() == petgraph.node_count());
65        assert!(hash_map_graph.has_edge(u.index(), v.index()));
66        assert!(hash_map_graph.has_edge(v.index(), w.index()));
67        assert!(hash_map_graph.has_edge(w.index(), u.index()));
68    }
69
70    #[test]
71    fn square() {
72        let mut petgraph = UndirectedGraph::default();
73        let t = petgraph.add_node(());
74        let u = petgraph.add_node(());
75        let v = petgraph.add_node(());
76        let w = petgraph.add_node(());
77        petgraph.add_edge(t, u, ());
78        petgraph.add_edge(u, v, ());
79        petgraph.add_edge(v, w, ());
80        petgraph.add_edge(w, t, ());
81
82        let hash_map_graph = to_hash_map_graph(&petgraph);
83        assert!(hash_map_graph.order() == petgraph.node_count());
84        assert!(hash_map_graph.has_edge(t.index(), u.index()));
85        assert!(hash_map_graph.has_edge(u.index(), v.index()));
86        assert!(hash_map_graph.has_edge(v.index(), w.index()));
87        assert!(hash_map_graph.has_edge(w.index(), t.index()));
88        assert!(!hash_map_graph.has_edge(t.index(), v.index()));
89        assert!(!hash_map_graph.has_edge(u.index(), w.index()));
90    }
91}
graph_algo_ptas/utils/convert.rs

graph_algo_ptas/utils/
convert.rs
