Lib.rs

Graph Library

Quick start

simple graph traversal

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

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.

• Floid algorithm

This algorithm for finding shortest paths in a weighted graph with positive or negative weights of edges (but no negative cycles). Algorithmic complexity - O(|V|^3), where |V| is the number of vertexs in the graph.

• Bellman-Ford algorithm

The Bellman-Ford algorithm is an algorithm for finding the shortest path in a weighted graph. Unlike Dijkstra's algorithm, Bellman-Ford's algorithm allows edges with negative weight, but negative weight loops are still forbidden. Algorithmic complexity - O(|E| * |V|), where |E| is the number of edges in the graph and |V| is the number of vertexs in the graph.

• Least common ancestor (LCA)

Algorithmic complexity of construction - O(n). Algorithmic complexity of the query response -O(log n) where n is number nodes of tree.

• Find bridges

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