Graph

class Vertex:
 def __init__(self, key):
  self.id = key
  self.connected_to = {}

 def add_neighbor(self, n, w):
  self.connected_to[n] = w

 def get_connections(self):
  return self.connected_to.keys()

 def get_id(self):
  return self.id

 def get_weight(self, n):
  return self.connected_to[n]

 def __str__(self):
  return str(self.id)

class Graph:
 def __init__(self):
  self.size = 0
  self.master_list = {}

 def add_vertex(self, key):
  self.size += 1
  vertex = Vertex(key)
  self.master_list[key] = vertex
  return vertex

 def get_vertex(self, n):
  if n in self.master_list:
   return self.master_list[n]
  return None

 def add_edge(self, u, v, weight=0):
  if u not in self.master_list:
   self.add_vertex(u)
  if v not in self.master_list:
   self.add_vertex(v)
  self.master_list[u].add_neighbor(self.add_vertex(v), weight)

 def get_vertices(self):
  return self.master_list.keys()

 def __iter__(self):
  return iter(self.master_list.values())

 def __contains__(self, n):
  if n in self.master_list:
   return True
  return False

if __name__ == "__main__":
 graph = Graph()
 for value in range(6):
  graph.add_vertex(value)

 graph.add_edge(0, 1, 5)

 for vertex in graph:
  print(vertex)

graph = {
    'A' : ['B', 'C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}

def bfs(graph, node):
    queue = [node]
    visited = [node]
    while queue:
        popped_node = queue.pop(0)
        for neighbour in graph[popped_node]:
            if neighbour not in visited:
                queue.append(neighbour)
                visited.append(neighbour)
    return visited

visited = bfs(graph, 'A')
print(visited)

class Graph:
  def __init__(self, num_vertex: int):
    self.num_vertex = num_vertex
    self.adj_list = [[] for _ in range(num_vertex)]

  def add_edge(self, from_node: int, to_node: int) -> None:
    self.adj_list[from_node].append(to_node)
    self.adj_list[to_node].append(from_node)

  def dfs(self, node, component, visited):
    visited[node] = True
    component.append(node)
    for neighbour in self.adj_list[node]:
      if visited[neighbour] == False:
        self.dfs(neighbour, component, visited)

  def connected_components(self):
    all_components = []
    visited = [ False for _ in range(self.num_vertex) ]
    for i in range(self.num_vertex):
      if visited[i] == False:
        component = []
        self.dfs(i, component, visited)
        all_components.append(component)
    return all_components

if __name__ == "__main__":
  graph = Graph(5)

  graph.add_edge(1,0)
  graph.add_edge(2,3)
  graph.add_edge(3,0)

  print(graph.connected_components())

from collections import defaultdict
  
class Graph():
    def __init__(self, order):
        self.graph = defaultdict(list)
        self.order = order
  
    def addEdge(self, u, v):
        self.graph[u].append(v)

    def is_cyclic_helper(self, node, visited, stack):
        visited[node] = True
        stack[node] = True
        for neighbour in self.graph[node]:
            if visited[neighbour] == False:
                if self.is_cyclic_helper(neighbour, visited, stack):
                    return True
            elif stack[neighbour] == True:
                return True
        stack[node] = False
        return False

    def is_cyclic(self):
        visited = [ False for _ in range(self.order) ]
        stack = [ False for _ in range(self.order) ] # may be needed for subgraphs
        for node in range(self.order): # helpful for disconnected graphs
            if visited[node] == False:
                if self.is_cyclic_helper(node, visited, stack):
                    return True
        return False

if __name__ == "__main__":
    graph = Graph(4)

    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 2)
    graph.addEdge(2, 0)
    graph.addEdge(2, 3)
    graph.addEdge(3, 3)
    print(graph.is_cyclic())

    # graph.addEdge(0, 1)
    # graph.addEdge(0, 2)
    # print(graph.is_cyclic())

from collections import defaultdict
  
class Graph():
    def __init__(self, order):
        self.graph = defaultdict(list)
        self.order = order
  
    def addEdge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def is_cyclic_helper(self, node, visited, parent):
        visited[node] = True
        for neighbour in self.graph[node]:
            if visited[neighbour] == False:
                if self.is_cyclic_helper(neighbour, visited, node):
                    return True
            elif parent != neighbour:
                return True
        return False

    def is_cyclic(self):
        visited = [ False for _ in range(self.order) ]
        for node in range(self.order): # helpful for disconnected graphs
            if visited[node] == False:
                if self.is_cyclic_helper(node, visited, -1):
                    return True
        return False


if __name__ == "__main__":
    graph = Graph(4)

    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 2)
    print(graph.is_cyclic())

    # graph.addEdge(0, 1)
    # graph.addEdge(0, 2)
    # print(graph.is_cyclic())

graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}

# preorder
# def dfs_iterative(graph, node, visited):
#     stack = [node]
#     while stack:
#         popped_item = stack.pop()
#         if popped_item not in visited:
#             visited.append(popped_item) # pre
#             for neighbour in graph[popped_item]:
#                 if neighbour not in visited:
#                     stack.append(neighbour)
#     return visited

# post-order
def dfs_iterative(graph: Dict[int, int], start_node: int) -> List[int]:
    stack = [start_node]
    visited = []
    while stack:
        popped_node = stack.pop()
        if popped_node not in visited:
            for neighbour in graph[popped_node]:
                if neighbour not in visited:
                    stack.append(neighbour)
            visited.append(popped_node)
    return visited

visited = dfs_iterative(graph, 'A')
print(visited)

# inorder bst traversal iterative
# class Node:
#     def __init__(self, val):
#         self.val = val
#         self.left = None
#         self.right = None

#     def inorder_iterative_dfs(root):
#         if not root:
#             return

#         stack = []
#         while True:
#             if root:
#                 stack.append(root)
#                 root = root.left
#             else:
#                 if not stack:
#                     break
#                 root = stack.pop()
#                 print(root.val)
#                 root = root.right


# root = Node(10)
# root.left = Node(0)
# root.left.left = Node(5)
# root.left.right = Node(6)
# root.right = Node(-10)
# root.right.right = Node(11)

# Node.inorder_iterative_dfs(root)

graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : [],
    'G' : ['H'],
    'H' : [],
}

def dfs(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for neighbour in graph[node]:
            dfs(graph, neighbour, visited)

# to traverse whole graph
visited = []
for node in graph:
    if node not in visited:
        dfs(graph, node, visited)

print(visited)

from collections import defaultdict
from typing import List, Tuple

class Graph:
 def __init__(self, order: int, edges: List[Tuple[int, int]]):
  self.order = order
  self.adj_list = {}

  for (src, dest) in edges:
   if src not in self.adj_list:
    self.adj_list[src] = []
   if dest not in self.adj_list:
    self.adj_list[dest] = []
   
   self.adj_list[src].append(dest)

 def __repr__(self):
  out = []
  for s_node in self.adj_list:
   out.append(f"{s_node} -> ")
   for d_node in self.adj_list[s_node]:
    out.append(f"{d_node}, ")
   out.append('\n')
  return ''.join(out)

def dfs(graph: Graph, start_node: int, visited: List[int], arrival: List[int], departure: List[int], time: int) -> int:
 if start_node not in visited:
  time += 1
  arrival[start_node] = time
  visited.append(start_node)
  for neighbour in graph.adj_list[start_node]:
   time = dfs(graph, neighbour, visited, arrival, departure, time)
  time += 1
  departure[start_node] = time
 return time

if __name__ == "__main__":
 edges = [ (0, 1), (0, 2), (2, 3), (2, 4), (3, 1), (3, 5), (4, 5), (6, 7) ]
 graph = Graph(8, edges)
 visited, arrival, departure = [], {}, {}
 time = -1
 for node in graph.adj_list:
  if node not in visited:
   time = dfs(graph, node, visited, arrival, departure, time)
 
 for i in range(len(visited)):
  print(f"{visited[i]} - {arrival[i]} - {departure[i]}")

from typing import List, Tuple

class Graph:
    def __init__(self, edge_list: List[Tuple[int, int]], order: int):
        self.adj_list = {}
        for (src, dest) in edge_list:
            if src not in self.adj_list:
                self.adj_list[src] = []
            if dest not in self.adj_list:
                self.adj_list[dest] = []
            self.adj_list[src].append(dest)
 
    def __repr__(self):
        out = []
        for s_node in self.adj_list:
            out.append(f"{s_node} -> ")
            for d_node in self.adj_list[s_node]:
                out.append(f"{d_node}, ")
            out.append('\n')
        return ''.join(out)
 
 
if __name__ == '__main__':
    edge_list = [ (0,1), (1,2), (2,3), (0,2), (3,2), (4,5), (5,4) ]
    order = 6
 
    graph = Graph(edge_list, order) 
    print(graph)

class DisjointSet:

 def __init__(self, size):
  self.root = [ i for i in range(size) ]

 def find(self, x):

  if self.root[x] == x:
   return x

  self.root[x] = self.find(self.root[x])

  return self.root[x]

 def union(self, x, y):

  rootX = self.find(x)
  rootY = self.find(y)

  if rootX != rootY:
   self.root[rootY] = rootX

 def connected(self, x, y):
  return self.find(x) == self.find(y)

 def __str__(self):
  return str(self.root)

disjoint_set = DisjointSet(10)

disjoint_set.union(1, 2)
disjoint_set.union(1, 2)
disjoint_set.union(2, 5)
disjoint_set.union(5, 6)
disjoint_set.union(6, 7)
disjoint_set.union(3, 8)
disjoint_set.union(8, 9)
disjoint_set.union(9, 4)

print(disjoint_set)

print(disjoint_set.connected(1, 5))

from typing import Dict, List

def dfs(graph: Dict[int, int], start_node: int) -> List[int]:
    stack = [start_node]
    visited = []
    while stack:
        popped_node = stack.pop()
        if popped_node not in visited:
            for neighbour in graph[popped_node]:
                if neighbour not in visited:
                    stack.append(neighbour)
            visited.append(popped_node)
    return visited

def bfs(graph: Dict[int, int], start_node: int) -> List[int]:
 visited = [start_node]
 queue = [start_node]
 while queue:
  popped_node = queue.pop(0)
  for neighbour in graph[popped_node]:
   if neighbour not in visited:
    queue.append(neighbour)
    visited.append(neighbour)
 return visited

def is_path(graph: Dict[int, int], start_node: int, end_node: int) -> bool:
 if start_node == end_node:
  return True

 if end_node in bfs(graph, start_node): # bfs := path from start node
  return True

 return False

if __name__ == "__main__":

 letter_graph = { 'a' : ['d'],
     'b' : ['d', 'f'],
     'c' : [],
     'd' : ['a', 'b', 'e', 'f'],
     'e' : ['d'],
     'f' : ['b', 'd'],
     }

 # print(dfs(letter_graph, 'a'))
 # print(bfs(letter_graph, 'b'))
 # print(is_path(graph=letter_graph, start_node='a', end_node='e'))
 # print(is_path(graph=letter_graph, start_node='c', end_node='f'))
 # print(is_path(graph=letter_graph, start_node='f', end_node='f'))

from typing import List, Tuple

class Graph:
    def __init__(self, edge_list: List[Tuple[int, int]]):
        self.graph = {}
        for (src, dest) in edge_list:
            if src not in self.graph:
                self.graph[src] = []
            if dest not in self.graph:
                self.graph[dest] = []
            self.graph[src].append(dest)

    def reverse_graph(self):
        rev = {}
        for src in self.graph:
            for dest in self.graph[src]:
                if src not in rev:
                    rev[src] = []
                if dest not in rev:
                    rev[dest] = []
                rev[dest].append(src)
        return rev

    def dfs(self, node, visited, departure):
        visited.append(node)
        for neig in self.graph[node]:
            if neig not in visited:
                self.dfs(neig, visited, departure)
        departure.append(node)

    def get_component(self, node, visited, component, rev_g):
        component.append(node)
        visited.append(node)
        for neig in rev_g[node]:
            if neig not in visited:
                self.get_component(neig, visited, component, rev_g)

    def strongly_connected_component(self):
        departure = [] # order of departure is the departure time
        visited = []
        for node in self.graph:
            if node not in visited:
                self.dfs(node, visited, departure)

        rev_g = self.reverse_graph()

        res = []
        visited = []
        while departure:
            node = departure.pop()
            if node not in visited:
                component = []
                self.get_component(node, visited, component, rev_g)
                res.append(component)
        return res        


if __name__ == '__main__':
    edge_list = [ (0,1), (1,2), (2,0), (1,3), (3,4), (4,5), (5,3), (5,6) ]
    g = Graph(edge_list)
    print(g.strongly_connected_component())

class Graph:
    def __init__(self, edges, order):
        self.order = order
        self.adj_list = {}
        for (src, dest) in edges:
            if src not in self.adj_list:
                self.adj_list[src] = []
            if dest not in self.adj_list:
                self.adj_list[dest] = []
            self.adj_list[src].append(dest)

    def dfs(self, node, visited):
        if node not in visited:
            visited.append(node)
            for neighbour in self.adj_list[node]:
                self.dfs(neighbour, visited)
            stack.append(node) # back

if __name__ == '__main__':
    edges = [ (0, 6), (1, 2), (1, 4), (1, 6), (3, 0), (3, 4), (5, 1), (7, 0), (7, 1) ]
    graph = Graph(edges, 8)
    visited = []
    stack = []
    for node in graph.adj_list:
        graph.dfs(node, visited)
    print(visited)
    print(stack)

from collections import defaultdict

def dfs(node, g):
 if node in visited:
  return visited[node] == g
 visited[node] = g
 return all(dfs(neighbour,1-g) for neighbour in graph[node])


if __name__ == "__main__":
 # dislikes = [ [1,2], [1,3], [2,3], [3,4] ]
 dislikes = [ [1,2], [1,3], [3,4] ]
 
 graph = defaultdict(list)

 for node in dislikes:
  graph[node[0]].append(node[1])
  graph[node[1]].append(node[0])

 visited = {}
 print(all(dfs(node,0) for node in graph if node not in visited))

class DisjointSet:

 def __init__(self, size):
  self.root = [i for i in range(size)]

 def find(self, x):
  return self.root[x]

 def union(self, x, y):
  rootX = self.find(x)
  rootY = self.find(y)
  if rootX != rootY:
   for i in range(len(self.root)):
    if self.root[i] == rootY:
     self.root[i] = rootX

 def is_connected(self, x, y):
  return self.find(x) == self.find(y)

 def __repr__(self):
  return str(self.root)


if __name__ == "__main__":

 disjoint_set = DisjointSet(size=10)
 disjoint_set.union(1, 2)
 disjoint_set.union(2, 5)
 disjoint_set.union(5, 6)
 disjoint_set.union(6, 7)
 disjoint_set.union(3, 8)
 disjoint_set.union(8, 9)
 print(disjoint_set.is_connected(1, 5))  # true
 print(disjoint_set.is_connected(5, 7))  # true
 print(disjoint_set.is_connected(4, 9))  # false
 # 1-2-5-6-7 3-8-9-4
 disjoint_set.union(9, 4)
 print(disjoint_set.is_connected(4, 9))  # true

class DisjointSet:

 def __init__(self, size):
  self.root = [i for i in range(size)]
  self.rank = [1 for i in range(size)]

 def find(self, x):
  while x != self.root[x]:
   x = self.root[x]
  return x

 def union(self, x, y):
  rootX = self.find(x)
  rootY = self.find(y)
  if rootX != rootY:
   if self.rank[rootX] > self.rank[rootY]:
    self.root[rootY] = rootX
   elif self.rank[rootX] < self.rank[rootY]:
    self.root[rootX] = rootY
   else:
    self.root[rootY] = rootX
    self.rank[rootX] += 1

 def __repr__(self):
  return str(self.root)
if __name__ == "__main__":

 disjoint_set = DisjointSet(10)

 disjoint_set.union(1, 2)
 disjoint_set.union(2, 5)
 disjoint_set.union(5, 6)
 disjoint_set.union(6, 7)
 disjoint_set.union(3, 8)
 disjoint_set.union(8, 9)
 disjoint_set.union(9, 4)
 print(str(disjoint_set))

from collections import defaultdict

class Graph:

    def __init__(self, graph):
        self.graph = graph

    def bfs(self, s, t, parent):
        visited = [s]
        queue = [s]
        while queue:
            u = queue.pop(0)
            for ind,val in enumerate(self.graph[u]):
                if ind not in visited and val > 0:
                    queue.append(ind)
                    visited.append(ind)
                    parent[ind] = u
        return t in visited

    def ford_fulkerson(self, source, sink):
        parent = [-1] * len(self.graph)
        max_flow = 0
        while self.bfs(source, sink, parent):

            s = sink
            path_flow = float("inf")
            while s != source:
                path_flow = min(path_flow, self.graph[parent[s]][s])
                s = parent[s]
            max_flow += path_flow

            v = sink
            while v != source:
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]

        return max_flow

g = Graph( [[0, 8, 0, 0, 3, 0],
            [0, 0, 9, 0, 0, 0],
            [0, 0, 0, 0, 7, 2],
            [0, 0, 0, 0, 0, 5],
            [0, 0, 7, 4, 0, 0],
            [0, 0, 0, 0, 0, 0], ])

print("Max Flow: %d " % g.ford_fulkerson(source=0, sink=5))

class Graph:

 def __init__(self, vertices):
  self.V = vertices
  self.graph = []

 def addEdge(self, u, v, w):
  self.graph.append([u, v, w])

 def find(self, parent, i):
  """ which set does i belong
  """
  if parent[i] == i:
   return i
  return self.find(parent, parent[i])

 def union(self, parent, rank, x, y):
  """ merge sets containing x and y
  """
  xroot = self.find(parent, x)
  yroot = self.find(parent, y)

  # Attach smaller rank tree under the root of high-rank tree
  if rank[xroot] < rank[yroot]:
   parent[xroot] = yroot
  elif rank[xroot] > rank[yroot]:
   parent[yroot] = xroot

  # If ranks are the same, then make one a root and increment its rank by one
  else:
   parent[yroot] = xroot
   rank[xroot] += 1

 def KruskalMST(self):

  result = []
  i, e = 0, 0
  self.graph = sorted(self.graph, key=lambda item: item[2])

  parent, rank = [], []
  for node in range(self.V):
   parent.append(node)
   rank.append(0)

  while e < self.V - 1:
   u, v, w = self.graph[i]
   i += 1
   x = self.find(parent, u)
   y = self.find(parent, v)
   if x != y:
    e += 1
    result.append([u, v, w])
    self.union(parent, rank, x, y)

  minimumCost = 0
  for u, v, weight in result:
   minimumCost += weight
   print("%d -- %d == %d" % (u, v, weight))
  print("Minimum Spanning Tree: " , minimumCost)

g = Graph(4)
g.addEdge(0, 1, 10)
g.addEdge(0, 2, 6)
g.addEdge(0, 3, 5)
g.addEdge(1, 3, 15)
g.addEdge(2, 3, 4)

g.KruskalMST()

class Graph:
     def __init__(self, order):
          self.V = order
          self.graph = [ [ 0 for column in range(order) ] for row in range(order) ]

     def printMST(self, parent):
          print("Edge \tWeight")
          for i in range(1, self.V):
               print (parent[i], "-", i, "\t", self.graph[i][parent[i]])
  
     def minKey(self, key, visited):
          min_ = float('inf')
          for v in range(self.V):
               if min_ > key[v] and v not in visited:
                    min_ = key[v]
                    min_index = v
  
          return min_index
  
     def primMST(self):
          key = [float('inf')] * self.V
          key[0] = 0

          parent = [None] * self.V
          parent[0] = -1

          visited = []
          for _ in range(self.V):
               u = self.minKey(key, visited)
               visited.append(u)
  
               for v in range(self.V):
                    if self.graph[u][v] > 0 and v not in visited and key[v] > self.graph[u][v]:
                         key[v] = self.graph[u][v]
                         parent[v] = u
  
          self.printMST(parent)
  
g = Graph(5)
g.graph = [ [0, 4, 0, 3, 5],
            [4, 0, 2, 0, 0],
            [0, 2, 0, 1, 0],
            [3, 0, 1, 0, 0],
            [5, 0, 0, 0, 0],
          ]
  
g.primMST()

from collections import defaultdict
import heapq

def create_spanning_tree(graph, starting_vertex):
    mst = defaultdict(set)
    visited = set([starting_vertex])
    edges = [ (cost, starting_vertex, to) for to, cost in graph[starting_vertex].items()]
    heapq.heapify(edges)

    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst[frm].add(to)
            for to_next, cost in graph[to].items():
                if to_next not in visited:
                    heapq.heappush(edges, (cost, to, to_next))
    return mst

if __name__ == "__main__":
    example_graph = {
        'A': {'B': 2, 'C': 3},
        'B': {'A': 2, 'C': 1, 'D': 1, 'E': 4},
        'C': {'A': 3, 'B': 1, 'F': 5},
        'D': {'B': 1, 'E': 1},
        'E': {'B': 4, 'D': 1, 'F': 1},
        'F': {'C': 5, 'E': 1, 'G': 1},
        'G': {'F': 1},
    }

    print(create_spanning_tree(example_graph, 'A'))

def dijkstra(nodes, edges, source_index=0):
 path_lengths = { node: float('inf') for node in nodes }
 path_lengths[source_index] = 0

 adj_nodes = { node: {} for node in nodes }
 for (u,v), w_uv in edges.items():
  adj_nodes[u][v] = w_uv
  adj_nodes[v][u] = w_uv

 temporary_nodes = [ node for node in nodes ]
 while len(temporary_nodes) > 0:
  upper_bounds = { node: path_lengths[node] for node in temporary_nodes }
  u = min(upper_bounds, key=upper_bounds.get)

  temporary_nodes.remove(u)

  for v, w_uv in adj_nodes[u].items():
   path_lengths[v] = min(path_lengths[v], path_lengths[u] + w_uv)

 return path_lengths

nodes = list(range(6))
edges = { (0,1): 1.0, (0,2): 1.5, (0,3):2.0, (1,3): 0.5, (1,4): 2.5, (2,3): 1.5, (3,5): 1.0 }
print(dijkstra(nodes, edges, source_index=0))

def floyd(G, nV):
    dist = { (u,v): float('inf') if u != v else 0 for u in range(nV) for v in range(nV) }
    dist = { (u,v): G[u][v] for u in range(nV) for v in range(nV) }

    for k in range(nV):
        dist = { (u,v): min(dist[(u,v)], dist[(u,k)] + dist[(k,v)]) for u in range(nV) for v in range(nV) }
    
    for u in range(nV):
        for v in range(nV):
            print(dist[(u,v)], end="  ")
        print(" ")

if __name__ == "__main__":
    INF = float('inf')
    G = [ [0,  5,   INF, INF],
          [50, 0,   15,  5  ],
          [30, INF, 0,   15 ],
          [15, INF, 5,   0  ],
        ]

    floyd(G, 4)