luka 0.2.0

Library 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

### Graph Library

[![Rust](https://github.com/amazing-hash/graph/actions/workflows/rust.yml/badge.svg?branch=main)](https://github.com/amazing-hash/graph/actions/workflows/rust.yml)
[![Coverage Status](https://coveralls.io/repos/github/amazing-hash/graph/badge.svg?branch=main)](https://coveralls.io/github/amazing-hash/graph?branch=main)
[![Build Status](https://app.travis-ci.com/amazing-hash/graph.svg?branch=main)](https://app.travis-ci.com/amazing-hash/graph)
[![crates.io](https://img.shields.io/crates/v/luka)](https://crates.io/crates/luka)
<hr/>

### Quick start
#### simple graph traversal
```rust
use luka::Graph;
use luka::algorithms;
use luka::utils;

fn main() {
    let mut graph = Graph::new(100);

    graph.add_edge(1, 2, 0).unwrap();
    graph.add_edge(1, 3, 0).unwrap();
    graph.add_edge(2, 4, 0).unwrap();
    graph.add_edge(3, 4, 0).unwrap();
    graph.add_edge(4, 5, 0).unwrap();

    let start = graph.get_vertex(1).unwrap();
    let target = graph.get_vertex(5).unwrap();
    let parents = algorithms::bfs(&graph, &start).unwrap();
    match utils::find_path(&graph, &target, &parents).unwrap() {
        Some(path) => {
            assert_eq!(path.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 5]);
        }
        None => {
            println!("Path not found !!!")
        }
    }
}
```
#### with visitor
```rust
use luka::Graph;
use luka::algorithms;
use luka::utils;

fn main() {
    struct CustomVisitor {
        visiting_order: Vec<usize>
    }

    impl <T> VisitorBFS<T> for CustomVisitor {
        fn queue_extract_event(&mut self, vertex: &Vertex<T>) -> Result<VisitorBFSAction, GraphError> {
            self.visiting_order.push(vertex.id());
            Ok(VisitorBFSAction::Nothing)
        }
    }

    let mut graph = Graph::new(100);
    graph.add_edge(1, 2, 0.0).unwrap();
    graph.add_edge(2, 3, 0.0).unwrap();
    graph.add_edge(2, 4, 0.0).unwrap();
    graph.add_edge(2, 5, 0.0).unwrap();
    graph.add_edge(4, 8, 0.0).unwrap();
    graph.add_edge(8, 17, 0.0).unwrap();

    let mut visitor = CustomVisitor{ visiting_order: vec![] };
    let start = graph.get_vertex(1).unwrap();
    bfs_with_visitor(&graph, &start, &mut visitor).unwrap();

    assert_eq!(vec![1, 2, 3, 4, 5, 8, 17], visitor.visiting_order);
}
```

### List algorithms

- BFS

Breadth-first search (BFS) is one of the simplest graph traversal algorithms and is the basis for many important graph algorithms.
Algorithmic complexity - O(|V| + |E|), where |V| is the number of vertexs in the graph and |E| is the number of edges in the graph.

- DFS 

Depth-first search (DFS) - one of the methods of graph traversal Algorithmic complexity - O(|V| + |E|), where |V| is the number of vertexs in the graph and |E| is the number of edges in the graph.

- Find connected components

Search for connectivity components. The algorithm works with an undirected graph. 
The algorithm divides the vertices of the graph into several groups, so that within one group one can reach from one vertex to any other, but between different groups there is no path.
Algorithmic complexity - O(|V| + |E|), where |V| is the number of vertexs in the graph and |E| is the number of edges in the graph.

- Find strongly connected components

A strong connectivity component is a subset of vertices (maximal inclusion) such that any two vertices of this subset are reachable from each other.
The graph is oriented. Algorithmic complexity - O(|V| + |E|), where |V| is the number of vertexs in the graph and |E| is the number of edges in the graph.

- Deikstra's Algorithm

Deikstra's Algorithm is an algorithm on graphs. It finds shortest paths from one of the vertices of a graph to all other vertices.
The algorithm works only for graphs without edges of negative weight. 
Algorithmic complexity - O(|E| log |V|), where |V| is the number of vertexs in the graph and |E| is the number of edges in the graph.

- Topological sort

The problem of topological sorting of a graph is as follows: specify such a linear order on its vertices that any edge leads from a vertex with a smaller number to a vertex with a larger number. 
Obviously, if the graph has cycles, there is no such order. Algorithmic complexity - O(|V| + |E|), where |V| is the number of vertexs in the graph and |E| is the number of edges in the graph.

- Find cycle in the graph (oriented and not oriented graph)

Algorithmic complexity - O(|V| + |E|), where |V| is the number of vertexs in the graph and |E| is the number of edges in the graph.

- Find subtree sizes

The algorithm finds the size of each subtree. The graph must be a tree, i.e. a connected acyclic graph.
Algorithmic complexity - O(|E|), where |E| is the number of edges in the graph.

- Find vertices depths

The algorithm finds the depth of each vertex. The graph must be a tree, i.e. a connected acyclic graph.
Algorithmic complexity - O(|E|), where |E| is the number of edges in the graph.

- Spanning Tree (Kruskal's algorithm)

Kruskal's algorithm is an efficient algorithm for constructing the minimum spanning tree of a weighted connected undirected graph Algorithmic complexity - O(|E| * log(|E|)), where |E| is the number of edges in the graph.