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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
use crate::math;
/// This struct is holds the vertex adjacency lists for a graph.
#[derive(Debug,Clone)]
pub struct AdjacencyList{
list: Vec::< Option<Vec::<usize>> >,
}
impl AdjacencyList{
//----------------------------------------------------------------------------
/// This method returns the number of vertices in the list.
pub fn len(&self) -> usize{ self.list.len() }
//----------------------------------------------------------------------------
/// This function `true` iff there are no vertices in the list.
pub fn is_empty(&self) -> bool{ self.list.is_empty() }
//----------------------------------------------------------------------------
/// This function returns an `AdjacencyList` with `n` active but empty
/// vertices.
pub fn active_with_capacity(n: usize) -> Self{
let mut list = Vec::< Option<Vec::<usize>> >::with_capacity(n);
for _ii in 0..n{
list.push(Some(Vec::new()));
}
AdjacencyList{list}
}
//----------------------------------------------------------------------------
/// This function returns an `AdjacencyList` with `n` empty vertices.
pub fn with_capacity(n: usize) -> Self{
let mut list = Vec::< Option<Vec::<usize>> >::with_capacity(n);
for _ii in 0..n{
list.push(None);
}
AdjacencyList{list}
}
//----------------------------------------------------------------------------
/// This method returns `true` iff vertices `m` and `n` have an edge between
/// them.
pub fn are_connected(&self, m: usize, n: usize) -> bool{
self.contains(m,n)
}
//----------------------------------------------------------------------------
// This method returns `true` iff vertices `m` and `n` have an edge between
// them.
fn contains(&self,m: usize, n: usize) -> bool{
if let Some(neighbors) = &self.list[m]{
for ii in neighbors.iter(){
if *ii == n{
return true;
}
}
}
false
}
//----------------------------------------------------------------------------
/// This function places an edge between vertices `m` and `n`.
/// Connecting a vertex to itself activates it.
pub fn connect(&mut self, m: usize, n: usize){
if m==n {
self.activate(m);
return
}
self.insert(m,n);
self.insert(n,m);
}
//----------------------------------------------------------------------------
// This method activates vertex `n`.
fn activate(&mut self, n: usize){
if self.list[n].is_none(){
self.list[n] = Some(Vec::new());
}
}
//----------------------------------------------------------------------------
// This function places `n` onto the neighbor list of `m`.
fn insert(&mut self, m: usize, n: usize){
if let Some(neighbors) = &mut self.list[m]{
neighbors.push(n);
*neighbors = math::unique((*neighbors).clone());
neighbors.sort();
}else{
self.list[m] = Some(Vec::from([n]));
}
}
//----------------------------------------------------------------------------
/// This function returns the neighbor list of vertex `n`.
pub fn get_neighbors(& self, n: usize) -> Option<& Vec::<usize>>{
if let Some(neighbors) = &self.list[n]{
return Some(neighbors);
}
None
}
//----------------------------------------------------------------------------
/// This function returns the number of active vertices.
pub fn n_active_vertices(&self) -> usize{
let mut counter = 0;
for ii in 0..self.len(){
if self.list[ii].is_some(){
counter += 1;
}
}
counter
}
//----------------------------------------------------------------------------
/// This method returns a list of the active vertices.
pub fn get_active_vertices(&self) -> Vec::<usize>{
let counter = self.n_active_vertices();
let mut vertices = Vec::<usize>::with_capacity(counter);
for ii in 0..self.len(){
if self.list[ii].is_some(){
vertices.push(ii);
}
}
vertices
}
//----------------------------------------------------------------------------
}
#[cfg(test)]
mod tests {
use super::*;
#[allow(non_snake_case)]
#[test]
fn test_AdjacencyList(){
let mut adjacency_list = AdjacencyList::with_capacity(6);
assert!(!adjacency_list.are_connected(0,1));
let neighbors = adjacency_list.get_neighbors(0);
assert_eq!(neighbors,None);
adjacency_list.connect(0,1);
assert!(adjacency_list.are_connected(0,1));
assert!(adjacency_list.are_connected(1,0));
assert!(!adjacency_list.are_connected(0,2));
let neighbors = adjacency_list.get_neighbors(0).unwrap();
assert_eq!(*neighbors,vec![1]);
adjacency_list.connect(0,2);
let neighbors = adjacency_list.get_neighbors(0).unwrap();
assert_eq!(*neighbors,vec![1,2]);
adjacency_list.connect(0,2);
let neighbors = adjacency_list.get_neighbors(0).unwrap();
assert_eq!(*neighbors,vec![1,2]);
let neighbors = adjacency_list.get_neighbors(1).unwrap();
assert_eq!(*neighbors,vec![0]);
adjacency_list.connect(4,2);
adjacency_list.connect(4,0);
let neighbors = adjacency_list.get_neighbors(4).unwrap();
assert_eq!(*neighbors,vec![0,2]);
let vertices = adjacency_list.get_active_vertices();
assert_eq!(vertices,vec![0,1,2,4]);
}
}