graaf 0.48.2

Functions and types for working with directed 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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

# ![Graaf](/logo.png "Graaf")   [![Crates.io](https://img.shields.io/crates/v/graaf.svg)](https://crates.io/crates/graaf) [![Build status](https://github.com/bsdrks/graaf/actions/workflows/rust.yml/badge.svg)](https://github.com/bsdrks/graaf/actions) [![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)

Work with directed graphs

## Installation

Add the following to your `Cargo.toml`:

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

## Overview

### Operations

Build and query digraphs.

```rust
use {
    graaf::{
        gen::EmptyConst,
        op::*,
    },
    std::collections::BTreeSet,
};

let mut digraph = <[BTreeSet<usize>; 3]>::empty();

digraph.add_arc(0, 1);
digraph.add_arc(0, 2);

assert_eq!(digraph.degree(0), 2);
assert_eq!(digraph.degree(1), 1);
assert_eq!(digraph.degree(2), 1);
```

### Algorithms

Search, traverse, and analyze digraphs.

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

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

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

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

### Generators

Generate parameterized digraphs.

```rust
use graaf::gen::*;

assert_eq!(
    Vec::<Vec<usize>>::empty(2),
    vec![Vec::new(), Vec::new()]
);

assert_eq!(
    Vec::<Vec<usize>>::cycle(3),
    vec![vec![1], vec![2], vec![0]]
);

assert_eq!(
    <[Vec::<usize>; 3]>::complete(),
    [vec![1, 2], vec![0, 2], vec![0, 1]]
);
```

Generate random digraphs.

```rust
use {
    graaf::{
        gen::RandomTournament,
        op::*,
    },
    std::collections::BTreeSet,
};

let tournament = Vec::<BTreeSet<usize>>::random_tournament(4);

assert_eq!(tournament.size(), 6);
assert_eq!(tournament.order(), 4);

for s in tournament.iter_vertices() {
    assert_eq!(tournament.degree(s), 3);
    assert!((0..3).contains(&tournament.outdegree(s)));
    assert!((0..3).contains(&tournament.indegree(s)));
}
```

### Representations

An adjacency matrix representation is available with the `adjacency_matrix`
feature.

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

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

digraph.add_arc(0, 1);
digraph.add_arc(1, 1);

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

## Project goals

- A flexible API for digraph operations
- A comprehensive set of algorithms
- Generators for common digraphs
- Competitive performance
- Complete documentation
- Full unit test coverage
- Full benchmark coverage
- Extensive property tests

## Features

These features require nightly Rust.

- `adjacency_matrix` enables the adjacency matrix representation.

## Changelog

See [CHANGELOG.md] for a list of changes.

## License

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

[CHANGELOG.md]: https://github.com/bsdrks/graaf/blob/main/CHANGELOG.md
[Apache License, Version 2.0]: LICENSE-APACHE
[MIT license]: LICENSE-MIT