graphene 0.1.5

A general purpose, extensible Graph Theory data type and algorithm library for Rust.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108


use super::*;


///
/// A marker trait for graphs containing only unique edges.
///
/// An edge is unique if it is the only edge in the graph
/// connecting two vertices.
/// If the graph is directed then between two vertices v1 and v2
/// two edges are allowed: (v1,v2,_) and (v2,v1,_).
/// If the graph is undirected, there may only be one edge of either
/// (v1,v2,_) or (v1,v2,_).
/// Regardless of directedness, only one loop is allowed for each vertex,
/// i.e. only one (v,v,_).
///
///
///
pub trait Unique: ConstrainedGraph
	where
		<Self::VertexIter as IntoIterator>::IntoIter: ExactSizeIterator,
		<Self::EdgeIter as IntoIterator>::IntoIter: ExactSizeIterator,
{}

graph_wrapper!{
	///
	/// A graph wrapper that enforces the `Unique` constraint on any graph its given.
	///
	/// See <INSERT LINK TO `Unique`> for a complete description.
	///
	struct UniqueGraph
}
impl_constraints_for_wrapper!{UniqueGraph : Unique}

impl<G> BaseGraph for UniqueGraph<G>
	where
		G: ConstrainedGraph,
		<G as BaseGraph>::Vertex: Vertex,
		<G as BaseGraph>::Weight: Weight,
		<<G as BaseGraph>::VertexIter as IntoIterator>::IntoIter: ExactSizeIterator,
		<<G as BaseGraph>::EdgeIter as IntoIterator>::IntoIter: ExactSizeIterator,
{
	type Vertex = <G as BaseGraph>::Vertex;
	type Weight = <G as BaseGraph>::Weight;
	type VertexIter = <G as BaseGraph>::VertexIter;
	type EdgeIter = <G as BaseGraph>::EdgeIter;
	
	fn empty_graph() -> Self {
		UniqueGraph::wrap(G::empty_graph())
	}
	
	wrapped_method!{all_vertices(&self) -> Self::VertexIter}
	
	wrapped_method!{all_edges(&self) -> Self::EdgeIter}
	
	wrapped_method!{add_vertex(&mut self, v: Self::Vertex) -> Result<(), ()>}
	
	wrapped_method!{remove_vertex(&mut self, v: Self::Vertex) -> Result<(), ()>}
	
	fn add_edge(&mut self, e: BaseEdge<Self::Vertex, Self::Weight>) -> Result<(), ()> {
		// If the edge is already present in the graph (ignoring weight)
		if let Some(_) = self.all_edges().into_iter().position(
			|edge| edge.source == e.source && edge.sink == e.sink )
		{
			// Disallow the addition
			return Err(());
		}
		self.wraps.add_edge(e)
	}
	
	wrapped_method!{remove_edge(&mut self, e: BaseEdge<Self::Vertex, Self::Weight>) -> Result<(), ()>}
}

impl<G> ConstrainedGraph for UniqueGraph<G>
	where
		G: ConstrainedGraph,
		<G as BaseGraph>::Vertex: Vertex,
		<G as BaseGraph>::Weight: Weight,
		<<G as BaseGraph>::VertexIter as IntoIterator>::IntoIter: ExactSizeIterator,
		<<G as BaseGraph>::EdgeIter as IntoIterator>::IntoIter: ExactSizeIterator,
{
	fn invariant_holds(&self) -> bool {
		
		// For each vertex
		for v1 in self.all_vertices(){
			
			for v2 in self.all_vertices(){
				// Find all edges from v1 to v2
				let mut v1_to_v2 = self.all_edges().into_iter().filter(|edge|{
					edge.source == v1 && edge.sink == v2
				});
				
				// Make sure there is at most 1
				v1_to_v2.next();
				
				// If there is another one
				if let Some(_) = v1_to_v2.next(){
					// Invariant doesn't hold
					return false;
				}
			}
		}
		// Invariant holds, make sure the inner graph's invariant also holds
		self.wraps.invariant_holds()
	}
	wrapped_uncon_methods!{}
}