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](./doc/petgraph/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`](./petgraph/enum.Directed.html) or 78 //! [`Undirected`](./petgraph/enum.Unirected.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`` 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 algo; 137 mod astar; 138 pub mod csr; 139 mod dijkstra; 140 pub mod dot; 141 #[cfg(feature = "generate")] 142 pub mod generate; 143 mod graph_impl; 144 #[cfg(feature = "graphmap")] 145 pub mod graphmap; 146 mod isomorphism; 147 mod iter_format; 148 mod iter_utils; 149 #[cfg(feature = "matrix_graph")] 150 pub mod matrix_graph; 151 #[cfg(feature = "quickcheck")] 152 mod quickcheck; 153 #[cfg(feature = "serde-1")] 154 mod serde_utils; 155 mod simple_paths; 156 mod traits_graph; 157 pub mod unionfind; 158 mod util; 159 160 pub mod prelude; 161 162 /// `Graph<N, E, Ty, Ix>` is a graph datastructure using an adjacency list representation. 163 pub mod graph { 164 pub use crate::graph_impl::{ 165 edge_index, node_index, DefaultIx, DiGraph, Edge, EdgeIndex, EdgeIndices, EdgeReference, 166 EdgeReferences, EdgeWeightsMut, Edges, EdgesConnecting, Externals, Frozen, Graph, 167 GraphIndex, IndexType, Neighbors, Node, NodeIndex, NodeIndices, NodeReferences, 168 NodeWeightsMut, UnGraph, WalkNeighbors, 169 }; 170 } 171 172 #[cfg(feature = "stable_graph")] 173 pub use crate::graph_impl::stable_graph; 174 175 macro_rules! copyclone { 176 ($name:ident) => { 177 impl Clone for $name { 178 #[inline] 179 fn clone(&self) -> Self { 180 *self 181 } 182 } 183 }; 184 } 185 186 // Index into the NodeIndex and EdgeIndex arrays 187 /// Edge direction. 188 #[derive(Copy, Debug, PartialEq, PartialOrd, Ord, Eq, Hash)] 189 #[repr(usize)] 190 pub enum Direction { 191 /// An `Outgoing` edge is an outward edge *from* the current node. 192 Outgoing = 0, 193 /// An `Incoming` edge is an inbound edge *to* the current node. 194 Incoming = 1, 195 } 196 197 copyclone!(Direction); 198 199 impl Direction { 200 /// Return the opposite `Direction`. 201 #[inline] opposite(self) -> Direction202 pub fn opposite(self) -> Direction { 203 match self { 204 Outgoing => Incoming, 205 Incoming => Outgoing, 206 } 207 } 208 209 /// Return `0` for `Outgoing` and `1` for `Incoming`. 210 #[inline] index(self) -> usize211 pub fn index(self) -> usize { 212 (self as usize) & 0x1 213 } 214 } 215 216 #[doc(hidden)] 217 pub use crate::Direction as EdgeDirection; 218 219 /// Marker type for a directed graph. 220 #[derive(Copy, Debug)] 221 pub enum Directed {} 222 copyclone!(Directed); 223 224 /// Marker type for an undirected graph. 225 #[derive(Copy, Debug)] 226 pub enum Undirected {} 227 copyclone!(Undirected); 228 229 /// A graph's edge type determines whether it has directed edges or not. 230 pub trait EdgeType { is_directed() -> bool231 fn is_directed() -> bool; 232 } 233 234 impl EdgeType for Directed { 235 #[inline] is_directed() -> bool236 fn is_directed() -> bool { 237 true 238 } 239 } 240 241 impl EdgeType for Undirected { 242 #[inline] is_directed() -> bool243 fn is_directed() -> bool { 244 false 245 } 246 } 247 248 /// Convert an element like `(i, j)` or `(i, j, w)` into 249 /// a triple of source, target, edge weight. 250 /// 251 /// For `Graph::from_edges` and `GraphMap::from_edges`. 252 pub trait IntoWeightedEdge<E> { 253 type NodeId; into_weighted_edge(self) -> (Self::NodeId, Self::NodeId, E)254 fn into_weighted_edge(self) -> (Self::NodeId, Self::NodeId, E); 255 } 256 257 impl<Ix, E> IntoWeightedEdge<E> for (Ix, Ix) 258 where 259 E: Default, 260 { 261 type NodeId = Ix; 262 into_weighted_edge(self) -> (Ix, Ix, E)263 fn into_weighted_edge(self) -> (Ix, Ix, E) { 264 let (s, t) = self; 265 (s, t, E::default()) 266 } 267 } 268 269 impl<Ix, E> IntoWeightedEdge<E> for (Ix, Ix, E) { 270 type NodeId = Ix; into_weighted_edge(self) -> (Ix, Ix, E)271 fn into_weighted_edge(self) -> (Ix, Ix, E) { 272 self 273 } 274 } 275 276 impl<'a, Ix, E> IntoWeightedEdge<E> for (Ix, Ix, &'a E) 277 where 278 E: Clone, 279 { 280 type NodeId = Ix; into_weighted_edge(self) -> (Ix, Ix, E)281 fn into_weighted_edge(self) -> (Ix, Ix, E) { 282 let (a, b, c) = self; 283 (a, b, c.clone()) 284 } 285 } 286 287 impl<'a, Ix, E> IntoWeightedEdge<E> for &'a (Ix, Ix) 288 where 289 Ix: Copy, 290 E: Default, 291 { 292 type NodeId = Ix; into_weighted_edge(self) -> (Ix, Ix, E)293 fn into_weighted_edge(self) -> (Ix, Ix, E) { 294 let (s, t) = *self; 295 (s, t, E::default()) 296 } 297 } 298 299 impl<'a, Ix, E> IntoWeightedEdge<E> for &'a (Ix, Ix, E) 300 where 301 Ix: Copy, 302 E: Clone, 303 { 304 type NodeId = Ix; into_weighted_edge(self) -> (Ix, Ix, E)305 fn into_weighted_edge(self) -> (Ix, Ix, E) { 306 self.clone() 307 } 308 } 309