Graph Visualization Example

# @ignore-function-tree
def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    visited = set()
    queue = [{'node': start, 'distance': 0}]
    
    while queue:
        # Find the node with the minimum current distance
        current = min(queue, key=lambda x: x['distance'])
        queue.remove(current)
        current_node = current['node']
        
        if current_node in visited:
            continue
        visited.add(current_node)
        
        # Update distances for neighboring nodes
        for neighbor, weight in graph[current_node].items():
            new_distance = distances[current_node] + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                queue.append({'node': neighbor, 'distance': new_distance})
    
    return distances

graph = create_graph({
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
})

shortest_distances = dijkstra(graph, 'A')

def bfs(graph, start):
    visited = set()
    queue = Queue()
    queue.enqueue(start)
    visited.add(start)
    result = []
    
    while queue.size:
        node = queue.dequeue()
        result.append(node)
        # Traverse all neighbors of the current node
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.enqueue(neighbor)
    return result

graph = create_graph({
    '1': {'2': 3, '3': 5},
    '2': {'1': 3, '4': 2, '5': 6},
    '3': {'1': 5, '5': 4},
    '4': {'2': 2, '5': 1, '6': 3},
    '5': {'2': 6, '3': 4, '4': 1},
    '6': {'4': 3}
})
bfs(graph, '1')

def dfs(graph, start):
    visited = set()
    stack = Stack()
    stack.push(start)
    visited.add(start)
    result = []
    
    while stack.size:
        node = stack.pop()
        result.append(node)
        # Traverse all neighbors of the current node
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.push(neighbor)
    return result

# Example graph definition
graph = create_graph({
    'Core': {'A': 5, 'B': 3, 'C': 7},
    'A': {'Core': 5},
    'B': {'Core': 3, 'D': 2},
    'C': {'Core': 7},
    'D': {'B': 2}
})

dfs(graph, 'A')

def bellman_ford(graph, start):
    # Initialize distance dictionary
    distance = {node: float('infinity') for node in graph}
    distance[start] = 0

    # Relaxation operation: iterate all edges V-1 times
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distance[node] + weight < distance[neighbor]:
                    distance[neighbor] = distance[node] + weight

    # Check for negative cycles
    for node in graph:
        for neighbor, weight in graph[node].items():
            if distance[node] + weight < distance[neighbor]:
                return "Graph contains a negative-weight cycle!"

    return distance

# Example graph (with negative-weight edges)
graph = create_graph({
    'A': {'B': 4, 'C': 5},
    'B': {'C': -2, 'D': 3},
    'C': {'D': 4},
    'D': {'E': 2},
    'E': {}
})

# Compute shortest paths from 'A'
result = bellman_ford(graph, 'A')

def kahn_algorithm(graph):
    # Initialize in-degree dictionary
    in_degree = {node: 0 for node in graph}
    # Calculate in-degrees for all nodes
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    # Initialize queue with nodes of in-degree 0
    queue = Queue()
    for node in in_degree:
        if in_degree[node] == 0:
            queue.enqueue(node)
    topological_order = []
    
    # Process nodes in queue
    while queue.size:
        current_node = queue.dequeue()
        topological_order.append(current_node)
        # Update in-degrees of neighbors
        for neighbor in graph[current_node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.enqueue(neighbor)
    
    # Check for cycles
    if len(topological_order) != len(graph):
        return "Graph contains a cycle! Topological sort not possible."
    else:
        return topological_order

# Example graph (course dependencies)
graph = create_graph({
    'Data Structures': ['Algorithms'],
    'Algorithms': ['Machine Learning'],
    'Mathematics': ['Machine Learning', 'Deep Learning'],
    'Machine Learning': ['Deep Learning'],
    'Deep Learning': [],
    'Python Basics': ['Data Structures', 'Mathematics']
}, True)

# Execute Kahn's algorithm
result = kahn_algorithm(graph)