Graph algorithms demystified #1

Simplest way to model a Graph or Tree

Photo by Nick Fewings on Unsplash

Disclaimer: The code examples are in Scala but they will be simple enough and without any advanced features such that anyone can understand them. I am planing to run this series in multiple languages because the problems demystified here are language agnostic

Disclaimer: The code examples are in Scala but they will be simple enough and without any advanced features such that anyone can understand them. I am planing to run this series in multiple languages because the problems demystified here are language agnostic

Context (you can skip that section and go to Code example directly, then come back here):

Lets say we want to create a simple Graph that will contain unique String values, like unique names

Each unique name will represent a person

Lets assume that this graph will hold only one type of relation:

person ---(knows)---> person

Lets make it even simpler, our Graph will be one directional:

if A knows B it does not mean that B knows A

So this graph will not be generic, it will be very limited

In what scenarios in a real world we would use such a simplified graph?

We may need that graph to perform some local operations to solve a very specific problem within a function scope that may not need all the features of a sophisticated Graph

But i think this is a very good example to understand Graph and Trees by starting with such a limited and simple examples

Lets have a algo that will answer the following questions

• does person A knows B
• can person A meet B which means can we find a one directional path between A and B

A person with assigned unique name can get to other only via people that they know already

So it sounds almost like a game with made up rules: Graph represent people in the room, each person have unique name assigned, in a game round each named person knows others and they can get to each other only directly or via other friend

Sounds fun!!

Code Example:

One of the simplest way to represent it is as Map of String to list of Strings:

Map[String, List[String]]

Lets create some example graph with the data described in context section

val PeopleInTheRoom: Map[String, List[String]] = Map(
  "Jane" -> List("Bob", "Mark", "Rajesh", "Samanta", "Hussein"),
  "Mark" -> List("Tom"),
  "Bob" -> List("Lisa", "Jenny"),
  "Tom" -> Nil,
  "Lisa" -> Nil,
  "Jenny" -> Nil
)

Now lets ask questions:

• does Jane knows Mark: yes
• does Jane knows Jenny: no
• can Jane meet Jenny: yes
• does Bob knows Jane: no
• can Bob meet Jane: no

How to write code to answer those questions will be in the following episode of Graph algorithms demystified series

Side note: the same way we can model a binary tree or b-tree

val binaryTree: Map[Int, List[Int]] = Map(
  5 -> List(4, 2),
  4 -> Nil,
  2 -> List(0, 3),
  4 -> List(-1)
)

We can assume that each map entry will be a list with max size 2, 1st element of list is left node 2nd element of the list is right node

I will describe it in more detail in another following episodes of Graph algorithms demystified

What do you think ? Let me know in comments below to help me improve this article

Thanks for reading!