import typing
import utils
#
# 1. https://www.python-course.eu/graphs_python.php
# 2. https://levelup.gitconnected.com/graphs-101-67581c17178d
# 3. https://ibrooffice.medium.com/introduction-to-graph-theory-implementation-of-the-graph-using-the-python-language-11af1ce4669
# 4. https://www.educative.io/edpresso/how-to-implement-a-breadth-first-search-in-python
# 5. https://www.educative.io/edpresso/how-to-implement-depth-first-search-in-python
# 6. https://www.programiz.com/dsa/bellman-ford-algorithm
# 7. https://www.geeksforgeeks.org/building-an-undirected-graph-and-finding-shortest-path-using-dictionaries-in-python/
# 8. https://www.youtube.com/watch?v=ne9eZ4ezg0Y
# 9. https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture14.pdf
# 10. https://www.techiedelight.com/determine-negative-weight-cycle-graph
# 11. https://www.youtube.com/watch?v=HDUzBEG1GlA
# 12. https://www.manning.com/books/grokking-algorithms
# 13. https://stackabuse.com/courses/graphs-in-python-theory-and-implementation/
#
# A graph is a data structure that consists of vertices that are connected via edges.
# The nodes are the Vertices & the lines-between-them are the Edges.
# Searching a graph means following the edges of the graph so as to visit the vertices of the graph.
#
# Graphs can be represented in three main ways;
# 1. adjacency lists (Space efficient): graph = {'A': [('B', 4)], 'B': [('A', 4), ('D', 5)]}
# 2. adjacency matrix (Less space efficient)
# 3. edge lists (Simple and easy to understand)
# We'll use edge lists method. adjacency lists are used in chapter 22 of Cormen et al.
# A. Undirected, Unweighted graph; G = (V,E)
# / [1] \
# / | \
# / | \
# [4] | [2]
# \ | /
# \ | /
# \ | /
# [3]
# B. Directed, Unweighted graph; G = (V,E)
# > [1] \
# / | \
# / | \>
# [4] | [2]
# <\ | /
# \ | /
# \ ↓ <
# [3]
# C. Directed, Weighted graph; G = (V,E)
# > [1] \
# 5/ | \ 1
# / | \>
# [4] |5 [2]
# <\ | /
# 7\ | / 3
# \ ↓ <
# [3]
# D. Ngative-weight-cycle; G = (V,E)
# This is when a cycle in a graph sums to a negative value.
# The graph below has a negative-weight-cycle. 1->2->3->1 sums upto -2
# [1] \
# ^ \ -3
# | \>
# -1 | [2]
# ^ /
# | / 2
# | <
# [3]
class Graph:
"""
A graph is a data structure that consists of vertices that are connected via edges.
The nodes are the Vertices & the lines-between-them are the Edges.
Searching a graph means following the edges of the graph so as to visit the vertices of the graph.
Graphs can be represented in three main ways;
1. adjacency lists (Space efficient)
2. adjacency matrix (Less space efficient)
3. edge lists (Simple and easy to understand)
We'll use edge lists method. adjacency lists are used in chapter 22 of Cormen et al.
This class uses edge lists representation.
We keep a master list of vertex objects.
1. Single-source shortest path alogs.
(a) BFS. O(V + E). It does not work for weighted graphs
(b) Dijkstra. O(V^2). Works for weighted graphs. It does not work for graphs with negative weights.
(c) Bellman-Ford. O(VE). Works for graphs with negative weights.
2. All-source shortest path algos.
(a) Floyd-Warshall. O(V^3)
This algos work for both directed and undirected graphs.
A negative-weight-cycle is when a cycle in a graph sums to a negative value.
This should not be confused with a graph having negative edges.
A graph can have negative edges without necessarily having a negative-weight-cycle
"""
def __init__(self) -> None:
# eg:
# [
# # src, dst, weight
# [1, 2, 1]
# [1, 3, 5]
# [2, 3, 3]
# ]
self.edgeList: typing.List[typing.List[int]] = []
def __repr__(self) -> str:
x = "Graph[ \n\tsrc, dst, weight"
for i in self.edgeList:
x = x + "\n\t{}".format(i)
x = x + "\n]"
return x
def add_edge(self, src, dst, weight, undirected=False):
"""
As a matter of fact any undirected graph is also a directed graph.
You just have to specify any edges {src, dst} twice (src, dst) and (dst, src)
- https://stackoverflow.com/a/14804529/2768067
"""
self.edgeList.append([src, dst, weight])
if undirected:
self.edgeList.append([dst, src, weight])
def get_neighbours(self, v):
n = []
for i in self.edgeList:
if i[0] == v:
n.append(i[1])
return n
def get_vertices(self):
vertices = set()
for n in self.edgeList:
vertices.add(n[0])
vertices.add(n[1])
return vertices
def bfs(self, start, goal=None):
"""
BFS for discovering all vertices that are reachable from `start`.
If `goal` is given, then it finds the shortest path between `start` & `goal`.
- see chapter 22.2 of Cormen et al.
"""
# O(V + E). v== vertices, e=edges.
# x in [] is a O(N). Whereas for a set() it is O(1). Consider using a set.
visited = []
queue = []
queue.append(start)
while queue:
v = queue.pop(0)
if v not in visited:
visited.append(v)
for neighbour in self.get_neighbours(v):
queue.append(neighbour)
if neighbour == goal:
if goal not in visited:
visited.append(goal)
return visited
if goal:
return []
return visited
def bellman_ford(self, start):
"""
https://www.youtube.com/watch?v=ne9eZ4ezg0Y
"""
# O(VE)
has_negative_weight_cycle = False
vertices = self.get_vertices()
# Step 1: fill the distance array and predecessor array
paths_length = {v: float("Inf") for v in vertices}
paths_length[start] = 0
paths = {v: [] for v in vertices}
paths[start] = [start]
# Step 2: relax edges
for _ in range(len(self.edgeList) - 1):
for src, dst, w in self.edgeList:
if paths_length[src] + w < paths_length[dst]:
paths_length[dst] = paths_length[src] + w
paths[dst] = paths[src] + [dst]
# Step 3: detect negative cycle
# means we cannot find the shortest distances
for src, dst, w in self.edgeList:
if paths_length[src] + w < paths_length[dst]:
has_negative_weight_cycle = True
return paths, paths_length, has_negative_weight_cycle
def floyd_warshall(self):
"""
As opposed to the other algos,
this is an all-source algo. Thus it doesn't take a vertex param
"""
# O(V^3)
has_negative_weight_cycle = False
vertices = self.get_vertices()
shortest_paths = {
(src, dst): float("inf") if src != dst else 0 for src in vertices for dst in vertices
}
for src, dst, w in self.edgeList:
shortest_paths[(src, dst)] = w
for k in vertices:
for src in vertices:
for dst in vertices:
shortest_paths[(src, dst)] = min(
shortest_paths[(src, dst)],
shortest_paths[(src, k)] + shortest_paths[(k, dst)],
)
if any(shortest_paths[(src, src)] < 0 for src in vertices):
has_negative_weight_cycle = True
return shortest_paths, has_negative_weight_cycle
def dfs(self, start, visited=None):
# O(V + E).
pass
def dijkstra(self):
# O(V^2)
pass
def reference_bfs(self, start):
"""
reference implementation from
https://www.educative.io/edpresso/how-to-implement-a-breadth-first-search-in-python
"""
visited = []
queue = []
visited.append(start)
queue.append(start)
while queue:
s = queue.pop(0)
for neighbour in self.get_neighbours(s):
if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)
return visited
def directed_weighted_graph():
# graph; dwg = (V,E)
# > [1] \
# 5/ | \ 1
# / | \>
# [4] |5 [2]
# <\ | /
# 7\ | / 3
# \ ↓ <
# [3]
dwg = Graph()
dwg.add_edge(1, 2, 1)
dwg.add_edge(1, 3, 5)
dwg.add_edge(2, 3, 3)
dwg.add_edge(3, 4, 7)
dwg.add_edge(4, 1, 5)
print("\n\t directed_weighted_graph: \n", dwg)
utils.assert_r("graph", dwg.edgeList, [[1, 2, 1], [1, 3, 5], [2, 3, 3], [3, 4, 7], [4, 1, 5]])
paths, paths_length, has_negative_weight_cycle = dwg.bellman_ford(1)
utils.assert_r("graph", paths, {1: [1], 2: [1, 2], 3: [1, 2, 3], 4: [1, 2, 3, 4]})
utils.assert_r("graph", paths_length, {1: 0, 2: 1, 3: 4, 4: 11})
utils.assert_r("graph", has_negative_weight_cycle, False)
paths, paths_length, has_negative_weight_cycle = dwg.bellman_ford(1)
utils.assert_r("graph", paths, {1: [1], 2: [1, 2], 3: [1, 2, 3], 4: [1, 2, 3, 4]})
utils.assert_r("graph", paths_length, {1: 0, 2: 1, 3: 4, 4: 11})
utils.assert_r("graph", has_negative_weight_cycle, False)
shortest_paths, has_negative_weight_cycle = dwg.floyd_warshall()
utils.assert_r(
"graph",
shortest_paths,
{
(1, 1): 0,
(1, 2): 1,
(1, 3): 4,
# The shortest path from vertex1 to vertex4 is 11
(1, 4): 11,
(2, 1): 15,
(2, 2): 0,
(2, 3): 3,
(2, 4): 10,
# The shortest path from vertex3 to vertex1 is 12
(3, 1): 12,
(3, 2): 13,
(3, 3): 0,
(3, 4): 7,
(4, 1): 5,
(4, 2): 6,
(4, 3): 9,
(4, 4): 0,
},
)
utils.assert_r("graph", has_negative_weight_cycle, False)
utils.assert_r("graph", dwg.bfs(start=1), [1, 2, 3, 4])
utils.assert_r("graph", dwg.bfs(start=4), [4, 1, 2, 3])
utils.assert_r("graph", dwg.bfs(start=1), dwg.reference_bfs(1))
utils.assert_r("graph", dwg.bfs(start=4), dwg.reference_bfs(4))
directed_weighted_graph()
def directed_weighted_graph_with_letter_vertices():
# Another example::
# graph; dwgl = (V,E)
# > [A] \
# 5/ | \ 1
# / | \> 2 3 12 66
# [D] |5 [B] -----> [E] -----> [F] -----> [G] -----> [H]
# <\ | / /
# 7\ | / 3 / 1
# \ ↓ < /
# [C] <-----------------------------
dwgl = Graph()
dwgl.add_edge("A", "B", 1)
dwgl.add_edge("A", "C", 5)
dwgl.add_edge("B", "C", 3)
dwgl.add_edge("C", "D", 7)
dwgl.add_edge("D", "A", 5)
dwgl.add_edge("B", "E", 2)
dwgl.add_edge("E", "F", 3)
dwgl.add_edge("F", "G", 12)
dwgl.add_edge("G", "C", 1)
dwgl.add_edge("G", "H", 66)
print("\n\tdirected_weighted_graph_with_letter_vertices: \n", dwgl)
# NB: BFS does not follow arrows. It moves in a breadth-first manner
utils.assert_r("graph", dwgl.bfs(start="G"), ["G", "C", "H", "D", "A", "B", "E", "F"])
utils.assert_r("graph", dwgl.bfs(start="G"), dwgl.reference_bfs("G"))
utils.assert_r("graph", dwgl.bfs(start="H"), ["H"])
utils.assert_r("graph", dwgl.bfs(start="H"), dwgl.reference_bfs("H"))
utils.assert_r("graph", dwgl.bfs(start="C", goal="G"), ["C", "D", "A", "B", "E", "F", "G"])
utils.assert_r("graph", dwgl.bfs(start="G", goal="H"), ["G", "H"])
utils.assert_r("graph", dwgl.bfs(start="H", goal="G"), [])
paths, paths_length, has_negative_weight_cycle = dwgl.bellman_ford("A")
utils.assert_r(
"graph",
paths,
{
"A": ["A"],
"C": ["A", "B", "C"],
"H": ["A", "B", "E", "F", "G", "H"],
"B": ["A", "B"],
"F": ["A", "B", "E", "F"],
"G": ["A", "B", "E", "F", "G"],
"E": ["A", "B", "E"],
"D": ["A", "B", "C", "D"],
},
)
utils.assert_r(
"graph", paths_length, {"A": 0, "C": 4, "H": 84, "B": 1, "F": 6, "G": 18, "E": 3, "D": 11}
)
utils.assert_r("graph", has_negative_weight_cycle, False)
directed_weighted_graph_with_letter_vertices()
def un_directed_weighted_graph():
# graph; udwg = (V,E). Undirected
# / [1] \
# 5/ | \ 1
# / | \
# [4] |5 [2]
# \ | /
# 7\ | / 3
# \ | /
# [3]
udwg = Graph()
udwg.add_edge(1, 2, 1, undirected=True)
udwg.add_edge(1, 3, 5, undirected=True)
udwg.add_edge(2, 3, 3, undirected=True)
udwg.add_edge(3, 4, 7, undirected=True)
udwg.add_edge(4, 1, 5, undirected=True)
print("\n\t un_directed_weighted_graph: \n", udwg)
paths, paths_length, has_negative_weight_cycle = udwg.bellman_ford(1)
utils.assert_r("graph", paths, {1: [1], 2: [1, 2], 3: [1, 2, 3], 4: [1, 4]})
utils.assert_r("graph", paths_length, {1: 0, 2: 1, 3: 4, 4: 5})
utils.assert_r("graph", has_negative_weight_cycle, False)
un_directed_weighted_graph()
def un_directed_weighted_graph_with_negative_weights():
# graph; udwgnw = (V,E).
# / [1] \
# -5/ | \ 1
# / | \
# [4] |5 [2]
# \ | /
# 7\ | / -3
# \ | /
# [3]
udwgnw = Graph()
udwgnw.add_edge(1, 2, 1, undirected=True)
udwgnw.add_edge(1, 3, 5, undirected=True)
udwgnw.add_edge(2, 3, -3, undirected=True)
udwgnw.add_edge(3, 4, 7, undirected=True)
udwgnw.add_edge(4, 1, -5, undirected=True)
print("\n\t un_directed_weighted_graph_with_negative_weights: \n", udwgnw)
paths, paths_length, has_negative_weight_cycle = udwgnw.bellman_ford(1)
utils.assert_r(
"graph",
paths,
{
1: [1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1],
2: [1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 2, 3, 2],
3: [1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 2, 3],
4: [1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4],
},
)
utils.assert_r("graph", paths_length, {1: -80, 2: -75, 3: -72, 4: -85})
utils.assert_r("graph", has_negative_weight_cycle, True)
un_directed_weighted_graph_with_negative_weights()
def directed_weighted_graph_with_negative_weights():
# graph; dwgnw = (V,E)
# > [1] \
# -5 / | \ 1
# / | \>
# [4] |5 [2]
# <\ | /
# 7\ | / -3
# \ ↓ <
# [3]
dwgnw = Graph()
dwgnw.add_edge(1, 2, 1)
dwgnw.add_edge(1, 3, 5)
dwgnw.add_edge(2, 3, -3)
dwgnw.add_edge(3, 4, 7)
dwgnw.add_edge(4, 1, -5)
print("\n\t directed_weighted_graph_with_negative_weights: \n", dwgnw)
shortest_paths, has_negative_weight_cycle = dwgnw.floyd_warshall()
utils.assert_r(
"graph",
shortest_paths,
{
(1, 1): 0,
(1, 2): 1,
(1, 3): -2,
(1, 4): 5,
(2, 1): -1,
(2, 2): 0,
(2, 3): -3,
(2, 4): 4,
# The shortest path from vertex3 to vertex1 is 2(ie -5+7)
(3, 1): 2,
(3, 2): 3,
(3, 3): 0,
(3, 4): 7,
(4, 1): -5,
(4, 2): -4,
(4, 3): -7,
(4, 4): 0,
},
)
utils.assert_r("graph", has_negative_weight_cycle, False)
directed_weighted_graph_with_negative_weights()
def directed_weighted_graph_with_negative_weight_cycle():
# A negative-weight-cycle is when a cycle in a graph sums to a negative value.
# This should not be confused with a graph having negative edges.
# A graph can have negative edges without necessarily having a negative-weight-cycle
# Graph dwgnwc has a negative-weight-cycle. 1->2->3->1 sums upto -2
# see: https://www.techiedelight.com/determine-negative-weight-cycle-graph
# graph; dwgnwc = (V,E)
# [1] \
# ^ \ -3
# | \>
# -1 | [2]
# ^ /
# | / 2
# | <
# [3]
dwgnwc = Graph()
dwgnwc.add_edge(1, 2, -3)
dwgnwc.add_edge(2, 3, 2)
dwgnwc.add_edge(3, 1, -1)
print("\n\t directed_weighted_graph_with_negative_weight_cycle: \n", dwgnwc)
paths, paths_length, has_negative_weight_cycle = dwgnwc.bellman_ford(1)
utils.assert_r(
"graph", paths, {1: [1, 2, 3, 1, 2, 3, 1], 2: [1, 2, 3, 1, 2], 3: [1, 2, 3, 1, 2, 3]}
)
utils.assert_r("graph", paths_length, {1: -4, 2: -5, 3: -3})
utils.assert_r("graph", has_negative_weight_cycle, True)
shortest_paths, has_negative_weight_cycle = dwgnwc.floyd_warshall()
utils.assert_r(
"graph",
shortest_paths,
{
(1, 1): -2,
(1, 2): -5,
(1, 3): -3,
(2, 1): 1,
(2, 2): -2,
(2, 3): 0,
(3, 1): -3,
(3, 2): -6,
(3, 3): -4,
},
)
utils.assert_r("graph", has_negative_weight_cycle, True)
directed_weighted_graph_with_negative_weight_cycle()