1 2 //! **petgraph** is a graph data structure library. 3 //! 4 //! - [`Graph`](./graph/struct.Graph.html) which is an adjacency list graph with 5 //! arbitrary associated data. 6 //! 7 //! - [`StableGraph`](./stable_graph/struct.StableGraph.html) is similar 8 //! to `Graph`, but it keeps indices stable across removals. 9 //! 10 //! - [`GraphMap`](./graphmap/struct.GraphMap.html) is an adjacency list graph 11 //! which is backed by a hash table and the node identifiers are the keys 12 //! into the table. 13 //! - [`CSR`](./csr/struct.Csr.html) is a sparse adjacency matrix graph with 14 //! arbitrary associated data. 15 //! 16 //! Optional crate feature: `"serde-1"`, see the Readme for more information. 17 //! 18 #![doc(html_root_url = "https://docs.rs/petgraph/0.4/")] 19 20 extern crate fixedbitset; 21 #[cfg(feature = "graphmap")] 22 extern crate ordermap; 23 24 #[cfg(feature = "serde-1")] 25 extern crate serde; 26 #[cfg(feature = "serde-1")] 27 #[macro_use] 28 extern crate serde_derive; 29 30 #[cfg(all(feature = "serde-1", test))] 31 extern crate itertools; 32 33 #[doc(no_inline)] 34 pub use graph::Graph; 35 36 pub use Direction::{Outgoing, Incoming}; 37 38 #[macro_use] 39 mod macros; 40 mod scored; 41 42 // these modules define trait-implementing macros 43 #[macro_use] 44 pub mod visit; 45 #[macro_use] 46 pub mod data; 47 48 pub mod algo; 49 #[cfg(feature = "generate")] 50 pub mod generate; 51 #[cfg(feature = "graphmap")] 52 pub mod graphmap; 53 mod graph_impl; 54 pub mod dot; 55 pub mod unionfind; 56 mod dijkstra; 57 mod astar; 58 pub mod csr; 59 mod iter_format; 60 mod iter_utils; 61 mod isomorphism; 62 mod traits_graph; 63 mod util; 64 #[cfg(feature = "quickcheck")] 65 mod quickcheck; 66 #[cfg(feature = "serde-1")] 67 mod serde_utils; 68 69 pub mod prelude; 70 71 /// `Graph<N, E, Ty, Ix>` is a graph datastructure using an adjacency list representation. 72 pub mod graph { 73 pub use graph_impl::{ 74 Edge, 75 EdgeIndex, 76 EdgeIndices, 77 EdgeReference, 78 EdgeReferences, 79 EdgeWeightsMut, 80 Edges, 81 Externals, 82 Frozen, 83 Graph, 84 Neighbors, 85 Node, 86 NodeIndex, 87 NodeIndices, 88 NodeWeightsMut, 89 NodeReferences, 90 WalkNeighbors, 91 GraphIndex, 92 IndexType, 93 edge_index, 94 node_index, 95 DefaultIx, 96 DiGraph, 97 UnGraph, 98 }; 99 } 100 101 #[cfg(feature = "stable_graph")] 102 pub use graph_impl::stable_graph; 103 104 macro_rules! copyclone { 105 ($name:ident) => { 106 impl Clone for $name { 107 #[inline] 108 fn clone(&self) -> Self { *self } 109 } 110 } 111 } 112 113 // Index into the NodeIndex and EdgeIndex arrays 114 /// Edge direction. 115 #[derive(Copy, Debug, PartialEq, PartialOrd, Ord, Eq, Hash)] 116 #[repr(usize)] 117 pub enum Direction { 118 /// An `Outgoing` edge is an outward edge *from* the current node. 119 Outgoing = 0, 120 /// An `Incoming` edge is an inbound edge *to* the current node. 121 Incoming = 1 122 } 123 124 copyclone!(Direction); 125 126 impl Direction { 127 /// Return the opposite `Direction`. 128 #[inline] opposite(&self) -> Direction129 pub fn opposite(&self) -> Direction { 130 match *self { 131 Outgoing => Incoming, 132 Incoming => Outgoing, 133 } 134 } 135 136 /// Return `0` for `Outgoing` and `1` for `Incoming`. 137 #[inline] index(&self) -> usize138 pub fn index(&self) -> usize { 139 (*self as usize) & 0x1 140 } 141 } 142 143 #[doc(hidden)] 144 pub use Direction as EdgeDirection; 145 146 /// Marker type for a directed graph. 147 #[derive(Copy, Debug)] 148 pub enum Directed { } 149 copyclone!(Directed); 150 151 /// Marker type for an undirected graph. 152 #[derive(Copy, Debug)] 153 pub enum Undirected { } 154 copyclone!(Undirected); 155 156 /// A graph's edge type determines whether is has directed edges or not. 157 pub trait EdgeType { is_directed() -> bool158 fn is_directed() -> bool; 159 } 160 161 impl EdgeType for Directed { 162 #[inline] is_directed() -> bool163 fn is_directed() -> bool { true } 164 } 165 166 impl EdgeType for Undirected { 167 #[inline] is_directed() -> bool168 fn is_directed() -> bool { false } 169 } 170 171 172 /// Convert an element like `(i, j)` or `(i, j, w)` into 173 /// a triple of source, target, edge weight. 174 /// 175 /// For `Graph::from_edges` and `GraphMap::from_edges`. 176 pub trait IntoWeightedEdge<E> { 177 type NodeId; into_weighted_edge(self) -> (Self::NodeId, Self::NodeId, E)178 fn into_weighted_edge(self) -> (Self::NodeId, Self::NodeId, E); 179 } 180 181 impl<Ix, E> IntoWeightedEdge<E> for (Ix, Ix) 182 where E: Default 183 { 184 type NodeId = Ix; 185 into_weighted_edge(self) -> (Ix, Ix, E)186 fn into_weighted_edge(self) -> (Ix, Ix, E) { 187 let (s, t) = self; 188 (s, t, E::default()) 189 } 190 } 191 192 impl<Ix, E> IntoWeightedEdge<E> for (Ix, Ix, E) 193 { 194 type NodeId = Ix; into_weighted_edge(self) -> (Ix, Ix, E)195 fn into_weighted_edge(self) -> (Ix, Ix, E) { 196 self 197 } 198 } 199 200 impl<'a, Ix, E> IntoWeightedEdge<E> for (Ix, Ix, &'a E) 201 where E: Clone 202 { 203 type NodeId = Ix; into_weighted_edge(self) -> (Ix, Ix, E)204 fn into_weighted_edge(self) -> (Ix, Ix, E) { 205 let (a, b, c) = self; 206 (a, b, c.clone()) 207 } 208 } 209 210 impl<'a, Ix, E> IntoWeightedEdge<E> for &'a (Ix, Ix) 211 where Ix: Copy, E: Default 212 { 213 type NodeId = Ix; into_weighted_edge(self) -> (Ix, Ix, E)214 fn into_weighted_edge(self) -> (Ix, Ix, E) { 215 let (s, t) = *self; 216 (s, t, E::default()) 217 } 218 } 219 220 impl<'a, Ix, E> IntoWeightedEdge<E> for &'a (Ix, Ix, E) 221 where Ix: Copy, E: Clone 222 { 223 type NodeId = Ix; into_weighted_edge(self) -> (Ix, Ix, E)224 fn into_weighted_edge(self) -> (Ix, Ix, E) { 225 self.clone() 226 } 227 } 228