Introduction to Graphs

Part 1: Outline

  • What is a graph
  • Directions and cycles
  • Graph representation

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

Position of nodes

Does not change semantics of the graph

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).

Degree

Number of edges incident on a node.

degree(“1”) = 3; degree(“3”) = 4

Graph representation

We can define a graph using:

  • Edge list
  • Adjacency list
  • Adjacency matrix

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 graph.

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 graph.


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

Adjacency matrix

Directional graph with weights.


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

Part 2: Outline

  • Euler path, Hamiltonian path
  • Types of graphs
  • Centrality (e.g. betweenness, closeness, eigenvector, node)

Traversal

Cycle

A closed path in which all the 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.

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)

Types of graphs

  • Empty
  • Star
  • Tree
  • Ring
  • Full
  • Bipartite

Empty Graph

Star Graph

Tree Graph

Ring Graph

Full Graph

Bipartite Graph

Graph in Python

class Graph:
  def __init__(self, graph_dict=None):
    """ initializes a graph object 
        If no dictionary or None is given, 
        an empty dictionary will be used
    """
    if graph_dict == None:
        graph_dict = {}
    self.__graph_dict = graph_dict
  
  def vertices(self):
    """ returns the vertices of a graph """
    return list(self.__graph_dict.keys())
  
  def edges(self):
    """ returns the edges of a graph """
    return self.__generate_edges()
  
  def add_vertex(self, vertex):
    """ If the vertex "vertex" is not in 
        self.__graph_dict, a key "vertex" with an empty
        list as a value is added to the dictionary. 
        Otherwise nothing has to be done. 
    """
    if vertex not in self.__graph_dict:
        self.__graph_dict[vertex] = []
  
  def add_edge(self, edge):
    """ assumes that edge is of type set, tuple or list; 
        between two vertices can be multiple edges! 
    """
    edge = set(edge)
    (vertex1, vertex2) = tuple(edge)
    if vertex1 in self.__graph_dict:
        self.__graph_dict[vertex1].append(vertex2)
    else:
        self.__graph_dict[vertex1] = [vertex2]
  
  def __generate_edges(self):
    """ A static method generating the edges of the 
        graph "graph". Edges are represented as sets 
        with one (a loop back to the vertex) or two 
        vertices 
    """
    edges = []
    for vertex in self.__graph_dict:
        for neighbour in self.__graph_dict[vertex]:
            if {neighbour, vertex} not in edges:
                edges.append({vertex, neighbour})
    return edges
  
  def __str__(self):
    res = "vertices: "
    for k in self.__graph_dict:
        res += str(k) + " "
    res += "\nedges: "
    for edge in self.__generate_edges():
        res += str(edge) + " "
    return res

Search Algorithms for Graphs

Part 1

  • Breadth-first search
  • Depth-first search

Visualization of search algorithms:

Graph to Traverse

Breadth-first search (BFS) Step 1

Breadth-first search (BFS) Step 2

Breadth-first search (BFS) Step 3

Breadth-first search (BFS) Step 4

Breadth-first search (BFS) Step 5

Breadth-first search (BFS) Step 6

Breadth-first search (BFS) Step 7

Breadth-first search (BFS) Step 8

Breadth-first search (BFS) Step 9

Breadth-first search (BFS) Step 10

BFS - Python


def bfs(graph, s, target):
  for v in graph.nodes:
    v.distance = inf;
    v.color = white
    v.path = None
  s.color = gray
  s.distance = 0
  s.path = None
  Q = []
  Q.append(s)
  v = None
  while length(Q)>0 and v!= target:
    u = Q.pop()
    for v in u.adj_nodes:
      if v.color == white:
        v.color = gray
        v.distance = u.d +1
        v.path = u
        Q.append(v)
    u.color = Black

Depth-first search (DFS) Step 1

Depth-first search (DFS) Step 2

Depth-first search (DFS) Step 3

Depth-first search (DFS) Step 4

Depth-first search (DFS) Step 5

Depth-first search (DFS) Step 6

Depth-first search (DFS) Step 7

Depth-first search (DFS) Step 8

Depth-first search (DFS) Step 9

Depth-first search (DFS) Step 10

Depth-first search (DFS)

def dfs(graph):
  for v in graph.nodes:
    u.color = white
    u.path = None
  time = 0
  for v in graph.nodes:
    if u.color == white:
      dfs_visit(graph, u)

def dfs_visit(graph, u):
  time = time + 1
  u.distance = time
  u.color = gray
  for v in u.adj_nodes:
    if v.color == white:
      v.path = u
      dfs_visit(graph, v)
  u.color = black
  time = time = 1
  u.f = time

Part 2

  • Shortest path. Dijkstra algorithm.
  • All-pairs shortest path.
  • Recap of the material