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
//! Submodule providing the trait `SimplePath`, which checks if the directed
//! graph associated with the provided structure is a simple path, i.e., a
//! linear sequence of nodes where each node (except the first and last) has
//! exactly one predecessor and one successor, with the last node having no
//! successors and the first node having no predecessors.
use num_traits::{One, SaturatingAdd, Zero};
use crate::traits::RootNodes;
/// A simple path is a special case of a directed acyclic graph (DAG) where
/// there is a single linear sequence of nodes. In a simple path, each node
/// (except the first and last) has exactly one predecessor and one successor,
/// with the last node having no successors and the first node having no
/// predecessors.
pub trait SimplePath: RootNodes {
/// Returns whether the directed graph associated with the structure is a
/// simple path.
///
/// # Examples
///
/// ```
/// use geometric_traits::{
/// impls::{SortedVec, SquareCSR2D},
/// prelude::*,
/// traits::{EdgesBuilder, VocabularyBuilder},
/// };
///
/// let nodes: Vec<usize> = vec![0, 1, 2];
/// let edges: Vec<(usize, usize)> = vec![(0, 1), (1, 2)];
/// let nodes: SortedVec<usize> = GenericVocabularyBuilder::default()
/// .expected_number_of_symbols(nodes.len())
/// .symbols(nodes.into_iter().enumerate())
/// .build()
/// .unwrap();
/// let edges: SquareCSR2D<_> = DiEdgesBuilder::default()
/// .expected_number_of_edges(edges.len())
/// .expected_shape(nodes.len())
/// .edges(edges.into_iter())
/// .build()
/// .unwrap();
/// let graph: DiGraph<usize> = DiGraph::from((nodes, edges));
///
/// assert!(graph.is_simple_path());
/// ```
#[inline]
fn is_simple_path(&self) -> bool {
if self.number_of_nodes() == Self::NodeId::zero() {
// An empty graph is not a simple path.
return false;
}
let root_nodes = self.root_nodes();
if root_nodes.len() != 1 {
return false; // A simple path must have exactly one root node.
}
let mut current_node = root_nodes[0];
let mut visited_nodes = Self::NodeId::zero();
loop {
visited_nodes = visited_nodes.saturating_add(&Self::NodeId::one());
if self.out_degree(current_node) > Self::NodeId::one() {
return false; // More than one outgoing edge means it's not a simple path.
}
if let Some(successor) = self.successors(current_node).next() {
if visited_nodes == self.number_of_nodes() {
return false; // More visited nodes than total nodes means a cycle.
}
current_node = successor;
} else {
break;
}
}
visited_nodes == self.number_of_nodes()
}
}
impl<T> SimplePath for T where T: RootNodes {}