1pub use self::filter::*;
43pub use self::reversed::*;
44
45#[macro_use] mod macros;
46
47mod dfsvisit;
48mod traversal;
49pub use self::dfsvisit::*;
50pub use self::traversal::*;
51
52use fixedbitset::FixedBitSet;
53use std::collections::{
54 HashSet,
55};
56use std::hash::{Hash, BuildHasher};
57
58use prelude::{Graph, Direction};
59#[cfg(feature = "graphmap")]
60use prelude::GraphMap;
61#[cfg(feature = "stable_graph")]
62use prelude::StableGraph;
63use graph::{NodeIndex};
64use super::{
65 graph,
66 EdgeType,
67};
68
69use graph::{
70 IndexType,
71};
72#[cfg(feature = "stable_graph")]
73use stable_graph;
74use graph::Frozen;
75
76#[cfg(feature = "graphmap")]
77use graphmap::{
78 self,
79 NodeTrait,
80};
81
82trait_template!{
83pub trait GraphBase {
86 @escape [type NodeId]
88 @escape [type EdgeId]
89 @section nodelegate
90 type EdgeId: Copy + PartialEq;
92 type NodeId: Copy + PartialEq;
94}
95}
96
97GraphBase!{delegate_impl []}
98GraphBase!{delegate_impl [['a, G], G, &'a mut G, deref]}
99
100pub trait GraphRef : Copy + GraphBase { }
102
103impl<'a, G> GraphRef for &'a G where G: GraphBase { }
104
105impl<'a, G> GraphBase for Frozen<'a, G> where G: GraphBase {
106 type NodeId = G::NodeId;
107 type EdgeId = G::EdgeId;
108}
109
110#[cfg(feature = "stable_graph")]
111impl<'a, N, E: 'a, Ty, Ix> IntoNeighbors for &'a StableGraph<N, E, Ty, Ix>
112 where Ty: EdgeType,
113 Ix: IndexType,
114{
115 type Neighbors = stable_graph::Neighbors<'a, E, Ix>;
116 fn neighbors(self, n: Self::NodeId) -> Self::Neighbors {
117 (*self).neighbors(n)
118 }
119}
120
121
122#[cfg(feature = "graphmap")]
123impl<'a, N: 'a, E, Ty> IntoNeighbors for &'a GraphMap<N, E, Ty>
124 where N: Copy + Ord + Hash,
125 Ty: EdgeType,
126{
127 type Neighbors = graphmap::Neighbors<'a, N, Ty>;
128 fn neighbors(self, n: Self::NodeId) -> Self::Neighbors {
129 self.neighbors(n)
130 }
131}
132
133
134trait_template! {
135pub trait IntoNeighbors : GraphRef {
142 @section type
143 type Neighbors: Iterator<Item=Self::NodeId>;
144 @section self
145 fn neighbors(self: Self, a: Self::NodeId) -> Self::Neighbors;
147}
148}
149
150IntoNeighbors!{delegate_impl []}
151
152trait_template! {
153pub trait IntoNeighborsDirected : IntoNeighbors {
162 @section type
163 type NeighborsDirected: Iterator<Item=Self::NodeId>;
164 @section self
165 fn neighbors_directed(self, n: Self::NodeId, d: Direction)
166 -> Self::NeighborsDirected;
167}
168}
169
170impl<'a, N, E: 'a, Ty, Ix> IntoNeighbors for &'a Graph<N, E, Ty, Ix>
171 where Ty: EdgeType,
172 Ix: IndexType,
173{
174 type Neighbors = graph::Neighbors<'a, E, Ix>;
175 fn neighbors(self, n: graph::NodeIndex<Ix>)
176 -> graph::Neighbors<'a, E, Ix>
177 {
178 Graph::neighbors(self, n)
179 }
180}
181
182impl<'a, N, E: 'a, Ty, Ix> IntoNeighborsDirected for &'a Graph<N, E, Ty, Ix>
183 where Ty: EdgeType,
184 Ix: IndexType,
185{
186 type NeighborsDirected = graph::Neighbors<'a, E, Ix>;
187 fn neighbors_directed(self, n: graph::NodeIndex<Ix>, d: Direction)
188 -> graph::Neighbors<'a, E, Ix>
189 {
190 Graph::neighbors_directed(self, n, d)
191 }
192}
193
194#[cfg(feature = "stable_graph")]
195impl<'a, N, E: 'a, Ty, Ix> IntoNeighborsDirected for &'a StableGraph<N, E, Ty, Ix>
196 where Ty: EdgeType,
197 Ix: IndexType,
198{
199 type NeighborsDirected = stable_graph::Neighbors<'a, E, Ix>;
200 fn neighbors_directed(self, n: graph::NodeIndex<Ix>, d: Direction)
201 -> Self::NeighborsDirected
202 {
203 StableGraph::neighbors_directed(self, n, d)
204 }
205}
206
207#[cfg(feature = "graphmap")]
208impl<'a, N: 'a, E, Ty> IntoNeighborsDirected for &'a GraphMap<N, E, Ty>
209 where N: Copy + Ord + Hash,
210 Ty: EdgeType,
211{
212 type NeighborsDirected = graphmap::NeighborsDirected<'a, N, Ty>;
213 fn neighbors_directed(self, n: N, dir: Direction)
214 -> Self::NeighborsDirected
215 {
216 self.neighbors_directed(n, dir)
217 }
218}
219
220trait_template! {
221pub trait IntoEdges : IntoEdgeReferences + IntoNeighbors {
234 @section type
235 type Edges: Iterator<Item=Self::EdgeRef>;
236 @section self
237 fn edges(self, a: Self::NodeId) -> Self::Edges;
238}
239}
240
241IntoEdges!{delegate_impl []}
242
243trait_template! {
244pub trait IntoEdgesDirected : IntoEdges + IntoNeighborsDirected {
259 @section type
260 type EdgesDirected: Iterator<Item=Self::EdgeRef>;
261 @section self
262 fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected;
263}
264}
265
266IntoEdgesDirected!{delegate_impl []}
267
268trait_template! {
269pub trait IntoNodeIdentifiers : GraphRef {
271 @section type
272 type NodeIdentifiers: Iterator<Item=Self::NodeId>;
273 @section self
274 fn node_identifiers(self) -> Self::NodeIdentifiers;
275}
276}
277
278IntoNodeIdentifiers!{delegate_impl []}
279
280impl<'a, N, E: 'a, Ty, Ix> IntoNodeIdentifiers for &'a Graph<N, E, Ty, Ix>
281 where Ty: EdgeType,
282 Ix: IndexType,
283{
284 type NodeIdentifiers = graph::NodeIndices<Ix>;
285 fn node_identifiers(self) -> graph::NodeIndices<Ix> {
286 Graph::node_indices(self)
287 }
288}
289
290impl<N, E, Ty, Ix> NodeCount for Graph<N, E, Ty, Ix>
291 where Ty: EdgeType,
292 Ix: IndexType,
293{
294 fn node_count(&self) -> usize {
295 self.node_count()
296 }
297}
298
299#[cfg(feature = "stable_graph")]
300impl<'a, N, E: 'a, Ty, Ix> IntoNodeIdentifiers for &'a StableGraph<N, E, Ty, Ix>
301 where Ty: EdgeType,
302 Ix: IndexType,
303{
304 type NodeIdentifiers = stable_graph::NodeIndices<'a, N, Ix>;
305 fn node_identifiers(self) -> Self::NodeIdentifiers {
306 StableGraph::node_indices(self)
307 }
308}
309
310#[cfg(feature = "stable_graph")]
311impl<N, E, Ty, Ix> NodeCount for StableGraph<N, E, Ty, Ix>
312 where Ty: EdgeType,
313 Ix: IndexType,
314{
315 fn node_count(&self) -> usize {
316 self.node_count()
317 }
318}
319
320IntoNeighborsDirected!{delegate_impl []}
321
322trait_template! {
323pub trait Data : GraphBase {
325 @section type
326 type NodeWeight;
327 type EdgeWeight;
328}
329}
330
331Data!{delegate_impl []}
332Data!{delegate_impl [['a, G], G, &'a mut G, deref]}
333
334pub trait EdgeRef : Copy {
338 type NodeId;
339 type EdgeId;
340 type Weight;
341 fn source(&self) -> Self::NodeId;
343 fn target(&self) -> Self::NodeId;
345 fn weight(&self) -> &Self::Weight;
347 fn id(&self) -> Self::EdgeId;
349}
350
351impl<'a, N, E> EdgeRef for (N, N, &'a E)
352 where N: Copy
353{
354 type NodeId = N;
355 type EdgeId = (N, N);
356 type Weight = E;
357
358 fn source(&self) -> N { self.0 }
359 fn target(&self) -> N { self.1 }
360 fn weight(&self) -> &E { self.2 }
361 fn id(&self) -> (N, N) { (self.0, self.1) }
362}
363
364pub trait NodeRef : Copy {
366 type NodeId;
367 type Weight;
368 fn id(&self) -> Self::NodeId;
369 fn weight(&self) -> &Self::Weight;
370}
371
372trait_template! {
373pub trait IntoNodeReferences : Data + IntoNodeIdentifiers {
375 @section type
376 type NodeRef: NodeRef<NodeId=Self::NodeId, Weight=Self::NodeWeight>;
377 type NodeReferences: Iterator<Item=Self::NodeRef>;
378 @section self
379 fn node_references(self) -> Self::NodeReferences;
380}
381}
382
383IntoNodeReferences!{delegate_impl []}
384
385impl<Id> NodeRef for (Id, ())
386 where Id: Copy,
387{
388 type NodeId = Id;
389 type Weight = ();
390 fn id(&self) -> Self::NodeId { self.0 }
391 fn weight(&self) -> &Self::Weight {
392 static DUMMY: () = ();
393 &DUMMY
394 }
395}
396
397impl<'a, Id, W> NodeRef for (Id, &'a W)
398 where Id: Copy,
399{
400 type NodeId = Id;
401 type Weight = W;
402 fn id(&self) -> Self::NodeId { self.0 }
403 fn weight(&self) -> &Self::Weight { self.1 }
404}
405
406
407trait_template! {
408pub trait IntoEdgeReferences : Data + GraphRef {
410 @section type
411 type EdgeRef: EdgeRef<NodeId=Self::NodeId, EdgeId=Self::EdgeId,
412 Weight=Self::EdgeWeight>;
413 type EdgeReferences: Iterator<Item=Self::EdgeRef>;
414 @section self
415 fn edge_references(self) -> Self::EdgeReferences;
416}
417}
418
419IntoEdgeReferences!{delegate_impl [] }
420
421#[cfg(feature = "graphmap")]
422impl<N, E, Ty> Data for GraphMap<N, E, Ty>
423 where N: Copy + PartialEq,
424 Ty: EdgeType,
425{
426 type NodeWeight = N;
427 type EdgeWeight = E;
428}
429
430trait_template! {
431 pub trait GraphProp : GraphBase {
433 @section type
434 type EdgeType: EdgeType;
436
437 @section nodelegate
438 fn is_directed(&self) -> bool {
439 <Self::EdgeType>::is_directed()
440 }
441}
442}
443
444GraphProp!{delegate_impl []}
445
446impl<N, E, Ty, Ix> GraphProp for Graph<N, E, Ty, Ix>
447 where Ty: EdgeType,
448 Ix: IndexType,
449{
450 type EdgeType = Ty;
451}
452
453#[cfg(feature = "stable_graph")]
454impl<N, E, Ty, Ix> GraphProp for StableGraph<N, E, Ty, Ix>
455 where Ty: EdgeType,
456 Ix: IndexType,
457{
458 type EdgeType = Ty;
459}
460
461#[cfg(feature = "graphmap")]
462impl<N, E, Ty> GraphProp for GraphMap<N, E, Ty>
463 where N: NodeTrait,
464 Ty: EdgeType,
465{
466 type EdgeType = Ty;
467}
468
469
470impl<'a, N: 'a, E: 'a, Ty, Ix> IntoEdgeReferences for &'a Graph<N, E, Ty, Ix>
471 where Ty: EdgeType,
472 Ix: IndexType,
473{
474 type EdgeRef = graph::EdgeReference<'a, E, Ix>;
475 type EdgeReferences = graph::EdgeReferences<'a, E, Ix>;
476 fn edge_references(self) -> Self::EdgeReferences {
477 (*self).edge_references()
478 }
479}
480
481
482trait_template!{
483 pub trait NodeIndexable : GraphBase {
485 @section self
486 fn node_bound(self: &Self) -> usize;
489 fn to_index(self: &Self, a: Self::NodeId) -> usize;
491 fn from_index(self: &Self, i: usize) -> Self::NodeId;
493 }
494}
495
496NodeIndexable!{delegate_impl []}
497
498trait_template! {
499pub trait NodeCount : GraphBase {
501 @section self
502 fn node_count(self: &Self) -> usize;
503}
504}
505
506NodeCount!{delegate_impl []}
507
508trait_template! {
509pub trait NodeCompactIndexable : NodeIndexable + NodeCount { }
514}
515
516NodeCompactIndexable!{delegate_impl []}
517
518impl<N, E, Ty, Ix> NodeIndexable for Graph<N, E, Ty, Ix>
519 where Ty: EdgeType,
520 Ix: IndexType,
521{
522 fn node_bound(&self) -> usize { self.node_count() }
523 fn to_index(&self, ix: NodeIndex<Ix>) -> usize { ix.index() }
524 fn from_index(&self, ix: usize) -> Self::NodeId { NodeIndex::new(ix) }
525}
526
527impl<N, E, Ty, Ix> NodeCompactIndexable for Graph<N, E, Ty, Ix>
528 where Ty: EdgeType,
529 Ix: IndexType,
530{ }
531
532pub trait VisitMap<N> {
534 fn visit(&mut self, a: N) -> bool;
538
539 fn is_visited(&self, a: &N) -> bool;
541}
542
543impl<Ix> VisitMap<graph::NodeIndex<Ix>> for FixedBitSet
544 where Ix: IndexType,
545{
546 fn visit(&mut self, x: graph::NodeIndex<Ix>) -> bool {
547 !self.put(x.index())
548 }
549 fn is_visited(&self, x: &graph::NodeIndex<Ix>) -> bool {
550 self.contains(x.index())
551 }
552}
553
554impl<Ix> VisitMap<graph::EdgeIndex<Ix>> for FixedBitSet
555 where Ix: IndexType,
556{
557 fn visit(&mut self, x: graph::EdgeIndex<Ix>) -> bool {
558 !self.put(x.index())
559 }
560 fn is_visited(&self, x: &graph::EdgeIndex<Ix>) -> bool {
561 self.contains(x.index())
562 }
563}
564
565impl<Ix> VisitMap<Ix> for FixedBitSet
566 where Ix: IndexType,
567{
568 fn visit(&mut self, x: Ix) -> bool {
569 !self.put(x.index())
570 }
571 fn is_visited(&self, x: &Ix) -> bool {
572 self.contains(x.index())
573 }
574}
575
576impl<N, S> VisitMap<N> for HashSet<N, S>
577 where N: Hash + Eq,
578 S: BuildHasher,
579{
580 fn visit(&mut self, x: N) -> bool {
581 self.insert(x)
582 }
583 fn is_visited(&self, x: &N) -> bool {
584 self.contains(x)
585 }
586}
587
588trait_template!{
589pub trait Visitable : GraphBase {
591 @section type
592 type Map: VisitMap<Self::NodeId>;
594 @section self
595 fn visit_map(self: &Self) -> Self::Map;
597 fn reset_map(self: &Self, map: &mut Self::Map) -> ();
599}
600}
601Visitable!{delegate_impl []}
602
603impl<N, E, Ty, Ix> GraphBase for Graph<N, E, Ty, Ix>
604 where Ix: IndexType,
605{
606 type NodeId = graph::NodeIndex<Ix>;
607 type EdgeId = graph::EdgeIndex<Ix>;
608}
609
610impl<N, E, Ty, Ix> Visitable for Graph<N, E, Ty, Ix>
611 where Ty: EdgeType,
612 Ix: IndexType,
613{
614 type Map = FixedBitSet;
615 fn visit_map(&self) -> FixedBitSet { FixedBitSet::with_capacity(self.node_count()) }
616
617 fn reset_map(&self, map: &mut Self::Map) {
618 map.clear();
619 map.grow(self.node_count());
620 }
621}
622
623#[cfg(feature = "stable_graph")]
624impl<N, E, Ty, Ix> GraphBase for StableGraph<N, E, Ty, Ix>
625 where Ix: IndexType,
626{
627 type NodeId = graph::NodeIndex<Ix>;
628 type EdgeId = graph::EdgeIndex<Ix>;
629}
630
631#[cfg(feature = "stable_graph")]
632impl<N, E, Ty, Ix> Visitable for StableGraph<N, E, Ty, Ix>
633 where Ty: EdgeType,
634 Ix: IndexType,
635{
636 type Map = FixedBitSet;
637 fn visit_map(&self) -> FixedBitSet {
638 FixedBitSet::with_capacity(self.node_bound())
639 }
640 fn reset_map(&self, map: &mut Self::Map) {
641 map.clear();
642 map.grow(self.node_bound());
643 }
644}
645
646#[cfg(feature = "stable_graph")]
647impl<N, E, Ty, Ix> Data for StableGraph<N, E, Ty, Ix>
648 where Ty: EdgeType,
649 Ix: IndexType,
650{
651 type NodeWeight = N;
652 type EdgeWeight = E;
653}
654
655
656#[cfg(feature = "graphmap")]
657impl<N, E, Ty> GraphBase for GraphMap<N, E, Ty>
658 where N: Copy + PartialEq,
659{
660 type NodeId = N;
661 type EdgeId = (N, N);
662}
663
664#[cfg(feature = "graphmap")]
665impl<N, E, Ty> Visitable for GraphMap<N, E, Ty>
666 where N: Copy + Ord + Hash,
667 Ty: EdgeType,
668{
669 type Map = HashSet<N>;
670 fn visit_map(&self) -> HashSet<N> { HashSet::with_capacity(self.node_count()) }
671 fn reset_map(&self, map: &mut Self::Map) {
672 map.clear();
673 }
674}
675
676trait_template! {
677pub trait GetAdjacencyMatrix : GraphBase {
682 @section type
683 type AdjMatrix;
685 @section self
686 fn adjacency_matrix(self: &Self) -> Self::AdjMatrix;
688 fn is_adjacent(self: &Self, matrix: &Self::AdjMatrix, a: Self::NodeId, b: Self::NodeId) -> bool;
692}
693}
694
695
696GetAdjacencyMatrix!{delegate_impl []}
697
698#[cfg(feature = "graphmap")]
699impl<N, E, Ty> GetAdjacencyMatrix for GraphMap<N, E, Ty>
701 where N: Copy + Ord + Hash,
702 Ty: EdgeType,
703{
704 type AdjMatrix = ();
705 #[inline]
706 fn adjacency_matrix(&self) { }
707 #[inline]
708 fn is_adjacent(&self, _: &(), a: N, b: N) -> bool {
709 self.contains_edge(a, b)
710 }
711}
712
713mod filter;
714mod reversed;