# Graphs

> UStore for Rust

A graph collection, created with `Modality::Graph`, indexes every edge from both of its vertices, and an `Edge` is laid out as the source, target and identifier keys the ABI puts on its tapes.
A slice of edges therefore crosses as three strided columns, and the tape a lookup exports reads back as `&[Edge]` without a copy.

`Collection::graph` adds and removes one edge at a time under the default identifier, and looks up a batch of vertices in one role through a one-off arena, copying the edges or the degrees out of it:

```rust
let mut similar = database.collection("similar")?;
similar.graph().add_edge(avatar, titanic)?;
let recommendations: Vec<Edge> = similar.graph().read_edges(&[avatar], Role::Source)?;
let degrees: Vec<Degree> = similar.graph().degrees(&[avatar, titanic], Role::Any)?;
similar.graph().remove_edge(avatar, titanic)?;
```

The batch verbs, named as the C ABI names them, take edges with identifiers of their own, vertices, and a role per vertex:

```rust
use ustore::{Edge, Role, Roles};

let follows = database.collection_create("follows", Modality::Graph)?;
let [first, second, third, fourth, seventh] = [1u64, 2, 3, 4, 7].map(Key::from);
let edges = [Edge::new(first, second), Edge::new(first, third), Edge::with_id(second, third, seventh)];
database.head().graph_write_edges(follows, &edges, Durability::Buffered)?;
database.head().graph_write_vertices(follows, [fourth], Durability::Buffered)?;

let vertices = [first, third];
let found = database.head().graph_read_edges(follows, &vertices, Roles::Every(Role::Any), &mut arena)?;
for (vertex, run) in vertices.iter().zip(found.iter()) {
    for edge in run.unwrap_or_default() {
        println!("{vertex} meets {:?}", edge.neighbor_of(*vertex));
    }
}

let roles = Roles::Each(&[Role::Source, Role::Target]);
let degrees = database.head().graph_degrees(follows, [first, second], roles, &mut arena)?;
database.head().graph_remove_edges(follows, [Edge::with_id(second, third, seventh)], Durability::Buffered)?;
database.head().graph_remove_vertices(follows, [first], Roles::Every(Role::Any), Durability::Buffered)?;
```

`Neighborhoods` holds the degree of every vertex, the edges of all of them on one tape, and one more offset than vertices bounding the run of each, where a vertex the graph does not hold spans none, and its iterator splits the tape at those offsets.
Within one role the edges of a vertex come sorted by neighbor, and with both roles the outgoing edges precede the incoming ones.
`graph_degrees` asks for the degrees alone, exporting no edges.
`Roles::Every` gives the whole batch one role and `Roles::Each` gives every vertex its own, which must match the batch in length.
Every graph verb takes owned edges and vertices as well, so a deferred view serves each of them.

`use ustore::Graph;`

`use ustore::Edge;`

`use ustore::GraphSampleVerticesConfig;`

`use ustore::GraphScanVerticesConfig;`

`use ustore::GraphVerticesCursor;`

`use ustore::GraphVerticesCursorConfig;`

`use ustore::Neighborhoods;`

`use ustore::Role;`

`use ustore::Roles;`

`use ustore::graph::EdgeRuns;`

`use ustore::graph::GraphWriteEdges;`

`use ustore::graph::GraphRemoveEdges;`

`use ustore::graph::GraphWriteVertices;`

`use ustore::graph::GraphRemoveVertices;`

`use ustore::graph::GraphRemoveVerticesRange;`

`use ustore::graph::GraphScanVertices;`

`use ustore::graph::GraphSampleVertices;`

`use ustore::graph::GraphMeasureVertices;`

`use ustore::graph::GraphDegrees;`

`use ustore::graph::GraphReadEdges;`

`use ustore::*;`

## Degree

The number of edges a vertex connects to in the roles a lookup asked for.

```rust
pub type Degree = u32;
```

## Graph

The edges of one collection, each under the default identifier.

```rust
pub struct Graph<'collection, 'view, Parent = Database>
```

Every verb consumes the view; [`Collection::graph`](https://www.unum.cloud/docs/ustore/rust/collections.md#graph) hands out the next one.

Implements: `Debug`

## add_edge

Adds an edge from `source` to `target`, creating the collection as a graph when it is missing.

```rust
pub fn add_edge(self, source: Key, target: Key) -> Result<()>
```

## remove_edge

Removes the edge from `source` to `target`, whether or not the graph holds it.

```rust
pub fn remove_edge(self, source: Key, target: Key) -> Result<()>
```

## read_edges

The edges of every vertex in `role`, one run after another, copied out of a one-off arena, as `db['similar'].graph.read_edges(avatar)` lists them.

```rust
pub fn read_edges(self, vertices: &[Key], role: Role) -> Result<Vec<Edge>>
```

## degrees

The degree of every vertex in `role`, copied out of a one-off arena that exports no edges.

```rust
pub fn degrees(self, vertices: &[Key], role: Role) -> Result<Vec<Degree>>
```

## Edge

An edge from its source to its target, laid out as the three keys every edge takes on a tape.

```rust
pub struct Edge
```

- `source` `Key`: The vertex the edge leaves.
- `target` `Key`: The vertex the edge enters.
- `id` `Key`: The identifier telling apart several edges between the same vertices.

Implements: `Clone`, `Copy`, `StructuralPartialEq`, `PartialEq`, `Eq`, `PartialOrd`, `Ord`, `Debug`, `Hash`

## new

An edge carrying the default identifier.

```rust
pub fn new(source: Key, target: Key) -> Self
```

## with_id

An edge carrying its own identifier.

```rust
pub fn with_id(source: Key, target: Key, id: Key) -> Self
```

## neighbor_of

The end of the edge opposite `vertex`, or [`None`](https://www.unum.cloud/docs/ustore/rust/transactions.md#None) when `vertex` is neither end.

```rust
pub fn neighbor_of(&self, vertex: Key) -> Option<Key>
```

## GraphSampleVerticesConfig

The vertices a sample draws; see [`On::graph_sample_vertices`](https://www.unum.cloud/docs/ustore/rust/batches-and-arenas.md#graph_sample_vertices).

```rust
pub struct GraphSampleVerticesConfig
```

- `wanted` `usize`: Vertices drawn, at most.

Implements: `Clone`, `Copy`, `Debug`, `From<usize>`

## GraphScanVerticesConfig

The vertices a scan keeps, what admits them and how it reports; see [`On::graph_scan_vertices`](https://www.unum.cloud/docs/ustore/rust/batches-and-arenas.md#graph_scan_vertices).

```rust
pub struct GraphScanVerticesConfig<'config>
```

- `wanted` `usize`: Vertices kept, at most.
- `matching` `Matching<'config>`: Admits only the vertices its predicate approves; every vertex by default.
- `mode` `ScanMode`: In what order the vertices come.
- `progress` `Option<&'config mut ProgressCallback<'config>>`: Reports the scans finished and stops wherever it says to.

Implements: `From<usize>`

## GraphVerticesCursor

A walk over the vertices of one graph collection, which every pull resumes past the last key the pull before it handed out, as a [`crate::Cursor`](https://www.unum.cloud/docs/ustore/rust/scans.md#Cursor) walks blobs, keeping the keys its [`Matching`](https://www.unum.cloud/docs/ustore/rust/scans.md#Matching) admits.

```rust
pub struct GraphVerticesCursor<'view>
```

Mirrors `ustore_graph_vertices_cursor_t`; dropping it calls `ustore_graph_vertices_cursor_free`.

Implements: `Debug`, `Drop`

## next

Pulls up to `wanted` next keys into `arena`, fewer once the walk nears its end and none past it.

```rust
pub fn next<'arena>(&mut self, wanted: usize, arena: &'arena mut Arena) -> Result<&'arena [Key]>
```

Calls `ustore_graph_vertices_cursor_next`.

## GraphVerticesCursorConfig

What admits the vertices a cursor hands out; see [`On::graph_vertices_cursor`](https://www.unum.cloud/docs/ustore/rust/batches-and-arenas.md#graph_vertices_cursor).

```rust
pub struct GraphVerticesCursorConfig<'config>
```

- `matching` `Matching<'config>`: Admits only the vertices its predicate approves; every vertex by default.

Implements: `Debug`, `Default`, `From<[Matching](https://www.unum.cloud/docs/ustore/rust/scans.md#Matching)<'config>>`

## Neighborhoods

The degree and the edges of every vertex one lookup addressed, in the order they were asked for.

```rust
pub struct Neighborhoods<'arena>
```

The edges of one vertex run consecutively: sorted by neighbor within one role, with the outgoing edges
ahead of the incoming ones when both roles were asked for.

Implements: `Clone`, `Copy`, `Debug`, `IntoIterator`

## degrees

The degree of every vertex, with [`degree_missing`](#degree_missing) for a vertex the graph does not hold.

```rust
pub fn degrees(&self) -> &'arena [Degree]
```

## offsets

One more offset than vertices into [`Neighborhoods::edges`](#edges), counted in edges, bounding the run of every vertex, where a vertex the graph does not hold spans none.

```rust
pub fn offsets(&self) -> &'arena [u64]
```

## edges

The edges of every vertex, one run after another.

```rust
pub fn edges(&self) -> &'arena [Edge]
```

## iter

The edges of every vertex in order, or [`None`](https://www.unum.cloud/docs/ustore/rust/transactions.md#None) for a vertex the graph does not hold.

```rust
pub fn iter(&self) -> EdgeRuns<'arena>
```

## Role

The role a vertex plays in the edges a call addresses.

```rust
pub enum Role
```

- `Source` = `1`: The vertex the edges leave.
- `Target` = `2`: The vertex the edges enter.
- `Any` = `3`: Either end, which is the only role an undirected graph uses.

Implements: `Clone`, `Copy`, `StructuralPartialEq`, `PartialEq`, `Eq`, `Debug`, `Default`, `Hash`, `Display`, `FromStr`

## Roles

The roles of a batch of vertices: one for all of them, or one each.

```rust
pub enum Roles<'roles>
```

- `Every` = `(<a data-ref="Role">Role</a>)`: Every vertex plays the same role.
- `Each` = `(&amp;'roles [<a data-ref="Role">Role</a>])`: The vertex at each position plays the role at the same position.

Implements: `Clone`, `Copy`, `StructuralPartialEq`, `PartialEq`, `Eq`, `Debug`, `Hash`

## EdgeRuns

The edges of every vertex of one lookup in order, or [`None`](https://www.unum.cloud/docs/ustore/rust/transactions.md#None) for a vertex the graph does not hold.

```rust
pub struct EdgeRuns<'arena>
```

Implements: `Clone`, `Debug`, `Iterator`, `ExactSizeIterator`, `FusedIterator`

## GraphWriteEdges

An upsert of edges; see [`On::graph_write_edges`](https://www.unum.cloud/docs/ustore/rust/batches-and-arenas.md#graph_write_edges).

```rust
pub struct GraphWriteEdges<'collections, Edges>
```

Implements: `Debug`

## GraphRemoveEdges

A removal of edges; see [`On::graph_remove_edges`](https://www.unum.cloud/docs/ustore/rust/batches-and-arenas.md#graph_remove_edges).

```rust
pub struct GraphRemoveEdges<'collections, Edges>
```

Implements: `Debug`

## GraphWriteVertices

An upsert of bare vertices; see [`On::graph_write_vertices`](https://www.unum.cloud/docs/ustore/rust/batches-and-arenas.md#graph_write_vertices).

```rust
pub struct GraphWriteVertices<'collections, Keys>
```

Implements: `Debug`

## GraphRemoveVertices

A removal of vertices with their edges; see [`On::graph_remove_vertices`](https://www.unum.cloud/docs/ustore/rust/batches-and-arenas.md#graph_remove_vertices).

```rust
pub struct GraphRemoveVertices<'inputs, Keys>
```

Implements: `Debug`

## GraphRemoveVerticesRange

A removal of one range of vertices with their edges; see [`On::graph_remove_vertices_range`](https://www.unum.cloud/docs/ustore/rust/batches-and-arenas.md#graph_remove_vertices_range).

```rust
pub struct GraphRemoveVerticesRange
```

Implements: `Debug`

## GraphScanVertices

A walk over the vertices of one graph collection; see [`On::graph_scan_vertices`](https://www.unum.cloud/docs/ustore/rust/batches-and-arenas.md#graph_scan_vertices).

```rust
pub struct GraphScanVertices<'arena, 'config>
```

Implements: `Debug`

## GraphSampleVertices

A random draw of vertices from one graph collection; see [`On::graph_sample_vertices`](https://www.unum.cloud/docs/ustore/rust/batches-and-arenas.md#graph_sample_vertices).

```rust
pub struct GraphSampleVertices<'arena>
```

Implements: `Debug`

## GraphMeasureVertices

An estimate of what a range of vertices holds; see [`On::graph_measure_vertices`](https://www.unum.cloud/docs/ustore/rust/batches-and-arenas.md#graph_measure_vertices).

```rust
pub struct GraphMeasureVertices<'arena>
```

Implements: `Debug`

## GraphDegrees

A lookup of the degrees of vertices; see [`On::graph_degrees`](https://www.unum.cloud/docs/ustore/rust/batches-and-arenas.md#graph_degrees).

```rust
pub struct GraphDegrees<'arena, 'inputs, Keys>
```

Implements: `Debug`

## GraphReadEdges

A lookup of the degrees and the edges of vertices; see [`On::graph_read_edges`](https://www.unum.cloud/docs/ustore/rust/batches-and-arenas.md#graph_read_edges).

```rust
pub struct GraphReadEdges<'arena, 'inputs, Keys>
```

Implements: `Debug`

## degree_missing

The degree a lookup reports for a vertex the graph does not hold.

```rust
pub const fn degree_missing() -> Degree
```

## default_edge_id

The identifier an edge carries when it was given none, every bit of it set like [`key_unknown`](https://www.unum.cloud/docs/ustore/rust/collections.md#key_unknown).

```rust
pub const fn default_edge_id() -> Key
```