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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
//!
//! `graphene` is a general purpose, extensible [Graph Theory](https://en.wikipedia.org/wiki/Graph_theory)
//! data type and algorithm library.
//!
//! ### Quick Examples:
//!
//! Using `common::AdjListGraph`, we define a graph with 3 vertices
//! **1** , **2** , **3** and 3 weighted edges ( **1** -(1)-> **2** -(2)-> **3** -(3)-> **1**):
//!
//! ```
//! # #![allow(unused_variables)]
//! use graphene::core::{BaseGraph, BaseEdge};
//! use graphene::common::AdjListGraph;
//!
//! // `graph()` takes a Vec of vertex values and a Vec of edges
//! // where an edge is a tuple, (v1,v2,w), of the source v1, the sink v2, and the weight w.
//! let mut g = AdjListGraph::graph(vec![1,2,3], vec![(1,2,1),(2,3,2),(3,1,3)]).unwrap();
//! //Adding a vertex
//! assert!(g.add_vertex(4).is_ok());
//! //Adding an edge
//! assert!(g.add_edge(BaseEdge::new(3,4,2)).is_ok());
//! ```
//! ---
//!
//! We can declare a different graph that does not allow edge duplicates (a unique graph) and
//! is undirected (the previous graph wasn't Unique and was directed):
//!
//! ```
//! #[macro_use]
//! extern crate graphene;
//! use graphene::core::{*,constraint::*};
//! use graphene::common::AdjListGraph;
//!
//! custom_graph!{
//! // Name of the resulting graph type
//! struct MyGraph<V,W>
//! // The BaseGraph implementation to base the new graph on.
//! as AdjListGraph<V,W>
//! // The graph wrappers that will constrain the BaseGraph implementation so that
//! // it upholds the constraint traits.
//! use UniqueGraph,UndirectedGraph
//! // The constraint traits the new graph implements
//! impl Unique,Undirected
//! // The generic bounds
//! where V: Vertex, W: Weight
//! }
//!
//! fn main(){
//! let mut g = MyGraph::graph(vec![1,2,3], vec![(1,2,1),(2,3,2),(3,1,3)]).unwrap();
//! assert_eq!(g.edges_between(1,2).len(), 2);
//!
//! // Cannot add an edge that is already there because the graph
//! // is declared as Unique, meaning no two edges may be incident
//! // on the same vertices and have the weight.
//! assert!(g.add_edge(BaseEdge::new(1,2,1)).is_err());
//! assert_eq!(g.edges_between(1,2).len(), 2);
//!
//! // When a graph is undirected, the direction of the given edge
//! // (whether 1 -> 2 or 2 -> 1) makes no difference.
//! // Since the graph is unique, adding an edge in the opposite
//! // direction as an existing edge is therefore illegal.
//! assert!(g.add_edge(BaseEdge::new(2,1,1)).is_err());
//! assert_eq!(g.edges_between(1,2).len(), 2);
//! }
//! ```
//!
//! # About
//!
//! `graphene` aims at providing general purpose traits, structs, and macros for defining
//! graphs, and functions that implement various algorithms that will run on any implementer of the library. Additionally,
//! general purpose graph implementations will be provided.
//!
//! Because of the promise of generality, `graphene` is designed in a way that will allow
//! users to implement their own graph types for their specific needs that can easily be integrated
//! with the library's algorithms. Additionally, `graphene` aims at avoiding graph type bloat,
//! i.e. defining many similar graph types:
//!
//! - `SimpleWeightedDirectedGraph`
//! - `SimpleUnweightedDirectedGraph`
//! - `SimpleWeightedUndirectedGraph`
//! - `WeightedUndirectedGraph`
//! - ...
//!
//! Instead, the user can semi-dynamically specify constraints on basic graph implementation to suit
//! his needs. More on that later.
//!
//! `graphene` will use the terminology used by
//! [Wolfram MathWorld](http://mathworld.wolfram.com/topics/GraphTheory.html)
//! where possible. More specifically, 'vertex' and 'edge' will be used. We define that
//! given a directed edge **v1** -> **v2**, then the `source` vertex is **v1** and the
//! `sink` vertex is **v2**. Likewise, the edge is *sourced* in **v1** and *sinked* (the misspelling
//! of 'sunk' is intentional) in **v2**. For both directed and undirected graphs the edge is
//! *incident* on **v1** and **v2**.
//!
//! The crate is divided in three modules:
//!
//! - `core`: Contains the general purpose traits, structs, functions, and macros for graph implementation.
//! - `algo` (**TODO**) : Contains graph algorithms that accept any graph that implements `core`.
//! - `common`: Contains general purpose and commonly used graph implementations of `core` for quick usage.
//!
//! # Vertices and Edges
//!
//! In `graphene` vertices have a value, which is use to identify each vertex. Therefore, these
//! values must be unique for every vertex in the graph. Internally, a graph implementation may
//! manage its vertices as it wishes, but it must comminicate with the outside world using the vertices'
//! values.
//!
//! Edges are identified by the tuple `(source,sink,weight)`. Edges do not have to be unique in the
//! graph, which means two edges with the same source, sink and weight are practically indistinguishable.
//! This is by design, as if the information in the tuple is not enough to distinguish two edges,
//! then choosing either one should not make a difference.
//!
//! # Directionality
//!
//! By default, edges in any graph are directed. If an undirected graph is needed, the `core`
//! provides an `Undirected` constraint trait which can be implemented for a given graph. However,
//! behind the scenes, any `Undirected` graph is a directed graph with edges in both directions.
//! Therefore, given that any BaseGraph may be `Undirected`, an additional constraint trait, `Directed`
//! is provided (**TODO**) which defines a graph as being specifically directed.
//!
//! This may seem confusing, so here is a deeper explanation:
//!
//! A BaseGraph uses directed edges. An `Undirected` BaseGraph will still use directed edges, but
//! it will treat all edges it receives from the user as undirected. This means, if the user wants
//! to add an undirected edge **1** - **2**, the graph will actually add **1** -> **2** and **1** <- **2**.
//! On the other hand, when the graph outputs edges to the user, they are given as their directed pairs,
//! e.g. **1** -> **2** and **1** <- **2** for the undirected edge **1** - **2**. This means that the
//! user must handle these two directed edges as one undirected one.
//!
//! Consider then a function which takes a BaseGraph as its input. Since the input is not bounded
//! by `Directed` it may be `Undirected`. If the function cannot handle undirected graphs
//! it will fail if given any such graph. Therefore it should bound its input with `Directed`.
//!
//! So, when to actually bound a function with `Directed` instead of just `BaseGraph`?:
//!
//! - If it cannot handle there are an edge in each directed between two vertices.
//!
//! - If it cannot handle that two edges between two vertices, one in each direction, have the same weight.
//!
//! - If it needs to keep track of specific edges. Consider an algorithm that tracks whether an edge has been used,
//! if the graph is 'Directed`, then an edge in each direction between two vertices must be tracked independently,
//! but if its `Undirected`, then a pair in each direction must be tracked as one edge.
//!
//! The formal requirements and definitions have only been presented in a way sufficient for
//! understanding the idea. Therefore, the formal definition should be consulted for complete
//! accuracy.
//!
//! ### FAQ on directionality
//!
//! - Why does an `Undirected` graph output edges in directed pairs?
//!
//! In short, to allow functions to be directionality-agnostic. Consider implementing an algorithm
//! that works on both directed and undirected graphs. If `Undirected` did not return pairs, then the function
//! would have to know that the outputted edge was undirected, which means it would have to bound its input with `Undirected`
//! forcing you to implement another, differently named function for the `Directed` case. But if `Undirected` outputs
//! directed pairs, the function will be able to use them as if they were one undirected edge, since they tell
//! the function that both directions are available between the two vertices. Therefore, the function can just bound
//! its input with `BaseGraph` and handle both directionalities at once.
//!
//! - Why does an `Undirected` graph treat input edges as undirected and not require a directed pair instead?
//!
//! For similar reasons as the above answer. If a function is directionality-agnostic, but does
//! mutate the graph, then it wouldn't know that a graph is `Undirected` and therefore wouldn't know to add a pair
//! for each edge. By having the graph itself handle the splitting of an undirected edge into a directed pair,
//! the function can bound its input by just `BaseGraph` and handle both directionalities at the same time.
//!
//! ### Directionality example
//!
//! Consider the constraint trait `Unique`. A graph is unique if for all edges, no two
//! edges are incident on the same two vertices in the same direction. Consequently, for undirected
//! graphs this means that only one undirected edge is allowed between any two vertices, while an edge
//! in each direction is allowed for directed graphs.
//!
//! The `graphene::core::constaint` module is able to simply implement this constraint by iterating
//! over all the directed edges a graph has, and reject it if any two edges have the same source
//! and sink. This implementation is directionality agnostic since undirected graphs return a directed
//! pair, which is allowed of a directed unique graph. Had `Undirected` graphs returned only one
//! undirected edge, two constraint traits `UniqueDirection` and `UniqueUndirected` would have been needed.
//! This is because the following two edges, (1,2) and (2,1), would be invalid for undirected graphs,
//! as the edges are identical when disregarding direction (which undirected graphs do). For directed
//! graphs the two edges are acceptable, as they have different directions.
//!
//! Therefore, the `graphene`'s directionality design allows for a single implementation for
//! the `Unique` constraint that works for both directed and undirected graphs.
//!
//!
//! # FAQ
//!
//! - How do i initialize an unweighted graph, it seems then all require a weight, e.g. AdjListGraph<V,W>?
//!
//! By convention, `()` is treated as the lack of a weight. Therefore, AdjListGraph<V,()> is
//! an unweighted graph.
//!
//!