PART I

Introduction to Graphs

  • What is a graph
  • Nodes, Edges, Directions, Weghts

Not about

Charts and Grafs

Nodes represent objects

(e.g. people, cities, countries, computers).

Nodes can be called vertices as well.

Edges represent relationships

(e.g. friendship, connectedness)

Graphs can be called networks as well.

Direction of relationships

(e.g. A follows B, A is a student of B)

Does it remind you something?

Blood donation

O- can donate blood to anybody. AB+ can donate blood only to themselves.

Position of nodes

Does not change semantics of the graph

Edge weights

(e.g. cost of travel, distance, energy to transition)

In a directional graph cost in one direction could be different than back (e.g. going up hill and downhill).

Node degree

Number of edges incident on a node.

degree(“1”) = 3; degree(“3”) = 4. What is your node degree on LinkedIn?

PART II

Graph representation

  • Edge list
  • Adjacency list
  • Adjacency matrix
  • Graphs in Python

Edge list

[Edge1, Edge2, Edge3, Edge4]

Edge1 = [Node1, Node2]

edge_list = [[0,1],[1,2],[1,3],[2,3]]

Adjacency list

[Node1Conns, Node2Conns, Node3Conns, Node4Conns]

Node1Conns = [Node2, Node3]

adj_list = [[1],[0,2,3],[1,3],[1,2]]

Adjacency list

More efficient storage options for sparse graphs

adj_list = [[1],[0,2,3],[1,3],[1,2],[],[],[],[],[],[],[],[],[],[]]
adj_dict = {
  "v0": ["v1"],
  "v1": ["v0","v2","v3"],
  "v2": ["v1","v3"],
  "v3": ["v1","v2"]
}
adj_dict_weights = {
  "v0": {"v1":1},
  "v1": {"v0":1,"v2":1,"v3":1},
  "v2": {"v1":1,"v3":1},
  "v3": {"v1":1,"v2":1}
}

Adjacency matrix

Column names = Nodes, Row names = Nodes, Cells = Edges

adj_matrix = [
[0, 1, 0, 0],
[1, 0, 1, 1],
[0, 1, 0, 1],
[0, 1, 1, 0],
]

Adjacency matrix (non directional)

Cells are symmetrical across the main diagonal.

adj_matrix = [
[0, 1, 0, 0],
[1, 0, 1, 1],
[0, 1, 0, 1],
[0, 1, 1, 0],
]

Adjacency matrix (directional)

Cells can be not symmetrical across the main diagonal.

adj_matrix = [
[0, 1, 0, 0],
[1, 0, 1, 1],
[1, 0, 0, 1],
[0, 0, 0, 0],
]

Adjacency matrix (directional)

Cells can represent weights.

adj_matrix = [
[0, 1, 0, 0],
[1, 0, 3, 1],
[2, 0, 0, 1],
[0, 0, 0, 0],
]

Graph in Python

class Graph:
    def __init__(self, graph_dict = {}, directed = False):
        self.graph_dict = graph_dict
        self.directed = directed
    
    def __str__(self):
        M = self.getMatrix()
        S = '\n'.join([''.join(['{:4}'.format(item) for item in row]) for row in M])
        return "\n"+S+"\n"
    
    def nodes(self):
        return list(self.graph_dict.keys())
    
    def addNode(self, node_id):
        self.graph_dict[node_id] = {}
        return self
    
    def createEdge(self, node_idA, node_idB, weight = 1):
        nodeA_connections = self.graph_dict.get(node_idA)
        nodeA_connections.update({node_idB:weight})
        self.graph_dict.update({node_idA:nodeA_connections})
        return self
    def deleteEdge(self, node_idA, node_idB):
        del self.graph_dict[node_idA][node_idB]
    def removeEdge(self, node_idA, node_idB):
        self.deleteEdge(node_idA, node_idB)
        if (not self.directed):
            self.deleteEdge(node_idB, node_idA)
    def removeNode(self, node_id):
        connections = self.graph_dict[node_id]
        for node_adj in set(connections):
            self.deleteEdge(node_id,node_adj)
            self.deleteEdge(node_adj,node_id)
        del self.graph_dict[node_id]
    def addEdge(self, node_idA, node_idB, weight = 1):
        self.createEdge(node_idA, node_idB, weight)
        if (not self.directed):
            self.createEdge(node_idB, node_idA, weight)
        return self
    def getEdgeWeight(self, node_idA, node_idB):
        return self.graph_dict.get(node_idA).get(node_idB,0) 
    def getMatrix(self):
        matrix = [[self.getEdgeWeight(i,j) for j in self.nodes()] for i in self.nodes()] 
        return matrix

Graph in Python

graph = Graph()
graph.addNode("a")
graph.addNode("b")
graph.addNode("c")
print(graph)
#   0   0   0
#   0   0   0
#   0   0   0
graph.addEdge("a","b")
graph.addEdge("a","c")
print(graph)
#   0   1   1
#   1   0   0
#   1   0   0

Hands on

Let’s code.

code gist

PART III

Graph Types, Cycles, Paths

  • Graph Types
  • Traversal, Cycle

Types of graphs

Traversal

Process of visiting (checking and/or updating) each node in a graph.

Cycle

A closed path where all edges are different (0 - 1 - 3 - 2 - 0)

Trees can not have cycles. Graphs can have cycles.

Hamiltonian path

Path that visits each node exactly once. (0 - 2 - 3 - 1 - 0)

Hamiltonian cycle is Hamiltonian path which is a cycle.

Hamiltonian path

Example: a tourist visiting all attractions in the city and coming back to the train station where he started the trip.

Eulerian path

Path that visits each edge exactly once. (2 - 3 - 1 - 0 - 2 - 1)

Eulerian cycle is Eulerian path which is a cycle. (Not this case)

Eulerian path

Path that visits each edge exactly once. (2 - 3 - 1 - 0 - 2 - 1)

Example: a tourist going through all iconic attractions, without going over the same road again.

PART IV

Search problem

  • Searching how two nodes in a graph are connected is a typical problem.
  • It has a wide range of applications.

Finding a path in a maze

Such maze could be presented as a grid graph, with no connections, in places with walls.

Finding a path on a map

Points of interest are nodes. And roads are edges connecting points of interests.

Finding people who can introduce you on Linkedin

People are nodes. And edges are connections between them.

Search Algorithms

  • Breadth-first search (BFS)
  • Depth-first search (DFS)

Visualization of search algorithms:

Graph to Traverse

Start with Node 1 and see how BFS and DFS traverse the graph.

Breadth-first search (BFS)

Breadth-first search is an algorithm for traversing or searching tree or graph data structures. It starts at some arbitrary node of a graph and explores the neighbor nodes first, before moving to the next level neighbours.

Worst-case performance = O(|V| + |E|)

Breadth-first search (BFS) Step 1

All nodes are not visited (tomato color). The node 1 is current.

Breadth-first search (BFS) Step 2

We discover the neighbors of Node 1: Node 2,…

Breadth-first search (BFS) Step 3

We discover the neighbors of Node 1: Node 2, and Node 5.

Breadth-first search (BFS) Step 4

As we discovered all neighbors of Node 1, we mark Node 1 as visited (black) and go to make Node 2 as current.

Breadth-first search (BFS) Step 5

We discover the nodes of Node 2, which is only 3, as all others are already discovered or visited.

Breadth-first search (BFS) Step 6

We mark Node 2 as visited, and make Node 5 as the current node.

Breadth-first search (BFS) Step 7

The single not discovered neighbor of Node 5 is Node 4.

Breadth-first search (BFS) Step 8

We mark Node 5 as visited and make Node 3 as the current node.

Breadth-first search (BFS) Step 9

There are no more nodes to discover, so we mark Node 3 as visited and make Node 4 as the current one.

Breadth-first search (BFS) Step 10

With Node 4 we discover Node 6.

Breadth-first search (BFS) Step 11

We mark Node 4 as visited and make Node 6 as the current one.

Breadth-first search (BFS) Step 12

Node 6 does not have any more nodes to discover. We mark Node 6 as visited. No more nodes to visit. The algorithm is acomplished.

Online visualization

Breadth-first search initialization

\[ \begin{aligned} &Initialize(G,s)\\ &\qquad for \space each \space node \space u \in G.V - \{s\}\\ &\qquad \qquad u.color = WHITE\\ &\qquad \qquad u.d = \infty\\ &\qquad \qquad u.\pi = NIL\\ &\qquad s.color = GRAY \\ &\qquad s.d = 0\\ &\qquad s.\pi = NIL\\ &\qquad Q = \emptyset\\ &\qquad Enqueue(Q,s)\\ \end{aligned} \]

Breadth-first search algorithm

\[ \begin{aligned} &BFS(G,s)\\ &\qquad Initialize(G,s)\\ &\qquad while \space Q \neq \emptyset\\ &\qquad \qquad u = Dequeue(Q) \\ &\qquad \qquad for \space each \space v \in G.Adj[u] \\ &\qquad \qquad \qquad if \space v.color == WHITE\\ &\qquad \qquad \qquad \qquad v.color = GRAY\\ &\qquad \qquad \qquad \qquad v.d = u.d + 1\\ &\qquad \qquad \qquad \qquad v.\pi = u\\ &\qquad \qquad \qquad \qquad Enqueue(Q,v)\\ &\qquad \qquad u.color = BLACK\\ \end{aligned} \]

BFS - Python (initialization)

def initialize(graph, start = None):
    nodes_prop = {}
    for node in graph.keys():
        nodes_prop[node] = {
            "color": "white",
            "distance": float('inf'),
            "parent":None
        }
    nodes_prop[start] = {
        "color":"gray",
        "distance": 0,
        "parent": None,
    }
    Q = [start]
    return nodes_prop, Q

BFS - Python (algorithm)

def bfs(graph, start):
    nodes, queue = initialize(graph, start)
    while queue:
        u = queue.pop(0)
        for v in graph[u]:
            if nodes[v]["color"] == "white":
                nodes[v] = {
                    "color":"gray",
                    "distance": nodes[u]["distance"] + 1,
                    "parent": u
                }
                queue.append(v)
        nodes[u]["color"] = "black"
    return nodes

BFS - Python (get path)

def getPath(nodes, targetNode):
    current = targetNode
    path = []
    while nodes[current]["parent"]:
        path.append(nodes[current]["parent"])
        current = nodes[current]["parent"]
    return path

Depth-first search (DFS)

Breadth-first search is an algorithm for traversing graph data structures. One starts selecting some arbitrary node as the root and explores as far as possible along each branch before backtracking.

Worst-case performance O(|V| + |E|)

Depth-first search (BFS) Step 1

Node 1 is current (darkgreen). All other nodes are never visited (tomato color).

Depth-first search (BFS) Step 2

Node 1 is current (darkgreen). We discover node 2.

Depth-first search (BFS) Step 3

Node 2 is current (darkgreen).

Depth-first search (BFS) Step 4

Node 2 is current (darkgreen). We discover Node 3.

Depth-first search (BFS) Step 5

Node 3 is current (darkgreen).

Depth-first search (BFS) Step 6

Node 3 is current (darkgreen). We discover Node 4.

Depth-first search (BFS) Step 7

Node 4 is current (darkgreen).

Depth-first search (BFS) Step 8

Node 4 is current (darkgreen). We discover Node 5.

Depth-first search (BFS) Step 9

Node 5 is current (darkgreen). No nodes to discover.

Depth-first search (BFS) Step 10

Node 5 becomes visited. We go back to the node 4.

Depth-first search (BFS) Step 11

We go back to the node 4 and discover node 6.

Depth-first search (BFS) Step 12

Node 6 becomes current. No nodes to discover there.

Depth-first search (BFS) Step 13

Node 6 becomes visited. Node 4 becomes current.

Depth-first search (BFS) Step 14

Node 4 becomes visited. Node 3 becomes current.

Depth-first search (BFS) Step 15

Node 3 becomes visited. Node 2 becomes current.

Depth-first search (BFS) Step 16

Node 2 becomes visited. Node 1 becomes current.

Depth-first search (BFS) Step 17

Node 1 becomes visited. Algorithm finished.

Online visualization

Depth-first search initialization

\[ \begin{aligned} &DFS(G,s)\\ &\qquad for \space each \space node \space u \in G.V\\ &\qquad \qquad u.color = WHITE\\ &\qquad \qquad u.\pi = NIL\\ &\qquad time = 0 \\ &\qquad for \space each \space node \space u \in G.V\\ &\qquad \qquad if \space u.color == WHITE\\ &\qquad \qquad \qquad DFSVisit(G,u) \end{aligned} \]

Depth-first search algorithm

\[ \begin{aligned} &DFSVisit(G,u)\\ &\qquad time = time + 1 \\ &\qquad u.d = time \\ &\qquad u.color = GRAY \\ &\qquad for \space each \space v \in G.Adj[u]\\ &\qquad \qquad if \space v.color == WHITE\\ &\qquad \qquad \qquad v.\pi = u \\ &\qquad \qquad \qquad DFSVisit(G,v) \\ &\qquad u.color = BLACK \\ &\qquad time = time + 1 \\ &\qquad u.f = time \\ \end{aligned} \]

DFS - Python (initialization)

def dfs(graph):
    nodes_prop = {}
    for u in graph.keys():
        nodes_prop[u] = {
            "color":"white",
            "parent": None
        }
    global time
    time = 0
    for u in graph.keys():
        if nodes_prop[u]["color"] == "white":
            nodes_prop = dfs_visit(graph, nodes_prop, u)
    return nodes_prop

DFS - Python (algorithm)

def dfs_visit(graph, nodes_prop, u):
    global time
    time = time + 1
    nodes_prop[u]["distance"] = time
    nodes_prop[u]["color"] = "gray"
    for v in graph[u]:
        if nodes_prop[v]["color"] == "white":
            nodes_prop[v]["parent"] = u
            nodes_prop = dfs_visit(graph, nodes_prop, v)
    nodes_prop[u]["color"] = "black"
    time = time + 1
    nodes_prop[u]["finish"] = time
    return nodes_prop

Hands on

Let’s code.

code gist

REFERENCES