73 lines
2.1 KiB
Rust
73 lines
2.1 KiB
Rust
// ----------------------------------------------------------------
|
|
// IMPORTS
|
|
// ----------------------------------------------------------------
|
|
|
|
//
|
|
|
|
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
|
// CLASS Graph
|
|
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
|
|
|
/**
|
|
A data structure for graphs
|
|
*/
|
|
pub struct Graph<T> {
|
|
pub nodes: Vec<T>,
|
|
pub edges: Vec<(T,T)>,
|
|
#[allow(dead_code)]
|
|
string: String,
|
|
}
|
|
|
|
impl<T> Graph<T>
|
|
where T: PartialEq + Clone + ToString {
|
|
/// Creates new typed instance of stack.
|
|
pub fn new(nodes: Vec<T>, edges: Vec<(T,T)>) -> Graph<T> {
|
|
return Graph {
|
|
nodes: nodes,
|
|
edges: edges,
|
|
string: String::from(""),
|
|
};
|
|
}
|
|
|
|
/// @returns number of elements in stack.
|
|
#[allow(dead_code)]
|
|
pub fn len(self: &Self) -> usize {
|
|
return self.nodes.len();
|
|
}
|
|
|
|
/// @returns graph induced by subset of nodes
|
|
#[allow(dead_code)]
|
|
pub fn subgraph(self: Self, nodes: Vec<T>) -> Graph<T> {
|
|
let nodes_ = self.nodes
|
|
.iter()
|
|
.filter(|&u| (nodes.contains(u)))
|
|
.map(|u| u.clone())
|
|
.collect::<Vec<T>>();
|
|
let edges_ = self.edges
|
|
.iter()
|
|
.filter(|&(u, v)| (nodes.contains(u) && nodes.contains(v)))
|
|
.map(|(u, v)| (u.clone(), v.clone()))
|
|
.collect::<Vec<(T,T)>>();
|
|
return Graph::new(nodes_, edges_);
|
|
}
|
|
|
|
/// @returns all successor nodes of a particular node
|
|
pub fn successors(self: &Self, u: &T) -> Vec<T> {
|
|
return self.edges
|
|
.iter()
|
|
.filter(|&(u_, _)| (*u_ == *u))
|
|
.map(|(_, v)| (v.clone()))
|
|
.collect::<Vec<T>>();
|
|
}
|
|
|
|
/// @returns all predecessors nodes of a particular node
|
|
#[allow(dead_code)]
|
|
pub fn predecessors(self: &Self, v: &T) -> Vec<T> {
|
|
return self.edges
|
|
.iter()
|
|
.filter(|&(_, v_)| (*v_ == *v))
|
|
.map(|(u, _)| (u.clone()))
|
|
.collect::<Vec<T>>();
|
|
}
|
|
}
|