Graphs
# SIMPLE GRAPHS
# -------------
# Concept:
# - A graph is a data structure used to represent relationships.
# - It is made of: vertices (nodes) and edges (relationships).
#
# Unline stacks of queue:
# - There is NO top or front
# - connections can be many-to-many
#
# Real-life graphs:
# - social networks
# - flight routes
# - recommendations systems
#
# Example: Friend relationships
# - We use a dictionary
# - Each key is a vertex
# - Each list contains connected vertices
# - Connections are biderectional
# -----------------------------------------
friends = {
'Alice': ['Bob', 'Diana', 'Fred'],
'Bob': ['Alice', 'Cynthia', 'Diana'],
'Cynthia': ['Bob'],
'Diana': ['Alice', 'Bob', 'Fred'],
'Elise': ['Fred'],
'Fred': ['Alice', 'Diana', 'Elise'],
}
print("Alice's friends:", friends['Alice'])
# -----------------------------------------
# Alice's friends: ['Bob', 'Diana', 'Fred']
Directed Graphs
# DIRECTED GRAPHS
# ---------------
# Relationships are not always mutual.
# In directed graphs connection is one-way.
#
# Example: Social medial follows:
# - Alice follows Bob
# - Bob does not have to follow Alice
# -------------------------------------
followees = {}
followees['Alice'] = ['Bob', 'Diana']
followees['Bob'] = ['Cynthia']
followees['Cynthia'] = ['Bob']
assert 'Bob' in followees['Alice']
assert 'Alice' not in followees['Bob']
print("Bob is following Alice")
print("Alice is not following Bob")
# ---------------------------------
# Bob is following Alice
# Alice is not following Bob
Object Oriented Graphs
# OBJECT ORIENTED GRAPHS
# ----------------------
# Dictionary are great for simple graphs.
#
# Sometimes we need objects that provide us:
# - behavior
# - encapsulation
# - clear relationships
#
# Example:
# - Friend relationships (mutual)
# ---------------------------------
class Vertex:
def __init__(self, name):
self.value = name
self.adjacent_vertices = [] # LIST
def add_adjacent(self, vertex):
# Add connection
self.adjacent_vertices.append(vertex)
# Ensure mutual relationship
if self not in vertex.adjacent_vertices:
vertex.adjacent_vertices.append(self)
a = Vertex("Alice")
b = Vertex("Bob")
c = Vertex("Cynthia")
a.add_adjacent(b)
a.add_adjacent(c)
b.add_adjacent(c)
print("A neighbours:", [v.value for v in a.adjacent_vertices])
print("B neighbours:", [v.value for v in b.adjacent_vertices])
# ----------------------------------
# A neighbours: ['Bob', 'Cynthia']
# B neighbours: ['Alice', 'Cynthia']
Weighted Graphs
# WEIGHTED GRAPHS
#----------------
# Concept:
# - In some graphs, connections have values:
# (distance, cost, time, price)
#
# Example:
# - Flights between cities
#
# Vertices:
# - Dallas -> Toronto costs $138
# - Toronto -> Dalls costs $216
#
# Direction and cost both matters
# -------------------------------
class WeightedVertex:
def __init__(self, value):
self.value = value
self.adjacent_vertices = {} # DICT
def add_adjacent(self, vertex, price):
self.adjacent_vertices[vertex.value] = price
d = WeightedVertex('Dallas')
t = WeightedVertex('Toronto')
d.add_adjacent(t, 138)
t.add_adjacent(d, 216)
print('Dallas flights:', d.adjacent_vertices)
print('Toronto flights:', t.adjacent_vertices)
# --------------------------------------------
# Dallas flights: {'Toronto': 138}
# Toronto flights: {'Dallas': 216}
