directed and undirected (weighted) graph Algorithm
A directed graph (also called a "digraph") is a graph that contains a set of vertices and a set of directed edges (also called "arcs"). In a directed graph, each edge has an initial vertex, called its "tail" and a terminal vertex, called its "head". The edges are usually represented by arrows, indicating the direction of the relationship between the vertices. Algorithms that operate on directed graphs include graph traversal algorithms such as depth-first search (DFS) and breadth-first search (BFS), shortest path algorithms such as Dijkstra's algorithm and Bellman-Ford algorithm, and topological sorting algorithms.
An undirected weighted graph is a graph with a set of vertices and a set of edges connecting the vertices, where each edge has an associated weight or cost. Unlike directed graphs, the edges in undirected graphs do not have a specific direction, implying that the relationship between the vertices is bidirectional. The weight of an edge typically represents a cost or a distance between two vertices. Weighted graph algorithms include minimum spanning tree algorithms such as Kruskal's algorithm and Prim's algorithm, and shortest path algorithms such as Dijkstra's algorithm and Floyd-Warshall algorithm. These algorithms are designed to solve various problems like finding the shortest path between two vertices, the minimum cost to visit all vertices, or the minimum weight to connect all vertices in a graph.
from collections import deque
import random as rand
import math as math
import time
# the default weight is 1 if not assigned but all the implementation is weighted
class DirectedGraph:
def __init__(self):
self.graph = {}
# adding vertices and edges
# adding the weight is optional
# handles repetition
def add_pair(self, u, v, w=1):
if self.graph.get(u):
if self.graph[u].count([w, v]) == 0:
self.graph[u].append([w, v])
else:
self.graph[u] = [[w, v]]
if not self.graph.get(v):
self.graph[v] = []
def all_nodes(self):
return list(self.graph)
# handles if the input does not exist
def remove_pair(self, u, v):
if self.graph.get(u):
for _ in self.graph[u]:
if _[1] == v:
self.graph[u].remove(_)
# if no destination is meant the default value is -1
def dfs(self, s=-2, d=-1):
if s == d:
return []
stack = []
visited = []
if s == -2:
s = list(self.graph.keys())[0]
stack.append(s)
visited.append(s)
ss = s
while True:
# check if there is any non isolated nodes
if len(self.graph[s]) != 0:
ss = s
for __ in self.graph[s]:
if visited.count(__[1]) < 1:
if __[1] == d:
visited.append(d)
return visited
else:
stack.append(__[1])
visited.append(__[1])
ss = __[1]
break
# check if all the children are visited
if s == ss:
stack.pop()
if len(stack) != 0:
s = stack[len(stack) - 1]
else:
s = ss
# check if se have reached the starting point
if len(stack) == 0:
return visited
# c is the count of nodes you want and if you leave it or pass -1 to the function
# the count will be random from 10 to 10000
def fill_graph_randomly(self, c=-1):
if c == -1:
c = (math.floor(rand.random() * 10000)) + 10
for _ in range(c):
# every vertex has max 100 edges
e = math.floor(rand.random() * 102) + 1
for __ in range(e):
n = math.floor(rand.random() * (c)) + 1
if n == _:
continue
self.add_pair(_, n, 1)
def bfs(self, s=-2):
d = deque()
visited = []
if s == -2:
s = list(self.graph.keys())[0]
d.append(s)
visited.append(s)
while d:
s = d.popleft()
if len(self.graph[s]) != 0:
for __ in self.graph[s]:
if visited.count(__[1]) < 1:
d.append(__[1])
visited.append(__[1])
return visited
def in_degree(self, u):
count = 0
for _ in self.graph:
for __ in self.graph[_]:
if __[1] == u:
count += 1
return count
def out_degree(self, u):
return len(self.graph[u])
def topological_sort(self, s=-2):
stack = []
visited = []
if s == -2:
s = list(self.graph.keys())[0]
stack.append(s)
visited.append(s)
ss = s
sorted_nodes = []
while True:
# check if there is any non isolated nodes
if len(self.graph[s]) != 0:
ss = s
for __ in self.graph[s]:
if visited.count(__[1]) < 1:
stack.append(__[1])
visited.append(__[1])
ss = __[1]
break
# check if all the children are visited
if s == ss:
sorted_nodes.append(stack.pop())
if len(stack) != 0:
s = stack[len(stack) - 1]
else:
s = ss
# check if se have reached the starting point
if len(stack) == 0:
return sorted_nodes
def cycle_nodes(self):
stack = []
visited = []
s = list(self.graph.keys())[0]
stack.append(s)
visited.append(s)
parent = -2
indirect_parents = []
ss = s
on_the_way_back = False
anticipating_nodes = set()
while True:
# check if there is any non isolated nodes
if len(self.graph[s]) != 0:
ss = s
for __ in self.graph[s]:
if (
visited.count(__[1]) > 0
and __[1] != parent
and indirect_parents.count(__[1]) > 0
and not on_the_way_back
):
len_stack = len(stack) - 1
while True and len_stack >= 0:
if stack[len_stack] == __[1]:
anticipating_nodes.add(__[1])
break
else:
anticipating_nodes.add(stack[len_stack])
len_stack -= 1
if visited.count(__[1]) < 1:
stack.append(__[1])
visited.append(__[1])
ss = __[1]
break
# check if all the children are visited
if s == ss:
stack.pop()
on_the_way_back = True
if len(stack) != 0:
s = stack[len(stack) - 1]
else:
on_the_way_back = False
indirect_parents.append(parent)
parent = s
s = ss
# check if se have reached the starting point
if len(stack) == 0:
return list(anticipating_nodes)
def has_cycle(self):
stack = []
visited = []
s = list(self.graph.keys())[0]
stack.append(s)
visited.append(s)
parent = -2
indirect_parents = []
ss = s
on_the_way_back = False
anticipating_nodes = set()
while True:
# check if there is any non isolated nodes
if len(self.graph[s]) != 0:
ss = s
for __ in self.graph[s]:
if (
visited.count(__[1]) > 0
and __[1] != parent
and indirect_parents.count(__[1]) > 0
and not on_the_way_back
):
len_stack_minus_one = len(stack) - 1
while True and len_stack_minus_one >= 0:
if stack[len_stack_minus_one] == __[1]:
anticipating_nodes.add(__[1])
break
else:
return True
anticipating_nodes.add(stack[len_stack_minus_one])
len_stack_minus_one -= 1
if visited.count(__[1]) < 1:
stack.append(__[1])
visited.append(__[1])
ss = __[1]
break
# check if all the children are visited
if s == ss:
stack.pop()
on_the_way_back = True
if len(stack) != 0:
s = stack[len(stack) - 1]
else:
on_the_way_back = False
indirect_parents.append(parent)
parent = s
s = ss
# check if se have reached the starting point
if len(stack) == 0:
return False
def dfs_time(self, s=-2, e=-1):
begin = time.time()
self.dfs(s, e)
end = time.time()
return end - begin
def bfs_time(self, s=-2):
begin = time.time()
self.bfs(s)
end = time.time()
return end - begin
class Graph:
def __init__(self):
self.graph = {}
# adding vertices and edges
# adding the weight is optional
# handles repetition
def add_pair(self, u, v, w=1):
# check if the u exists
if self.graph.get(u):
# if there already is a edge
if self.graph[u].count([w, v]) == 0:
self.graph[u].append([w, v])
else:
# if u does not exist
self.graph[u] = [[w, v]]
# add the other way
if self.graph.get(v):
# if there already is a edge
if self.graph[v].count([w, u]) == 0:
self.graph[v].append([w, u])
else:
# if u does not exist
self.graph[v] = [[w, u]]
# handles if the input does not exist
def remove_pair(self, u, v):
if self.graph.get(u):
for _ in self.graph[u]:
if _[1] == v:
self.graph[u].remove(_)
# the other way round
if self.graph.get(v):
for _ in self.graph[v]:
if _[1] == u:
self.graph[v].remove(_)
# if no destination is meant the default value is -1
def dfs(self, s=-2, d=-1):
if s == d:
return []
stack = []
visited = []
if s == -2:
s = list(self.graph.keys())[0]
stack.append(s)
visited.append(s)
ss = s
while True:
# check if there is any non isolated nodes
if len(self.graph[s]) != 0:
ss = s
for __ in self.graph[s]:
if visited.count(__[1]) < 1:
if __[1] == d:
visited.append(d)
return visited
else:
stack.append(__[1])
visited.append(__[1])
ss = __[1]
break
# check if all the children are visited
if s == ss:
stack.pop()
if len(stack) != 0:
s = stack[len(stack) - 1]
else:
s = ss
# check if se have reached the starting point
if len(stack) == 0:
return visited
# c is the count of nodes you want and if you leave it or pass -1 to the function
# the count will be random from 10 to 10000
def fill_graph_randomly(self, c=-1):
if c == -1:
c = (math.floor(rand.random() * 10000)) + 10
for _ in range(c):
# every vertex has max 100 edges
e = math.floor(rand.random() * 102) + 1
for __ in range(e):
n = math.floor(rand.random() * (c)) + 1
if n == _:
continue
self.add_pair(_, n, 1)
def bfs(self, s=-2):
d = deque()
visited = []
if s == -2:
s = list(self.graph.keys())[0]
d.append(s)
visited.append(s)
while d:
s = d.popleft()
if len(self.graph[s]) != 0:
for __ in self.graph[s]:
if visited.count(__[1]) < 1:
d.append(__[1])
visited.append(__[1])
return visited
def degree(self, u):
return len(self.graph[u])
def cycle_nodes(self):
stack = []
visited = []
s = list(self.graph.keys())[0]
stack.append(s)
visited.append(s)
parent = -2
indirect_parents = []
ss = s
on_the_way_back = False
anticipating_nodes = set()
while True:
# check if there is any non isolated nodes
if len(self.graph[s]) != 0:
ss = s
for __ in self.graph[s]:
if (
visited.count(__[1]) > 0
and __[1] != parent
and indirect_parents.count(__[1]) > 0
and not on_the_way_back
):
len_stack = len(stack) - 1
while True and len_stack >= 0:
if stack[len_stack] == __[1]:
anticipating_nodes.add(__[1])
break
else:
anticipating_nodes.add(stack[len_stack])
len_stack -= 1
if visited.count(__[1]) < 1:
stack.append(__[1])
visited.append(__[1])
ss = __[1]
break
# check if all the children are visited
if s == ss:
stack.pop()
on_the_way_back = True
if len(stack) != 0:
s = stack[len(stack) - 1]
else:
on_the_way_back = False
indirect_parents.append(parent)
parent = s
s = ss
# check if se have reached the starting point
if len(stack) == 0:
return list(anticipating_nodes)
def has_cycle(self):
stack = []
visited = []
s = list(self.graph.keys())[0]
stack.append(s)
visited.append(s)
parent = -2
indirect_parents = []
ss = s
on_the_way_back = False
anticipating_nodes = set()
while True:
# check if there is any non isolated nodes
if len(self.graph[s]) != 0:
ss = s
for __ in self.graph[s]:
if (
visited.count(__[1]) > 0
and __[1] != parent
and indirect_parents.count(__[1]) > 0
and not on_the_way_back
):
len_stack_minus_one = len(stack) - 1
while True and len_stack_minus_one >= 0:
if stack[len_stack_minus_one] == __[1]:
anticipating_nodes.add(__[1])
break
else:
return True
anticipating_nodes.add(stack[len_stack_minus_one])
len_stack_minus_one -= 1
if visited.count(__[1]) < 1:
stack.append(__[1])
visited.append(__[1])
ss = __[1]
break
# check if all the children are visited
if s == ss:
stack.pop()
on_the_way_back = True
if len(stack) != 0:
s = stack[len(stack) - 1]
else:
on_the_way_back = False
indirect_parents.append(parent)
parent = s
s = ss
# check if se have reached the starting point
if len(stack) == 0:
return False
def all_nodes(self):
return list(self.graph)
def dfs_time(self, s=-2, e=-1):
begin = time.time()
self.dfs(s, e)
end = time.time()
return end - begin
def bfs_time(self, s=-2):
begin = time.time()
self.bfs(s)
end = time.time()
return end - begin