petgraph/
traits_graph.rs

1use fixedbitset::FixedBitSet;
2
3use super::EdgeType;
4
5use super::graph::{Graph, IndexType, NodeIndex};
6#[cfg(feature = "stable_graph")]
7use crate::stable_graph::StableGraph;
8use crate::visit::EdgeRef;
9#[cfg(feature = "stable_graph")]
10use crate::visit::{IntoEdgeReferences, NodeIndexable};
11
12use super::visit::GetAdjacencyMatrix;
13
14/// The adjacency matrix for **Graph** is a bitmap that's computed by
15/// `.adjacency_matrix()`.
16impl<N, E, Ty, Ix> GetAdjacencyMatrix for Graph<N, E, Ty, Ix>
17where
18    Ty: EdgeType,
19    Ix: IndexType,
20{
21    type AdjMatrix = FixedBitSet;
22
23    fn adjacency_matrix(&self) -> FixedBitSet {
24        let n = self.node_count();
25        let mut matrix = FixedBitSet::with_capacity(n * n);
26        for edge in self.edge_references() {
27            let i = edge.source().index() * n + edge.target().index();
28            matrix.put(i);
29            if !self.is_directed() {
30                let j = edge.source().index() + n * edge.target().index();
31                matrix.put(j);
32            }
33        }
34        matrix
35    }
36
37    fn is_adjacent(&self, matrix: &FixedBitSet, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
38        let n = self.node_count();
39        let index = n * a.index() + b.index();
40        matrix.contains(index)
41    }
42}
43
44#[cfg(feature = "stable_graph")]
45/// The adjacency matrix for **Graph** is a bitmap that's computed by
46/// `.adjacency_matrix()`.
47impl<N, E, Ty, Ix> GetAdjacencyMatrix for StableGraph<N, E, Ty, Ix>
48where
49    Ty: EdgeType,
50    Ix: IndexType,
51{
52    type AdjMatrix = FixedBitSet;
53
54    fn adjacency_matrix(&self) -> FixedBitSet {
55        let n = self.node_bound();
56        let mut matrix = FixedBitSet::with_capacity(n * n);
57        for edge in self.edge_references() {
58            let i = edge.source().index() * n + edge.target().index();
59            matrix.put(i);
60            if !self.is_directed() {
61                let j = edge.source().index() + n * edge.target().index();
62                matrix.put(j);
63            }
64        }
65        matrix
66    }
67
68    fn is_adjacent(&self, matrix: &FixedBitSet, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
69        let n = self.node_count();
70        let index = n * a.index() + b.index();
71        matrix.contains(index)
72    }
73}
petgraph/traits_graph.rs

petgraph/
traits_graph.rs
