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
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 neighbor- The remaining are just getters
Graph
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
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.
VariableEdges
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.
Vertex
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
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.
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