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
use crate::vertex::Vertex;
use crate::VtxTrait;
#[derive(Debug)]
pub struct GraphIter<'a, T: VtxTrait> {
inner: &'a Graph<T>,
cur: usize,
}
impl<'a, T: VtxTrait> Iterator for GraphIter<'a, T> {
type Item = &'a Vertex<T>;
fn next(&mut self) -> Option<Self::Item> {
if self.cur < self.inner.vtxs.len() {
let i: usize = self.cur;
self.cur = self.cur + 1;
Some(&*self.inner.vtxs[i])
} else {
None
}
}
}
#[derive(Debug)]
pub struct Graph<T: VtxTrait> {
vtxs: Vec<Box<Vertex<T>>>,
next_vtx: u64,
}
impl<T: VtxTrait> Graph<T> {
pub fn new() -> Graph<T> {
Graph {
vtxs: vec![],
next_vtx: 0,
}
}
pub fn iter<'a>(&'a self) -> GraphIter<'a, T> {
GraphIter {
inner: self,
cur: 0,
}
}
pub fn add_vtx(&mut self, ind: u64, v: T) {
self.create_vtx();
self.init_vtx(ind, v);
}
pub fn num_vtxs(&self) -> usize {
self.vtxs.len()
}
pub fn get_vtx(&self, ind: usize) -> &Vertex<T> {
&*(self.vtxs[ind])
}
pub fn set_vtx(&mut self, ind: usize, new_v: Vertex<T>) {
let vtxs = &mut self.vtxs[..];
if let Some(v) = vtxs.get_mut(ind) {
*v = Box::new(new_v);
}
}
pub fn add_edge(&mut self, ind: u64, nei: u64) {
if self.has_edge(ind, nei) == false {
self.vtxs[ind as usize].add_neigh(nei);
}
}
pub fn has_edge(&mut self, ind: u64, nei: u64) -> bool {
let v = self.get_vtx(ind as usize);
match v {
Vertex::V {
id: _,
val: _,
ref neigh,
} => {
for ne in neigh {
if **ne == nei {
return true;
}
}
}
Vertex::Empty => (),
}
return false;
}
fn init_vtx(&mut self, ind: u64, v: T) {
self.vtxs[ind as usize].init(ind, v);
}
fn create_vtx(&mut self) {
let next_id = self.next_vtx;
self.next_vtx = self.next_vtx + 1;
self.vtxs.insert(next_id as usize, Box::new(Vertex::Empty));
}
pub fn print(&self) {
for i in 0..self.vtxs.len() {
self.vtxs[i].print();
}
}
}