graph_algo_ptas/generation/
planar.rs

1//! Contains an algorithm to generate planar graphs derived from [A simple linear time algorithm for
2//! embedding maximal planar graphs](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.9303&rep=rep1&type=pdf)
3//!
4//! ```rust
5//! use graph_algo_ptas::generation::planar::generate;
6//!
7//! // Generates a random graph with 10 nodes.
8//! let rg = generate(10, None).to_pet_graph();
9//! assert_eq!(rg.node_count(), 10);
10//! assert_eq!(rg.edge_count(), 3 * 10 - 6);
11//! // Generates a graph with 100 nodes the same graph is generated for every call with the same seed.
12//! let dg = generate(100, Some(44)).to_pet_graph();
13//! assert_eq!(dg.node_count(), 100);
14//! assert_eq!(dg.edge_count(), 3 * 100 - 6);
15//! ```
16
17use crate::data_structure::list_graph::ListGraph;
18use rand::rngs::StdRng;
19use rand::{seq::SliceRandom, Rng, SeedableRng};
20
21/// Returns a randomly generated Graph with degree `n`.
22/// If `seed` is not `None` the rng is seeded with the value of `seed`.
23pub fn generate(mut n: usize, seed: Option<u64>) -> ListGraph {
24    #[cfg(feature = "debug_graph_generation")]
25    let mut counter = 0;
26    let max_edges = 5 * n;
27    let mut graph = ListGraph::k4();
28    let mut urn = Vec::with_capacity(max_edges);
29    let mut active = vec![false; max_edges];
30    let mut rng = match seed {
31        Some(seed) => StdRng::seed_from_u64(seed),
32        None => StdRng::from_entropy(),
33    };
34
35    for edge in graph.edge_indexes() {
36        urn.push(edge);
37        active[edge] = true;
38    }
39
40    while n > 4 {
41        let mut edge;
42        while {
43            edge = *urn.choose(&mut rng).unwrap();
44            urn.remove(urn.iter().position(|e| &edge == e).unwrap());
45            !active[edge]
46        } {}
47        urn.push(edge);
48
49        let (v_a, v_b) = graph.edge(edge).unwrap();
50        let vertex = if rng.gen_bool(0.5) { v_a } else { v_b };
51        let typ = *if graph.edges(vertex).unwrap().len() == 3 {
52            [3, 4].choose(&mut rng)
53        } else {
54            [3, 4, 5].choose(&mut rng)
55        }
56        .unwrap();
57        if typ >= 4 {
58            let succ_edge = graph.cyclic_incident_succ(edge, vertex).unwrap();
59            graph.remove_edge(succ_edge);
60            active[succ_edge] = false;
61        }
62        if typ == 5 {
63            let succ_edge = graph.cyclic_incident_succ(edge, vertex).unwrap();
64            graph.remove_edge(succ_edge);
65            active[succ_edge] = false;
66        }
67
68        let new_vertex = graph.new_vertex();
69        let mut current_edge = edge;
70        let mut current_vertex = vertex;
71        while {
72            let new_edge = graph.add_edge(new_vertex, current_vertex, None, Some(current_edge));
73            #[cfg(feature = "debug_graph_generation")]
74            debug_graph(
75                &graph,
76                vertex,
77                current_vertex,
78                new_vertex,
79                edge,
80                current_edge,
81                new_edge,
82                &mut counter,
83            );
84            active[new_edge] = true;
85            urn.push(new_edge);
86
87            current_vertex = graph.opposite(current_vertex, current_edge).unwrap();
88            current_edge = graph
89                .cyclic_incident_prev(current_edge, current_vertex)
90                .unwrap();
91            current_vertex != vertex
92        } {}
93        n -= 1;
94    }
95
96    graph
97}
98
99#[cfg(feature = "debug_graph_generation")]
100use crate::data_structure::list_graph::{EdgeId, NodeId};
101#[cfg(feature = "debug_graph_generation")]
102#[allow(clippy::too_many_arguments)]
103fn debug_graph(
104    graph: &ListGraph,
105    vertex: NodeId,
106    current_vertex: NodeId,
107    new_vertex: EdgeId,
108    edge: EdgeId,
109    current_edge: EdgeId,
110    new_edge: EdgeId,
111    counter: &mut usize,
112) {
113    let mut node_color = std::collections::HashMap::new();
114    let mut edge_color = std::collections::HashMap::new();
115    node_color.insert(vertex, "green".to_string());
116    node_color.insert(current_vertex, "blue".to_string());
117    node_color.insert(new_vertex, "red".to_string());
118    edge_color.insert(edge, "green".to_string());
119    edge_color.insert(current_edge, "blue".to_string());
120    edge_color.insert(new_edge, "red".to_string());
121    crate::debug::list_graph::write_as_files(graph, &node_color, &edge_color, counter);
122}
123
124#[cfg(test)]
125mod tests {
126    use super::generate;
127
128    #[test]
129    fn test_graph_generation_base() {
130        let graph = generate(4, Some(0));
131
132        assert_eq!(graph.node_indexes().count(), 4);
133    }
134
135    #[test]
136    fn test_graph_generation_min() {
137        let graph = generate(5, Some(0));
138
139        assert_eq!(graph.node_indexes().count(), 5);
140    }
141
142    #[test]
143    fn test_graph_generation_small() {
144        let graph = generate(10, Some(0));
145
146        assert_eq!(graph.node_indexes().count(), 10);
147    }
148
149    #[test]
150    fn test_graph_generation_medium() {
151        let graph = generate(50, Some(0));
152
153        assert_eq!(graph.node_indexes().count(), 50);
154    }
155
156    #[test]
157    fn test_graph_generation_large() {
158        let graph = generate(100, Some(0));
159
160        assert_eq!(graph.node_indexes().count(), 100);
161    }
162}
graph_algo_ptas/generation/planar.rs

graph_algo_ptas/generation/
planar.rs
