petgraph/
lib.rs

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
20extern crate fixedbitset;
21#[cfg(feature = "graphmap")]
22extern crate ordermap;
23
24#[cfg(feature = "serde-1")]
25extern crate serde;
26#[cfg(feature = "serde-1")]
27#[macro_use]
28extern crate serde_derive;
29
30#[cfg(all(feature = "serde-1", test))]
31extern crate itertools;
32
33#[doc(no_inline)]
34pub use graph::Graph;
35
36pub use Direction::{Outgoing, Incoming};
37
38#[macro_use]
39mod macros;
40mod scored;
41
42// these modules define trait-implementing macros
43#[macro_use]
44pub mod visit;
45#[macro_use]
46pub mod data;
47
48pub mod algo;
49#[cfg(feature = "generate")]
50pub mod generate;
51#[cfg(feature = "graphmap")]
52pub mod graphmap;
53mod graph_impl;
54pub mod dot;
55pub mod unionfind;
56mod dijkstra;
57mod astar;
58pub mod csr;
59mod iter_format;
60mod iter_utils;
61mod isomorphism;
62mod traits_graph;
63mod util;
64#[cfg(feature = "quickcheck")]
65mod quickcheck;
66#[cfg(feature = "serde-1")]
67mod serde_utils;
68
69pub mod prelude;
70
71/// `Graph<N, E, Ty, Ix>` is a graph datastructure using an adjacency list representation.
72pub 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")]
102pub use graph_impl::stable_graph;
103
104macro_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)]
117pub 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
124copyclone!(Direction);
125
126impl Direction {
127    /// Return the opposite `Direction`.
128    #[inline]
129    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]
138    pub fn index(&self) -> usize {
139        (*self as usize) & 0x1
140    }
141}
142
143#[doc(hidden)]
144pub use Direction as EdgeDirection;
145
146/// Marker type for a directed graph.
147#[derive(Copy, Debug)]
148pub enum Directed { }
149copyclone!(Directed);
150
151/// Marker type for an undirected graph.
152#[derive(Copy, Debug)]
153pub enum Undirected { }
154copyclone!(Undirected);
155
156/// A graph's edge type determines whether is has directed edges or not.
157pub trait EdgeType {
158    fn is_directed() -> bool;
159}
160
161impl EdgeType for Directed {
162    #[inline]
163    fn is_directed() -> bool { true }
164}
165
166impl EdgeType for Undirected {
167    #[inline]
168    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`.
176pub trait IntoWeightedEdge<E> {
177    type NodeId;
178    fn into_weighted_edge(self) -> (Self::NodeId, Self::NodeId, E);
179}
180
181impl<Ix, E> IntoWeightedEdge<E> for (Ix, Ix)
182    where E: Default
183{
184    type NodeId = Ix;
185
186    fn into_weighted_edge(self) -> (Ix, Ix, E) {
187        let (s, t) = self;
188        (s, t, E::default())
189    }
190}
191
192impl<Ix, E> IntoWeightedEdge<E> for (Ix, Ix, E)
193{
194    type NodeId = Ix;
195    fn into_weighted_edge(self) -> (Ix, Ix, E) {
196        self
197    }
198}
199
200impl<'a, Ix, E> IntoWeightedEdge<E> for (Ix, Ix, &'a E)
201    where E: Clone
202{
203    type NodeId = Ix;
204    fn into_weighted_edge(self) -> (Ix, Ix, E) {
205        let (a, b, c) = self;
206        (a, b, c.clone())
207    }
208}
209
210impl<'a, Ix, E> IntoWeightedEdge<E> for &'a (Ix, Ix)
211    where Ix: Copy, E: Default
212{
213    type NodeId = Ix;
214    fn into_weighted_edge(self) -> (Ix, Ix, E) {
215        let (s, t) = *self;
216        (s, t, E::default())
217    }
218}
219
220impl<'a, Ix, E> IntoWeightedEdge<E> for &'a (Ix, Ix, E)
221    where Ix: Copy, E: Clone
222{
223    type NodeId = Ix;
224    fn into_weighted_edge(self) -> (Ix, Ix, E) {
225        self.clone()
226    }
227}
petgraph/lib.rs

petgraph/
lib.rs
