luka 0.4.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

use crate::{Graph, Vertex};
use crate::error::GraphError;

pub fn find_path<'a, T>(graph: &'a Graph<T>, target: &'a Vertex<T>, parents: &'a [Option<&Vertex<T>>]) -> Result<Option<Vec<&'a Vertex<T>>>, GraphError> {
    let mut target = target.id();
    if parents[target].is_none() {
        return Ok(None);
    }
    let mut path = vec![&graph.adj[target]];
    while let Some(next) = parents[target] {
        path.push(next);
        target = next.id;
    }
    path.reverse();
    Ok(Some(path))
}

pub fn transpose<T>(graph: &Graph<T>) -> Graph<T> where T: Copy {
    let mut graph_transp = Graph::new(graph.size() - 1);
    for vertex in graph.adj.iter() {
        for edge in &vertex.edges {
            graph_transp.add_edge(edge.to, vertex.id(), edge.weight).unwrap();
        }
    }
    graph_transp
}