graaf 0.32.2

Functions and types for working with graphs
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

# ![Graaf!](/logo.png "Graaf")   [![Build status](https://github.com/bsdrks/graaf/actions/workflows/rust.yml/badge.svg)](https://github.com/bsdrks/graaf/actions) [![Crates.io](https://img.shields.io/crates/v/graaf.svg)](https://crates.io/crates/graaf) [![API reference](https://docs.rs/graaf/badge.svg)](https://docs.rs/graaf) [![Coverage Status](https://coveralls.io/repos/github/bsdrks/graaf/badge.svg?branch=main)](https://coveralls.io/github/bsdrks/graaf?branch=main)

Graph algorithms, operations, generators, and representations.

## Installation

Add the following to your `Cargo.toml`:

```toml
[dependencies]
graaf = "0.32.2"
```

To use stable Rust, disable the `adjacency_matrix` feature:

```toml
[dependencies]
graaf = { version = "0.32.2", default-features = false }
```

## Overview

### Operations

Build and query graphs made with standard collections, or implement the operation traits for your types.

```rust
use {
    graaf::op::{
        AddEdge,
        Indegree,
        Outdegree,
        RemoveEdge,
    },
    std::collections::BTreeSet,
};

let mut graph = vec![BTreeSet::new(); 3];

// 1 ← 0 → 2

graph.add_edge(0, 1);
graph.add_edge(0, 2);

assert_eq!(graph.outdegree(0), 2);
assert_eq!(graph.indegree(1), 1);
assert_eq!(graph.indegree(2), 1);

graph.remove_edge(0, 1);

assert_eq!(graph.outdegree(0), 1);
assert_eq!(graph.indegree(1), 0);
assert_eq!(graph.indegree(2), 1);
```

### Algorithms

Search, traverse, and analyze graphs built from the types that implement the operation traits.

```rust
use graaf::algo::bfs::single_pair_shortest_path as spsp;

// 0  ←  1
// ↑     ↑
// 3  →  2

let graph = [Vec::new(), vec![0], vec![1], vec![0, 2]];

assert_eq!(spsp(&graph, 3, 0), Some(vec![3, 0]));
assert_eq!(spsp(&graph, 3, 1), Some(vec![3, 2, 1]));
assert_eq!(spsp(&graph, 3, 2), Some(vec![3, 2]));
assert_eq!(spsp(&graph, 0, 3), None);
```

### Representations

Use custom graph representations. An adjacency matrix representation is available with the `adjacency_matrix` feature.

```rust
use graaf::{
    op::{
        AddEdge,
        IsSimple,
    },
    repr::AdjacencyMatrix,
};

let mut graph = AdjacencyMatrix::<3>::new();

graph.add_edge(0, 1);

assert!(graph.is_simple());

graph.add_edge(1, 1);

assert!(!graph.is_simple());
```

### Generators

Generate parameterized graphs.

```rust
use graaf::gen::Cycle;

let graph = Vec<Vec<usize>>::cycle(5);

assert_eq!(graph, vec![
    vec![0, 1],
    vec![1, 2],
    vec![2, 3],
    vec![3, 4],
    vec![4, 0],
]);
```

## License

Licensed under either [Apache License, Version 2.0] or [MIT license] at your option.

[Apache License, Version 2.0]: LICENSE-APACHE
[MIT license]: LICENSE-MIT