day7/src/topo_order.rs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

use std::collections::HashSet;
use {Vertex, Edge};

pub fn find(V: &HashSet<Vertex>, E: &HashSet<Edge>, V_sources: &HashSet<Vertex>) -> String {
  let mut sources_vec: Vec<Vertex> = V_sources.iter().map(|&v| v).collect();
  sources_vec.sort();

  let sources_repr: String = sources_vec.iter().collect();
  println!("sources_repr: {}", sources_repr);

  let mut result: Vec<char> = Vec::new();
  let mut ready: Vec<Vertex> = sources_vec;
  loop {
    if ready.len() == 0 {
      break;
    }

    let v: Vertex = ready[0];
    ready.remove(0);

    if !result.contains(&v) {
      result.push(v);
    }

    let destinations: Vec<Vertex> = E.iter()
      .filter(|&(v1, _v2)| *v1 == v)
      .map(|&(_v1, v2)| v2)
      .collect();

    for dest_v in &destinations {
      let sources: Vec<Vertex> = E.iter()
        .filter(|&(_v1, v2)| *v2 == *dest_v)
        .map(|&(v1, _v2)| v1)
        .collect();

      let mut ok = true;
      for s in &sources {
        if !result.contains(&s) {
          ok = false;
          break;
        }
      }

      if ok {
        ready.push(*dest_v);
      }
    }

    ready.sort();
  }

  let result_repr: String = result.into_iter().collect();
  result_repr
}