aboutsummaryrefslogtreecommitdiff
path: root/src/rpc/graph_algo.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/rpc/graph_algo.rs')
-rw-r--r--src/rpc/graph_algo.rs79
1 files changed, 39 insertions, 40 deletions
diff --git a/src/rpc/graph_algo.rs b/src/rpc/graph_algo.rs
index 13c60692..5bd6cc51 100644
--- a/src/rpc/graph_algo.rs
+++ b/src/rpc/graph_algo.rs
@@ -6,10 +6,10 @@ use std::cmp::{max, min};
use std::collections::HashMap;
use std::collections::VecDeque;
-//Vertex data structures used in all the graphs used in layout.rs.
-//usize parameters correspond to node/zone/partitions ids.
-//To understand the vertex roles below, please refer to the formal description
-//of the layout computation algorithm.
+///Vertex data structures used in all the graphs used in layout.rs.
+///usize parameters correspond to node/zone/partitions ids.
+///To understand the vertex roles below, please refer to the formal description
+///of the layout computation algorithm.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Vertex {
Source,
@@ -20,8 +20,7 @@ pub enum Vertex {
Sink,
}
-//Edge data structure for the flow algorithm.
-//The graph is stored as an adjacency list
+///Edge data structure for the flow algorithm.
#[derive(Clone, Copy, Debug)]
pub struct FlowEdge {
cap: u32, //flow maximal capacity of the edge
@@ -30,8 +29,7 @@ pub struct FlowEdge {
rev: usize, //index of the reversed edge (v, self) in the edge list of vertex v
}
-//Edge data structure for the detection of negative cycles.
-//The graph is stored as a list of edges (u,v).
+///Edge data structure for the detection of negative cycles.
#[derive(Clone, Copy, Debug)]
pub struct WeightedEdge {
w: i32, //weight of the edge
@@ -42,13 +40,14 @@ pub trait Edge: Clone + Copy {}
impl Edge for FlowEdge {}
impl Edge for WeightedEdge {}
-//Struct for the graph structure. We do encapsulation here to be able to both
-//provide user friendly Vertex enum to address vertices, and to use usize indices
-//and Vec instead of HashMap in the graph algorithm to optimize execution speed.
+///Struct for the graph structure. We do encapsulation here to be able to both
+///provide user friendly Vertex enum to address vertices, and to use internally usize
+///indices and Vec instead of HashMap in the graph algorithm to optimize execution speed.
pub struct Graph<E: Edge> {
vertextoid: HashMap<Vertex, usize>,
idtovertex: Vec<Vertex>,
+ //The graph is stored as an adjacency list
graph: Vec<Vec<E>>,
}
@@ -69,8 +68,8 @@ impl<E: Edge> Graph<E> {
}
impl Graph<FlowEdge> {
- //This function adds a directed edge to the graph with capacity c, and the
- //corresponding reversed edge with capacity 0.
+ ///This function adds a directed edge to the graph with capacity c, and the
+ ///corresponding reversed edge with capacity 0.
pub fn add_edge(&mut self, u: Vertex, v: Vertex, c: u32) -> Result<(), String> {
if !self.vertextoid.contains_key(&u) || !self.vertextoid.contains_key(&v) {
return Err("The graph does not contain the provided vertex.".to_string());
@@ -94,8 +93,8 @@ impl Graph<FlowEdge> {
Ok(())
}
- //This function returns the list of vertices that receive a positive flow from
- //vertex v.
+ ///This function returns the list of vertices that receive a positive flow from
+ ///vertex v.
pub fn get_positive_flow_from(&self, v: Vertex) -> Result<Vec<Vertex>, String> {
if !self.vertextoid.contains_key(&v) {
return Err("The graph does not contain the provided vertex.".to_string());
@@ -110,7 +109,7 @@ impl Graph<FlowEdge> {
Ok(result)
}
- //This function returns the value of the flow incoming to v.
+ ///This function returns the value of the flow incoming to v.
pub fn get_inflow(&self, v: Vertex) -> Result<i32, String> {
if !self.vertextoid.contains_key(&v) {
return Err("The graph does not contain the provided vertex.".to_string());
@@ -123,7 +122,7 @@ impl Graph<FlowEdge> {
Ok(result)
}
- //This function returns the value of the flow outgoing from v.
+ ///This function returns the value of the flow outgoing from v.
pub fn get_outflow(&self, v: Vertex) -> Result<i32, String> {
if !self.vertextoid.contains_key(&v) {
return Err("The graph does not contain the provided vertex.".to_string());
@@ -136,14 +135,14 @@ impl Graph<FlowEdge> {
Ok(result)
}
- //This function computes the flow total value by computing the outgoing flow
- //from the source.
+ ///This function computes the flow total value by computing the outgoing flow
+ ///from the source.
pub fn get_flow_value(&mut self) -> Result<i32, String> {
self.get_outflow(Vertex::Source)
}
- //This function shuffles the order of the edge lists. It keeps the ids of the
- //reversed edges consistent.
+ ///This function shuffles the order of the edge lists. It keeps the ids of the
+ ///reversed edges consistent.
fn shuffle_edges(&mut self) {
let mut rng = rand::thread_rng();
for i in 0..self.graph.len() {
@@ -157,7 +156,7 @@ impl Graph<FlowEdge> {
}
}
- //Computes an upper bound of the flow n the graph
+ ///Computes an upper bound of the flow on the graph
pub fn flow_upper_bound(&self) -> u32 {
let idsource = self.vertextoid[&Vertex::Source];
let mut flow_upper_bound = 0;
@@ -167,9 +166,9 @@ impl Graph<FlowEdge> {
flow_upper_bound
}
- //This function computes the maximal flow using Dinic's algorithm. It starts with
- //the flow values already present in the graph. So it is possible to add some edge to
- //the graph, compute a flow, add other edges, update the flow.
+ ///This function computes the maximal flow using Dinic's algorithm. It starts with
+ ///the flow values already present in the graph. So it is possible to add some edge to
+ ///the graph, compute a flow, add other edges, update the flow.
pub fn compute_maximal_flow(&mut self) -> Result<(), String> {
if !self.vertextoid.contains_key(&Vertex::Source) {
return Err("The graph does not contain a source.".to_string());
@@ -270,11 +269,11 @@ impl Graph<FlowEdge> {
Ok(())
}
- //This function takes a flow, and a cost function on the edges, and tries to find an
- // equivalent flow with a better cost, by finding improving overflow cycles. It uses
- // as subroutine the Bellman Ford algorithm run up to path_length.
- // We assume that the cost of edge (u,v) is the opposite of the cost of (v,u), and only
- // one needs to be present in the cost function.
+ ///This function takes a flow, and a cost function on the edges, and tries to find an
+ /// equivalent flow with a better cost, by finding improving overflow cycles. It uses
+ /// as subroutine the Bellman Ford algorithm run up to path_length.
+ /// We assume that the cost of edge (u,v) is the opposite of the cost of (v,u), and
+ /// only one needs to be present in the cost function.
pub fn optimize_flow_with_cost(
&mut self,
cost: &CostFunction,
@@ -309,7 +308,7 @@ impl Graph<FlowEdge> {
Ok(())
}
- //Construct the weighted graph G_f from the flow and the cost function
+ ///Construct the weighted graph G_f from the flow and the cost function
fn build_cost_graph(&self, cost: &CostFunction) -> Result<Graph<WeightedEdge>, String> {
let mut g = Graph::<WeightedEdge>::new(&self.idtovertex);
let nb_vertices = self.idtovertex.len();
@@ -334,7 +333,7 @@ impl Graph<FlowEdge> {
}
impl Graph<WeightedEdge> {
- //This function adds a single directed weighted edge to the graph.
+ ///This function adds a single directed weighted edge to the graph.
pub fn add_edge(&mut self, u: Vertex, v: Vertex, w: i32) -> Result<(), String> {
if !self.vertextoid.contains_key(&u) || !self.vertextoid.contains_key(&v) {
return Err("The graph does not contain the provided vertex.".to_string());
@@ -345,12 +344,12 @@ impl Graph<WeightedEdge> {
Ok(())
}
- //This function lists the negative cycles it manages to find after path_length
- //iterations of the main loop of the Bellman-Ford algorithm. For the classical
- //algorithm, path_length needs to be equal to the number of vertices. However,
- //for particular graph structures like our case, the algorithm is still correct
- //when path_length is the length of the longest possible simple path.
- //See the formal description of the algorithm for more details.
+ ///This function lists the negative cycles it manages to find after path_length
+ ///iterations of the main loop of the Bellman-Ford algorithm. For the classical
+ ///algorithm, path_length needs to be equal to the number of vertices. However,
+ ///for particular graph structures like in our case, the algorithm is still correct
+ ///when path_length is the length of the longest possible simple path.
+ ///See the formal description of the algorithm for more details.
fn list_negative_cycles(&self, path_length: usize) -> Vec<Vec<Vertex>> {
let nb_vertices = self.graph.len();
@@ -384,8 +383,8 @@ impl Graph<WeightedEdge> {
}
}
-//This function returns the list of cycles of a directed 1 forest. It does not
-//check for the consistency of the input.
+///This function returns the list of cycles of a directed 1 forest. It does not
+///check for the consistency of the input.
fn cycles_of_1_forest(forest: &[Option<usize>]) -> Vec<Vec<usize>> {
let mut cycles = Vec::<Vec<usize>>::new();
let mut time_of_discovery = vec![None; forest.len()];