1 //! `petgraph` is a graph data structure library.
2 //!
3 //! Graphs are collections of nodes, and edges between nodes. `petgraph`
4 //! provides several [graph types](index.html#graph-types) (each differing in the
5 //! tradeoffs taken in their internal representation),
6 //! [algorithms](./algo/index.html#functions) on those graphs, and functionality to
7 //! [output graphs](./dot/struct.Dot.html) in
8 //! [`graphviz`](https://www.graphviz.org/) format. Both nodes and edges
9 //! can have arbitrary associated data, and edges may be either directed or undirected.
10 //!
11 //! # Example
12 //!
13 //! ```rust
14 //! use petgraph::graph::{NodeIndex, UnGraph};
15 //! use petgraph::algo::{dijkstra, min_spanning_tree};
16 //! use petgraph::data::FromElements;
17 //! use petgraph::dot::{Dot, Config};
18 //!
19 //! // Create an undirected graph with `i32` nodes and edges with `()` associated data.
20 //! let g = UnGraph::<i32, ()>::from_edges(&[
21 //!     (1, 2), (2, 3), (3, 4),
22 //!     (1, 4)]);
23 //!
24 //! // Find the shortest path from `1` to `4` using `1` as the cost for every edge.
25 //! let node_map = dijkstra(&g, 1.into(), Some(4.into()), |_| 1);
26 //! assert_eq!(&1i32, node_map.get(&NodeIndex::new(4)).unwrap());
27 //!
28 //! // Get the minimum spanning tree of the graph as a new graph, and check that
29 //! // one edge was trimmed.
30 //! let mst = UnGraph::<_, _>::from_elements(min_spanning_tree(&g));
31 //! assert_eq!(g.raw_edges().len() - 1, mst.raw_edges().len());
32 //!
33 //! // Output the tree to `graphviz` `DOT` format
34 //! println!("{:?}", Dot::with_config(&mst, &[Config::EdgeNoLabel]));
35 //! // graph {
36 //! //     0 [label="\"0\""]
37 //! //     1 [label="\"0\""]
38 //! //     2 [label="\"0\""]
39 //! //     3 [label="\"0\""]
40 //! //     1 -- 2
41 //! //     3 -- 4
42 //! //     2 -- 3
43 //! // }
44 //! ```
45 //!
46 //! # Graph types
47 //!
48 //! * [`Graph`](./graph/struct.Graph.html) -
49 //!   An adjacency list graph with arbitrary associated data.
50 //! * [`StableGraph`](./stable_graph/struct.StableGraph.html) -
51 //!   Similar to `Graph`, but it keeps indices stable across removals.
52 //! * [`GraphMap`](./graphmap/struct.GraphMap.html) -
53 //!   An adjacency list graph backed by a hash table. The node identifiers are the keys
54 //!   into the table.
55 //! * [`MatrixGraph`](./matrix_graph/struct.MatrixGraph.html) -
56 //!   An adjacency matrix graph.
57 //! * [`CSR`](./csr/struct.Csr.html) -
58 //!   A sparse adjacency matrix graph with arbitrary associated data.
59 //!
60 //! ### Generic parameters
61 //!
62 //! Each graph type is generic over a handful of parameters. All graphs share 3 common
63 //! parameters, `N`, `E`, and `Ty`. This is a broad overview of what those are. Each
64 //! type's documentation will have finer detail on these parameters.
65 //!
66 //! `N` & `E` are called *weights* in this implementation, and are associated with
67 //! nodes and edges respectively. They can generally be of arbitrary type, and don't have to
68 //! be what you might conventionally consider weight-like. For example, using `&str` for `N`
69 //! will work. Many algorithms that require costs let you provide a cost function that
70 //! translates your `N` and `E` weights into costs appropriate to the algorithm. Some graph
71 //! types and choices do impose bounds on `N` or `E`.
72 //! [`min_spanning_tree`](./algo/fn.min_spanning_tree.html) for example requires edge weights that
73 //! implement [`PartialOrd`](https://doc.rust-lang.org/stable/core/cmp/trait.PartialOrd.html).
74 //! [`GraphMap`](./graphmap/struct.GraphMap.html) requires node weights that can serve as hash
75 //! map keys, since that graph type does not create standalone node indices.
76 //!
77 //! `Ty` controls whether edges are [`Directed`](./enum.Directed.html) or
78 //! [`Undirected`](./enum.Undirected.html).
79 //!
80 //! `Ix` appears on graph types that use indices. It is exposed so you can control
81 //! the size of node and edge indices, and therefore the memory footprint of your graphs.
82 //! Allowed values are `u8`, `u16`, `u32`, and `usize`, with `u32` being the default.
83 //!
84 //! ### Shorthand types
85 //!
86 //! Each graph type vends a few shorthand type definitions that name some specific
87 //! generic choices. For example, [`DiGraph<_, _>`](./graph/type.DiGraph.html) is shorthand
88 //! for [`Graph<_, _, Directed>`](graph/struct.Graph.html).
89 //! [`UnMatrix<_, _>`](./matrix_graph/type.UnMatrix.html) is shorthand for
90 //! [`MatrixGraph<_, _, Undirected>`](./matrix_graph/struct.MatrixGraph.html). Each graph type's
91 //! module documentation lists the available shorthand types.
92 //!
93 //! # Crate features
94 //!
95 //! * **serde-1** -
96 //!   Defaults off. Enables serialization for ``Graph, StableGraph, GraphMap`` using
97 //!   [`serde 1.0`](https://crates.io/crates/serde). May require a more recent version
98 //!   of Rust than petgraph alone.
99 //! * **graphmap** -
100 //!   Defaults on. Enables [`GraphMap`](./graphmap/struct.GraphMap.html).
101 //! * **stable_graph** -
102 //!   Defaults on. Enables [`StableGraph`](./stable_graph/struct.StableGraph.html).
103 //! * **matrix_graph** -
104 //!   Defaults on. Enables [`MatrixGraph`](./matrix_graph/struct.MatrixGraph.html).
105 //!
106 #![doc(html_root_url = "https://docs.rs/petgraph/0.4/")]
107 
108 extern crate fixedbitset;
109 #[cfg(feature = "graphmap")]
110 extern crate indexmap;
111 
112 #[cfg(feature = "serde-1")]
113 extern crate serde;
114 #[cfg(feature = "serde-1")]
115 #[macro_use]
116 extern crate serde_derive;
117 
118 #[cfg(all(feature = "serde-1", test))]
119 extern crate itertools;
120 
121 #[doc(no_inline)]
122 pub use crate::graph::Graph;
123 
124 pub use crate::Direction::{Incoming, Outgoing};
125 
126 #[macro_use]
127 mod macros;
128 mod scored;
129 
130 // these modules define trait-implementing macros
131 #[macro_use]
132 pub mod visit;
133 #[macro_use]
134 pub mod data;
135 
136 pub mod adj;
137 pub mod algo;
138 pub mod csr;
139 pub mod dot;
140 #[cfg(feature = "generate")]
141 pub mod generate;
142 mod graph_impl;
143 #[cfg(feature = "graphmap")]
144 pub mod graphmap;
145 mod iter_format;
146 mod iter_utils;
147 #[cfg(feature = "matrix_graph")]
148 pub mod matrix_graph;
149 #[cfg(feature = "quickcheck")]
150 mod quickcheck;
151 #[cfg(feature = "serde-1")]
152 mod serde_utils;
153 mod traits_graph;
154 pub mod unionfind;
155 mod util;
156 
157 pub mod operator;
158 pub mod prelude;
159 
160 /// `Graph<N, E, Ty, Ix>` is a graph datastructure using an adjacency list representation.
161 pub mod graph {
162     pub use crate::graph_impl::{
163         edge_index, node_index, DefaultIx, DiGraph, Edge, EdgeIndex, EdgeIndices, EdgeReference,
164         EdgeReferences, EdgeWeightsMut, Edges, EdgesConnecting, Externals, Frozen, Graph,
165         GraphIndex, IndexType, Neighbors, Node, NodeIndex, NodeIndices, NodeReferences,
166         NodeWeightsMut, UnGraph, WalkNeighbors,
167     };
168 }
169 
170 #[cfg(feature = "stable_graph")]
171 pub use crate::graph_impl::stable_graph;
172 
173 // Index into the NodeIndex and EdgeIndex arrays
174 /// Edge direction.
175 #[derive(Clone, Copy, Debug, PartialEq, PartialOrd, Ord, Eq, Hash)]
176 #[repr(usize)]
177 pub enum Direction {
178     /// An `Outgoing` edge is an outward edge *from* the current node.
179     Outgoing = 0,
180     /// An `Incoming` edge is an inbound edge *to* the current node.
181     Incoming = 1,
182 }
183 
184 impl Direction {
185     /// Return the opposite `Direction`.
186     #[inline]
opposite(self) -> Direction187     pub fn opposite(self) -> Direction {
188         match self {
189             Outgoing => Incoming,
190             Incoming => Outgoing,
191         }
192     }
193 
194     /// Return `0` for `Outgoing` and `1` for `Incoming`.
195     #[inline]
index(self) -> usize196     pub fn index(self) -> usize {
197         (self as usize) & 0x1
198     }
199 }
200 
201 #[doc(hidden)]
202 pub use crate::Direction as EdgeDirection;
203 
204 /// Marker type for a directed graph.
205 #[derive(Clone, Copy, Debug)]
206 pub enum Directed {}
207 
208 /// Marker type for an undirected graph.
209 #[derive(Clone, Copy, Debug)]
210 pub enum Undirected {}
211 
212 /// A graph's edge type determines whether it has directed edges or not.
213 pub trait EdgeType {
is_directed() -> bool214     fn is_directed() -> bool;
215 }
216 
217 impl EdgeType for Directed {
218     #[inline]
is_directed() -> bool219     fn is_directed() -> bool {
220         true
221     }
222 }
223 
224 impl EdgeType for Undirected {
225     #[inline]
is_directed() -> bool226     fn is_directed() -> bool {
227         false
228     }
229 }
230 
231 /// Convert an element like `(i, j)` or `(i, j, w)` into
232 /// a triple of source, target, edge weight.
233 ///
234 /// For `Graph::from_edges` and `GraphMap::from_edges`.
235 pub trait IntoWeightedEdge<E> {
236     type NodeId;
into_weighted_edge(self) -> (Self::NodeId, Self::NodeId, E)237     fn into_weighted_edge(self) -> (Self::NodeId, Self::NodeId, E);
238 }
239 
240 impl<Ix, E> IntoWeightedEdge<E> for (Ix, Ix)
241 where
242     E: Default,
243 {
244     type NodeId = Ix;
245 
into_weighted_edge(self) -> (Ix, Ix, E)246     fn into_weighted_edge(self) -> (Ix, Ix, E) {
247         let (s, t) = self;
248         (s, t, E::default())
249     }
250 }
251 
252 impl<Ix, E> IntoWeightedEdge<E> for (Ix, Ix, E) {
253     type NodeId = Ix;
into_weighted_edge(self) -> (Ix, Ix, E)254     fn into_weighted_edge(self) -> (Ix, Ix, E) {
255         self
256     }
257 }
258 
259 impl<'a, Ix, E> IntoWeightedEdge<E> for (Ix, Ix, &'a E)
260 where
261     E: Clone,
262 {
263     type NodeId = Ix;
into_weighted_edge(self) -> (Ix, Ix, E)264     fn into_weighted_edge(self) -> (Ix, Ix, E) {
265         let (a, b, c) = self;
266         (a, b, c.clone())
267     }
268 }
269 
270 impl<'a, Ix, E> IntoWeightedEdge<E> for &'a (Ix, Ix)
271 where
272     Ix: Copy,
273     E: Default,
274 {
275     type NodeId = Ix;
into_weighted_edge(self) -> (Ix, Ix, E)276     fn into_weighted_edge(self) -> (Ix, Ix, E) {
277         let (s, t) = *self;
278         (s, t, E::default())
279     }
280 }
281 
282 impl<'a, Ix, E> IntoWeightedEdge<E> for &'a (Ix, Ix, E)
283 where
284     Ix: Copy,
285     E: Clone,
286 {
287     type NodeId = Ix;
into_weighted_edge(self) -> (Ix, Ix, E)288     fn into_weighted_edge(self) -> (Ix, Ix, E) {
289         self.clone()
290     }
291 }
292