my github: star_evan
intro:
The department of laptop science generally known as knowledge buildings makes use of graphs to characterize networks of communication, knowledge group, computational gadgets, the stream of computation, and so on. As an illustration, the hyperlink construction of a web site may be represented by a directed graph, by which the vertices characterize internet pages and directed edges characterize hyperlinks from one web page to a different. An identical method may be taken to issues in social media, journey, biology, laptop chip design, mapping the development of neuro-degenerative illnesses, and lots of different fields. The event of algorithms to deal with graphs is due to this fact of main curiosity in laptop science. The transformation of graphs is usually formalized and represented by graph rewrite methods. Complementary to graph transformation methods specializing in rule-based in-memory manipulation of graphs are graph databases geared in direction of transaction-safe, persistent storing and querying of graph-structured knowledge.
now let’s create a GRAPH in rust !
🦀goal:
#[test]
fn debug() {
let mut g: Graph<usize> = Graph::new();
g.add_edge(1, 3, 1);
g.add_edge(1, 4, 2);
g.add_edge(4, 6, 2);
g.add_edge(2, 5, 2);
g.add_edge(2, 4, 3);
g.add_edge(3, 4, 3);
g.add_edge(1, 2, 6);
g.add_edge(4, 5, 6);
g.add_edge(3, 6, 7);
g.print();
// we will use for as a result of we carried out iterator for our graph!!
for e in g.dfs_iter() {
println!("{e}")
}
}
😀goal output:
working 1 check
* 1 2 3 4 5 6
1|. 6 1 2 . .
2|6 . . 3 2 .
3|1 . . 3 . 7
4|2 3 3 . 6 2
5|. 2 . 6 . .
6|. . 7 2 . .
{(1, 2): 6, (1, 3): 1, (1, 4): 2, (2, 4): 3, (2, 5): 2, (3, 4): 3, (3, 6): 7, (4, 5): 6, (4, 6): 2}
总权值和:32
1
4
6
3
5
2
1. initialize graph:
1. create a brand new venture
cargo new rust-graph
2. declare graph struct
pub struct Graph<T> {
pub matrix: Vec<Vec<Choice<usize>>>,
pub edge_list: BTreeMap<Edge, Weight>,
pub nodes: BTreeMap<usize, Choice<T>>,
}
3. new methodology
write a constructor for
Graph
pub fn new() -> Self {
Self {
matrix: vec![],
nodes: BTreeMap::new(),
edge_list: BTreeMap::new(),
}
}
4. add node
one is add node with out worth, one other is add node with worth.(as a result of the worth may be None)
pub fn add_node(&mut self, index: usize) {
self.nodes.insert(index, None);
self.fix_length(index);
}
pub fn add_node_with_value(&mut self, index: usize, worth: T) {
self.nodes.insert(index, Some(worth));
self.fix_length(index);
}
5. repair size
We would like this adjacency matrix to vary in measurement as nodes are added
pub fn fix_length(&mut self, index: usize) -> bool {
if self.matrix.len() > index {
false
} else {
// this enlargement algorithm may be modified by yourself.
let target_len = (index as f32 * 1.3) as usize + 2;
whereas self.matrix.len() < target_len {
self.matrix.push(vec![]);
}
for i in 0..target_len {
whereas self.matrix[i].len() < target_len {
self.matrix[i].push(None)
}
}
true
}
}
6. add edge
pub fn add_edge(&mut self, from: usize, to: usize, weight: usize) {
// make edge_list .0 lower than .1
// replace edge_list,matrix and nodes
if from > to {
self.edge_list.insert((to, from), weight);
} else {
self.edge_list.insert((from, to), weight);
}
if !self.nodes.contains_key(&from) {
self.add_node(from);
}
if !self.nodes.contains_key(&to) {
self.add_node(to);
}
self.matrix[from][to] = Some(weight);
self.matrix[to][from] = Some(weight);
}
7. output weight summation
pub fn get_sum_weight(&self) -> usize x).sum();
sum
8. entry most index of all of the nodes
This methodology may be very helpful, we’ll use it later.
pub fn certain(&self) -> usize {
match self.nodes.iter().max() {
Some((&e, _)) => e,
None => 0,
}
}
9. fairly print
- write a way which returns string for print.
pub fn debug(&self) -> String {
let certain = self.certain();
let mut paint = " *".to_string();
(1..=certain).for_each(|x| paint.push_str(&format!("{:2} ", x)));
paint.push_str("n");
for i in 1..=certain {
paint.push_str(&format!("{:2}|", i));
for j in 1..=certain {
paint.push_str(&format!(
"{:2} ",
(match self.matrix[i][j] {
Some(e) => format!("{}", e),
None => String::from("."),
})
))
}
paint.push_str("n");
}
paint
}
pub fn debug_edge_list(&self) -> String {
format!("{:?}", self.edge_list)
}
- print methodology:
pub fn print(&self) {
println!("{}", self.debug());
println!("{}", self.debug_edge_list());
println!("总权值和:{}", self.get_sum_weight());
}
10. delete node, edge
- take away node:
pub fn rm_node(&mut self, index: usize) -> bool {
if !self.nodes.contains_key(&index) {
false
} else {
// after we take away node, we have to delete the perimeters linked to it.
self.remove_relative_edge(index);
self.nodes.take away(&index);
//replace matrix.
self.matrix[index].fill(None);
for i in 1..=self.certain() {
self.matrix[i][index] = None;
}
true
}
}
// remove_relative_edge
fn remove_relative_edge(&mut self, index: usize) {
// 3 (1,2) /* (2,3) (3,4) */ (2,4)
// BTreeMap
for e in self.neighbour(index) {
if e < index {
self.edge_list.take away(&(e, index));
} else {
self.edge_list.take away(&(index, e));
}
}
}
- take away edge:
pub fn rm_edge_single(&mut self, from: usize, to: usize) -> bool {
if from.max(to) > self.certain() {
false
} else {
self.matrix[from][to] = None;
true
}
}
pub fn rm_edge(&mut self, from: usize, to: usize) -> bool {
/* 删除边表内的边的逻辑 */
if from > to {
self.edge_list.take away(&(to, from));
} else {
self.edge_list.take away(&(from, to));
}
self.rm_edge_single(from, to) && self.rm_edge_single(to, from)
}
11. is empty?
pub fn is_empty(&self) -> bool {
self.nodes.len() == 0
}
2. implement DFS iterator:
1. declare an iterator for graph:
We have to create a stack for retailer temp values.
pub struct DFSIterator<'a, T: Ord + Debug> {
pub graph: &'a Graph<T>,
pub stk: Vec<usize>,
pub visited: Vec<bool>,
}
2. impl into iter methodology:
impl<T: Debug + Ord> Graph<T> {
pub fn dfs_iter(&self) -> DFSIterator<T> {
let stk = match self.get_first() {
Some(e) => vec![e],
None => vec![],
};
DFSIterator {
graph: self,
stk,
visited: vec![false; self.bound() + 1],
}
}
}
3. impl subsequent for the customized iterator:
impl<'a, T: Ord + Debug> Iterator for BFSIterator<'a, T> {
sort Merchandise = usize;
fn subsequent(&mut self) -> Choice<Self::Merchandise> {
if self.graph.is_empty() {
return None;
} else {
whereas !self.que.is_empty() {
let v = self.que.pop_front().unwrap();
if self.visited[v] {
proceed;
}
self.visited[v] = true;
for e in self.graph.neighbour(v) {
if !self.visited[e] {
self.que.push_back(e)
}
}
return Some(v);
}
None
}
}
}
3. check:
working 1 check
* 1 2 3 4 5 6
1|. 6 1 2 . .
2|6 . . 3 2 .
3|1 . . 3 . 7
4|2 3 3 . 6 2
5|. 2 . 6 . .
6|. . 7 2 . .
{(1, 2): 6, (1, 3): 1, (1, 4): 2, (2, 4): 3, (2, 5): 2, (3, 4): 3, (3, 6): 7, (4, 5): 6, (4, 6): 2}
总权值和:32
1
4
6
3
5
2
