### 1 unstable release

✓ Uses Rust 2018 edition

0.0.1-alpha.1 | Aug 29, 2019 |
---|

#**541** in Data structures

**MIT**license

29KB

486 lines

# Graph Representations

This crate provides different representations for graphs, some of which are efficient to use, and others that are efficient to construct.

The crate supports conversion between the different representations while preserving node ids.

## Quick Start Examples

Creating an adjacency array.

`use` `graphrepresentations``::``simplegraph``::`SimpleGraph`;`
`use` `graphrepresentations``::``graph``::``{`MutableGraph`,` Node`,` Edge`,` Graph`}``;`
`use` `graphrepresentations``::``adjacencyarray``::`AdjacencyArray`;`
`let` `mut` simple_graph `=` `SimpleGraph``::`new`(``)``;`
`let` n1 `=` simple_graph`.``add_node``(``Node``::`new`(``5``)``)``;`
`let` n2 `=` simple_graph`.``add_node``(``Node``::`new`(``7``)``)``;`
`let` e1 `=` simple_graph`.``add_edge``(``Edge``::`new`(`n1`,` n2`,` `'`c`'``)``)``.``unwrap_or_else``(``|``error``|` `panic!``(``"`The edge refers nonexistent nodes: {:?}`"``,` error`)``)``;`
`let` adjacency_array `=` `AdjacencyArray``::`from`(``&`simple_graph`)``;`
`let` `mut` node_iter `=` adjacency_array`.``node_id_iter``(``)``;`
`let` `mut` edge_iter `=` adjacency_array`.``edge_id_iter``(``)``;`
`assert_eq!``(`simple_graph`.``node_data``(`node_iter`.``next``(``)``.``expect``(``"`Node got lost`"``)``)``,` adjacency_array`.``node_data``(`n1`)``)``;` `//` The order of the nodes is guaranteed to stay the same
`assert_eq!``(`simple_graph`.``node_data``(`node_iter`.``next``(``)``.``expect``(``"`Node got lost`"``)``)``,` adjacency_array`.``node_data``(`n2`)``)``;`
`assert_eq!``(`node_iter`.``next``(``)``,` `None``)``;`
`assert_eq!``(`adjacency_array`.``edge``(`edge_iter`.``next``(``)``.``expect``(``"`Edge was not converted correctly`"``)``)``,` simple_graph`.``edge``(`e1`)``)``;`
`assert_eq!``(`edge_iter`.``next``(``)``,` `None``)``;`

Navigating that same adjacency array.

`//` The same adjacency array as above
`let` `mut` neighbors `=` adjacency_array`.``out_edges``(`n1`)``;`
`assert_eq!``(`adjacency_array`.``edge``(`neighbors`.``next``(``)``.``expect``(``"`Edge was not converted correctly`"``)``)``,` simple_graph`.``edge``(`e1`)``)``;`
`assert_eq!``(`neighbors`.``next``(``)``,` `None``)``;`

## Graph Traits

The basic trait for graphs. It cannot do much more than acting as an unmodifiable container. Supported are iteration of node and edge ids and lookup of node and edge data by id.`Graph`

A trait for mutable graphs. Graphs implementing this trait are supposed to allow efficient mutations. At the moment, the trait only requires`MutableGraph`

-methods.`add`

A graph that can be navigated forward. It requires the method`ForwardNavigableGraph`

that returns an iterator over all out-edges of a node.`out_edges`

A graph that supports efficient iteration of complete node and edge data. This is not implemented and blocked by #29661.`IterableGraph`

## Graph Representations

At the moment, this crate supports only two graph representations. One dynamic, and one static.

A dynamic graph representation, that allows efficient modification, but is not very useful to implement any algorithms.`SimpleGraph``:`Graph`+`MutableGraph

A static graph representation that is efficient to use in graph algorithms, but inefficient to modify. At the moment, modification needs to be done by rebuilding it from a`AdjacencyArray``:`Graph`+`ForwardNavigableGraph

.`SimpleGraph`

## Ids Explained

This crate uses ids to refer to nodes and edges. This comes natural when implementing adjacency arrays or edge lists. It is a fast and easy solution to pass around node and edge data in client code without having to worry about borrowing. Ids are 32 bit (or maybe also 64 bit in the future), so passing them around is basically zero-cost.

**Keep in mind** that ids are not bound in any way to the graph instance that created them.
There is no protection against using an id for one graph in another, resulting in unpredictable behavior.
**But** using the node ids of one graph instance with a converted version of that same graph is guaranteed to work consistently, if none of the graphs were modified after conversion.

If you are missing a feature or found a bug, please open an issue on github.

#### Dependencies

~23KB