graaf 0.53.3

Work 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

# 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)

Build, search, and manipulate digraphs.

## Project goals

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

## Installation

Add the following to your `Cargo.toml`:

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

## Example

```rust
use {
    graaf::{
        algo::bfs::single_pair_shortest_path as spsp,
        gen::*,
        op::*,
        repr::*,
    },
    std::collections::BTreeSet,
};

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

// 0 -> {1, 2}
// 1 -> {}
// 2 -> {}

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);

// 0 -> {}
// 1 -> {0}
// 2 -> {1}
// 3 -> {0, 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!(Vec::<Vec<usize>>::empty(3)
    .iter()
    .eq(&[Vec::new(), Vec::new(), Vec::new()]));

// 0 -> {1}
// 1 -> {2}
// 2 -> {0}

assert!(Vec::<Vec<usize>>::cycle(3)
    .iter()
    .eq(&[vec![1], vec![2], vec![0]]));

// 0 -> {1, 2}
// 1 -> {0, 2}
// 2 -> {0, 1}

assert!(<[Vec::<usize>; 3]>::complete()
    .iter()
    .eq(&[vec![1, 2], vec![0, 2], vec![0, 1]]));

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)));
}

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

// 0 -> {1}
// 1 -> {1}

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

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

## 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