basic_graphs.py

fromcollectionsimportdeque


def_input(message):
returninput(message).strip().split(" ")


definitialize_unweighted_directed_graph(
node_count: int, edge_count: int
) ->dict[int, list[int]]:
graph: dict[int, list[int]] = {}
foriinrange(node_count):
graph[i+1] = []

foreinrange(edge_count):
x, y= (int(i) foriin_input(f"Edge {e+1}: <node1> <node2> "))
graph[x].append(y)
returngraph


definitialize_unweighted_undirected_graph(
node_count: int, edge_count: int
) ->dict[int, list[int]]:
graph: dict[int, list[int]] = {}
foriinrange(node_count):
graph[i+1] = []

foreinrange(edge_count):
x, y= (int(i) foriin_input(f"Edge {e+1}: <node1> <node2> "))
graph[x].append(y)
graph[y].append(x)
returngraph


definitialize_weighted_undirected_graph(
node_count: int, edge_count: int
) ->dict[int, list[tuple[int, int]]]:
graph: dict[int, list[tuple[int, int]]] = {}
foriinrange(node_count):
graph[i+1] = []

foreinrange(edge_count):
x, y, w= (int(i) foriin_input(f"Edge {e+1}: <node1> <node2> <weight> "))
graph[x].append((y, w))
graph[y].append((x, w))
returngraph


if__name__=="__main__":
n, m= (int(i) foriin_input("Number of nodes and edges: "))

graph_choice=int(
_input(
"Press 1 or 2 or 3 \n"
"1. Unweighted directed \n"
"2. Unweighted undirected \n"
"3. Weighted undirected \n"
 )[0]
 )

g= {
1: initialize_unweighted_directed_graph,
2: initialize_unweighted_undirected_graph,
3: initialize_weighted_undirected_graph,
 }[graph_choice](n, m)


"""
--------------------------------------------------------------------------------
 Depth First Search.
 Args : G - Dictionary of edges
 s - Starting Node
 Vars : vis - Set of visited nodes
 S - Traversal Stack
--------------------------------------------------------------------------------
"""


defdfs(g, s):
"""
 >>> dfs({1: [2, 3], 2: [4, 5], 3: [], 4: [], 5: []}, 1)
 1
 2
 4
 5
 3
 """
vis, _s= {s}, [s]
print(s)
while_s:
flag=0
foriing[_s[-1]]:
ifinotinvis:
_s.append(i)
vis.add(i)
flag=1
print(i)
break
ifnotflag:
_s.pop()


"""
--------------------------------------------------------------------------------
 Breadth First Search.
 Args : G - Dictionary of edges
 s - Starting Node
 Vars : vis - Set of visited nodes
 Q - Traversal Stack
--------------------------------------------------------------------------------
"""


defbfs(g, s):
"""
 >>> bfs({1: [2, 3], 2: [4, 5], 3: [6, 7], 4: [], 5: [8], 6: [], 7: [], 8: []}, 1)
 1
 2
 3
 4
 5
 6
 7
 8
 """
vis, q= {s}, deque([s])
print(s)
whileq:
u=q.popleft()
forving[u]:
ifvnotinvis:
vis.add(v)
q.append(v)
print(v)


"""
--------------------------------------------------------------------------------
 Dijkstra's shortest path Algorithm
 Args : G - Dictionary of edges
 s - Starting Node
 Vars : dist - Dictionary storing shortest distance from s to every other node
 known - Set of knows nodes
 path - Preceding node in path
--------------------------------------------------------------------------------
"""


defdijk(g, s):
"""
 dijk({1: [(2, 7), (3, 9), (6, 14)],
 2: [(1, 7), (3, 10), (4, 15)],
 3: [(1, 9), (2, 10), (4, 11), (6, 2)],
 4: [(2, 15), (3, 11), (5, 6)],
 5: [(4, 6), (6, 9)],
 6: [(1, 14), (3, 2), (5, 9)]}, 1)
 7
 9
 11
 20
 20
 """
dist, known, path= {s: 0}, set(), {s: 0}
whileTrue:
iflen(known) ==len(g) -1:
break
mini=100000
forkey, valueindist:
ifkeynotinknownandvalue<mini:
mini=value
u=key
known.add(u)
forving[u]:
ifv[0] notinknownanddist[u] +v[1] <dist.get(v[0], 100000):
dist[v[0]] =dist[u] +v[1]
path[v[0]] =u
forkey, valueindist.items():
ifkey!=s:
print(value)


"""
--------------------------------------------------------------------------------
 Topological Sort
--------------------------------------------------------------------------------
"""


deftopo(g, ind=None, q=None):
ifqisNone:
q= [1]
ifindisNone:
ind= [0] * (len(g) +1) # SInce oth Index is ignored
foruing:
forving[u]:
ind[v] +=1
q=deque()
foriing:
ifind[i] ==0:
q.append(i)
iflen(q) ==0:
return
v=q.popleft()
print(v)
forwing[v]:
ind[w] -=1
ifind[w] ==0:
q.append(w)
topo(g, ind, q)


"""
--------------------------------------------------------------------------------
 Reading an Adjacency matrix
--------------------------------------------------------------------------------
"""


defadjm():
r"""
 Reading an Adjacency matrix

 Parameters:
 None

 Returns:
 tuple: A tuple containing a list of edges and number of edges

 Example:
 >>> # Simulate user input for 3 nodes
 >>> input_data = "4\n0 1 0 1\n1 0 1 0\n0 1 0 1\n1 0 1 0\n"
 >>> import sys,io
 >>> original_input = sys.stdin
 >>> sys.stdin = io.StringIO(input_data) # Redirect stdin for testing
 >>> adjm()
 ([(0, 1, 0, 1), (1, 0, 1, 0), (0, 1, 0, 1), (1, 0, 1, 0)], 4)
 >>> sys.stdin = original_input # Restore original stdin
 """
n=int(input().strip())
a= []
for_inrange(n):
a.append(tuple(map(int, input().strip().split())))
returna, n


"""
--------------------------------------------------------------------------------
 Floyd Warshall's algorithm
 Args : G - Dictionary of edges
 s - Starting Node
 Vars : dist - Dictionary storing shortest distance from s to every other node
 known - Set of knows nodes
 path - Preceding node in path

--------------------------------------------------------------------------------
"""


deffloy(a_and_n):
 (a, n) =a_and_n
dist=list(a)
path= [[0] *nforiinrange(n)]
forkinrange(n):
foriinrange(n):
forjinrange(n):
ifdist[i][j] >dist[i][k] +dist[k][j]:
dist[i][j] =dist[i][k] +dist[k][j]
path[i][k] =k
print(dist)


"""
--------------------------------------------------------------------------------
 Prim's MST Algorithm
 Args : G - Dictionary of edges
 s - Starting Node
 Vars : dist - Dictionary storing shortest distance from s to nearest node
 known - Set of knows nodes
 path - Preceding node in path
--------------------------------------------------------------------------------
"""


defprim(g, s):
dist, known, path= {s: 0}, set(), {s: 0}
whileTrue:
iflen(known) ==len(g) -1:
break
mini=100000
forkey, valueindist.items():
ifkeynotinknownandvalue<mini:
mini=value
u=key
known.add(u)
forving[u]:
ifv[0] notinknownandv[1] <dist.get(v[0], 100000):
dist[v[0]] =v[1]
path[v[0]] =u
returndist


"""
--------------------------------------------------------------------------------
 Accepting Edge list
 Vars : n - Number of nodes
 m - Number of edges
 Returns : l - Edge list
 n - Number of Nodes
--------------------------------------------------------------------------------
"""


defedglist():
r"""
 Get the edges and number of edges from the user

 Parameters:
 None

 Returns:
 tuple: A tuple containing a list of edges and number of edges

 Example:
 >>> # Simulate user input for 3 edges and 4 vertices: (1, 2), (2, 3), (3, 4)
 >>> input_data = "4 3\n1 2\n2 3\n3 4\n"
 >>> import sys,io
 >>> original_input = sys.stdin
 >>> sys.stdin = io.StringIO(input_data) # Redirect stdin for testing
 >>> edglist()
 ([(1, 2), (2, 3), (3, 4)], 4)
 >>> sys.stdin = original_input # Restore original stdin
 """
n, m=tuple(map(int, input().split(" ")))
edges= []
for_inrange(m):
edges.append(tuple(map(int, input().split(" "))))
returnedges, n


"""
--------------------------------------------------------------------------------
 Kruskal's MST Algorithm
 Args : E - Edge list
 n - Number of Nodes
 Vars : s - Set of all nodes as unique disjoint sets (initially)
--------------------------------------------------------------------------------
"""


defkrusk(e_and_n):
"""
 Sort edges on the basis of distance
 """
 (e, n) =e_and_n
e.sort(reverse=True, key=lambdax: x[2])
s= [{i} foriinrange(1, n+1)]
whileTrue:
iflen(s) ==1:
break
print(s)
x=e.pop()
foriinrange(len(s)):
ifx[0] ins[i]:
break
forjinrange(len(s)):
ifx[1] ins[j]:
ifi==j:
break
s[j].update(s[i])
s.pop(i)
break


deffind_isolated_nodes(graph):
"""
 Find the isolated node in the graph

 Parameters:
 graph (dict): A dictionary representing a graph.

 Returns:
 list: A list of isolated nodes.

 Examples:
 >>> graph1 = {1: [2, 3], 2: [1, 3], 3: [1, 2], 4: []}
 >>> find_isolated_nodes(graph1)
 [4]

 >>> graph2 = {'A': ['B', 'C'], 'B': ['A'], 'C': ['A'], 'D': []}
 >>> find_isolated_nodes(graph2)
 ['D']

 >>> graph3 = {'X': [], 'Y': [], 'Z': []}
 >>> find_isolated_nodes(graph3)
 ['X', 'Y', 'Z']

 >>> graph4 = {1: [2, 3], 2: [1, 3], 3: [1, 2]}
 >>> find_isolated_nodes(graph4)
 []

 >>> graph5 = {}
 >>> find_isolated_nodes(graph5)
 []
 """
isolated= []
fornodeingraph:
ifnotgraph[node]:
isolated.append(node)
returnisolated