luka 0.1.0

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.