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!{}
}