A rust library providing traits for implementing graphs.
All traits are defined making large use generics. Allowing programmers to shape their graph in every detail.
The defined traits are here descripted. Documentation is yet to be added in the project
```rust
pub trait DirectedGraph
fn neighbors(&self, from: &K) -> Vec<&K>;
fn leading_to(&self, to: &K) -> Vec<&K>;
fn get_vertex(&self, key: &K) -> Option<&T>;
fn get_mutable_vertex(&mut self, key: &K) -> Option<&mut T>;
fn get_edge(&self, pair: (&K, &K)) -> Option<&E>;
fn get_mutable_edge(&mut self, pair: (&K, &K)) -> Option<&mut E>;
} ```
This is the main trait defined in this library. It is intended for implementing graphs with directed edges.
adjacent Takes the key of two vertexes and returns a boolen stating if exixts an arc going from the first to the secondneighbors Takes the key of a vertex and returns a vector containing the keys of all adjacent vertexes (reachable from the passed vertex)leading_to Takes the key of a vertex and returns a vector of the vertexes with the passed as neighborrust
pub trait Graph<T, E, K, V, W, C>: DirectedGraph<T, E, K, V, W, C>
where K: Hash + Eq + Clone,
C: Hash + Eq + Clone,
W: Sum + Sub + Eq + Ord + Copy,
T: Vertex<K, V>,
E: Edge<K, W, C>
{}
This traits does not define methods. It only specify that the graph is not dircted.
This following properties must be held true:
graph.neighbors().sort() == graph.leading_to().sort()graph.get_edge((a, b)) == graph.get_edge((b, a)) (valid also for .getmutableedge())graph.adjacent(a, b) == graph.adjacent(b, a)```rust
pub trait VariableVertexes
fn remove_vertex(&mut self, key: K) -> Option<T>;
} ```
This trait adds the add and remove methods for vertexes. Must be implemented in graphs with a variable number of vertexes
The add method shall return None if the element was not previously set. Otherwise the element shall be updated (but no the key) and the old element shall be returned as Some(old_element).
The remove method shall return None if the element was not found, or Some(element) if it was found.
```rust
pub trait VariableEdges
fn remove_edge(&mut self, pair: (&K, &K)) -> Option<E>;
}
```
This trait adds the add and remove methods for edges. Must be implemented in graphs with a variable number of edges
The add method shall return None if the element was not previously set. Otherwise the element shall be updated (but no the key) and the old element shall be returned as Some(old_element).
The remove method shall return None if the element was not found, or Some(element) if it was found.
```rust
pub trait Vertex
fn get_mutable(&mut self) -> &mut V;
fn key(&self) -> K;
} ```
Thist is the trait defining vertexes' behaviour. The Key type (K) must be hashable, equable (non just partially) and clonable. It is not required to implement copy, but it's suggested.
```rust
pub trait Edge
fn set_weight(&mut self, weight: W);
fn left(&self) -> &K;
fn right(&self) -> &K;
fn get_pair(&self) -> (&K, &K);
fn generate_key(pair: (&K, &K)) -> C;
fn key(&self) -> C;
} ```
This trait defines the behaviour of edges. It needs two key types, one for vertexes (K) an one for edges (C). it also require a Weight type to be summable, subtractable, equable, ordered and copiable.
An edge must implement an associated funcion to generate a key from a pair of vertex's keys. The key of an edge must be generated by a pair of vertex keys and nothing else.
The library provides modules with a few default implementations. Check the objective of the implementations before choosing wich to use, or if you should implement your own.
A directed graph with mutable number of both vertexes and edges, meant for working with large growing graphs.
Vertexes' key and value types and edges' weight type are generics.
Its implemented using HashMaps to keep the structure fast still allowing it to grow in size
A directed graph meant for working with small fast graphs. Vertexes number is fixed, but edges can be added or deleted
Vertexes' key type is usize, Vertexes' value type and Edges' weight type are still generics.
This is implemented using a two dimensional matrix storing weights allowing direct access to edges at the cost of preventing mutability in the number of Vertexes
A non directed implementation of graphs will be added in future