<Back

About graphs, simply.

In this article, we will begin our acquaintance with graphs, get acquainted with the breadth-first search algorithm (BFS) and implement the graph in the Rust programming language.

What is a graph?

The graph reproduces a set of connections. Imagine that there is Mark, who has heard a lot about Eva and now wants to get to meet her. Mark has two friends, Alice and Andrew. Alice knows Eve through her friend Monika, and Andrew knows Eve directly. Such formulations of connections are difficult to perceive, but you can easily display this connection using a graph. Arrows show the direction of connections: Mark friends with Alice and Andrew, Alice friends with Monika, etc.

Each graph consists of nodes and edges.

Types of graphs

There are many types of graphs, here are some of them:

• undirected;
• oriented;
• multigraph;
• pseudograph.

Let's look at their graphical representation.

Representation of graphs in code

There are four main methods of graph representation. The choice of representation is determined by the conditions of a specific task. They differ in the amount of memory occupied and the speed of operations on graphs. There are different combinations of graph components:

• The adjacency matrix of the graph (or the matrix of weights of the graph).
• Structures (lists) of adjacent graph vertices.
• The incidence matrix of the graph: vertex–edges.
• List of edges of the graph.

The adjacency matrix and lists of adjacent vertices are most often used. However, it should be emphasized that with a small number of nodes ~ 10, the representation does not matter.

In the following examples, I will use the adjacency matrix, but in the work use the representation that is most effective for your task.

The adjacency matrix of a graph with n nodes is called the matrix Anxn, whose elements:

• If node i is adjacent to node j, then the value = 1.
• If node i is not adjacent to node j, then the value = 0.
• If there are k number of edges coming from the node, then the value = k.
• If the node has v loops, then the corresponding value on the diagonal = v, if without loops = 0.

This is how the matrix for graphs from the previous section will look like:

In a directed graph, both 0 and -1 can be used to indicate the occurrence of a node. For example, for the second graph, in the figure above, the edge (3,1) can be denoted in the matrix either -1 or 0. In the examples I will use 0.

Let's implement the matrix in the Rust programming language.

use std::fmt::{Display, Formatter, Result, Write};
use std::ops::{Index, IndexMut};
use std::vec;

#[derive(Clone)]
pub struct Row {
    data: Vec<i32>,
}


impl Row {
    pub fn new(size: usize, filler: i32) -> Self {
        Self {
            data: vec![filler; size],
        }
    }
}


impl Index<usize> for Row {
    type Output = i32;
    fn index(&self, index: usize) -> &Self::Output {
        &self.data[index]
    }
}


impl IndexMut<usize> for Row {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        &mut self.data[index]
    }
}


impl Display for Row {
    fn fmt(&self, f: &mut Formatter) -> Result {
        let mut str_row = String::new();
        self.data
            .iter()
            .for_each(|c| write!(&mut str_row, "{} ", c).unwrap());
        write!(f, "{}", str_row.trim_end())
    }
}

Well, now we describe the structure of the matrix and the basic functions for working with adjacent nodes.

pub struct Matrix {
    /// Number of nodespub n: usize,
    data: Vec<Row>,
}

impl Index<usize> for Matrix {
    type Output = Row;
    fn index(&self, index: usize) -> &Self::Output {
        &self.data[index]
    }
}

impl IndexMut<usize> for Matrix {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        &mut self.data[index]
    }
}

impl Matrix {
    
    /// Creates a new instance of Matrix

    /// with n nodes

    pub fn new(nodes: usize, filler: i32) -> Self {    
        Self {
            n: nodes,
            data: vec![Row::new(nodes, filler); nodes],
        }
    }
}

impl Matrix {
    
    /// Adds a weighted edge

    pub fn add_weighted_edge(&mut self, n: usize, m: usize, val: i32) {
        self[n][m] = val;
    }

    /// Adds a directed edge without weight

    pub fn add_directed_edge(&mut self, n: usize, m: usize) {
        self.add_weighted_edge(n, m, 1);
        self.add_weighted_edge(m, n, -1);
    }

    /// Adds a directed edge with weight

    pub fn add_w_directed_edge(&mut self, n: usize, m: usize, w: i32) {
        self.add_weighted_edge(n, m, w);
        self.add_weighted_edge(m, n, -w);
    }

    /// Adds an undirected edge

    pub fn add_undirected_edge(&mut self, n: usize, m: usize) {
        self.add_weighted_edge(n, m, 1);
        self.add_weighted_edge(m, n, 1);
    }
}

impl Matrix {
    
    /// Returns true if some node has adjacent nodes

    pub fn has_adjs(&self, node: usize) -> bool {
        !self.get_adjs(node).is_empty()
    }

    /// Returns adjacent nodes

    pub fn get_adjs(&self, node: usize) -> Vec<usize> {
        let mut adjs = vec![];
        for j in 0..self.n {
            if self[node][j] > 0 {
                adjs.push(j);
            }
        }
        adjs
    }

    /// Returns adjacent nodes count

    pub fn adjs_count(&self, node: usize) -> usize {
        self.get_adjs(node).len()
    }
}

impl Display for Matrix {
    fn fmt(&self, f: &mut Formatter) -> Result {
        let mut matrix = String::new();
        if !self.data.is_empty() {
            for row in &self.data {
                matrix.push_str(&row.to_string());
                matrix.push('\n');
            }
        } else {
            matrix = String::from("Matrix is empty!");
        }
        write!(f, "{}", matrix)
    }
}

impl Matrix {
    pub fn bfs(&self, starter_node: usize, target_node: usize) -> bool {
        let mut queue = vec![];
        queue.push(starter_node);
        let mut searched = vec![];
        while !queue.is_empty() {
            let node = queue.remove(0);
            if !searched.contains(&node) {
                if node == target_node {
                    println!("The target node was found!");
                    println!("Searched: {:?}", searched);
                    return true;
                } else {
                    queue.extend(self.get_adjs(node));
                    searched.push(node);
                }
                println!("Node: {:?}", node);
                println!("Q: {:?}\n", queue);
            }
        }
        return false;
    }
}

Now is the time to consider one of the graph traversal algorithms - "Breadth-first Search".

BFS algorithm

This algorithm allows us to answer two questions:

1. Is there a path from one node to another?
2. Which is the shortest way?

Let's assume that our task is to find an influencer in the field of programming, among our friends and their friends who form a network of contacts. This is what our network looks like:

There are two influencers in our network of contacts: Marcus and Angelina, but we still don't about this.

We need to answer two questions:

1. Is there an influencer in our network?
2. What is the shortest way to the influencer?

Our graph has levels, let's reflect on them.

The algorithm starts from level one and moves on to the next levels as needed.

Abstractly, the algorithm looks like this:

1. We ask Mark and Russell if they are influencers. If one of them is an influencer, then we stop the algorithm on the first found influencer. If there are no influencers among them, then we ask them to share the question with their friends. Mark and Russell are not influencers, we go to their friends to the next level.
2. Mark and Russell ask Peter and Marcus if they are influencers. If one of them is an influencer, then we stop the algorithm on the first found influencer. If there are no influencers among them, then we ask you to repeat the request among their friends. Marcus is an influencer, so we stop the algorithm.

Let's program the implementation. We will use recursion, since it is clear from the text above that they perform the same action.

Let's program the implementation. We will use queues.

impl Matrix {
    pub fn bfs(&self, starter_node: usize, target_node: usize) -> bool {
        let mut queue = vec![];
        queue.push(starter_node);
        let mut searched = vec![];
        while !queue.is_empty() {
            let node = queue.remove(0);
            if !searched.contains(&node) {
                if node == target_node {
                    println!("The target node was found!");
                    println!("Searched: {:?}", searched);
                    return true;
                } else {
                    queue.extend(self.get_adjs(node));
                    searched.push(node);
                }
                println!("Node: {:?}", node);
                println!("Q: {:?}\n", queue);
            }
        }
        return false;
    }
}

Well, now let's create our graph and go through it with a search in width.

fn main() {
    // Node 0 - Me

    // Node 1 - Russell

    // Node 2 - Mark

    // Node 4 - Marcus

    // Node 3 - Peter

    // Node 5 - Angelina

    let mut graph: Matrix = Matrix::new(6, 0);
    graph.add_directed_edge(0, 1);
    graph.add_directed_edge(0, 2);
    graph.add_directed_edge(1, 4);
    graph.add_directed_edge(2, 3);
    graph.add_directed_edge(3, 5);
    graph.bfs(0, 4);
}

And this is what we get at the output:

Node: 0
Q: [1, 2]

Node: 1
Q: [2, 4]

Node: 2
Q: [4, 3]

The target node was found!
Searched: [0, 1, 2]

After passing the first level, nodes 1 and 2, the first in the queue was the desired node 4, which the algorithm reported and stopped its execution.

The source code can be found in my repository: https://github.com/arg2u/graphula

Conclusion

A graph is one of the fundamental structures for programmers. It is used for modeling different relations between objects.

Different graphics algorithms help to find a short path from A to B in the navigation maps, to find the most effective solution in complex systems and others.