pub use self::filter::*;
pub use self::reversed::*;
#[macro_use] mod macros;
mod dfsvisit;
mod traversal;
pub use self::dfsvisit::*;
pub use self::traversal::*;
use fixedbitset::FixedBitSet;
use std::collections::{
HashSet,
};
use std::hash::{Hash, BuildHasher};
use prelude::{Graph, Direction};
#[cfg(feature = "graphmap")]
use prelude::GraphMap;
#[cfg(feature = "stable_graph")]
use prelude::StableGraph;
use graph::{NodeIndex};
use super::{
graph,
EdgeType,
};
use graph::{
IndexType,
};
#[cfg(feature = "stable_graph")]
use stable_graph;
use graph::Frozen;
#[cfg(feature = "graphmap")]
use graphmap::{
self,
NodeTrait,
};
trait_template!{
pub trait GraphBase {
@escape [type NodeId]
@escape [type EdgeId]
@section nodelegate
type EdgeId: Copy + PartialEq;
type NodeId: Copy + PartialEq;
}
}
GraphBase!{delegate_impl []}
GraphBase!{delegate_impl [['a, G], G, &'a mut G, deref]}
pub trait GraphRef : Copy + GraphBase { }
impl<'a, G> GraphRef for &'a G where G: GraphBase { }
impl<'a, G> GraphBase for Frozen<'a, G> where G: GraphBase {
type NodeId = G::NodeId;
type EdgeId = G::EdgeId;
}
#[cfg(feature = "stable_graph")]
impl<'a, N, E: 'a, Ty, Ix> IntoNeighbors for &'a StableGraph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
type Neighbors = stable_graph::Neighbors<'a, E, Ix>;
fn neighbors(self, n: Self::NodeId) -> Self::Neighbors {
(*self).neighbors(n)
}
}
#[cfg(feature = "graphmap")]
impl<'a, N: 'a, E, Ty> IntoNeighbors for &'a GraphMap<N, E, Ty>
where N: Copy + Ord + Hash,
Ty: EdgeType,
{
type Neighbors = graphmap::Neighbors<'a, N, Ty>;
fn neighbors(self, n: Self::NodeId) -> Self::Neighbors {
self.neighbors(n)
}
}
trait_template! {
pub trait IntoNeighbors : GraphRef {
@section type
type Neighbors: Iterator<Item=Self::NodeId>;
@section self
fn neighbors(self: Self, a: Self::NodeId) -> Self::Neighbors;
}
}
IntoNeighbors!{delegate_impl []}
trait_template! {
pub trait IntoNeighborsDirected : IntoNeighbors {
@section type
type NeighborsDirected: Iterator<Item=Self::NodeId>;
@section self
fn neighbors_directed(self, n: Self::NodeId, d: Direction)
-> Self::NeighborsDirected;
}
}
impl<'a, N, E: 'a, Ty, Ix> IntoNeighbors for &'a Graph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
type Neighbors = graph::Neighbors<'a, E, Ix>;
fn neighbors(self, n: graph::NodeIndex<Ix>)
-> graph::Neighbors<'a, E, Ix>
{
Graph::neighbors(self, n)
}
}
impl<'a, N, E: 'a, Ty, Ix> IntoNeighborsDirected for &'a Graph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
type NeighborsDirected = graph::Neighbors<'a, E, Ix>;
fn neighbors_directed(self, n: graph::NodeIndex<Ix>, d: Direction)
-> graph::Neighbors<'a, E, Ix>
{
Graph::neighbors_directed(self, n, d)
}
}
#[cfg(feature = "stable_graph")]
impl<'a, N, E: 'a, Ty, Ix> IntoNeighborsDirected for &'a StableGraph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
type NeighborsDirected = stable_graph::Neighbors<'a, E, Ix>;
fn neighbors_directed(self, n: graph::NodeIndex<Ix>, d: Direction)
-> Self::NeighborsDirected
{
StableGraph::neighbors_directed(self, n, d)
}
}
#[cfg(feature = "graphmap")]
impl<'a, N: 'a, E, Ty> IntoNeighborsDirected for &'a GraphMap<N, E, Ty>
where N: Copy + Ord + Hash,
Ty: EdgeType,
{
type NeighborsDirected = graphmap::NeighborsDirected<'a, N, Ty>;
fn neighbors_directed(self, n: N, dir: Direction)
-> Self::NeighborsDirected
{
self.neighbors_directed(n, dir)
}
}
trait_template! {
pub trait IntoEdges : IntoEdgeReferences + IntoNeighbors {
@section type
type Edges: Iterator<Item=Self::EdgeRef>;
@section self
fn edges(self, a: Self::NodeId) -> Self::Edges;
}
}
IntoEdges!{delegate_impl []}
trait_template! {
pub trait IntoEdgesDirected : IntoEdges + IntoNeighborsDirected {
@section type
type EdgesDirected: Iterator<Item=Self::EdgeRef>;
@section self
fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected;
}
}
IntoEdgesDirected!{delegate_impl []}
trait_template! {
pub trait IntoNodeIdentifiers : GraphRef {
@section type
type NodeIdentifiers: Iterator<Item=Self::NodeId>;
@section self
fn node_identifiers(self) -> Self::NodeIdentifiers;
}
}
IntoNodeIdentifiers!{delegate_impl []}
impl<'a, N, E: 'a, Ty, Ix> IntoNodeIdentifiers for &'a Graph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
type NodeIdentifiers = graph::NodeIndices<Ix>;
fn node_identifiers(self) -> graph::NodeIndices<Ix> {
Graph::node_indices(self)
}
}
impl<N, E, Ty, Ix> NodeCount for Graph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
fn node_count(&self) -> usize {
self.node_count()
}
}
#[cfg(feature = "stable_graph")]
impl<'a, N, E: 'a, Ty, Ix> IntoNodeIdentifiers for &'a StableGraph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
type NodeIdentifiers = stable_graph::NodeIndices<'a, N, Ix>;
fn node_identifiers(self) -> Self::NodeIdentifiers {
StableGraph::node_indices(self)
}
}
#[cfg(feature = "stable_graph")]
impl<N, E, Ty, Ix> NodeCount for StableGraph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
fn node_count(&self) -> usize {
self.node_count()
}
}
IntoNeighborsDirected!{delegate_impl []}
trait_template! {
pub trait Data : GraphBase {
@section type
type NodeWeight;
type EdgeWeight;
}
}
Data!{delegate_impl []}
Data!{delegate_impl [['a, G], G, &'a mut G, deref]}
pub trait EdgeRef : Copy {
type NodeId;
type EdgeId;
type Weight;
fn source(&self) -> Self::NodeId;
fn target(&self) -> Self::NodeId;
fn weight(&self) -> &Self::Weight;
fn id(&self) -> Self::EdgeId;
}
impl<'a, N, E> EdgeRef for (N, N, &'a E)
where N: Copy
{
type NodeId = N;
type EdgeId = (N, N);
type Weight = E;
fn source(&self) -> N { self.0 }
fn target(&self) -> N { self.1 }
fn weight(&self) -> &E { self.2 }
fn id(&self) -> (N, N) { (self.0, self.1) }
}
pub trait NodeRef : Copy {
type NodeId;
type Weight;
fn id(&self) -> Self::NodeId;
fn weight(&self) -> &Self::Weight;
}
trait_template! {
pub trait IntoNodeReferences : Data + IntoNodeIdentifiers {
@section type
type NodeRef: NodeRef<NodeId=Self::NodeId, Weight=Self::NodeWeight>;
type NodeReferences: Iterator<Item=Self::NodeRef>;
@section self
fn node_references(self) -> Self::NodeReferences;
}
}
IntoNodeReferences!{delegate_impl []}
impl<Id> NodeRef for (Id, ())
where Id: Copy,
{
type NodeId = Id;
type Weight = ();
fn id(&self) -> Self::NodeId { self.0 }
fn weight(&self) -> &Self::Weight {
static DUMMY: () = ();
&DUMMY
}
}
impl<'a, Id, W> NodeRef for (Id, &'a W)
where Id: Copy,
{
type NodeId = Id;
type Weight = W;
fn id(&self) -> Self::NodeId { self.0 }
fn weight(&self) -> &Self::Weight { self.1 }
}
trait_template! {
pub trait IntoEdgeReferences : Data + GraphRef {
@section type
type EdgeRef: EdgeRef<NodeId=Self::NodeId, EdgeId=Self::EdgeId,
Weight=Self::EdgeWeight>;
type EdgeReferences: Iterator<Item=Self::EdgeRef>;
@section self
fn edge_references(self) -> Self::EdgeReferences;
}
}
IntoEdgeReferences!{delegate_impl [] }
#[cfg(feature = "graphmap")]
impl<N, E, Ty> Data for GraphMap<N, E, Ty>
where N: Copy + PartialEq,
Ty: EdgeType,
{
type NodeWeight = N;
type EdgeWeight = E;
}
trait_template! {
pub trait GraphProp : GraphBase {
@section type
type EdgeType: EdgeType;
@section nodelegate
fn is_directed(&self) -> bool {
<Self::EdgeType>::is_directed()
}
}
}
GraphProp!{delegate_impl []}
impl<N, E, Ty, Ix> GraphProp for Graph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
type EdgeType = Ty;
}
#[cfg(feature = "stable_graph")]
impl<N, E, Ty, Ix> GraphProp for StableGraph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
type EdgeType = Ty;
}
#[cfg(feature = "graphmap")]
impl<N, E, Ty> GraphProp for GraphMap<N, E, Ty>
where N: NodeTrait,
Ty: EdgeType,
{
type EdgeType = Ty;
}
impl<'a, N: 'a, E: 'a, Ty, Ix> IntoEdgeReferences for &'a Graph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
type EdgeRef = graph::EdgeReference<'a, E, Ix>;
type EdgeReferences = graph::EdgeReferences<'a, E, Ix>;
fn edge_references(self) -> Self::EdgeReferences {
(*self).edge_references()
}
}
trait_template!{
pub trait NodeIndexable : GraphBase {
@section self
fn node_bound(self: &Self) -> usize;
fn to_index(self: &Self, a: Self::NodeId) -> usize;
fn from_index(self: &Self, i: usize) -> Self::NodeId;
}
}
NodeIndexable!{delegate_impl []}
trait_template! {
pub trait NodeCount : GraphBase {
@section self
fn node_count(self: &Self) -> usize;
}
}
NodeCount!{delegate_impl []}
trait_template! {
pub trait NodeCompactIndexable : NodeIndexable + NodeCount { }
}
NodeCompactIndexable!{delegate_impl []}
impl<N, E, Ty, Ix> NodeIndexable for Graph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
fn node_bound(&self) -> usize { self.node_count() }
fn to_index(&self, ix: NodeIndex<Ix>) -> usize { ix.index() }
fn from_index(&self, ix: usize) -> Self::NodeId { NodeIndex::new(ix) }
}
impl<N, E, Ty, Ix> NodeCompactIndexable for Graph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{ }
pub trait VisitMap<N> {
fn visit(&mut self, a: N) -> bool;
fn is_visited(&self, a: &N) -> bool;
}
impl<Ix> VisitMap<graph::NodeIndex<Ix>> for FixedBitSet
where Ix: IndexType,
{
fn visit(&mut self, x: graph::NodeIndex<Ix>) -> bool {
!self.put(x.index())
}
fn is_visited(&self, x: &graph::NodeIndex<Ix>) -> bool {
self.contains(x.index())
}
}
impl<Ix> VisitMap<graph::EdgeIndex<Ix>> for FixedBitSet
where Ix: IndexType,
{
fn visit(&mut self, x: graph::EdgeIndex<Ix>) -> bool {
!self.put(x.index())
}
fn is_visited(&self, x: &graph::EdgeIndex<Ix>) -> bool {
self.contains(x.index())
}
}
impl<Ix> VisitMap<Ix> for FixedBitSet
where Ix: IndexType,
{
fn visit(&mut self, x: Ix) -> bool {
!self.put(x.index())
}
fn is_visited(&self, x: &Ix) -> bool {
self.contains(x.index())
}
}
impl<N, S> VisitMap<N> for HashSet<N, S>
where N: Hash + Eq,
S: BuildHasher,
{
fn visit(&mut self, x: N) -> bool {
self.insert(x)
}
fn is_visited(&self, x: &N) -> bool {
self.contains(x)
}
}
trait_template!{
pub trait Visitable : GraphBase {
@section type
type Map: VisitMap<Self::NodeId>;
@section self
fn visit_map(self: &Self) -> Self::Map;
fn reset_map(self: &Self, map: &mut Self::Map) -> ();
}
}
Visitable!{delegate_impl []}
impl<N, E, Ty, Ix> GraphBase for Graph<N, E, Ty, Ix>
where Ix: IndexType,
{
type NodeId = graph::NodeIndex<Ix>;
type EdgeId = graph::EdgeIndex<Ix>;
}
impl<N, E, Ty, Ix> Visitable for Graph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
type Map = FixedBitSet;
fn visit_map(&self) -> FixedBitSet { FixedBitSet::with_capacity(self.node_count()) }
fn reset_map(&self, map: &mut Self::Map) {
map.clear();
map.grow(self.node_count());
}
}
#[cfg(feature = "stable_graph")]
impl<N, E, Ty, Ix> GraphBase for StableGraph<N, E, Ty, Ix>
where Ix: IndexType,
{
type NodeId = graph::NodeIndex<Ix>;
type EdgeId = graph::EdgeIndex<Ix>;
}
#[cfg(feature = "stable_graph")]
impl<N, E, Ty, Ix> Visitable for StableGraph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
type Map = FixedBitSet;
fn visit_map(&self) -> FixedBitSet {
FixedBitSet::with_capacity(self.node_bound())
}
fn reset_map(&self, map: &mut Self::Map) {
map.clear();
map.grow(self.node_bound());
}
}
#[cfg(feature = "stable_graph")]
impl<N, E, Ty, Ix> Data for StableGraph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
type NodeWeight = N;
type EdgeWeight = E;
}
#[cfg(feature = "graphmap")]
impl<N, E, Ty> GraphBase for GraphMap<N, E, Ty>
where N: Copy + PartialEq,
{
type NodeId = N;
type EdgeId = (N, N);
}
#[cfg(feature = "graphmap")]
impl<N, E, Ty> Visitable for GraphMap<N, E, Ty>
where N: Copy + Ord + Hash,
Ty: EdgeType,
{
type Map = HashSet<N>;
fn visit_map(&self) -> HashSet<N> { HashSet::with_capacity(self.node_count()) }
fn reset_map(&self, map: &mut Self::Map) {
map.clear();
}
}
trait_template! {
pub trait GetAdjacencyMatrix : GraphBase {
@section type
type AdjMatrix;
@section self
fn adjacency_matrix(self: &Self) -> Self::AdjMatrix;
fn is_adjacent(self: &Self, matrix: &Self::AdjMatrix, a: Self::NodeId, b: Self::NodeId) -> bool;
}
}
GetAdjacencyMatrix!{delegate_impl []}
#[cfg(feature = "graphmap")]
impl<N, E, Ty> GetAdjacencyMatrix for GraphMap<N, E, Ty>
where N: Copy + Ord + Hash,
Ty: EdgeType,
{
type AdjMatrix = ();
#[inline]
fn adjacency_matrix(&self) { }
#[inline]
fn is_adjacent(&self, _: &(), a: N, b: N) -> bool {
self.contains_edge(a, b)
}
}
mod filter;
mod reversed;