Graphs
A graphs is a data structure specialized in relationships.
friends = {
'Alice': ['Bob', 'Diana', 'Fred'],
'Bob': ['Alice', 'Cynthia', 'Diana'],
'Cynthia': ['Bob'],
'Diana': ['Alice', 'Bob', 'Fred'],
'Elise': ['Fred'],
'Fred': ['Alice', 'Diana', 'Elise'],
}
print(friends['Alice'])
# ['Bob', 'Diana', 'Fred']
Directed Graphs
Relationships are not always mutual.
followees = {
'Alice': ['Bob', 'Diana'],
'Bob': ['Cynthia'],
'Cynthia': ['Bob'],
}
assert 'Bob' in followees['Alice']
assert 'Alice' not in followees['Bob']
Object Oriented
We can implement an undirected graph using an object oriented approach.
class Vertex:
def __init__(self, name):
self.value = name
self.adjacent_vertices = []
def add_adjacent(self, vertex):
self.adjacent_vertices.append(vertex)
# if the friendship is mutual (undirected graph),
# we automatically add self vertix
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)
c.add_adjacent(b)
print('Alice vertices:', [x.value for x in a.adjacent_vertices])
print('Bob vertices:', [x.value for x in b.adjacent_vertices])
"""
Alice vertices: ['Bob', 'Cynthia']
Bob vertices: ['Alice', 'Cynthia']
"""
Weighted Graphs
This type of graph adds additional information to the edges of the graph.
class WeightedVertex:
def __init__(self, value):
self.value = value
self.adjacent_vertices = {}
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 =>', d.adjacent_vertices)
print('Toronto =>', t.adjacent_vertices)
"""
Dallas => {'Toronto': 138}
Toronto => {'Dallas': 216}
"""
Last update: 352 days ago