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