from collections import defaultdict
from collections import deque
from queue import PriorityQueue
class Graph:
def __init__(self, nodes):
self.nodes = nodes
self.neighbours = defaultdict(list)
self.weights = {}
self.time = 0
# adds a directed edge to graph
def addDirectedEdge(self, u, v, w=0):
self.neighbours[u].append(v)
self.weights[(u, v)] = w
# adds a directed edge to graph
def addUndirectedEdge(self, u, v, w=0):
self.neighbours[u].append(v)
self.neighbours[v].append(u)
self.weights[(u, v)] = w
# deletes nodes that have the ids mentioned in nodes list
def deleteNodes(self, *nodes):
for node in nodes:
del self.neighbours[node]
self.nodes -= 1
for key in self.weights:
if key[0] == node:
del self.weights[key]
return self
# creates the transposed graph
def transpose(self):
if self.nodes > 0:
transposed_graph = defaultdict(list)
for source, targets in self.neighbours.items():
for target in targets:
transposed_graph[target].append(source)
t = Graph(self.nodes)
t.neighbours = transposed_graph
return t
else:
return None
# prints BFS order starting from source node and returns the path as a list
def bfs(self, source):
bfsOrder = []
visited = {i: False for i in range(1, self.nodes + 1)}
queue = []
queue.append(source)
visited[source] = True
while queue:
source = queue.pop(0)
bfsOrder.append(source)
print(source, sep=' ')
for i in self.neighbours[source]:
if not visited[i]:
queue.append(i)
visited[i] = True
print(f"BFS starting from node {source} is:\n {bfsOrder} \n")
return bfsOrder
# returns the minimum number of arches needed to get from source to every other node in the graph
# if there is no path the value will be -1
def bfs_cost(self, source):
visited = {i: False for i in range(1, self.nodes + 1)}
queue = []
cost = {i: 0 for i in range(1, self.nodes + 1)}
queue.append(source)
visited[source] = True
while queue:
source = queue.pop(0)
print(source, sep=' ')
for i in self.neighbours[source]:
if not visited[i]:
queue.append(i)
cost[i] = cost[source] + 1
visited[i] = True
for node in self.neighbours.keys():
if not visited[node]:
cost[node] = -1
return cost
# returns DFS order starting from source node and returns the path as a list
def dfs(self, source, visited):
visited[source] = True
for i in self.neighbours[source]:
if not visited[i]:
self.dfs(i, visited)
return visited
# returns number of connected componets in an undirected graph
def numberOfConnectedComponents(self):
visited = {i: False for i in range(1, self.nodes + 1)}
count = 0
for node in range(1, self.nodes + 1):
if not visited[node]:
self.dfs(node, visited)
count += 1
return count
def dfs_Kosaraju1(self, source, visited, stack):
visited[source] = True
for node in self.neighbours[source]:
if not visited[node]:
self.dfs_Kosaraju1(node, visited, stack)
stack.append(source)
def dfs_Kosaraju2(self, source, visited, components, count):
visited[source] = True
components[count].append(source)
transpose_g = self.transpose()
for node in transpose_g.neighbours[source]:
if not visited[node]:
self.dfs_Kosaraju2(node, visited, components, count)
# returns the strongly connected components in a directed graph
def SCC_Kosaraju(self):
stack = deque()
components = defaultdict(list)
count = 0
visited = {i: False for i in range(1, self.nodes + 1)}
for node in list(self.neighbours.keys()):
if not visited[node]:
self.dfs_Kosaraju1(node, visited, stack)
visited = {i: False for i in range(1, self.nodes + 1)}
while stack:
node = stack.pop()
if not visited[node]:
count += 1
self.dfs_Kosaraju2(node, visited, components, count)
return components
# helper function used in topologicalSort
def topoSortDFS(self, soruce, visited, stack):
visited[soruce] = True
for neighbour in self.neighbours[soruce]:
if not visited[neighbour]:
self.topoSortDFS(neighbour, visited, stack)
stack.append(soruce)
# returns a topological sort of the nodes of a directed graph
def topologicalSort(self):
stack = deque()
result = []
visited = {i: False for i in range(1, self.nodes + 1)}
for node in list(self.neighbours.keys()):
if not visited[node]:
self.topoSortDFS(node, visited, stack)
while stack:
node = stack.pop()
result.append(node)
return result
#helper function used in bridges
def bridgesDFS(self, u, visited, parent, low_link, timestamp, bridges):
visited[u] = True
timestamp[u] = self.time
low_link[u] = self.time
self.time += 1
for v in self.neighbours[u]:
if not visited[v]:
parent[v] = u
self.bridgesDFS(v, visited, parent, low_link, timestamp, bridges)
low_link[u] = min(low_link[u], low_link[v])
if low_link[v] > timestamp[u]:
print(u, v)
bridges.append((u, v))
elif v != parent[u]:
low_link[u] = min(low_link[u], timestamp[v])
# returns the bridges in an undirected graph
def bridges(self):
bridges = []
visited = [False] * (self.nodes + 1)
timestamp = [-1] * (self.nodes + 1)
low_link = [-1] * (self.nodes + 1)
parent = [-1] * (self.nodes + 1)
for node in range(1, self.nodes + 1):
if not visited[node]:
self.bridgesDFS(node, visited, parent, low_link, timestamp, bridges)
return bridges
# finds BFS order starting from source node and returns the path as a list
def bfs_shortest_path(self, source, target):
visited = {i: False for i in range(1, self.nodes + 1)}
distance = [float('inf')] * (self.nodes + 1)
number_of_paths = [0] * (self.nodes + 1)
queue = []
distance[source] = 0
number_of_paths[source] = 1
queue.append(source)
visited[source] = True
s = source
while queue:
source = queue.pop(0)
for i in self.neighbours[source]:
if not visited[i]:
queue.append(i)
visited[i] = True
if distance[i] > distance[source] + 1:
distance[i] = distance[source] + 1
number_of_paths[i] = number_of_paths[source]
elif distance[i] == distance[source] + 1:
number_of_paths[i] += number_of_paths[source]
paths = self.print_all_paths(s, target, distance[target])
return paths
def dfs_all_paths(self, source, target, visited, path, paths, length):
visited[source] = True
path.append(source)
if source == target:
if len(path) - 1 == length:
paths.append(path.copy())
else:
for i in self.neighbours[source]:
if not visited[i]:
self.dfs_all_paths(i, target, visited, path, paths, length)
path.pop()
visited[source] = False
def print_all_paths(self, source, target, length):
visited = {i: False for i in range(1, self.nodes + 1)}
path = []
paths = []
self.dfs_all_paths(source, target, visited, path, paths, length)
return paths
def bfs_all_shortest_paths(self, parent, source):
distance = [float('inf')] * (self.nodes + 1)
q = deque()
q.append(source)
parent[source] = [-1]
distance[source] = 0
while q:
currentNode = q[0]
q.popleft()
for neighbour in self.neighbours[currentNode]:
if distance[neighbour] > distance[currentNode] + 1:
distance[neighbour] = distance[currentNode] + 1
q.append(neighbour)
parent[neighbour].clear()
parent[neighbour].append(currentNode)
elif distance[neighbour] == distance[currentNode] + 1:
parent[neighbour].append(currentNode)
def find_paths(self, paths, path, parent, target):
if target == -1:
paths.append(path.copy())
return
for par in parent[target]:
path.append(target)
self.find_paths(paths, path, parent, par)
path.pop()
def print_paths(self, source, target):
paths = []
path = []
parent = {i: [] for i in range(1, self.nodes + 1)}
self.bfs_all_shortest_paths(parent, source)
self.find_paths(paths, path, parent, target)
for path in paths:
path = reversed(path)
for node in path:
print(node, end=" ")
print()
return paths
def Dijkstra(self, source):
visited = {i: False for i in range(1, self.nodes + 1)}
costs = {i: float('inf') for i in range(1, self.nodes + 1)}
costs[source] = 0
pq = PriorityQueue()
pq.put((0, source))
while not pq.empty():
(dist, current_node) = pq.get()
visited[current_node] = True
for neighbour in self.neighbours[current_node]:
try:
cost = self.weights[(current_node, neighbour)]
if not visited[neighbour]:
old_cost = costs[neighbour]
new_cost = costs[current_node] + cost
if new_cost < old_cost:
pq.put((new_cost, neighbour))
costs[neighbour] = new_cost
except KeyError:
continue
print(f"The cost of getting from node {source}, to every other node is:\n {costs}")
return costs
def Bellman_Ford(self, source):
costs = {i: float('inf') for i in range(1, self.nodes + 1)}
costs[source] = 0
for i in range(1, self.nodes + 1):
for edge, cost in self.weights.items():
if costs[edge[0]] + cost < costs[edge[1]]:
costs[edge[1]] = costs[edge[0]] + cost
for edge, cost in self.weights.items():
if costs[edge[0]] + cost < costs[edge[1]]:
costs[edge[0]] = float("-inf")
return costs
# # STRONGLY CONNECTED COMPONENTS
# file_ctc = 'ctc.in'
#
# with open(file_ctc, 'rt') as f:
# content = f.readlines()
# content = [line.strip().split() for line in content]
# content = [[int(x) for x in line] for line in content]
# N, M = content[0][0], content[0][1]
#
# g = Graph(N)
# for edges in content[1:]:
# g.addDirectedEdge(edges[0], edges[1])
#
# visited = {i: False for i in range(1, g.nodes + 1)}
# result = g.SCC_Kosaraju()
#
# with open('ctc.out', 'wt') as f:
# f.write(str(len(result.keys())))
# f.write('\n')
# for component in result.values():
# for node in component:
# f.write(str(node))
# f.write(' ')
# f.write('\n')
# # TOPOLOGICAL SORT
# file_sortaret = 'sortaret.in'
#
# with open(file_sortaret, 'rt') as f:
# content = f.readlines()
# content = [line.strip().split() for line in content]
# content = [[int(x) for x in line] for line in content]
# N, M = content[0][0], content[0][1]
#
# g = Graph(N)
# for edges in content[1:]:
# g.addDirectedEdge(edges[0], edges[1])
#
# visited = {i: False for i in range(1, N + 1)}
#
# result = g.topologicalSort()
#
# with open('sortaret.out', 'wt') as f:
# for node in result:
# f.write(str(node))
# f.write(' ')
# # NUMBER OF CONNECTED COMPONENTS
# file_dfs = 'dfs.in'
#
# with open(file_dfs, 'rt') as f:
# content = f.readlines()
# content = [line.strip().split() for line in content]
# content = [[int(x) for x in line] for line in content]
# N, M = content[0][0], content[0][1]
#
# g = Graph(N)
# for edges in content[1:]:
# g.addUndirectedEdge(edges[0], edges[1])
#
# result = g.numberOfConnectedComponents()
#
# with open('dfs.out', 'wt') as f:
# f.write(str(result))
# NUMBER OF SHORTEST PATHS BETWEEN 2 NODES OF UNDIRECTED GRAPH
# file_dfs = 'graf.in'
#
# with open(file_dfs, 'rt') as f:
# content = f.readlines()
# content = [line.strip().split() for line in content]
# content = [[int(x) for x in line] for line in content]
# N, M, source, target = content[0][0], content[0][1], content[0][2], content[0][3]
#
# g = Graph(N)
# for edges in content[1:]:
# g.addUndirectedEdge(edges[0], edges[1])
#
#
# r = g.bfs_shortest_path(source, target)
# print(r)
#
# r = [set(s) for s in r]
# result = set.intersection(*r)
# # print(result)
#
# with open('graf.out', 'wt') as f:
# f.write(str(len(result)))
# f.write('\n')
# for element in result:
# f.write(str(element))
# f.write(' ')
# # DIJKSTRA'S ALGORITHM
# file_dfs = 'dijkstra.in'
#
# with open(file_dfs, 'rt') as f:
# content = f.readlines()
# content = [line.strip().split() for line in content]
# content = [[int(x) for x in line] for line in content]
# N, M = content[0][0], content[0][1]
#
# g = Graph(N)
# for edges in content[1:]:
# g.addDirectedEdge(edges[0], edges[1], edges[2])
#
# result = g.Dijkstra(1)
#
# with open('dijkstra.out', 'wt') as f:
# for cost in list(result.values()):
# if cost != 0:
# f.write(str(cost))
# f.write(' ')
# # BELLMAN-FORD'S ALGORITHM
file_dfs = 'bellmanford.in'
with open(file_dfs, 'rt') as f:
content = f.readlines()
content = [line.strip().split() for line in content]
content = [[int(x) for x in line] for line in content]
N, M = content[0][0], content[0][1]
g = Graph(N)
for edges in content[1:]:
g.addDirectedEdge(edges[0], edges[1], edges[2])
result = g.Bellman_Ford(1)
with open('bellmanford.out', 'wt') as f:
if float("-inf") in result.values():
f.write("Ciclu negativ!")
else:
for cost in list(result.values()):
if cost != 0:
f.write(str(cost))
f.write(' ')
Andrei Sturzu Andrei_Sturzu