Python Algorithm Implementations: NetworkX, DFS, BFS
Python Algorithm Implementations
Graph Algorithms with NetworkX
These examples demonstrate various graph algorithms using the NetworkX library in Python.
Shortest Path Algorithm (BFS Modification)
import networkx as nx
from sys import maxsize as infinite
from simple_stack import Stack
from simple_queue import Queue
def solve(graph, u, v):
solutions_list = []
distance = {node: infinite for node in graph.nodes}
distance[u] = 0
q = Queue()
q.enqueue(u)
while not q.isEmpty():
current_node = q.dequeue()
for neighbor in graph.neighbors(current_node):
weight = graph[current_node][neighbor]['weight']
if distance[current_node] + weight < distance[neighbor]:
distance[neighbor] = distance[current_node] + weight
q.enqueue(neighbor)
min_distance = distance[v]
if min_distance == infinite:
return solutions_list
stack = Stack()
stack.push((u, [u], 0))
while not stack.isEmpty():
current_node, current_path, current_distance = stack.pop()
if current_node == v:
if current_distance == min_distance:
solutions_list.append(current_path)
continue
for neighbor in graph.neighbors(current_node):
weight = graph[current_node][neighbor]['weight']
new_distance = current_distance + weight
if new_distance <= min_distance:
stack.push((neighbor, current_path + [neighbor], new_distance))
return solutions_list
Custom Iterator Implementations
These classes provide custom iterator functionality using a stack-based approach.
Iterator with Minimum and Maximum Values
from simple_stack import Stack
class My_Iterator:
def __init__(self, num_digits, min_values, max_values):
self.num_digits = num_digits
self.min_values = min_values
self.max_values = max_values
self.stack = Stack()
initial_state = [min_values[i] for i in range(num_digits)]
self.stack.push((initial_state, 0))
def next(self):
while not self.stack.isEmpty():
current_state, index = self.stack.pop()
if index == self.num_digits:
yield current_state
else:
for value in range(self.max_values[index], self.min_values[index] - 1, -1):
new_state = current_state[:]
new_state[index] = value
self.stack.push((new_state, index + 1))
Iterator with Digit Values
from simple_stack import Stack
class My_Iterator:
def __init__(self, num_digits, digit_values):
self.num_digits = num_digits
self.digit_values = digit_values
self.stack = Stack()
initial_state = [None] * num_digits
self.stack.push((initial_state, 0))
def next(self):
while not self.stack.isEmpty():
current_state, index = self.stack.pop()
if index == self.num_digits:
yield current_state
else:
for value in reversed(self.digit_values[index]):
new_state = current_state[:]
new_state[index] = value
self.stack.push((new_state, index + 1))
Dynamic Programming and Greedy Algorithms
Greedy Coin Change
from sys import maxsize as infinite
def solve(coins, change):
change_list = []
while change > 0 and coins != [0] * len(coins):
max_coin = max(coins)
index = coins.index(max_coin)
if change >= coins[index]:
change_list.append(index + 1)
change -= coins[index]
coins[index] = 0
return change_list
Greedy Knapsack
def solve(items, capacity):
taken = []
value = 0
items = sorted(
enumerate(items), key=lambda x: x[1][0] / x[1][1], reverse=True
)
for index, (v, w) in items:
if w <= capacity:
capacity -= w
value += v
taken.append(index + 1)
if capacity == 0:
break
return taken, value
Coin Change with DFS (Distinct Coins)
from sys import maxsize as infinite
def solve(coins, change):
solutions_list = []
solutions_set = []
min_num_coins = infinite
def is_valid(solution, level):
current_change = 0
current_coins = set()
for index in range(level):
current_change += coins[solution[index] - 1]
current_coins.add(coins[solution[index] - 1])
return (
current_change <= change and \
len(solution[:level]) == len(current_coins)
), current_change == change
def dfs(solution=[-1] * len(coins), level=0):
nonlocal min_num_coins
valid, is_solution = is_valid(solution, level)
if not valid or level == len(coins):
return
if is_solution:
solution = solution[:level]
if (solution_set := set(solution)) not in solutions_set:
if level < min_num_coins:
min_num_coins = level
solutions_list.clear()
solutions_set.clear()
if level == min_num_coins:
solutions_list.append(solution)
solutions_set.append(solution_set)
return
for digit in range(1, len(coins) + 1):
solution[level] = digit
dfs(list(solution), level + 1)
solution[level] = -1
dfs()
return solutions_list if solutions_list else None
Median Finding (Quickselect)
from simple_stack import Stack
def solve(items, median_index):
stack = Stack()
stack.push((0, len(items) - 1))
while not stack.isEmpty():
low, high = stack.pop()
if low == high:
return items[low]
pivot = partition(items, low, high)
if pivot == median_index:
return items[pivot]
elif pivot > median_index:
stack.push((low, pivot - 1))
else:
stack.push((pivot + 1, high))
return -1
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
Dijkstra’s Algorithm (Shortest Path)
import networkx as nx
from sys import maxsize as infinite
from simple_queue import Queue
import heapq
def solve(graph, from_node, to_node):
priority_queue = []
distances = {node: float('inf') for node in graph.nodes}
distances[from_node] = 0
heapq.heappush(priority_queue, (0, from_node))
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_distance > distances[current_node]:
continue
for neighbor in graph.successors(current_node):
weight = graph[current_node][neighbor]['weight']
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances[to_node] if distances[to_node] != float('inf') else -1
Shortest Path (Recursive, Memoized)
from networkx import *
def solve(graph, from_node, to_node):
value = 0
taken = []
mem = {7: ((None, 7), 0)}
def dist(u, v):
solutions = []
if v == from_node:
return 0
for pred in graph.predecessors(v):
solutions.append(
((pred, v), dist(v, pred) + graph[pred][v]['weight'])
)
if not solutions:
mem[v] = [(v, u), graph[v][u]['weight']]
return mem[v][1]
minimum = min(solutions, key=lambda item: item[1])
mem[v] = minimum
return minimum[1]
dist(to_node, to_node)
data = mem[to_node]
taken.append(data[0][1])
value = data[1]
while True:
u, v = data[0]
taken.insert(0, u)
if u == from_node:
break
data = mem[u]
return value, taken
Longest Increasing Subsequence (Tabulation)
def solve_tabulation(items):
table = [0] * len(items)
taken = []
def fill_table():
aux = [1] * len(items)
for i in range(len(items) - 2, -1, -1):
for j in range(i + 1, len(items)):
if items[i] < items[j]:
aux[i] = max(aux[i], aux[j] + 1)
max_length = max(aux)
for i in range(len(items)):
if aux[i] == max_length:
table[i] = 1
max_length -= 1
if max_length == 0:
break
def fill_taken():
nonlocal taken
for i in range(len(items)):
if table[i] == 1:
taken.append(i + 1)
fill_table()
fill_taken()
return len(taken), taken
Graph Coloring Algorithms
Greedy Graph Coloring
def greedy_coloring(graph, order_nodes):
node_colors = [None] * len(order_nodes)
current_color = 0
current_node = 0
node_colors[0] = current_color
while None in node_colors:
if node_colors[current_node] is None:
apto = True
for neighbour in graph.neighbors(order_nodes[current_node]):
neighbour_index = order_nodes.index(neighbour)
if node_colors[neighbour_index] == current_color:
apto = False
break
if apto:
node_colors[current_node] = current_color
else:
current_color = current_color + 1
node_colors[current_node] = current_color
if current_node == len(order_nodes) - 1:
current_node = 0
current_color += 1
current_node += 1
return node_colors
Recursive Largest First (RLF) Graph Coloring
import networkx as nx
def rlf_graph_coloring(graph):
nodes = set(graph.nodes())
colors = {} # Dictionary: key=node, value=color
color = 0 # Start with color 0
while nodes:
node = max(nodes, key=lambda v: graph.degree(v))
colors[node] = color # Assign color to the initial node
colored_this_round = {node} # Set of nodes colored in this round
available_nodes = nodes - {node}
for v in available_nodes.copy():
if all(neighbor not in colored_this_round for neighbor in graph.neighbors(v)):
colors[v] = color
colored_this_round.add(v)
nodes -= colored_this_round
color += 1
sorted_dict = {k: colors[k] for k in sorted(colors)}
return list(sorted_dict.values())
Depth-First Search (DFS) – Knapsack Example
def dfs(node):
nonlocal best, best_value
# Register the node visiting order
if record_visiting_order:
visiting_order.append(node.index)
if node.index >= len(items):
if node.value > best_value:
best_value = node.value
best = node
return
item = items[node.index]
new_node = Node(index=node.index + 1, taken=node.taken, value=node.value, room=node.room)
dfs(new_node) # Recurse without the item
if node.room >= item.weight:
new_taken = node.taken + [item.index]
new_node = Node(index=node.index + 1, taken=new_taken, value=node.value + item.value, room=node.room - item.weight)
dfs(new_node)
dfs(root_node)