use fixedbitset::FixedBitSet;
use std::collections::{
HashSet,
VecDeque,
};
use std::hash::Hash;
use super::{
graphmap,
graph,
EdgeType,
EdgeDirection,
Graph,
GraphMap,
Incoming,
Outgoing,
};
use graph::{
IndexType,
NodeIndex,
};
#[cfg(feature = "stable_graph")]
use stable_graph;
#[cfg(feature = "stable_graph")]
use stable_graph::StableGraph;
use graph::Frozen;
use graphmap::{
NodeTrait,
};
pub trait GraphBase {
type NodeId: Copy;
type EdgeId: Copy;
}
impl<'a, G> GraphBase for &'a G where G: GraphBase {
type NodeId = G::NodeId;
type EdgeId = G::EdgeId;
}
pub trait GraphRef : Copy + GraphBase { }
impl<'a, G> GraphRef for &'a G where G: GraphBase { }
impl<G: GraphBase> GraphBase for Reversed<G> {
type NodeId = G::NodeId;
type EdgeId = G::EdgeId;
}
impl<G: GraphRef> GraphRef for Reversed<G> { }
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)
}
}
impl<'a, N: 'a, E> IntoNeighbors for &'a GraphMap<N, E>
where N: Copy + Ord + Hash
{
type Neighbors = graphmap::Neighbors<'a, N>;
fn neighbors(self, n: N) -> graphmap::Neighbors<'a, N>
{
GraphMap::neighbors(self, n)
}
}
impl<'a, 'b, G> IntoNeighbors for &'b Frozen<'a, G>
where &'b G: IntoNeighbors,
G: GraphBase<NodeId=<&'b G as GraphBase>::NodeId>,
{
type Neighbors = <&'b G as IntoNeighbors>::Neighbors;
fn neighbors(self, n: G::NodeId) -> Self::Neighbors {
(**self).neighbors(n)
}
}
#[derive(Copy, Clone)]
pub struct AsUndirected<G>(pub G);
#[derive(Copy, Clone)]
pub struct Reversed<G>(pub G);
impl<'b, N, E, Ty, Ix> IntoNeighbors for AsUndirected<&'b Graph<N, E, Ty, Ix>> where
Ty: EdgeType,
Ix: IndexType,
{
type Neighbors = graph::Neighbors<'b, E, Ix>;
fn neighbors(self, n: graph::NodeIndex<Ix>) -> graph::Neighbors<'b, E, Ix>
{
Graph::neighbors_undirected(self.0, n)
}
}
pub trait IntoNeighbors : GraphRef {
type Neighbors: Iterator<Item=Self::NodeId>;
fn neighbors(self, n: Self::NodeId) -> Self::Neighbors;
}
pub trait IntoNeighborsDirected : IntoNeighbors {
type NeighborsDirected: Iterator<Item=Self::NodeId>;
fn neighbors_directed(self, n: Self::NodeId, d: EdgeDirection)
-> 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: EdgeDirection)
-> 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: EdgeDirection)
-> Self::NeighborsDirected
{
StableGraph::neighbors_directed(self, n, d)
}
}
pub trait IntoNodeIdentifiers : GraphRef {
type NodeIdentifiers: Iterator<Item=Self::NodeId>;
fn node_identifiers(self) -> Self::NodeIdentifiers;
fn node_count(&self) -> usize;
}
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)
}
fn node_count(&self) -> usize {
Graph::node_count(self)
}
}
#[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)
}
fn node_count(&self) -> usize {
StableGraph::node_count(self)
}
}
impl<'a, G> IntoNeighbors for &'a G
where G: Copy + IntoNeighbors
{
type Neighbors = G::Neighbors;
fn neighbors(self, n: G::NodeId) -> G::Neighbors {
(*self).neighbors(n)
}
}
impl<'a, G> IntoNeighborsDirected for &'a G
where G: Copy + IntoNeighborsDirected
{
type NeighborsDirected = G::NeighborsDirected;
fn neighbors_directed(self, n: G::NodeId, d: EdgeDirection)
-> G::NeighborsDirected
{
(*self).neighbors_directed(n, d)
}
}
impl<G> IntoNeighbors for Reversed<G>
where G: IntoNeighborsDirected
{
type Neighbors = G::NeighborsDirected;
fn neighbors(self, n: G::NodeId) -> G::NeighborsDirected
{
self.0.neighbors_directed(n, Incoming)
}
}
impl<G> IntoNeighborsDirected for Reversed<G>
where G: IntoNeighborsDirected
{
type NeighborsDirected = G::NeighborsDirected;
fn neighbors_directed(self, n: G::NodeId, d: EdgeDirection)
-> G::NeighborsDirected
{
self.0.neighbors_directed(n, d.opposite())
}
}
pub trait IntoExternals : GraphRef {
type Externals: Iterator<Item=Self::NodeId>;
fn externals(self, d: EdgeDirection) -> Self::Externals;
}
impl<'a, N: 'a, E, Ty, Ix> IntoExternals for &'a Graph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
type Externals = graph::Externals<'a, N, Ty, Ix>;
fn externals(self, d: EdgeDirection) -> graph::Externals<'a, N, Ty, Ix> {
Graph::externals(self, d)
}
}
impl<G> IntoExternals for Reversed<G>
where G: IntoExternals,
{
type Externals = G::Externals;
fn externals(self, d: EdgeDirection) -> G::Externals {
self.0.externals(d.opposite())
}
}
pub trait GraphEdgeRef : GraphRef {
type EdgeRef: EdgeRef<NodeId=Self::NodeId, EdgeId=Self::EdgeId>;
}
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 IntoEdgeReferences : GraphEdgeRef {
type EdgeReferences: Iterator<Item=Self::EdgeRef>;
fn edge_references(self) -> Self::EdgeReferences;
}
impl<'a, N: 'a, E: 'a> GraphEdgeRef for &'a GraphMap<N, E>
where N: Copy
{
type EdgeRef = (N, N, &'a E);
}
impl<'a, N: 'a, E: 'a> IntoEdgeReferences for &'a GraphMap<N, E>
where N: NodeTrait
{
type EdgeReferences = graphmap::AllEdges<'a, N, E>;
fn edge_references(self) -> Self::EdgeReferences {
self.all_edges()
}
}
impl<'a, N: 'a, E: 'a, Ty, Ix> GraphEdgeRef for &'a Graph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
type EdgeRef = graph::EdgeReference<'a, E, Ix>;
}
impl<'a, N: 'a, E: 'a, Ty, Ix> IntoEdgeReferences for &'a Graph<N, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
type EdgeReferences = graph::EdgeReferences<'a, E, Ix>;
fn edge_references(self) -> Self::EdgeReferences {
(*self).edge_references()
}
}
pub trait NodeIndexable : GraphBase {
fn node_bound(&self) -> usize;
fn to_index(Self::NodeId) -> usize;
}
pub trait NodeCompactIndexable : NodeIndexable { }
impl<'a, G> NodeIndexable for &'a G
where G: NodeIndexable
{
fn node_bound(&self) -> usize { (**self).node_bound() }
fn to_index(ix: Self::NodeId) -> usize { G::to_index(ix) }
}
impl<'a, G> NodeCompactIndexable for &'a G
where G: NodeCompactIndexable
{ }
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(ix: NodeIndex<Ix>) -> usize { ix.index() }
}
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, N) -> bool;
fn is_visited(&self, &N) -> bool;
}
impl<Ix> VisitMap<graph::NodeIndex<Ix>> for FixedBitSet where
Ix: IndexType,
{
fn visit(&mut self, x: graph::NodeIndex<Ix>) -> bool {
let present = self.contains(x.index());
self.insert(x.index());
!present
}
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 {
let present = self.contains(x.index());
self.insert(x.index());
!present
}
fn is_visited(&self, x: &graph::EdgeIndex<Ix>) -> bool {
self.contains(x.index())
}
}
impl<N: Eq + Hash> VisitMap<N> for HashSet<N> {
fn visit(&mut self, x: N) -> bool {
self.insert(x)
}
fn is_visited(&self, x: &N) -> bool {
self.contains(x)
}
}
pub trait Visitable : GraphBase {
type Map: VisitMap<Self::NodeId>;
fn visit_map(&self) -> Self::Map;
fn reset_map(&self, &mut Self::Map);
}
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<'a, G> Visitable for &'a G where G: Visitable {
type Map = G::Map;
fn visit_map(&self) -> Self::Map { (**self).visit_map() }
fn reset_map(&self, map: &mut Self::Map) {
(**self).reset_map(map)
}
}
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());
}
}
impl<'a, G> Visitable for Frozen<'a, G> where G: Visitable {
type Map = G::Map;
fn visit_map(&self) -> Self::Map { (**self).visit_map() }
fn reset_map(&self, map: &mut Self::Map) {
(**self).reset_map(map)
}
}
impl<N: Copy, E> GraphBase for GraphMap<N, E>
{
type NodeId = N;
type EdgeId = (N, N);
}
impl<N, E> Visitable for GraphMap<N, E>
where N: Copy + Ord + Hash
{
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();
}
}
impl<G: GraphBase> GraphBase for AsUndirected<G>
{
type NodeId = G::NodeId;
type EdgeId = G::EdgeId;
}
impl<G: GraphRef> GraphRef for AsUndirected<G> { }
impl<G: Visitable> Visitable for AsUndirected<G>
{
type Map = G::Map;
fn visit_map(&self) -> G::Map {
self.0.visit_map()
}
fn reset_map(&self, map: &mut Self::Map) {
self.0.reset_map(map);
}
}
impl<G: Visitable> Visitable for Reversed<G>
{
type Map = G::Map;
fn visit_map(&self) -> G::Map {
self.0.visit_map()
}
fn reset_map(&self, map: &mut Self::Map) {
self.0.reset_map(map);
}
}
pub trait GetAdjacencyMatrix : GraphBase {
type AdjMatrix;
fn adjacency_matrix(&self) -> Self::AdjMatrix;
fn is_adjacent(&self, matrix: &Self::AdjMatrix, a: Self::NodeId, b: Self::NodeId) -> bool;
}
impl<N, E> GetAdjacencyMatrix for GraphMap<N, E>
where N: Copy + Ord + Hash
{
type AdjMatrix = ();
#[inline]
fn adjacency_matrix(&self) { }
#[inline]
fn is_adjacent(&self, _: &(), a: N, b: N) -> bool {
self.contains_edge(a, b)
}
}
#[derive(Clone, Debug)]
pub struct Dfs<N, VM> {
pub stack: Vec<N>,
pub discovered: VM,
}
impl<N, VM> Dfs<N, VM>
where N: Copy,
VM: VisitMap<N>,
{
pub fn new<G>(graph: G, start: N) -> Self
where G: GraphRef + Visitable<NodeId=N, Map=VM>
{
let mut dfs = Dfs::empty(graph);
dfs.move_to(start);
dfs
}
pub fn empty<G>(graph: G) -> Self
where G: GraphRef + Visitable<NodeId=N, Map=VM>
{
Dfs {
stack: Vec::new(),
discovered: graph.visit_map(),
}
}
pub fn move_to(&mut self, start: N)
{
self.discovered.visit(start.clone());
self.stack.clear();
self.stack.push(start);
}
pub fn next<G>(&mut self, graph: G) -> Option<N> where
G: IntoNeighbors<NodeId=N>,
{
while let Some(node) = self.stack.pop() {
for succ in graph.neighbors(node.clone()) {
if self.discovered.visit(succ.clone()) {
self.stack.push(succ);
}
}
return Some(node);
}
None
}
}
pub struct DfsIter<G>
where G: GraphRef + Visitable,
{
graph: G,
dfs: Dfs<G::NodeId, G::Map>,
}
impl<G> DfsIter<G>
where G: GraphRef + Visitable
{
pub fn new(graph: G, start: G::NodeId) -> Self {
DfsIter {
graph: graph,
dfs: Dfs::new(graph, start),
}
}
pub fn move_to(&mut self, start: G::NodeId) {
self.dfs.move_to(start)
}
}
impl<G> Iterator for DfsIter<G>
where G: GraphRef + Visitable + IntoNeighbors
{
type Item = G::NodeId;
#[inline]
fn next(&mut self) -> Option<G::NodeId>
{
self.dfs.next(self.graph)
}
fn size_hint(&self) -> (usize, Option<usize>)
{
(self.dfs.stack.len(), None)
}
}
impl<G> Clone for DfsIter<G>
where G: GraphRef + Visitable,
Dfs<G::NodeId, G::Map>: Clone
{
fn clone(&self) -> Self {
DfsIter {
graph: self.graph,
dfs: self.dfs.clone(),
}
}
}
#[derive(Clone)]
pub struct Bfs<N, VM> {
pub stack: VecDeque<N>,
pub discovered: VM,
}
impl<N, VM> Bfs<N, VM>
where N: Copy,
VM: VisitMap<N>,
{
pub fn new<G>(graph: G, start: N) -> Self
where G: GraphRef + Visitable<NodeId=N, Map=VM>
{
let mut discovered = graph.visit_map();
discovered.visit(start.clone());
let mut stack = VecDeque::new();
stack.push_front(start.clone());
Bfs {
stack: stack,
discovered: discovered,
}
}
pub fn next<G>(&mut self, graph: G) -> Option<N> where
G: IntoNeighbors<NodeId=N>
{
while let Some(node) = self.stack.pop_front() {
for succ in graph.neighbors(node.clone()) {
if self.discovered.visit(succ.clone()) {
self.stack.push_back(succ);
}
}
return Some(node);
}
None
}
}
pub struct BfsIter<G: Visitable> {
graph: G,
bfs: Bfs<G::NodeId, G::Map>,
}
impl<G: Visitable> BfsIter<G>
where G::NodeId: Copy,
G: GraphRef,
{
pub fn new(graph: G, start: G::NodeId) -> Self {
BfsIter {
graph: graph,
bfs: Bfs::new(graph, start),
}
}
}
impl< G: Visitable> Iterator for BfsIter<G>
where G: IntoNeighbors,
{
type Item = G::NodeId;
fn next(&mut self) -> Option<G::NodeId> {
self.bfs.next(self.graph)
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.bfs.stack.len(), None)
}
}
impl<G: Visitable> Clone for BfsIter<G>
where Bfs<G::NodeId, G::Map>: Clone,
G: GraphRef
{
fn clone(&self) -> Self {
BfsIter {
graph: self.graph,
bfs: self.bfs.clone(),
}
}
}
#[derive(Clone)]
pub struct Topo<N, VM> {
tovisit: Vec<N>,
ordered: VM,
}
impl<N, VM> Topo<N, VM>
where N: Copy,
VM: VisitMap<N>,
{
pub fn new<G>(graph: G) -> Self
where G: IntoExternals + Visitable<NodeId=N, Map=VM>,
{
let mut topo = Self::empty(graph);
topo.tovisit.extend(graph.externals(Incoming));
topo
}
fn empty<G>(graph: G) -> Self
where G: GraphRef + Visitable<NodeId=N, Map=VM>
{
Topo {
ordered: graph.visit_map(),
tovisit: Vec::new(),
}
}
pub fn reset<G>(&mut self, graph: G)
where G: IntoExternals + Visitable<NodeId=N, Map=VM>,
{
graph.reset_map(&mut self.ordered);
self.tovisit.clear();
self.tovisit.extend(graph.externals(Incoming));
}
pub fn next<G>(&mut self, g: G) -> Option<N>
where G: IntoNeighborsDirected + Visitable<NodeId=N, Map=VM>,
{
while let Some(nix) = self.tovisit.pop() {
if self.ordered.is_visited(&nix) {
continue;
}
self.ordered.visit(nix.clone());
for neigh in g.neighbors(nix) {
if Reversed(g).neighbors(neigh).all(|b| self.ordered.is_visited(&b)) {
self.tovisit.push(neigh);
}
}
return Some(nix);
}
None
}
}
#[derive(Clone)]
pub struct SubTopo<N, VM> {
tovisit: Vec<N>,
notvisited: VecDeque<N>,
ordered: VM,
discovered: VM,
}
impl<N, VM> SubTopo<N, VM>
where N: Copy,
VM: VisitMap<N>,
{
pub fn from_node<G>(graph: G, node: N) -> Self
where G: IntoExternals + Visitable<NodeId=N, Map=VM>,
{
let mut topo = Self::empty(graph);
topo.tovisit.push(node);
topo
}
fn empty<G>(graph: G) -> Self
where G: Visitable<NodeId=N, Map=VM>
{
SubTopo {
ordered: graph.visit_map(),
discovered: graph.visit_map(),
tovisit: Vec::new(),
notvisited: VecDeque::new(),
}
}
pub fn reset_with_node<G>(&mut self, graph: &G, node: N)
where G: Visitable<NodeId=N, Map=VM>,
{
graph.reset_map(&mut self.ordered);
graph.reset_map(&mut self.discovered);
self.tovisit.clear();
self.tovisit.push(node);
}
fn discover<G>(&mut self, g: G, n: N)
where G: IntoNeighborsDirected + Visitable<NodeId=N, Map=VM>,
{
if self.discovered.is_visited(&n) {
return;
}
self.discovered.visit(n.clone());
for neigh in g.neighbors_directed(n, Outgoing) {
self.discover(g, neigh);
}
}
pub fn next<G>(&mut self, g: G) -> Option<N>
where G: IntoNeighborsDirected + Visitable<NodeId=N, Map=VM>,
{
loop {
while let Some(nix) = self.tovisit.pop() {
if self.ordered.is_visited(&nix) {
continue;
}
self.ordered.visit(nix.clone());
self.discover(g, nix.clone());
for neigh in g.neighbors_directed(nix.clone(), Outgoing) {
if g.neighbors_directed(neigh.clone(), Incoming)
.filter(|b| self.discovered.is_visited(b))
.all(|b| self.ordered.is_visited(&b))
{
self.tovisit.push(neigh);
} else {
self.notvisited.push_back(neigh);
}
}
return Some(nix);
}
if let Some(nix) = self.notvisited.pop_front() {
self.tovisit.push(nix);
} else {
return None;
}
}
}
}