TwoHop Algo in C# and Rust

main.rs

use mimalloc::MiMalloc;
use rustc_hash::FxHashMap as HashMap;
use std::{collections::BinaryHeap, env::args};

#[global_allocator]
static GLOBAL: MiMalloc = MiMalloc;

struct Graph {
    n: usize,
    e: usize,
    ids: HashMap<usize, usize>,
    adj: Vec<Vec<(usize, usize)>>,
    rev_adj: Vec<Vec<(usize, usize)>>,
}

impl Graph {
    fn new(max: usize) -> Self {
        Self {
            n: 0,
            e: 0,
            ids: HashMap::default(),
            adj: vec![Vec::new(); max],
            rev_adj: vec![Vec::new(); max],
        }
    }
    fn add_edge(&mut self, u: usize, v: usize, w: usize) {
        self.e += 1;
        let uid = self.ids.entry(u).or_insert(self.n).to_owned();
        self.n = self.ids.len();
        let vid = self.ids.entry(v).or_insert(self.n).to_owned();
        self.n = self.ids.len();
        self.adj[uid].push((vid, w));
        self.rev_adj[vid].push((uid, w));
    }
}

#[derive(Clone)]
struct Label {
    id: usize,
    label_in: HashMap<usize, usize>,
    label_out: HashMap<usize, usize>,
}

impl Label {
    fn new(id: usize) -> Label {
        Self {
            id,
            label_in: HashMap::default(),
            label_out: HashMap::default(),
        }
    }
    fn update(&mut self, v: usize, w: usize, rev: bool) -> &mut Label {
        let entry = if rev {
            self.label_out.entry(v)
        } else {
            self.label_in.entry(v)
        };
        entry.and_modify(|e| *e = w.min(*e)).or_insert(w);
        self
    }

    fn dist_to(&mut self, rhs: &Label) -> Option<usize> {
        if let Some(&w) = self.label_out.get(&rhs.id) {
            return Some(w);
        }
        if let Some(&w) = rhs.label_in.get(&self.id) {
            return Some(w);
        }
        let (small, large) = if self.label_out.len() < rhs.label_in.len() {
            (&self.label_out, &rhs.label_in)
        } else {
            (&rhs.label_in, &self.label_out)
        };
        let mut min: Option<usize> = None;
        for (v, w) in small {
            if let Some(&w2) = large.get(v) {
                min = Some(min.map_or(w + w2, |m| m.min(w + w2)));
            }
        }
        min.inspect(|m| {
            self.update(rhs.id, *m, false);
        })
    }
}

impl std::ops::Shr<&Label> for &Label {
    type Output = Option<usize>;
    fn shr(self, rhs: &Label) -> Self::Output {
        if let Some(&w) = rhs.label_in.get(&self.id) {
            return Some(w);
        }
        if let Some(&w) = self.label_out.get(&rhs.id) {
            return Some(w);
        }
        let (small, large) = if self.label_out.len() < rhs.label_in.len() {
            (&self.label_out, &rhs.label_in)
        } else {
            (&rhs.label_in, &self.label_out)
        };
        let mut min: Option<usize> = None;
        for (v, w) in small {
            if let Some(&w2) = large.get(v) {
                min = Some(min.map_or(w + w2, |m| m.min(w + w2)));
            }
        }
        min
    }
}

#[derive(Eq, PartialEq)]
struct QueueUnit {
    v: usize,
    dis: usize,
}

impl From<(usize, usize)> for QueueUnit {
    fn from((v, dis): (usize, usize)) -> Self {
        Self { v, dis }
    }
}

impl Into<(usize, usize)> for QueueUnit {
    fn into(self) -> (usize, usize) {
        (self.v, self.dis)
    }
}

impl std::cmp::Ord for QueueUnit {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.dis.cmp(&self.dis)
    }
}

impl std::cmp::PartialOrd for QueueUnit {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

struct Labeling {
    graph: Graph,
    labels: Vec<Label>,
    queue: BinaryHeap<QueueUnit>,
}

impl Labeling {
    fn new(graph: Graph) -> Self {
        let n = graph.n;
        let labels = (0..n).map(Label::new).collect::<Vec<_>>();
        Self {
            graph,
            labels,
            queue: BinaryHeap::new(),
        }
    }

    fn bfs(&mut self, s: usize, rev: bool) {
        self.queue.extend(
            if rev {
                &self.graph.rev_adj[s]
            } else {
                &self.graph.adj[s]
            }
            .iter()
            .map(|(u, w)| (*u, *w).into())
            .collect::<Vec<_>>(),
        );
        while let Some(QueueUnit { v, dis }) = self.queue.pop() {
            let (label_s, label_v) = if s < v {
                if let [label_s, .., label_v] = &mut self.labels[s..=v] {
                    (label_s, label_v)
                } else {
                    unreachable!()
                }
            } else {
                if let [label_v, .., label_s] = &mut self.labels[v..=s] {
                    (label_s, label_v)
                } else {
                    unreachable!()
                }
            };
            let current_min = if rev {
                label_v.dist_to(label_s)
            } else {
                label_s.dist_to(label_v)
            };
            if let Some(current_min) = current_min {
                if current_min <= dis {
                    continue;
                }
            }
            label_v.update(s, dis, rev);
            self.queue.extend(
                if rev {
                    &self.graph.rev_adj[v]
                } else {
                    &self.graph.adj[v]
                }
                .iter()
                .filter(|(u, _)| *u != s)
                .map(|(u, w)| (*u, dis + w).into()),
            );
        }
    }

    fn pre_process(&mut self) {
        let mut degree = (0..self.graph.n)
            .map(|i| (i, self.graph.adj[i].len() + self.graph.rev_adj[i].len()))
            .collect::<Vec<_>>();
        degree.sort_unstable_by_key(|(_, d)| !*d);
        for (i, _) in degree {
            self.bfs(i, false);
            self.bfs(i, true);
        }
    }

    fn query(&self, u: usize, v: usize) -> Option<usize> {
        let uid = self.graph.ids[&u];
        let vid = self.graph.ids[&v];
        let label_u = &self.labels[uid];
        let label_v = &self.labels[vid];
        label_u >> label_v
    }

    fn cound_label_size(&self) {
        let label_size = self
            .labels
            .iter()
            .map(|l| l.label_in.len() + l.label_out.len())
            .sum::<usize>();
        let factor = label_size as f64 / (self.graph.n + self.graph.e) as f64;
        println!(
            "N: {}, E: {}, Label Size: {}, Factor: {}",
            self.graph.n, self.graph.e, label_size, factor
        );
    }
}

fn main() {
    let graph_file = std::fs::read_to_string(args().nth(1).unwrap()).unwrap();
    let mut graph = Graph::new(graph_file.lines().count() * 2);
    for line in graph_file.lines() {
        let mut iter = line.split_whitespace();
        let u = iter.next().unwrap().parse::<usize>().unwrap();
        let v = iter.next().unwrap().parse::<usize>().unwrap();
        let w = iter.next().unwrap().parse::<usize>().unwrap();
        graph.add_edge(u, v, w);
    }
    let mut labeling = Labeling::new(graph);

    let stopwatch = std::time::Instant::now();
    labeling.pre_process();
    println!("Preprocessing time: {:?}", stopwatch.elapsed());

    let query_file = std::fs::read_to_string(args().nth(2).unwrap()).unwrap();
    for line in query_file.lines() {
        let mut iter = line.split_whitespace();
        let u = iter.next().unwrap().parse::<usize>().unwrap();
        let v = iter.next().unwrap().parse::<usize>().unwrap();
        let ans = iter.next().unwrap().parse::<usize>().unwrap();
        let res = labeling.query(u, v);
        let eq = if let Some(res) = res {
            if ans == res {
                "=="
            } else {
                "!="
            }
        } else {
            "!="
        };

        println!("{} {} {:?}", ans, eq, res);
    }
    labeling.cound_label_size();
}

Program.cs

var graph = new Graph();
var graphFile = File.ReadLines(args[0]);
foreach (var line in graphFile)
{
    var data = line.Split().Select(int.Parse).ToArray();
    graph.AddEdge(data[0], data[1], data[2]);
}

var labeling = new Labeling(graph);

var stopwatch = System.Diagnostics.Stopwatch.StartNew();
labeling.PreProcess();
stopwatch.Stop();
Console.WriteLine($"Preprocessing time: {stopwatch.Elapsed.TotalSeconds} sec");

var queryFile = File.ReadLines(args[1]);
foreach (var line in queryFile)
{
    var data = line.Split().Select(int.Parse).ToArray();
    var res = labeling.Query(data[0], data[1]);
    var ans = data[2];
    var eq = res == ans ? "==" : "!=";
    Console.WriteLine($"Correct answer: {res} {eq} {ans}");
}

labeling.CountLabelSize();

class Graph
{
    public int N;
    public int E;
    public Dictionary<int, int> Ids { get; } = [];
    public List<List<(int, int)>> Adj { get; } = [];
    public List<List<(int, int)>> RevAdj { get; } = [];

    public void AddEdge(int u, int v, int w)
    {
        E++;
        int vid;
        int uid;
        if (Ids.TryAdd(u, N))
        {
            vid = N++;
        }
        else
        {
            vid = Ids[u];
        }
        if (Ids.TryAdd(v, N))
        {
            uid = N++;
        }
        else
        {
            uid = Ids[v];
        }

        while (Adj.Count < N)
            Adj.Add([]);
        while (RevAdj.Count < N)
            RevAdj.Add([]);

        Adj[uid].Add((vid, w));
        RevAdj[vid].Add((uid, w));
    }
}

readonly struct Label(int Id)
{
    private int Id { get; } = Id;
    public Dictionary<int, int> In { get; } = [];
    public Dictionary<int, int> Out { get; } = [];

    public void Update(int v, int w, bool rev)
    {
        if (rev)
            Out[v] = w;
        else
            In[v] = w;
    }

    public static int? operator >>>(Label u, Label v)
    {
        if (u.Out.TryGetValue(v.Id, out var we))
        {
            return we;
        }
        if (v.In.TryGetValue(u.Id, out var ws))
        {
            return ws;
        }
        var (small, large) = u.Out.Count < v.In.Count ? (u.Out, v.In) : (v.In, u.Out);
        var min = int.MaxValue;
        foreach (var (k, w) in small)
            if (large.TryGetValue(k, out var w2))
                min = Math.Min(min, w + w2);
        if (min == int.MaxValue)
            return null;
        v.Update(u.Id, min, true);
        return min;
    }
}

class Labeling
{
    private readonly Graph _graph;
    private readonly Label[] _labels;
    private PriorityQueue<int, int>? queue;

    public Labeling(Graph graph)
    {
        _graph = graph;
        _labels = Enumerable.Range(0, _graph.N).Select(i => new Label(i)).ToArray();
    }

    private void Bfs(int s, bool rev)
    {
        queue = new(rev ? _graph.RevAdj[s] : _graph.Adj[s]);

        while (queue.TryDequeue(out var v, out var dis))
        {
            var curMin = rev ? _labels[v] >>> _labels[s] : _labels[s] >>> _labels[v];
            if (curMin is not null && curMin <= dis)
                continue;
            _labels[v].Update(s, dis, rev);
            var adj = rev ? _graph.RevAdj[v] : _graph.Adj[v];
            foreach (var (u, w) in adj)
                queue.Enqueue(u, dis + w);
        }
    }

    public void PreProcess()
    {
        var degree = Enumerable
            .Range(0, _graph.N)
            .Select(i => (i, _graph.Adj[i].Count + _graph.RevAdj[i].Count))
            .OrderByDescending(t => t.Item2);
        foreach (var (s, _) in degree)
        {
            Bfs(s, false);
            Bfs(s, true);
        }
    }

    public int? Query(int u, int v)
    {
        var uid = _graph.Ids[u];
        var vid = _graph.Ids[v];
        return _labels[uid] >>> _labels[vid];
    }

    public void CountLabelSize()
    {
        var labelSize = _labels.Sum(l => l.In.Count + l.Out.Count);
        var factor = labelSize / (double)(_graph.N + _graph.E);
        Console.WriteLine($"N:{_graph.N}, E:{_graph.E}, Factor: {factor}");
    }
}