| |
| //! **petgraph** is a graph data structure library. |
| //! |
| //! - [`Graph`](./graph/struct.Graph.html) which is an adjacency list graph with |
| //! arbitrary associated data. |
| //! |
| //! - [`StableGraph`](./stable_graph/struct.StableGraph.html) is similar |
| //! to `Graph`, but it keeps indices stable across removals. |
| //! |
| //! - [`GraphMap`](./graphmap/struct.GraphMap.html) is an adjacency list graph |
| //! which is backed by a hash table and the node identifiers are the keys |
| //! into the table. |
| //! |
| //! - [`MatrixGraph`](./matrix_graph/struct.MatrixGraph.html) is an adjacency matrix graph. |
| //! |
| //! - [`CSR`](./csr/struct.Csr.html) is a sparse adjacency matrix graph with |
| //! arbitrary associated data. |
| //! |
| //! Optional crate feature: `"serde-1"`, see the Readme for more information. |
| //! |
| #![doc(html_root_url = "https://docs.rs/petgraph/0.4/")] |
| |
| extern crate fixedbitset; |
| #[cfg(feature = "graphmap")] |
| extern crate indexmap; |
| |
| #[cfg(feature = "serde-1")] |
| extern crate serde; |
| #[cfg(feature = "serde-1")] |
| #[macro_use] |
| extern crate serde_derive; |
| |
| #[cfg(all(feature = "serde-1", test))] |
| extern crate itertools; |
| |
| #[doc(no_inline)] |
| pub use crate::graph::Graph; |
| |
| pub use crate::Direction::{Outgoing, Incoming}; |
| |
| #[macro_use] |
| mod macros; |
| mod scored; |
| |
| // these modules define trait-implementing macros |
| #[macro_use] |
| pub mod visit; |
| #[macro_use] |
| pub mod data; |
| |
| pub mod algo; |
| #[cfg(feature = "generate")] |
| pub mod generate; |
| #[cfg(feature = "graphmap")] |
| pub mod graphmap; |
| #[cfg(feature = "matrix_graph")] |
| pub mod matrix_graph; |
| mod graph_impl; |
| pub mod dot; |
| pub mod unionfind; |
| mod dijkstra; |
| mod astar; |
| pub mod csr; |
| mod iter_format; |
| mod iter_utils; |
| mod isomorphism; |
| mod traits_graph; |
| mod util; |
| #[cfg(feature = "quickcheck")] |
| mod quickcheck; |
| #[cfg(feature = "serde-1")] |
| mod serde_utils; |
| |
| pub mod prelude; |
| |
| /// `Graph<N, E, Ty, Ix>` is a graph datastructure using an adjacency list representation. |
| pub mod graph { |
| pub use crate::graph_impl::{ |
| Edge, |
| EdgeIndex, |
| EdgeIndices, |
| EdgeReference, |
| EdgeReferences, |
| EdgeWeightsMut, |
| Edges, |
| Externals, |
| Frozen, |
| Graph, |
| Neighbors, |
| Node, |
| NodeIndex, |
| NodeIndices, |
| NodeWeightsMut, |
| NodeReferences, |
| WalkNeighbors, |
| GraphIndex, |
| IndexType, |
| edge_index, |
| node_index, |
| DefaultIx, |
| DiGraph, |
| UnGraph, |
| }; |
| } |
| |
| #[cfg(feature = "stable_graph")] |
| pub use crate::graph_impl::stable_graph; |
| |
| macro_rules! copyclone { |
| ($name:ident) => { |
| impl Clone for $name { |
| #[inline] |
| fn clone(&self) -> Self { *self } |
| } |
| } |
| } |
| |
| // Index into the NodeIndex and EdgeIndex arrays |
| /// Edge direction. |
| #[derive(Copy, Debug, PartialEq, PartialOrd, Ord, Eq, Hash)] |
| #[repr(usize)] |
| pub enum Direction { |
| /// An `Outgoing` edge is an outward edge *from* the current node. |
| Outgoing = 0, |
| /// An `Incoming` edge is an inbound edge *to* the current node. |
| Incoming = 1 |
| } |
| |
| copyclone!(Direction); |
| |
| impl Direction { |
| /// Return the opposite `Direction`. |
| #[inline] |
| pub fn opposite(&self) -> Direction { |
| match *self { |
| Outgoing => Incoming, |
| Incoming => Outgoing, |
| } |
| } |
| |
| /// Return `0` for `Outgoing` and `1` for `Incoming`. |
| #[inline] |
| pub fn index(&self) -> usize { |
| (*self as usize) & 0x1 |
| } |
| } |
| |
| #[doc(hidden)] |
| pub use crate::Direction as EdgeDirection; |
| |
| /// Marker type for a directed graph. |
| #[derive(Copy, Debug)] |
| pub enum Directed { } |
| copyclone!(Directed); |
| |
| /// Marker type for an undirected graph. |
| #[derive(Copy, Debug)] |
| pub enum Undirected { } |
| copyclone!(Undirected); |
| |
| /// A graph's edge type determines whether it has directed edges or not. |
| pub trait EdgeType { |
| fn is_directed() -> bool; |
| } |
| |
| impl EdgeType for Directed { |
| #[inline] |
| fn is_directed() -> bool { true } |
| } |
| |
| impl EdgeType for Undirected { |
| #[inline] |
| fn is_directed() -> bool { false } |
| } |
| |
| |
| /// Convert an element like `(i, j)` or `(i, j, w)` into |
| /// a triple of source, target, edge weight. |
| /// |
| /// For `Graph::from_edges` and `GraphMap::from_edges`. |
| pub trait IntoWeightedEdge<E> { |
| type NodeId; |
| fn into_weighted_edge(self) -> (Self::NodeId, Self::NodeId, E); |
| } |
| |
| impl<Ix, E> IntoWeightedEdge<E> for (Ix, Ix) |
| where E: Default |
| { |
| type NodeId = Ix; |
| |
| fn into_weighted_edge(self) -> (Ix, Ix, E) { |
| let (s, t) = self; |
| (s, t, E::default()) |
| } |
| } |
| |
| impl<Ix, E> IntoWeightedEdge<E> for (Ix, Ix, E) |
| { |
| type NodeId = Ix; |
| fn into_weighted_edge(self) -> (Ix, Ix, E) { |
| self |
| } |
| } |
| |
| impl<'a, Ix, E> IntoWeightedEdge<E> for (Ix, Ix, &'a E) |
| where E: Clone |
| { |
| type NodeId = Ix; |
| fn into_weighted_edge(self) -> (Ix, Ix, E) { |
| let (a, b, c) = self; |
| (a, b, c.clone()) |
| } |
| } |
| |
| impl<'a, Ix, E> IntoWeightedEdge<E> for &'a (Ix, Ix) |
| where Ix: Copy, E: Default |
| { |
| type NodeId = Ix; |
| fn into_weighted_edge(self) -> (Ix, Ix, E) { |
| let (s, t) = *self; |
| (s, t, E::default()) |
| } |
| } |
| |
| impl<'a, Ix, E> IntoWeightedEdge<E> for &'a (Ix, Ix, E) |
| where Ix: Copy, E: Clone |
| { |
| type NodeId = Ix; |
| fn into_weighted_edge(self) -> (Ix, Ix, E) { |
| self.clone() |
| } |
| } |