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