generic_graph

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.

traits descriptions

The defined traits are here descripted. Documentation is yet to be added in the project

DirectedGraph

pub trait DirectedGraph<T, E, K, V, W, C>
    where K: Hash + Eq + Clone,
          C: Hash + Eq + Clone,
          W: Sum + Eq + Ord + Copy,
          T: Vertex<K, V>,
          E: Edge<K, W, C>
{
    fn adjacent(&self, from: &K, to: &K) -> bool;

    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 second
• neighbors 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 neighbor
• The remaining are just getters

Graph

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 + 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 .get_mutable_edge())
• graph.adjacent(a, b) == graph.adjacent(b, a)

VariableVertexes

pub trait VariableVertexes<T, E, K, V, W, C>: DirectedGraph<T, E, K, V, W, C>
    where K: Hash + Eq + Clone,
          C: Hash + Eq + Clone,
          W: Sum + Eq + Ord + Copy,
          T: Vertex<K, V>,
          E: Edge<K, W, C>
{
    fn add_vertex(&mut self, vertex: T);

    fn remove_vertex(&mut self, key: K);
}

This trait adds the add and remove methods for vertexes. Must be implemented in graphs with a variable number of vertexes

VariableEdges

pub trait VariableEdges<T, E, K, V, W, C>: DirectedGraph<T, E, K, V, W, C>
    where K: Hash + Eq + Clone,
          C: Hash + Eq + Clone,
          W: Sum + Eq + Ord + Copy,
          T: Vertex<K, V>,
          E: Edge<K, W, C>
{
    fn add_edge(&mut self, edge: E);

    fn remove_edge(&mut self, pair: (&K, &K));
}

This trait adds the add and remove methods for edges. Must be implemented in graphs with a variable number of edges

Vertex

pub trait Vertex<K, V>
    where K: Hash + Eq + Clone
{
    fn get_value(&self) -> &V;

    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.

Edge

pub trait Edge<K, W, C>
    where K: Hash + Eq + Clone,
          C: Hash + Eq + Clone,
          W: Sum + Eq + Ord + Copy
{
    fn get_weight(&self) -> W;

    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, 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.

default implementations

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.

AdjacencyList (WIP)

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

AdjacencyMatrix (future implementation)

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

(yet to be defined non directed graph)

A non directed implementation of graphs will be added in future