7
\$\begingroup\$

I would like to get any feedback about my implementation of Dijkstra algorithm in Rust following this youtube video.

Please be aware that this my first code in Rust as well as my first Dijkstra implementation in any language.

type Vertex = char;

#[derive(Debug)]
struct Connection {
    peers   : (Vertex, Vertex),
    weight  : u32,
}

#[derive(Debug)]
struct Graph {
    connections : Vec<Connection>,
    vertices    : Vec<Vertex>,
}

#[derive(Debug)]
#[derive(Clone)]
struct Road {
    vertex     : Vertex,
    distance   : u32,
    via_vertex : Vertex,
}

#[derive(Debug)]
#[derive(Clone)]
struct DijkstraTable {
    start_vertex : Vertex,
    roads        : Vec<Road>,
    unvisited    : Vec<Vertex>,
}

impl DijkstraTable {
    fn get_distance(&self, vertex: Vertex) -> u32 {
        let mut ret = 0;

        for r in &self.roads {
            if r.vertex == vertex {
                ret = r.distance;
            }
        }

        ret
    }

    fn get_road_mut(&mut self, vertex: &Vertex) -> Option<&mut Road> {
        for r in &mut self.roads {
            if r.vertex == *vertex {
                return Some(r);
            }
        }

        None
    }

    fn get_road(&self, vertex: &Vertex) -> Option<&Road> {
        for r in &self.roads {
            if r.vertex == *vertex {
                return Some(r);
            }
        }

        None
    }

    fn get_next_unvisited(&self) -> Option<&Vertex> {
        let mut min = u32::MAX;
        let mut next = None;

        for v in &self.unvisited {
            match self.get_road(&v) {
                None => break,
                Some(r) => {
                    if r.distance < min {
                        min = r.distance;
                        next = Some(v);
                    }
                }
            }
        }
        next
    }

    fn remove(&mut self, v : &Vertex) {
        let mut index = 0;
        while index < self.unvisited.len() {
            let toremove = &self.unvisited[index];
            if v == toremove {
                self.unvisited.remove(index);
                break
            }
            index += 1;
        }
    }
}

impl Road {
    fn new(from: Vertex) -> Road {
        Road {
            vertex      : from,
            distance    : u32::MAX,
            via_vertex  : '-',
        }
    }
}

impl Graph {
    fn get_weight(&self, peers: (Vertex, Vertex)) -> u32 {
        let mut ret : u32 = 0;

        for c in &self.connections {
            let (a, b) = peers;

            if c.peers == peers || c.peers == (b, a) {
                ret = c.weight;
                break;
            }
        }
        ret
    }

    fn get_neighbours(&self, vertex: &Vertex) -> Vec<&Vertex> {
        let mut neighbours : Vec<&Vertex> = Vec::new();

        for c in &self.connections {
            if c.peers.0 == *vertex {
                neighbours.push(&c.peers.1);
            } else if c.peers.1 == *vertex {
                neighbours.push(&c.peers.0);
            }
        }

        neighbours
    }

    fn vertices_from_connections(conns : &Vec<Connection>) -> Vec<Vertex> {
        let mut verts : Vec<Vertex> = Vec::new();

        for c in conns.iter() {
            if ! verts.contains(&c.peers.0) {
                verts.push(c.peers.0);
            }
            if ! verts.contains(&c.peers.1) {
                verts.push(c.peers.1);
            }
        }
        verts
    }

    fn new(conns: Vec<Connection>) -> Graph {
        Graph {
            vertices    : Graph::vertices_from_connections(&conns),
            connections : conns,
        }
    }

    fn dijkstra(&self, start: Vertex) -> DijkstraTable {
        let mut table = DijkstraTable {
            start_vertex : start,
            roads        : Vec::new(),
            unvisited    : self.vertices.clone(),
        };

        for v in &self.vertices {
            let mut road = Road::new(*v);

            if v == &start {
                road.distance = 0;
            }

            table.roads.push(road);
        }

        loop {
            let xx = table.clone();
            match xx.get_next_unvisited() {
                None => break,
                Some(v) => {
                    //println!("{}##################",v);
                    for n in self.get_neighbours(v) {
                        match table.get_road_mut(n) {
                            None => println!("Error"),
                            Some(rn) => {
                                let d = self.get_weight((*v, *n));
                                let k = d + xx.get_distance(*v);
                                if k < rn.distance {
                                    rn.via_vertex = *v;
                                    rn.distance = k;
                                }
                            }
                        }
                    }
                    table.remove(v);
                    //println!(" {:#?} ", table);
                }
            }
        }

        table
    }
}

fn main() {
    let graph = Graph::new(
        vec![
            Connection {
                peers: ('A', 'B'),
                weight: 6,
            },
            Connection {
                peers: ('A', 'D'),
                weight: 1,
            },
            Connection {
                peers: ('D', 'E'),
                weight: 1,
            },
            Connection {
                peers: ('D', 'B'),
                weight: 2,
            },
            Connection {
                peers: ('E', 'B'),
                weight: 2,
            },
            Connection {
                peers: ('E', 'C'),
                weight: 5,
            },
            Connection {
                peers: ('B', 'C'),
                weight: 5,
            },
        ]
    );

    println!(" Dijkstra of 'A': {:#?}", graph.dijkstra('A'));

}

Edit:

The code and feedbacks are pushed to this github repo.

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

Many of your methods can be simplified (?) with iterators. Here's a few examples:


fn get_distance(&self, vertex: Vertex) -> u32 {
    let mut ret = 0;

    for r in &self.roads {
        if r.vertex == vertex {
            ret = r.distance;
        }
    }

    ret
}

becomes

fn get_distance(&self, vertex: Vertex) -> u32 {
    self.roads
        .iter()
        .rev()
        .find(|road| road.vertex == vertex)
        .map(|road| road.distance)
        .unwrap_or(0)
}

fn get_road_mut(&mut self, vertex: &Vertex) -> Option<&mut Road> {
    for r in &mut self.roads {
        if r.vertex == *vertex {
            return Some(r);
        }
    }

    None
}

becomes

fn get_road_mut(&mut self, vertex: &Vertex) -> Option<&mut Road> {
    self.roads
        .iter_mut()
        .find(|road| road.vertex == vertex)
}

fn remove(&mut self, v : &Vertex) {
    let mut index = 0;
    while index < self.unvisited.len() {
        let toremove = &self.unvisited[index];
        if v == toremove {
            self.unvisited.remove(index);
            break
        }
        index += 1;
    }
}

becomes

fn remove(&mut self, v: &Vertex) {
    let index = self.unvisited.iter().position(|vertex| vertex == v);
    if let Some(index) = index {
        self.unvisited.remove(index);
    }
}
\$\endgroup\$
5
  • \$\begingroup\$ Thanks @L.F. now the code looks more rust idiomatic. \$\endgroup\$
    – Zskdan
    Aug 13, 2020 at 10:03
  • \$\begingroup\$ The new remove() code trig a compilation issue since iterator::position return an Option. So I had to adapt it to: match self.unvisited.iter().position(|vertex| vertex==v) { None => (), Some(index) => { self.unvisited.remove(index); } } \$\endgroup\$
    – Zskdan
    Aug 13, 2020 at 11:38
  • \$\begingroup\$ @Zskdan That's right. I've modified the code. \$\endgroup\$
    – L. F.
    Aug 13, 2020 at 11:53
  • \$\begingroup\$ I'm not sure of understanding the syntax of the new code: Does let Some(index) = index is handled as condition which return False in case of index == None and True otherwise? \$\endgroup\$
    – Zskdan
    Aug 13, 2020 at 11:58
  • \$\begingroup\$ Yes. if let is a control flow that works the way you described - enter the block if the let binding matches. \$\endgroup\$
    – L. F.
    Aug 13, 2020 at 12:54
1
\$\begingroup\$

The call to clone() in Graph::dijkstra feels wrong. Without actually re-factoring the code, I am not sure of the solution, I can see you have some problems with borrowing / mut.

My intuition is that you need to make the method that constructs DijkstraTable a method of DijkstraTable rather than Graph. It would take a (non-mutable) reference to the Graph.

Edit:

After taking a much closer look, I made some changes to eliminate the cloning ( the #derive(Clone)s are no longer needed ), and other changes:

type Vertex = char;

#[derive(Debug)]
struct Connection {
    peers   : (Vertex, Vertex),
    weight  : u32,
}

#[derive(Debug)]
struct Graph {
    connections : Vec<Connection>,
    vertices    : Vec<Vertex>,
}

#[derive(Debug)]
struct Road {
    vertex     : Vertex,
    distance   : u32,
    via_vertex : Vertex,
}

#[derive(Debug)]
struct DijkstraTable {
    start_vertex : Vertex,
    roads        : Vec<Road>,
    unvisited    : Vec<Vertex>,
}

impl DijkstraTable {
    fn get_distance(&self, vertex: Vertex) -> u32 {
        let mut ret = 0;

        for r in &self.roads {
            if r.vertex == vertex {
                ret = r.distance;
            }
        }

        ret
    }

    fn get_next_unvisited(&self) -> Option<Vertex> {
        let mut min = u32::MAX;
        let mut next = None;

        for vertex in &self.unvisited {
            for r in &self.roads
            {
              if r.vertex == *vertex 
              {
                if r.distance < min {
                  min = r.distance;
                  next = Some(*vertex);
                }
              }
            }
        }
        next
    }

    fn remove(&mut self, v : Vertex) {
        let mut index = 0;
        while index < self.unvisited.len() {
            let toremove = self.unvisited[index];
            if v == toremove {
                self.unvisited.remove(index);
                break
            }
            index += 1;
        }
    }


    fn new( graph: &Graph, start: Vertex ) -> DijkstraTable {
        let mut table = DijkstraTable {
            start_vertex : start,
            roads        : Vec::new(),
            unvisited    : graph.vertices.clone(),
        };

        for v in &graph.vertices {
            let mut road = Road::new(*v);

            if *v == start {
                road.distance = 0;
            }

            table.roads.push(road);
        }

        loop {
            match table.get_next_unvisited() {
                None => break,
                Some(v) => {
                    //println!("{}##################",v);

                    for n in graph.get_neighbours(v) {
                      let d = graph.get_weight((v, n));
                      let k = d + table.get_distance(v);
                      for road in &mut table.roads
                      {         
                        if road.vertex == n
                        {
                          if k < road.distance {
                            road.via_vertex = v;
                            road.distance = k;
                          }
                          break;
                        }
                      }
                    }
                    table.remove(v);
                    // println!(" {:#?} ", table);
                }
            }
        }
        table
    }
}

impl Road {
    fn new(from: Vertex) -> Road {
        Road {
            vertex      : from,
            distance    : u32::MAX,
            via_vertex  : '-',
        }
    }
}

impl Graph {
    fn get_weight(&self, peers: (Vertex, Vertex)) -> u32 {
        let mut ret : u32 = 0;

        for c in &self.connections {
            let (a, b) = peers;

            if c.peers == peers || c.peers == (b, a) {
                ret = c.weight;
                break;
            }
        }
        ret
    }

    fn get_neighbours(&self, vertex: Vertex) -> Vec<Vertex> {
        let mut neighbours : Vec<Vertex> = Vec::new();

        for c in &self.connections {
            if c.peers.0 == vertex {
                neighbours.push(c.peers.1);
            } else if c.peers.1 == vertex {
                neighbours.push(c.peers.0);
            }
        }

        neighbours
    }

    fn vertices_from_connections(conns : &Vec<Connection>) -> Vec<Vertex> {
        let mut verts : Vec<Vertex> = Vec::new();

        for c in conns.iter() {
            if ! verts.contains(&c.peers.0) {
                verts.push(c.peers.0);
            }
            if ! verts.contains(&c.peers.1) {
                verts.push(c.peers.1);
            }
        }
        verts
    }

    fn new(conns: Vec<Connection>) -> Graph {
        Graph {
            vertices    : Graph::vertices_from_connections(&conns),
            connections : conns,
        }
    }
}

fn main() {
    let graph = Graph::new(
        vec![
            Connection {
                peers: ('A', 'B'),
                weight: 6,
            },
            Connection {
                peers: ('A', 'D'),
                weight: 1,
            },
            Connection {
                peers: ('D', 'E'),
                weight: 1,
            },
            Connection {
                peers: ('D', 'B'),
                weight: 2,
            },
            Connection {
                peers: ('E', 'B'),
                weight: 2,
            },
            Connection {
                peers: ('E', 'C'),
                weight: 5,
            },
            Connection {
                peers: ('B', 'C'),
                weight: 5,
            },
        ]
    );
    let dt = DijkstraTable::new( &graph, 'A' );
    println!(" Dijkstra of 'A': {:#?}", dt );
}

I ought ideally to explain the changes in more detail, but I hope the above helps. In particular you had functions returning &Vertex rather than simply Vertex, which I think caused problems. Also, I have eliminated the functions get_road_mut and get_road. I'm not sure if this was strictly necessary or not, but having functions that return references is I think generally problematic.

Edit 2:

It is possible to have a function get_road that returns a mutable reference:

fn get_road(&mut self,  n: Vertex) -> &mut Road
{
  for road in &mut self.roads
  {         
    if road.vertex == n { return road; }
  }
  panic!("Road not found");
}

Which is used like this:

                  let road = table.get_road( n );
                  if k < road.distance {
                    road.via_vertex = v;
                    road.distance = k;
                  }  

Besides, since we have a keyed set of values, it may be easier to use a Hash Map.

\$\endgroup\$
4
  • \$\begingroup\$ Indeed I was forced to do the clone() to handle ownership issues (Cannot borrow as immutable because it is also borrowed as mutable). I think you're right, It seems now (After reading your comment) obvious that I should move dijkstra() method to DijkstraTable. I'll try that. Thanks @George for your feedback. \$\endgroup\$
    – Zskdan
    Aug 12, 2020 at 12:19
  • \$\begingroup\$ Your changes makes the code more clear and clean. In fact I still don't feel comfortable with references. And when should I return references. With get_road_mut and get_road I was hoping to factorize them in a single call. But this seems not possible since they are returning different object type. Can you please elaborate on why having functions that return references is problematic ? \$\endgroup\$
    – Zskdan
    Aug 12, 2020 at 12:49
  • \$\begingroup\$ The reason is that the lifetime of the return value will be limited, also returning a mutable reference ( allowing part of a struct to be modified ) feels not quite right to me, but it is possible, see my latest edit to my answer above. \$\endgroup\$ Aug 12, 2020 at 13:39
  • \$\begingroup\$ My understanding of returning references is that the lifetime will be rather guaranteed by the compiler. And they may be helpful to avoid wasting memory on copying the object -like returning pointer in C- (so it worth it for Road object but not for Vertex(char)). \$\endgroup\$
    – Zskdan
    Aug 12, 2020 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.