gryf 0.2.1

Graph data structure library with focus on convenience, versatility, correctness and performance.
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

use std::collections::{VecDeque, hash_map::Entry};

use rustc_hash::{FxBuildHasher, FxHashMap, FxHashSet};

use crate::{
    core::{Neighbors, base::NeighborReference, marker::Direction, weight::Weight},
    visit::VisitSet,
};

use super::{Error, ShortestPaths};

pub fn bfs<G, W>(
    graph: &G,
    source: G::VertexId,
    goal: Option<G::VertexId>,
    edge_dist: W,
) -> Result<ShortestPaths<W, G>, Error>
where
    G: Neighbors,
    W: Weight,
{
    // The check for unsignedness should eliminate the negativity weight check,
    // because the implementation of `is_unsigned` method is always a constant
    // boolean in practice.
    if !W::is_unsigned() && edge_dist < W::zero() {
        return Err(Error::NegativeWeight);
    }

    // FIXME: We want to use `visit::Bfs` here instead of reimplementing the
    // algorithm again. For that, we need more information than the current
    // implementation provides (e.g., the other vertex to the currently
    // processed vertex). This should be changed after the capabilities of the
    // visit module are extended.

    // Not using FixedBitSet with CompactIdMap because the algorithm supports
    // early termination when reaching given goal. It is likely that reaching
    // goal means visiting a subgraph which is significantly smaller than the
    // original graph.
    let mut visited =
        FxHashSet::with_capacity_and_hasher(graph.vertex_count_hint().unwrap_or(32), FxBuildHasher);

    let mut dist = FxHashMap::default();
    let mut pred = FxHashMap::default();
    let mut queue = VecDeque::new();

    dist.insert(source.clone(), W::zero());
    queue.push_back((source.clone(), W::zero()));

    while let Some((vertex, vertex_dist)) = queue.pop_front() {
        if goal.as_ref() == Some(&vertex) {
            // Mark as visited, because below is a test that checks that goal
            // was visited.
            visited.visit(vertex);
            break;
        }

        for neighbor in graph.neighbors_directed(&vertex, Direction::Outgoing) {
            let next = neighbor.id();

            if visited.is_visited(&*next) {
                continue;
            }

            let next = next.into_owned();
            let next_dist = vertex_dist.clone() + edge_dist.clone();

            if let Entry::Vacant(slot) = dist.entry(next.clone()) {
                slot.insert(next_dist.clone());
                pred.insert(next.clone(), vertex.clone());
            }

            queue.push_back((next, next_dist));
        }

        // The vertex is finished.
        visited.visit(vertex.clone());
    }

    if let Some(ref goal) = goal
        && !visited.is_visited(goal)
    {
        return Err(Error::GoalNotReached);
    }

    Ok(ShortestPaths { source, dist, pred })
}