TwoHopBFS.rs

use std::collections::{HashMap, HashSet};
use std::io;
use std::cmp::Reverse;
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::i64;
use std::f64;
#[allow(unused_imports)]
use rand::prelude::*;

/*
曖昧な理解に基づいた TwoHopBFS の Rust 実装

参考資料：
https://db-event.jpn.org/deim2014/final/proceedings/A8-3.pdf
2-Hop ラベルの直接的な計算によるグラフ最短経路クエリ処理の効率化
秋葉 拓哉† 岩田 陽一† 吉田 悠一††
† 東京大学情報理工学系研究科 〒 113–8656 東京都文京区本郷 7-3-1
†† 国立情報学研究所 〒 101–8430 東京都千代田区一ツ橋 2-1-2
DEIM Forum 2014 A8-3
*/

/*
License:

Copyright: 2022 yamule/odat

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/

#[derive(Copy, Clone,Debug,  PartialEq)]
struct PointDist{
    point:usize,
    dist:f64
}
impl Eq for PointDist{
}

impl Ord for PointDist {
    fn cmp(&self, other: &PointDist) -> Ordering { 
        other.dist.partial_cmp(&self.dist).unwrap_or(self.point.cmp(&other.point))
    }
}

// `PartialOrd` needs to be implemented as well.
impl PartialOrd for PointDist {
    fn partial_cmp(&self, other: &PointDist) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

pub struct TwoHopBFS{
    pub edges:Vec<HashMap<usize,f64>>,
    pub dictionary:Vec<HashMap<usize,f64>>,
    pub route:Vec<HashMap<usize,Vec<usize>>>
}
impl TwoHopBFS{
    pub fn construct(edges:Vec<HashMap<usize,f64>>)->TwoHopBFS{
        let numnodes = edges.len();
        let mut ret =  TwoHopBFS{edges:vec![],dictionary:vec![HashMap::new();numnodes],route:vec![HashMap::new();numnodes]};
        ret.construct_(edges);
        return ret;
    }

    //現在地と終了地を渡すと次に向かうべきノードのインデクスと残り距離を返す
    pub fn get_next(&self,current:usize,goal:usize)->Option<(usize,f64)>{
        if current == goal{
            return None;
        }
        let mut next_index:i64 = -1;
        let mut mindist = 0.0;
        //let mut mindist_z = 0.0;//dijkstra とルートが同じようになるようにしようとしたが無理だった。
        for ii in self.edges[current].iter(){
            let pdist = self.get_dist(*ii.0,goal).0+ii.1;
            if pdist == f64::INFINITY{
                continue;
            }
            if pdist < mindist || next_index < 0{
                next_index = *ii.0 as i64;
                mindist = pdist;
                //mindist_z = *ii.1;
            }/*else if pdist == mindist{
                if mindist_z < *ii.1{
                    next_index = *ii.0 as i64;
                    mindist = pdist;
                    mindist_z = *ii.1;
                }
            }*/
        }
        if next_index < 0{
            return None;
        }
        return Some((next_index as usize,mindist));
    }

    pub fn get_route(&self,start:usize,goal:usize)-> (Vec<usize>,f64){
        let mut current = start;
        let mut ret:Vec<usize> = vec![current];
        let ddist = self.get_dist(start,goal);
        if ddist.0 == f64::INFINITY{
            return (vec![],f64::INFINITY);
        }
        loop{
            let next :Option<(usize,f64)> = self.get_next(current,goal);
            //eprintln!("{} -> {:?}",current,next);
            if let None = next{
                break;
            }
            current = next.unwrap().0;
            ret.push(current);
        }
        return (ret,ddist.0);
    }
    pub fn insert_to_dict(&mut self,from_:usize,to_:usize,dist:f64){
        assert!(from_ != to_);
        let from = from_.min(to_);
        let to = from_.max(to_);
        self.dictionary[to].insert(from,dist);
        self.dictionary[from].insert(to,dist);
    }
    

    pub fn remove_direct_dist(&mut self,from_:usize,to_:usize){
        self.dictionary[from_].remove(&to_);
        self.dictionary[to_].remove(&from_);
    }

    pub fn get_direct_dist(&self,from_:usize,to_:usize)->f64{
        if from_ == to_{
            return 0.0;
        }
        let from = from_.min(to_);
        let to = from_.max(to_);

        if self.dictionary[from].contains_key(&to){
            return *self.dictionary[from].get(&to).unwrap();
        }
        return f64::INFINITY;
    }
    //距離と中間点を返す
    pub fn get_dist(&self,from_:usize,to_:usize)->(f64,Option<usize>){
        if from_ == to_{
            return (0.0,None);
        }
        let from = from_.min(to_);
        let to = from_.max(to_);

        let mut mindist = f64::INFINITY;
        let mut minindex:i64 = -2;

        if self.dictionary[from].contains_key(&to){
            mindist =  *self.dictionary[from].get(&to).unwrap();
            minindex = -1;
        }
        if self.dictionary[from].len() > self.dictionary[to].len(){
            for hh in self.dictionary[to].iter(){
                if self.dictionary[from].contains_key(hh.0){
                    let pd = *hh.1+self.dictionary[from].get(hh.0).unwrap();
                    if mindist > pd{
                        mindist = pd;
                        minindex = *hh.0 as i64;
                    }
                }
            }
        }else{
            for hh in self.dictionary[from].iter(){
                if self.dictionary[to].contains_key(hh.0){
                    let pd = *hh.1+self.dictionary[to].get(hh.0).unwrap();
                    if mindist > pd{
                        mindist = pd;
                        minindex = *hh.0 as i64;
                    }
                }
            }
        }
        if minindex < 0{
            return (mindist,None);
        }
        return (mindist,Some(minindex as usize));
    }

    pub fn construct_(&mut self,edges:Vec<HashMap<usize,f64>>){
        let n_nodes = self.dictionary.len();
        for ii in 0..n_nodes{
            let mut next_vertex:BinaryHeap<PointDist> = BinaryHeap::new();
            next_vertex.push(PointDist { dist: 0.0, point: ii});
            //eprintln!("{}",ii);
            while next_vertex.len() > 0{
                
                let target = next_vertex.pop().unwrap();
                let edd = &edges[target.point];
                for pp in edd.iter(){
                    if target.dist+pp.1 >= self.get_direct_dist(ii,*pp.0){
                        continue;
                    }
                    let mindist = self.get_dist(ii,*pp.0);
                    //println!("##{} {} {:?}",ii,pp.0,mindist);
                    if mindist.0 < target.dist+*pp.1{
                        self.insert_to_dict(ii,*pp.0, mindist.0);
                        if let Some(x) = mindist.1{
                            assert!(x <= ii || *pp.0 <= ii);//無いはず
                        }
                    }else{
                        self.insert_to_dict(ii,*pp.0, target.dist+*pp.1);
                        next_vertex.push(PointDist{point:*pp.0,dist: target.dist+*pp.1});
                    }
                }
            }
        }
        self.edges = edges;
    }
}


fn main() {
    let num_nodes = 8;
    //無向グラフに対して TwoHopBFS を適用する

    //nodeid, nodeid, distance の Vec 
    let edges_:Vec<(usize,usize,f64)> = vec![
        (0,2,2.0),
        (1,2,2.0),
        (3,2,2.0),
        (4,2,2.0),
        (5,2,2.0),
        (6,2,2.0),
        (3,4,2.0),
    ];
    
    //全ノード分の HashMap 要素を持つ Vec を作成して渡す。HashMap はそのノードからのエッジを示す。
    let mut edges:Vec<HashMap<usize,f64>> = vec![HashMap::new();num_nodes];
    for ee in edges_.into_iter(){
        edges[ee.0].insert(ee.1,ee.2);
        edges[ee.1].insert(ee.0,ee.2);
    }

    let sbfs = TwoHopBFS::construct(edges);
    println!("{:?}",sbfs.get_dist(3,4));
    println!("{:?}",sbfs.get_dist(3,5));//距離
    println!("{:?}",sbfs.get_route(3,5));//始点から終点に至るまでのパス付
}


#[allow(dead_code)]
fn parseline_numeric<T:std::str::FromStr>(k:&str) -> Vec<T>{
    let mut ret:Vec<T> = vec![];
    for ss in k.split_ascii_whitespace(){
        if ss.len() > 0{
            if let Ok(u) = (ss).parse::<T>(){
                ret.push(u);
            }else{
                panic!("Couldn't parse {}. ",ss);
            }
        }
    }
    return ret;
}

#[allow(dead_code)]
fn parseinput_numeric<T:std::str::FromStr>()->Vec<T>{
    let mut inn:String = String::new();
    io::stdin().read_line(&mut inn).expect("Failed to read line.");
    //eprintln!("{}",inn);
    return parseline_numeric(&inn);
}



#[allow(dead_code)]
fn dijkstra(start:usize,end:usize,edges:&HashMap<usize,HashMap<usize,usize>> )->(usize,Vec<usize>){
    let mut updated:BinaryHeap<(Reverse<i128>,usize,Vec<usize>)> = BinaryHeap::new();
    updated.push((Reverse(1),start,vec![start]));
    let mut processed:HashSet<usize> = HashSet::new();
    while updated.len() > 0{
        let nexx = updated.pop().unwrap();
        if processed.contains(&nexx.1){
            continue;
        }
        if nexx.1 == end{
            return ((((nexx.0).0 - nexx.2.len() as i128) >> 64) as usize,nexx.2);
        }
        processed.insert(nexx.1);
        if ! edges.contains_key(&nexx.1){
            continue;
        }
        let currentdist = ((nexx.0).0 - nexx.2.len() as i128) >> 64;
        for ee in edges.get(&nexx.1).unwrap().iter(){
            let mut newvec = nexx.2.clone();
            newvec.push(*ee.0);
            updated.push((Reverse(((currentdist as i128+*ee.1 as i128) << 64) + newvec.len() as i128 ),*ee.0,newvec));
        }
    }
    return (usize::MAX,vec![]);
}


#[test]
fn test(){
    let mut rgen:StdRng = SeedableRng::seed_from_u64(10_u64);
    for num_nodes in 5..100{
        let mut edges_:Vec<(usize,usize,usize)> = vec![
        ];

        for _ii in 0..(num_nodes+rgen.gen_range(0..num_nodes)){
            let u = rgen.gen_range(0..num_nodes);
            let v = rgen.gen_range(0..num_nodes);
            if u == v{
                continue;
            }
            let d = rgen.gen_range(1..20);
            edges_.push((u,v,d));
        }

        let mut edges:Vec<HashMap<usize,f64>> = vec![HashMap::new();num_nodes];
        let mut edges_hm:HashMap<usize,HashMap<usize,usize>> = HashMap::new();
        for ee in edges_.into_iter(){
            
            edges[ee.0].insert(ee.1,ee.2 as f64);
            edges[ee.1].insert(ee.0,ee.2 as f64);

            if !edges_hm.contains_key(&ee.0){
                edges_hm.insert(ee.0,HashMap::new());
            }
            if !edges_hm.contains_key(&ee.1){
                edges_hm.insert(ee.1,HashMap::new());
            }
            edges_hm.get_mut(&ee.0).unwrap().insert(ee.1,ee.2);
            edges_hm.get_mut(&ee.1).unwrap().insert(ee.0,ee.2);
        }

        //println!("{:?}",&edges);
        let sbfs = TwoHopBFS::construct(edges);
        let mut checked = 0;
        for ii in 0..num_nodes{
            for jj in 0..num_nodes{
                if sbfs.get_dist(ii,jj).0 == f64::INFINITY{
                    continue;
                }
                let dres = dijkstra(ii,jj,&edges_hm);
                let sdist = sbfs.get_dist(ii,jj);
                let sroute = sbfs.get_route(ii,jj);
                checked += 1;
                /*if  sdist.0 as usize != dres.0 || dres.1 != sroute.0{
                    println!("{}-{} {:?} {} ",ii,ii+1,sdist,dres.0);
                    println!("{:?}",sroute);
                    println!("{:?}",dres.1);
                    panic!();
                }*/
                if  sdist.0 as usize != dres.0 || dres.0 != sroute.1 as usize{
                    println!("{}-{} {:?} {} ",ii,jj,sdist,dres.0);
                    println!("{:?}",sroute);
                    println!("{:?}",dres.1);
                    panic!();
                }
            }
        }
        
        println!("{}:{}",num_nodes,checked);
    }
}