Struct Graph

pub struct Graph<L: Hash, T, E = (), M: MulTE<T, E> = MulTEDefaultType> {
    pub edges: Vec<Edge<T, E>>,
    /* private fields */
}

存储图的数据结构

其中L为点的标签(label)的类型

T为边的容量的类型

E为边的费用的类型

M用于实现容量和费用的相乘

Fields

edges: Vec<Edge<T, E>>

Implementations

impl<L, T, E, M> Graph<L, T, E, M>

where L: Clone + Hash + Eq, E: Default, T: Default, M: MulTE<T, E>,

pub fn get_index(&self, label: &L) -> Option<usize>

获得某一个label对应的编号

pub fn get_label(&self, index: usize) -> Option<&L>

获得某一个编号对应的label

pub fn init_graph(&mut self)

初始化一个图， 将原有的边和点全部去除

pub fn new() -> Self

创建一个初始为空的图

pub fn create_graph(nodes: &[L]) -> Self

使用一些点的标签来创建一个图，按照在vector中的顺序赋予其编号

pub fn add_node(&mut self, label: &L)

在最后添加一个新的点

pub fn first_edge(&self, index: usize) -> Option<&Edge<T, E>>

获得从index指出的第一条边

pub fn next_edge(&self, now: &Edge<T, E>) -> Option<&Edge<T, E>>

获得和now从同一个点指出的下一条边

配合first_edge可以这样使用：

use network_flow::graph::Graph;
let mut g = Graph::<usize, i32>::new();
// build graph
let mut temp = g.first_edge(0);
while let Some(edge) = temp {
    // do something
    temp = g.next_edge(edge);
}

pub fn get_all_edges(&self, index: usize) -> Vec<(&Edge<T, E>, usize)>

使用first_edge和next_edge函数得到从index出发的所有边及其编号

pub fn get_neighbor(&self, index: usize) -> Vec<usize>

获得与index相邻的所有点

impl<L, T, E, M> Graph<L, T, E, M>

where L: Hash, E: Clone + Default, T: Clone + Default, M: MulTE<T, E>,

pub fn add_edge(&mut self, from: usize, to: usize, weight: &T)

添加一条从from到to的边，容量为weight，费用为默认值

pub fn add_edge2(&mut self, from: usize, to: usize, weight: &T, cost: &E)

添加一条从from到to的边，容量为weight，费用为cost

impl<L, T, E, M> Graph<L, T, E, M>

where L: Clone + Hash + Eq, E: Clone + Default, T: Clone + Default + Add<Output = T> + Sub<Output = T> + PartialEq + PartialOrd, M: MulTE<T, E>,

pub fn get_max_flow(&mut self, s: usize, t: usize) -> T

求从s到t的最大流

pub fn get_cut(&self, s: usize) -> Vec<usize>

求从s为源的最小割，返回与s相连的所有点。

需要先调用最大流函数或者费用流函数

如：

use network_flow::graph::Graph;
let mut g = Graph::<usize, i32>::new();
// 建图
g.get_max_flow(0, 10);
let v = g.get_cut(0);

impl<L, T, E, M> Graph<L, T, E, M>

where L: Clone + Hash + Eq, E: Clone + Default + Add<Output = E> + Sub<Output = E> + PartialEq + PartialOrd, T: Clone + Default + Add<Output = T> + Sub<Output = T> + PartialEq + PartialOrd, M: MulTE<T, E>,

pub fn mcmf(&mut self, s: usize, t: usize) -> (T, E)

求从s到t的最小费用最大流

impl<L, T, E, M: MulTE<T, E>> Graph<L, T, E, M>

where L: BitIO + Clone + Hash + Eq, E: BitIO + Clone + Default, T: BitIO + Clone + Default,

pub fn output_file(&self, file: &str) -> Result<(), Error>

将当前的图的状态输出到文件中

L, T, E均需实现BitIO trait

pub fn input_file(file: &str) -> Result<Self, Error>

从文件中生成一个图

L, T, E均需实现BitIO trait

impl<L, T, E, M: MulTE<T, E>> Graph<L, T, E, M>

where L: StrIO + Clone + Hash + Eq, E: StrIO + Clone + Default + Add<Output = E> + Sub<Output = E>, T: StrIO + Clone + Default + Add<Output = T> + Sub<Output = T>,

pub fn output_to_dot(&self, file: &str) -> Result<(), Error>

将图输出到.dot文件中

pub fn from_dot(file: &str) -> Result<Self, Error>

从.dot文件中读取图

Trait Implementations

impl<L: Debug + Hash, T: Debug, E: Debug, M: Debug + MulTE<T, E>> Debug for Graph<L, T, E, M>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.