petgraph_gen/
classic.rs

1use crate::common::empty_graph_with_capacity;
2use petgraph::graph::{IndexType, NodeIndex};
3use petgraph::{EdgeType, Graph};
4
5/// Generates a complete graph with `n` nodes. A complete graph is a graph where
6/// each node is connected to every other node. On a directed graph, this means
7/// that each node has `n - 1` incoming edges and `n - 1` outgoing edges.
8///
9/// # Examples
10/// ```
11/// use petgraph_gen::complete_graph;
12/// use petgraph::{Directed, Graph, Undirected};
13///
14/// let directed_graph: Graph<(), (), Directed> = complete_graph(10);
15/// assert_eq!(directed_graph.node_count(), 10);
16/// assert_eq!(directed_graph.edge_count(), 90);
17///
18/// let undirected_graph: Graph<(), (), Undirected> = complete_graph(10);
19/// assert_eq!(undirected_graph.node_count(), 10);
20/// assert_eq!(undirected_graph.edge_count(), 45);
21/// ```
22///
23pub fn complete_graph<Ty: EdgeType, Ix: IndexType>(n: usize) -> Graph<(), (), Ty, Ix> {
24    let mut graph = empty_graph_with_capacity(n, n, n * n);
25    if n <= 1 {
26        return graph;
27    }
28    for i in 0..n - 1 {
29        for j in i + 1..n {
30            graph.add_edge(NodeIndex::new(i), NodeIndex::new(j), ());
31            if Ty::is_directed() {
32                graph.add_edge(NodeIndex::new(j), NodeIndex::new(i), ());
33            }
34        }
35    }
36    graph
37}
38
39/// Generates an empty graph with `n` nodes and no edges.
40///
41/// # Examples
42/// ```
43/// use petgraph::Graph;
44/// use petgraph_gen::empty_graph;
45///
46/// let graph: Graph<(), ()> = empty_graph(5);
47/// assert_eq!(graph.node_count(), 5);
48/// assert_eq!(graph.edge_count(), 0);
49/// ```
50pub fn empty_graph<Ty: EdgeType, Ix: IndexType>(n: usize) -> Graph<(), (), Ty, Ix> {
51    empty_graph_with_capacity(n, n, 0)
52}
53
54/// Generates a star graph with a single center node connected to `n` other nodes. The resulting
55/// graph has `n + 1` nodes and `n` edges.
56///
57/// # Examples
58/// ```
59/// use petgraph_gen::star_graph;
60/// use petgraph::{Directed, Graph, Undirected};
61/// use petgraph::graph::NodeIndex;
62/// use petgraph::visit::EdgeRef;
63///
64/// let graph: Graph<(), ()> = star_graph(10);
65/// assert_eq!(graph.node_count(), 11);
66/// assert_eq!(graph.edge_count(), 10);
67/// let center_node = NodeIndex::new(0);
68/// assert_eq!(graph.edges(center_node).count(), 10);
69/// for edge in graph.edges(center_node) {
70///    assert_eq!(edge.source(), center_node);
71/// }
72///
73pub fn star_graph<Ty: EdgeType, Ix: IndexType>(n: usize) -> Graph<(), (), Ty, Ix> {
74    let mut graph = Graph::with_capacity(n + 1, n);
75    let center = graph.add_node(());
76    for _ in 0..n {
77        let node = graph.add_node(());
78        graph.add_edge(center, node, ());
79    }
80    graph
81}
82
83#[cfg(test)]
84mod tests {
85    use super::*;
86    use crate::common::assert_graph_eq;
87    use petgraph::graph::{DiGraph, UnGraph};
88
89    #[test]
90    fn test_complete_directed_graph() {
91        let graph: DiGraph<(), (), u32> = complete_graph(4);
92        let expected = Graph::from_edges(&[
93            (0, 1),
94            (1, 0),
95            (0, 2),
96            (2, 0),
97            (0, 3),
98            (3, 0),
99            (1, 2),
100            (2, 1),
101            (1, 3),
102            (3, 1),
103            (2, 3),
104            (3, 2),
105        ]);
106        assert_graph_eq(&graph, &expected);
107    }
108
109    #[test]
110    fn test_complete_undirected_graph() {
111        let graph: UnGraph<(), (), u16> = complete_graph(4);
112        let expected = Graph::from_edges(&[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]);
113        assert_graph_eq(&graph, &expected);
114    }
115}
petgraph_gen/classic.rs

petgraph_gen/
classic.rs
