traitgraph_algo/
predefined_graphs.rs

1use rand::seq::IteratorRandom;
2use rand::Rng;
3use traitgraph::interface::DynamicGraph;
4
5/// Adds a binary tree to the given graph.
6///
7/// The first added node is the root of the tree.
8/// A negative depth adds no nodes to the graph, a depth of 0 just the root, a depth of 1 the root an its children, and so on.
9pub fn create_binary_tree<Graph: DynamicGraph>(
10    graph: &mut Graph,
11    depth: i32,
12) -> Option<Graph::NodeIndex>
13where
14    Graph::NodeData: Default,
15    Graph::EdgeData: Default,
16{
17    if depth < 0 {
18        return None;
19    }
20
21    let root = graph.add_node(Default::default());
22    create_binary_tree_recursively(graph, depth - 1, root);
23    Some(root)
24}
25
26fn create_binary_tree_recursively<Graph: DynamicGraph>(
27    graph: &mut Graph,
28    depth: i32,
29    root: Graph::NodeIndex,
30) where
31    Graph::NodeData: Default,
32    Graph::EdgeData: Default,
33{
34    if depth < 0 {
35        return;
36    }
37
38    let l = graph.add_node(Default::default());
39    let r = graph.add_node(Default::default());
40    graph.add_edge(root, l, Default::default());
41    graph.add_edge(root, r, Default::default());
42    create_binary_tree_recursively(graph, depth - 1, l);
43    create_binary_tree_recursively(graph, depth - 1, r);
44}
45
46/// Computes the amount of edges in a graph with n nodes, given the hamiltonian edge factor c.
47pub fn compute_m_from_n_and_c(n: usize, c: f64) -> usize {
48    let node_amount_f64 = n as f64;
49    let target_edge_amount =
50        c * node_amount_f64 * (node_amount_f64.ln().max(1.0) + node_amount_f64.ln().ln().max(0.0));
51    target_edge_amount.round() as usize
52}
53
54/// Creates a random hamiltonian graph with the given amount of nodes.
55/// Assumes that the graph is empty.
56/// The amount of arcs will be `c * n * (log(n) + log(log(n)))`, where `n` is the amount of nodes.
57pub fn create_random_hamiltonian_graph<Graph: DynamicGraph, Random: Rng>(
58    graph: &mut Graph,
59    node_amount: usize,
60    c: f64,
61    random: &mut Random,
62) where
63    Graph::NodeData: Default,
64    Graph::EdgeData: Default,
65{
66    if node_amount == 0 {
67        return;
68    }
69
70    for _ in 0..node_amount {
71        graph.add_node(Default::default());
72    }
73    for (n1, n2) in graph
74        .node_indices_copied()
75        .take(graph.node_count() - 1)
76        .zip(graph.node_indices_copied().skip(1))
77    {
78        graph.add_edge(n1, n2, Default::default());
79    }
80
81    let n1 = graph.node_indices().last().unwrap();
82    let n2 = graph.node_indices().next().unwrap();
83    graph.add_edge(n1, n2, Default::default());
84
85    let target_edge_amount = compute_m_from_n_and_c(node_amount, c);
86    debug_assert!(
87        target_edge_amount >= node_amount && target_edge_amount <= node_amount * (node_amount - 1),
88        "node_amount <= target_edge_amount <= node_amount * (node_amount - 1): {} <= {} <= {} (c: {})",
89        node_amount,
90        target_edge_amount,
91        node_amount * (node_amount - 1),
92        c,
93    );
94
95    while graph.edge_count() < target_edge_amount {
96        let n1 = graph.node_indices().choose(random).unwrap();
97        let n2 = graph.node_indices().choose(random).unwrap();
98
99        if n1 != n2 && !graph.contains_edge_between(n1, n2) {
100            graph.add_edge(n1, n2, Default::default());
101        }
102    }
103}
104
105/// Creates a random graph with the given amount of nodes.
106/// Assumes that the graph is empty.
107/// The amount of arcs will be `c * n * (log(n) + log(log(n)))`, where `n` is the amount of nodes.
108pub fn create_random_graph<Graph: DynamicGraph, Random: Rng>(
109    graph: &mut Graph,
110    node_amount: usize,
111    c: f64,
112    random: &mut Random,
113) where
114    Graph::NodeData: Default,
115    Graph::EdgeData: Default,
116{
117    if node_amount == 0 {
118        return;
119    }
120
121    for _ in 0..node_amount {
122        graph.add_node(Default::default());
123    }
124
125    let target_edge_amount = compute_m_from_n_and_c(node_amount, c);
126    debug_assert!(
127        target_edge_amount >= node_amount && target_edge_amount <= node_amount * (node_amount - 1)
128    );
129
130    while graph.edge_count() < target_edge_amount {
131        let n1 = graph.node_indices().choose(random).unwrap();
132        let n2 = graph.node_indices().choose(random).unwrap();
133
134        if n1 != n2 && !graph.contains_edge_between(n1, n2) {
135            graph.add_edge(n1, n2, Default::default());
136        }
137    }
138}
139
140#[cfg(test)]
141mod tests {
142    use super::create_binary_tree;
143    use traitgraph::implementation::petgraph_impl::PetGraph;
144    use traitgraph::interface::ImmutableGraphContainer;
145
146    #[test]
147    fn test_create_binary_tree_2() {
148        let mut graph = PetGraph::<(), ()>::new();
149        create_binary_tree(&mut graph, 2);
150        debug_assert_eq!(graph.node_count(), 7);
151        debug_assert_eq!(graph.edge_count(), 6);
152    }
153}
traitgraph_algo/predefined_graphs.rs

traitgraph_algo/
predefined_graphs.rs
