network_flow/graph/
mod.rs

1//! 用于建立存储图的数据结构的module
2pub mod edge;
3
4use edge::*;
5use core::ops::Add;
6use core::ops::Sub;
7use core::mem::size_of;
8use std::collections::VecDeque;
9use std::collections::HashMap;
10use std::hash::Hash;
11use std::io::Read;
12use std::io::Write;
13// use std::collections::HashMap;
14use std::marker::PhantomData;
15use std::fs::File;
16use std::io::Error;
17
18/// 存储图的数据结构
19/// 
20/// 其中L为点的标签(label)的类型
21/// 
22/// T为边的容量的类型
23/// 
24/// E为边的费用的类型
25/// 
26/// M用于实现容量和费用的相乘
27#[derive(Debug)]
28pub struct Graph<L : Hash, T, E = (), M : super::costtype::MulTE<T, E> = super::costtype::MulTEDefaultType> {
29    labels : Vec<L>,
30    pub edges : Vec<Edge<T, E>>,
31    first : Vec<Edge<T, E>>,
32    m : PhantomData<M>,
33    hs : HashMap<L, usize>
34}
35
36fn copy_nodes<L : Clone>(nodes : &[L]) -> Vec<L> {
37    let mut res = vec![];
38    for i in nodes {
39        res.push(i.clone());
40    }
41    res
42}
43
44fn empty_edges<T : Default, E : Default>(len : usize) -> Vec<Edge<T, E>> {
45    let mut res = vec![];
46    for i in 0..len {
47        res.push(Edge::empty_edge(i));
48    }
49    res
50}
51
52fn make_hash<L : Clone + Hash + Eq>(nodes : &[L]) -> HashMap<L, usize> {
53    let mut res = HashMap::new();
54    for i in 0..nodes.len() {
55        res.insert(nodes[i].clone(), i);
56    }
57    res
58}
59
60impl<L, T, E, M> Graph<L, T, E, M> 
61    where 
62        L : Clone + Hash + Eq,
63        E : Default,
64        T : Default,
65        M : super::costtype::MulTE<T, E> {
66
67    /// 获得某一个label对应的编号
68    pub fn get_index(&self, label : &L) -> Option<usize> {
69        self.hs.get(label).map(|x| *x)
70    }
71
72    /// 获得某一个编号对应的label
73    pub fn get_label(&self, index : usize) -> Option<&L> {
74        if index >= self.labels.len() {
75            None
76        }
77        else {
78            Some(&self.labels[index])
79        }
80    }
81
82    /// 初始化一个图， 将原有的边和点全部去除
83    pub fn init_graph(&mut self) {
84        self.edges = vec![];
85        self.labels = vec![];
86        self.first = vec![];
87        self.hs.clear();
88    }
89
90    /// 创建一个初始为空的图
91    pub fn new() -> Self {
92        Self {
93            labels : vec![],
94            edges : vec![],
95            first : vec![],
96            m : PhantomData,
97            hs : HashMap::<L, usize>::new()
98        }
99    }
100
101    /// 使用一些点的标签来创建一个图，按照在vector中的顺序赋予其编号
102    pub fn create_graph(nodes : &[L]) -> Self {
103        Self {
104            labels : copy_nodes(nodes),
105            edges : vec![],
106            first : empty_edges(nodes.len()),
107            m : PhantomData,
108            hs : make_hash(nodes)
109        }
110    }
111
112    /// 在最后添加一个新的点
113    pub fn add_node(&mut self, label : &L) {
114        self.labels.push(label.clone());
115        self.first.push(Edge::empty_edge(self.labels.len() - 1));
116        self.hs.insert(label.clone(), self.labels.len() - 1);
117    }
118
119    /// 获得从index指出的第一条边
120    pub fn first_edge(&self, index : usize) -> Option<&Edge<T, E>> {
121        if self.first[index].next_edge == usize::MAX {
122            None
123        }
124        else {
125            Some(&self.edges[self.first[index].next_edge])
126        }
127    }
128
129    fn first_edge_mut(&mut self, index : usize) -> Option<&mut Edge<T, E>> {
130        if self.first[index].next_edge == usize::MAX {
131            None
132        }
133        else {
134            Some(&mut self.edges[self.first[index].next_edge])
135        }
136    }
137
138    /// 获得和now从同一个点指出的下一条边
139    /// 
140    /// 配合first_edge可以这样使用：
141    /// 
142    /// ```no_run
143    /// use network_flow::graph::Graph;
144    /// let mut g = Graph::<usize, i32>::new();
145    /// // build graph
146    /// let mut temp = g.first_edge(0);
147    /// while let Some(edge) = temp {
148    ///     // do something
149    ///     temp = g.next_edge(edge);
150    /// }
151    /// ```
152    pub fn next_edge(&self, now : &Edge<T, E>) -> Option<&Edge<T, E>> {
153        if now.next_edge == usize::MAX {
154            None
155        }
156        else {
157            Some(&self.edges[now.next_edge])
158        }
159    }
160    
161    fn next_edge_mut(&mut self, now : &mut Edge<T, E>) -> Option<&mut Edge<T, E>> {
162        if now.next_edge == usize::MAX {
163            None
164        }
165        else {
166            Some(&mut self.edges[now.next_edge])
167        }
168    }
169
170    /// 使用first_edge和next_edge函数得到从index出发的所有边及其编号
171    pub fn get_all_edges(&self, index : usize) -> Vec<(&Edge<T, E>, usize)> {
172        let mut res = vec![];
173        let mut temp = self.first_edge(index);
174        let mut no = self.first[index].next_edge;
175        while let Some(edge) = temp {
176            res.push((edge, no));
177            no = edge.next_edge;
178            temp = self.next_edge(edge);
179        }
180        res
181    }
182
183    /// 获得与index相邻的所有点
184    pub fn get_neighbor(&self, index : usize) -> Vec<usize> {
185        let mut res = vec![];
186        let mut edge = self.first_edge(index);
187        while let Some(x) = edge {
188            res.push(x.to);
189            edge = self.next_edge(x);
190        }
191        res
192    }
193
194}
195
196impl<L, T, E, M> Graph<L, T, E, M> 
197    where
198        L : Hash,
199        E : Clone + Default,
200        T : Clone + Default,
201        M : super::costtype::MulTE<T, E> {
202
203    /// 添加一条从from到to的边，容量为weight，费用为默认值
204    pub fn add_edge(&mut self, from : usize, to : usize, weight : &T) {
205        let mut edge = Edge::create_edge(
206            from, to, self.first[from].next_edge, 0, weight.clone(), E::default());
207        let mut edge2 = Edge::create_edge(
208            to, from, self.first[to].next_edge, 0, T::default(), E::default());
209        edge.opp_edge = self.edges.len() + 1;
210        edge2.opp_edge = self.edges.len();
211        edge2.reversed = true;
212        self.first[from].next_edge = self.edges.len();
213        self.first[to].next_edge = self.edges.len() + 1;
214        self.edges.push(edge);
215        self.edges.push(edge2);
216    }
217
218    /// 添加一条从from到to的边，容量为weight，费用为cost
219    pub fn add_edge2(&mut self, from : usize, to : usize, weight : &T, cost : &E) {
220        let mut edge = Edge::create_edge(
221            from, to, self.first[from].next_edge, 0, weight.clone(), cost.clone());
222        let mut edge2 = Edge::create_edge(
223            to, from, self.first[to].next_edge, 0, T::default(), cost.clone());
224        edge.opp_edge = self.edges.len() + 1;
225        edge2.opp_edge = self.edges.len();
226        edge2.reversed = true;
227        self.first[from].next_edge = self.edges.len();
228        self.first[to].next_edge = self.edges.len() + 1;
229        self.edges.push(edge);
230        self.edges.push(edge2);
231    }
232
233}
234
235
236impl<L, T, E, M> Graph<L, T, E, M> 
237    where 
238        L : Clone + Hash + Eq,
239        E : Clone + Default,
240        T : Clone + Default + Add<Output = T> + Sub<Output = T> + PartialEq + PartialOrd,
241        M : super::costtype::MulTE<T, E> {
242    /// 求从s到t的最大流
243    pub fn get_max_flow(&mut self, s : usize, t : usize) -> T {
244        self.dinic(s, t)
245    }
246
247    fn bfs(&self, levels : &mut Vec<u32>, s : usize) {
248        levels[s] = 1;
249        let mut q1 = vec![];
250        let mut q2 = vec![];
251        q2.push(s);
252        while ! q1.is_empty() || ! q2.is_empty() {
253            if q1.is_empty() {
254                while !q2.is_empty() {
255                    q1.push(q2.pop().unwrap());
256                }
257            }
258            let now = q1.pop().unwrap();
259            let mut temp = self.first_edge(now);
260            while let Some(edge) = temp {
261                let x = edge.to;
262                if edge.weight != T::default() && levels[x] == 0 {
263                    levels[x] = levels[now] + 1;
264                    q2.push(x);
265                }
266                temp = self.next_edge(edge);
267            }
268        }
269    }
270
271    fn dfs(&mut self, now : usize, t : usize, levels : &Vec<u32>, flow : T) -> T {
272        if now == t {
273            flow
274        }
275        else {
276            let edges = self.get_all_edges(now);
277            let mut v = vec![];
278            for (edge, index) in edges {
279                v.push((edge.weight.clone(), edge.to, index));
280            }
281            let mut res = T::default();
282            for (w, x, index) in v {
283                if w != T::default() && levels[x] == levels[now] + 1 {
284                    if flow == T::default() {
285                        res = self.dfs(x, t, levels, w);
286                    }
287                    else if flow < w {
288                        res = self.dfs(x, t, levels, flow.clone());
289                    }
290                    else {
291                        res = self.dfs(x, t, levels, w);
292                    }
293                    if res != T::default() {
294                        self.edges[index].weight = self.edges[index].weight.clone() - res.clone();
295                        let temp = self.edges[index].opp_edge;
296                        self.edges[temp].weight = self.edges[temp].weight.clone() + res.clone();
297                        return res;
298                    }
299                }
300            }
301            res
302        }
303    }
304
305    fn dinic(&mut self, s : usize, t : usize) -> T {
306        let mut res = T::default();
307        loop {
308            let mut levels = vec![0; self.labels.len()];
309            self.bfs(&mut levels, s);
310            if levels[t] == 0 {
311                break res
312            }
313            loop {
314                let temp = self.dfs(s, t, &levels, T::default());
315                if temp == T::default() {
316                    break
317                }
318                res = res + temp;
319            }
320        }
321    }
322
323    /// 求从s为源的最小割，返回与s相连的所有点。
324    /// 
325    /// 需要先调用最大流函数或者费用流函数
326    /// 
327    /// 如：
328    /// 
329    /// ```no_run
330    /// use network_flow::graph::Graph;
331    /// let mut g = Graph::<usize, i32>::new();
332    /// // 建图
333    /// g.get_max_flow(0, 10);
334    /// let v = g.get_cut(0);
335    /// ```
336    pub fn get_cut(&self, s : usize) -> Vec<usize> {
337        let mut levels = vec![0; self.labels.len()];
338        self.bfs(&mut levels, s);
339        let mut res = vec![];
340        for i in 0..self.labels.len() {
341            if levels[i] != 0 {
342                res.push(i);
343            }
344        }
345        res
346    }
347}
348
349impl<L, T, E, M> Graph<L, T, E, M> 
350    where 
351        L : Clone + Hash + Eq,
352        E : Clone + Default + Add<Output = E> + Sub<Output = E> + PartialEq + PartialOrd,
353        T : Clone + Default + Add<Output = T> + Sub<Output = T> + PartialEq + PartialOrd,
354        M : super::costtype::MulTE<T, E> {
355
356    fn spfa(&self, s : usize, t : usize, dist : &mut [E]) -> bool {
357        let mut q = VecDeque::new();
358        q.push_back(t); dist[t] = E::default();
359        let mut vis = vec![false; self.labels.len()];
360        let mut inque = vec![false; self.labels.len()];
361        inque[t] = true;
362        vis[t] = true;
363        while !q.is_empty() {
364            let now = q.pop_front().unwrap();
365            let edges = self.get_all_edges(now);
366            let mut v = vec![];
367            for (edge, _) in edges {
368                v.push((self.edges[edge.opp_edge].weight.clone(), edge.cost.clone(), edge.to, edge.reversed));
369            }
370            for (w, c, to, r) in v {
371                if w == T::default() {
372                    continue;
373                }
374                let newcost = if r { dist[now].clone() + c } else { dist[now].clone() - c };
375                if !vis[to] || dist[to] > newcost {
376                    vis[to] = true;
377                    dist[to] = newcost;
378                    if !inque[to] {
379                        inque[to] = true;
380                        if q.is_empty() || dist[*q.front().unwrap()] < dist[to] {
381                            q.push_back(to);
382                        }
383                        else {
384                            q.push_front(to);
385                        }
386                    }
387                }
388            }
389            inque[now] = false;
390        }
391        vis[s]
392    }
393
394    fn mcmf_dfs(&mut self, now : usize, flow : T, cost : &mut E, dist : &[E], vis : &mut [bool], t : usize) -> T {
395        vis[now] = true;
396        if now == t {
397            flow
398        }
399        else {
400            let edges = self.get_all_edges(now);
401            let mut v = vec![];
402            for (edge, index) in edges {
403                v.push((edge.opp_edge, edge.weight.clone(), edge.cost.clone(), edge.to, edge.reversed, index));
404            }
405            for (opp, w, c, to, r, i) in v {
406                let temp = if r {dist[to].clone() - c.clone()} else {dist[to].clone() + c.clone()};
407                if dist[now] != temp || vis[to] || w == T::default() {
408                    continue;
409                }
410                let f : T;
411                if flow == T::default() {
412                    f = self.mcmf_dfs(to, w, cost, dist, vis, t);
413                }
414                else if flow < w {
415                    f = self.mcmf_dfs(to, flow.clone(), cost, dist, vis, t);
416                }
417                else {
418                    f = self.mcmf_dfs(to, w, cost, dist, vis, t);
419                }
420                if f != T::default() {
421                    *cost = cost.clone() + M::mul(&f, &c);
422                    self.edges[i].weight = self.edges[i].weight.clone() - f.clone();
423                    self.edges[opp].weight = self.edges[opp].weight.clone() + f.clone();
424                    return f;
425                }
426            }
427            T::default()
428        }
429    }
430
431    /// 求从s到t的最小费用最大流
432    pub fn mcmf(&mut self, s : usize, t : usize) -> (T, E) {
433        let mut cost = E::default();
434        let mut flow = T::default();
435        let mut dist = vec![E::default(); self.labels.len()];
436        while self.spfa(s, t,&mut dist) {
437            let mut vis = vec![false; self.labels.len()];
438            vis[t] = true;
439            while vis[t] {
440                for i in &mut vis {
441                    *i = false;
442                }
443                flow = flow + self.mcmf_dfs(s, T::default(), &mut cost, &dist, &mut vis, t);
444            }
445        }
446        (flow, cost)
447    }
448}
449
450use crate::io::BitIO;
451
452impl<L, T, E, M : super::costtype::MulTE<T, E>> Graph<L, T, E, M> 
453    where
454        L : BitIO + Clone + Hash + Eq,
455        E : BitIO + Clone + Default,
456        T : BitIO + Clone + Default {
457    /// 将当前的图的状态输出到文件中
458    /// 
459    /// L, T, E均需实现BitIO trait
460    pub fn output_file(&self, file : &str) -> Result<(), Error> {
461        let mut fs = File::create(file)?;
462        fs.write(&self.labels.len().to_be_bytes())?;
463        for i in &self.labels {
464            let temp = i.to_bit();
465            fs.write(&temp.len().to_be_bytes())?;
466            fs.write(&temp)?;
467        }
468        fs.write(&self.edges.len().to_be_bytes())?;
469        for edge in &self.edges {
470            fs.write(&edge.from.to_be_bytes())?;
471            fs.write(&edge.to.to_be_bytes())?;
472            fs.write(&edge.next_edge.to_be_bytes())?;
473            fs.write(&edge.opp_edge.to_be_bytes())?;
474            fs.write(&(edge.reversed as u8).to_be_bytes())?;
475            let temp = edge.weight.to_bit();
476            fs.write(&temp.len().to_be_bytes())?;
477            fs.write(&temp)?;
478            let temp = edge.cost.to_bit();
479            fs.write(&temp.len().to_be_bytes())?;
480            fs.write(&temp)?;
481        }
482        fs.write(&self.first.len().to_be_bytes())?;
483        for edge in &self.first {
484            fs.write(&edge.from.to_be_bytes())?;
485            fs.write(&edge.to.to_be_bytes())?;
486            fs.write(&edge.next_edge.to_be_bytes())?;
487            fs.write(&edge.opp_edge.to_be_bytes())?;
488            fs.write(&(edge.reversed as u8).to_be_bytes())?;
489            let temp = edge.weight.to_bit();
490            fs.write(&temp.len().to_be_bytes())?;
491            fs.write(&temp)?;
492            let temp = edge.cost.to_bit();
493            fs.write(&temp.len().to_be_bytes())?;
494            fs.write(&temp)?;
495        }
496        Ok(())
497    }
498    /// 从文件中生成一个图
499    /// 
500    /// L, T, E均需实现BitIO trait
501    pub fn input_file(file : &str) -> Result<Self, Error> {
502        let mut res = Self::new();
503        let mut fs = File::open(file)?;
504        let mut buf = [0; size_of::<usize>()];
505        assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
506        let len = usize::from_be_bytes(buf);
507        for _ in 0..len {
508            assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
509            let len = usize::from_be_bytes(buf);
510            let mut buf2 = vec![0; len];
511            assert_eq!(fs.read(&mut buf2)?, len);
512            let l = L::from_bit(&buf2);
513            res.labels.push(l);
514        }
515        assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
516        let len = usize::from_be_bytes(buf);
517        for _ in 0..len {
518            assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
519            let from = usize::from_be_bytes(buf);
520
521            assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
522            let to = usize::from_be_bytes(buf);
523
524            assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
525            let next_edge = usize::from_be_bytes(buf);
526
527            assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
528            let opp_edge = usize::from_be_bytes(buf);
529
530            let mut buf3 = [0];
531            assert_eq!(fs.read(&mut buf3)?, 1);
532            let reversed = u8::from_be_bytes(buf3) != 0;
533
534            assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
535            let len = usize::from_be_bytes(buf);
536            let mut buf2 = vec![0; len];
537            assert_eq!(fs.read(&mut buf2)?, len);
538            let weight = T::from_bit(&buf2);
539
540            assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
541            let len = usize::from_be_bytes(buf);
542            let mut buf2 = vec![0; len];
543            assert_eq!(fs.read(&mut buf2)?, len);
544            let cost = E::from_bit(&buf2);
545            
546            res.edges.push(Edge{from, to, next_edge, opp_edge, reversed, weight, cost});
547        }
548        assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
549        let len = usize::from_be_bytes(buf);
550        for _ in 0..len {
551            assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
552            let from = usize::from_be_bytes(buf);
553
554            assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
555            let to = usize::from_be_bytes(buf);
556
557            assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
558            let next_edge = usize::from_be_bytes(buf);
559
560            assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
561            let opp_edge = usize::from_be_bytes(buf);
562
563            let mut buf3 = [0];
564            assert_eq!(fs.read(&mut buf3)?, 1);
565            let reversed = u8::from_be_bytes(buf3) != 0;
566
567            assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
568            let len = usize::from_be_bytes(buf);
569            let mut buf2 = vec![0; len];
570            assert_eq!(fs.read(&mut buf2)?, len);
571            let weight = T::from_bit(&buf2);
572
573            assert_eq!(fs.read(&mut buf)?, size_of::<usize>());
574            let len = usize::from_be_bytes(buf);
575            let mut buf2 = vec![0; len];
576            assert_eq!(fs.read(&mut buf2)?, len);
577            let cost = E::from_bit(&buf2);
578            
579            res.first.push(Edge{from, to, next_edge, opp_edge, reversed, weight, cost});
580        }
581        Ok(res)
582    }
583}
584
585use crate::io::StrIO;
586use graphviz_rust_bla::parse;
587use graphviz_rust_bla::printer::{PrinterContext, DotPrinter};
588
589impl <L, T, E, M : super::costtype::MulTE<T, E>> Graph<L, T, E, M> 
590where
591    L : StrIO + Clone + Hash + Eq,
592    E : StrIO + Clone + Default + Add<Output = E> + Sub<Output = E>,
593    T : StrIO + Clone + Default + Add<Output = T> + Sub<Output = T>, {
594    /// 将图输出到.dot文件中
595    pub fn output_to_dot(&self, file : &str) -> Result<(), Error> {
596        use dot_structures::*;
597        use dot_generator::*;
598        let mut fs = File::create(file)?;
599        let mut g = graph!(di id!("test"));
600        let mut temp = 0;
601        for l in &self.labels {
602            g.add_stmt(stmt!(node!(temp.to_str();attr!("label",l.to_str()))));
603            temp = temp + 1;
604        }
605        for e in &self.edges {
606            if e.reversed { continue; }
607            let temp = self.edges[e.opp_edge].weight.clone();
608            let tot = temp.clone() + e.weight.clone();
609            let mut s = String::from("\"");
610            s.push_str(&temp.to_str());
611            s.push('/');
612            s.push_str(&tot.to_str());
613            s.push(',');
614            s.push_str(&e.cost.to_str());
615            s.push('"');
616            g.add_stmt(stmt!(edge!(node_id!(e.from) => node_id!(e.to);attr!("label",s))));
617        }
618        let mut ctx = PrinterContext::default();
619        fs.write_all(g.print(&mut ctx).as_bytes())?;
620        Ok(())
621    }
622
623    fn get_from_id(x : &dot_structures::Id) -> &String {
624        match x {
625            dot_structures::Id::Html(s) => s,
626            dot_structures::Id::Escaped(s) => s,
627            dot_structures::Id::Plain(s) => s,
628            dot_structures::Id::Anonymous(s) => s,
629        }
630    }
631
632    fn get_from_vertex(x : &dot_structures::Vertex) -> usize {
633        match x {
634            dot_structures::Vertex::N(x) => usize::from_str(Self::get_from_id(&x.0)),
635            _ => 0,
636        }
637    }
638
639    /// 从.dot文件中读取图
640    pub fn from_dot(file : &str) -> Result<Self, Error> {
641        let mut res = Self::new();
642        use dot_structures::Graph::DiGraph;
643        use dot_structures::Stmt::*;
644        let mut fs = File::open(file)?;
645        let mut buf = vec![];
646        fs.read_to_end(&mut buf)?;
647        let s = parse(&String::from_utf8(buf).unwrap()).unwrap();
648        match s {
649            DiGraph { id : _, strict : _, stmts } => {
650                for stmt in stmts {
651                    match stmt {
652                        Node(node) => {
653                            res.add_node(&L::from_str(Self::get_from_id(&node.attributes[0].1)));
654                        },
655                        Edge(edge) => {
656                            let mut from = 0;
657                            let mut to = 0;
658                            match edge.ty {
659                                dot_structures::EdgeTy::Pair(u, v) => {
660                                    from = Self::get_from_vertex(&u);
661                                    to = Self::get_from_vertex(&v);
662                                },
663                                _ => {}
664                            }
665                            if from == to {
666                                panic!("from_dot : invalid edge form");
667                            }
668                            let mut s = Self::get_from_id(&edge.attributes[0].1).clone().split_off(1);
669                            let p = s.find('/').unwrap();
670                            let mut ss = s.split_off(p);
671                            let w = T::from_str(&s);
672                            s = ss.split_off(1);
673                            let p = s.find(',').unwrap();
674                            ss = s.split_off(p);
675                            let ww = T::from_str(&s);
676                            s = ss.split_off(1);
677                            s.truncate(s.len() - 1);
678                            let c = E::from_str(&s);
679                            res.add_edge2(from, to, &ww, &c);
680                            let l = res.edges.len();
681                            res.edges[l - 1].weight = res.edges[l - 1].weight.clone() + w.clone();
682                            res.edges[l - 2].weight = res.edges[l - 2].weight.clone() - w.clone();
683                        },
684                        _ => ()
685                    }
686                }
687            },
688            _ => {panic!("from_dot : invalid graph form");}
689        }
690        Ok(res)
691    }
692}
network_flow/graph/mod.rs

network_flow/graph/
mod.rs
