graph

from collections import deque class Graph: def init(self, directed=False, weighted=False): self.graph = {} # Adjacency list self.directed = directed # Whether the graph is directed or undirected self.weighted = weighted # Whether the graph is weighted or not def add_vertex(self, vertex): """Add a vertex to the graph.""" if vertex not in self.graph: self.graph[vertex] = [] def remove_vertex(self, vertex): """Remove a vertex from the graph and its associated edges.""" if vertex in self.graph: del self.graph[vertex] for v in self.graph: # Remove the vertex from other vertex's adjacency list self.graph[v] = [neighbor for neighbor in self.graph[v] if neighbor[0] != vertex] def add_edge(self, vertex1, vertex2, weight=None): """Add an edge between vertex1 and vertex2 (directional or not, weighted or not).""" if vertex1 not in self.graph: self.add_vertex(vertex1) if vertex2 not in self.graph: self.add_vertex(vertex2) if self.weighted: # If the graph is weighted, store (neighbor, weight) self.graph[vertex1].append((vertex2, weight)) if not self.directed: self.graph[vertex2].append((vertex1, weight)) else: # If the graph is unweighted, just store the neighbor self.graph[vertex1].append(vertex2) if not self.directed: self.graph[vertex2].append(vertex1) def remove_edge(self, vertex1, vertex2): """Remove the edge between vertex1 and vertex2.""" if vertex1 in self.graph: self.graph[vertex1] = [neighbor for neighbor in self.graph[vertex1] if neighbor[0] != vertex2] if vertex2 in self.graph: self.graph[vertex2] = [neighbor for neighbor in self.graph[vertex2] if neighbor[0] != vertex1] def display(self): """Display the graph as an adjacency list.""" for vertex, edges in self.graph.items(): if self.weighted: # For weighted graphs, print edges with their weights edge_list = [(neighbor, weight) for neighbor, weight in edges] print(f"{vertex}: {edge_list}") else: # For unweighted graphs, print only the neighbors print(f"{vertex}: {edges}") def dfs(self, start): """Depth-First Search (DFS) traversal from start vertex.""" visited = set() self._dfs_recursive(start, visited) print() def _dfs_recursive(self, vertex, visited): """Recursive DFS helper.""" visited.add(vertex) print(vertex, end=" ") for neighbor in self.graph[vertex]: if self.weighted: neighbor = neighbor[0] # Get the vertex from (neighbor, weight) tuple if neighbor not in visited: self._dfs_recursive(neighbor, visited) def bfs(self, start): """Breadth-First Search (BFS) traversal from start vertex.""" visited = set() queue = deque([start]) visited.add(start) while queue: vertex = queue.popleft() print(vertex, end=" ") for neighbor in self.graph[vertex]: if self.weighted: neighbor = neighbor[0] # Get the vertex from (neighbor, weight) tuple if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) print() def has_cycle(self): """Check if the graph contains a cycle.""" visited = set() recursion_stack = set() for vertex in self.graph: if vertex not in visited: if self._has_cycle_recursive(vertex, visited, recursion_stack): return True return False def _has_cycle_recursive(self, vertex, visited, recursion_stack): """Helper for cycle detection.""" visited.add(vertex) recursion_stack.add(vertex) for neighbor in self.graph[vertex]: if self.weighted: neighbor = neighbor[0] # Get the vertex from (neighbor, weight) tuple if neighbor not in visited: if self._has_cycle_recursive(neighbor, visited, recursion_stack): return True elif neighbor in recursion_stack: return True recursion_stack.remove(vertex) return False # 3. Dijkstra's Algorithm (Shortest Path for Weighted Graphs) def dijkstra(self, start): """Dijkstra’s Algorithm to find the shortest path in a weighted graph.""" # Distance from start node to all other nodes distances = {vertex: float('inf') for vertex in self.graph} distances[start] = 0 # Priority queue to store vertices to be processed, ordered by distance

Mar 22, 2025 - 06:21

from collections import deque

class Graph:
    def __init__(self, directed=False, weighted=False):
        self.graph = {}  # Adjacency list
        self.directed = directed  # Whether the graph is directed or undirected
        self.weighted = weighted  # Whether the graph is weighted or not

    def add_vertex(self, vertex):
        """Add a vertex to the graph."""
        if vertex not in self.graph:
            self.graph[vertex] = []

    def remove_vertex(self, vertex):
        """Remove a vertex from the graph and its associated edges."""
        if vertex in self.graph:
            del self.graph[vertex]
            for v in self.graph:
                # Remove the vertex from other vertex's adjacency list
                self.graph[v] = [neighbor for neighbor in self.graph[v] if neighbor[0] != vertex]

    def add_edge(self, vertex1, vertex2, weight=None):
        """Add an edge between vertex1 and vertex2 (directional or not, weighted or not)."""
        if vertex1 not in self.graph:
            self.add_vertex(vertex1)
        if vertex2 not in self.graph:
            self.add_vertex(vertex2)

        if self.weighted:
            # If the graph is weighted, store (neighbor, weight)
            self.graph[vertex1].append((vertex2, weight))
            if not self.directed:
                self.graph[vertex2].append((vertex1, weight))
        else:
            # If the graph is unweighted, just store the neighbor
            self.graph[vertex1].append(vertex2)
            if not self.directed:
                self.graph[vertex2].append(vertex1)

    def remove_edge(self, vertex1, vertex2):
        """Remove the edge between vertex1 and vertex2."""
        if vertex1 in self.graph:
            self.graph[vertex1] = [neighbor for neighbor in self.graph[vertex1] if neighbor[0] != vertex2]
        if vertex2 in self.graph:
            self.graph[vertex2] = [neighbor for neighbor in self.graph[vertex2] if neighbor[0] != vertex1]

    def display(self):
        """Display the graph as an adjacency list."""
        for vertex, edges in self.graph.items():
            if self.weighted:
                # For weighted graphs, print edges with their weights
                edge_list = [(neighbor, weight) for neighbor, weight in edges]
                print(f"{vertex}: {edge_list}")
            else:
                # For unweighted graphs, print only the neighbors
                print(f"{vertex}: {edges}")


    def dfs(self, start):
        """Depth-First Search (DFS) traversal from start vertex."""
        visited = set()
        self._dfs_recursive(start, visited)
        print()

    def _dfs_recursive(self, vertex, visited):
        """Recursive DFS helper."""
        visited.add(vertex)
        print(vertex, end=" ")
        for neighbor in self.graph[vertex]:
            if self.weighted:
                neighbor = neighbor[0]  # Get the vertex from (neighbor, weight) tuple
            if neighbor not in visited:
                self._dfs_recursive(neighbor, visited)

    def bfs(self, start):
        """Breadth-First Search (BFS) traversal from start vertex."""
        visited = set()
        queue = deque([start])
        visited.add(start)

        while queue:
            vertex = queue.popleft()
            print(vertex, end=" ")

            for neighbor in self.graph[vertex]:
                if self.weighted:
                    neighbor = neighbor[0]  # Get the vertex from (neighbor, weight) tuple
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        print()

    def has_cycle(self):
        """Check if the graph contains a cycle."""
        visited = set()
        recursion_stack = set()

        for vertex in self.graph:
            if vertex not in visited:
                if self._has_cycle_recursive(vertex, visited, recursion_stack):
                    return True
        return False

    def _has_cycle_recursive(self, vertex, visited, recursion_stack):
        """Helper for cycle detection."""
        visited.add(vertex)
        recursion_stack.add(vertex)

        for neighbor in self.graph[vertex]:
            if self.weighted:
                neighbor = neighbor[0]  # Get the vertex from (neighbor, weight) tuple
            if neighbor not in visited:
                if self._has_cycle_recursive(neighbor, visited, recursion_stack):
                    return True
            elif neighbor in recursion_stack:
                return True

        recursion_stack.remove(vertex)
        return False
 # 3. Dijkstra's Algorithm (Shortest Path for Weighted Graphs)
    def dijkstra(self, start):
        """Dijkstra’s Algorithm to find the shortest path in a weighted graph."""
        # Distance from start node to all other nodes
        distances = {vertex: float('inf') for vertex in self.graph}
        distances[start] = 0

        # Priority queue to store vertices to be processed, ordered by distance
        pq = [(0, start)]  # (distance, vertex)

        while pq:
            current_distance, current_vertex = heapq.heappop(pq)

            # Skip processing if we already found a shorter path
            if current_distance > distances[current_vertex]:
                continue

            for neighbor in self.graph[current_vertex]:
                if self.weighted:
                    neighbor_vertex, weight = neighbor
                else:
                    neighbor_vertex, weight = neighbor, 1

                distance = current_distance + weight
                # If a shorter path is found
                if distance < distances[neighbor_vertex]:
                    distances[neighbor_vertex] = distance
                    heapq.heappush(pq, (distance, neighbor_vertex))

        return distances

    # 4. A* Algorithm (Shortest Path with Heuristic)
    def a_star(self, start, goal, heuristic):
        """A* Algorithm to find the shortest path using heuristic for weighted graphs."""
        # Distance from start node
        g_costs = {vertex: float('inf') for vertex in self.graph}
        g_costs[start] = 0

        # Estimated total cost from start to goal through each vertex
        f_costs = {vertex: float('inf') for vertex in self.graph}
        f_costs[start] = heuristic[start]

        # Priority queue to store vertices to be processed, ordered by f_cost (g_cost + heuristic)
        pq = [(f_costs[start], start)]  # (f_cost, vertex)

        came_from = {}  # To track the best path

        while pq:
            _, current_vertex = heapq.heappop(pq)

            if current_vertex == goal:
                # Reconstruct the path from start to goal
                path = []
                while current_vertex in came_from:
                    path.append(current_vertex)
                    current_vertex = came_from[current_vertex]
                path.append(start)
                path.reverse()
                return path

            for neighbor in self.graph[current_vertex]:
                if self.weighted:
                    neighbor_vertex, weight = neighbor
                else:
                    neighbor_vertex, weight = neighbor, 1

                tentative_g_cost = g_costs[current_vertex] + weight
                if tentative_g_cost < g_costs[neighbor_vertex]:
                    came_from[neighbor_vertex] = current_vertex
                    g_costs[neighbor_vertex] = tentative_g_cost
                    f_costs[neighbor_vertex] = g_costs[neighbor_vertex] + heuristic[neighbor_vertex]
                    heapq.heappush(pq, (f_costs[neighbor_vertex], neighbor_vertex))

        return None  # No path found
        # 4. Topological Sort (Using DFS)
    def topological_sort(self):
        """Perform a topological sort using DFS."""
        visited = set()
        stack = []

        # Helper function for DFS-based topological sort
        def dfs(vertex):
            visited.add(vertex)
            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    dfs(neighbor)
            stack.append(vertex)

        # Perform DFS for all vertices to make sure we get all components
        for vertex in self.graph:
            if vertex not in visited:
                dfs(vertex)

        # The stack will contain the topological order in reverse
        stack.reverse()  # Reverse to get the correct topological order
        return stack
# Example usage:

# Test 1: Undirected, Unweighted Graph
print("Test 1: Undirected Unweighted Graph")
graph_undirected_unweighted = Graph(directed=False, weighted=False)

# Add vertices and edges (undirected and unweighted)
graph_undirected_unweighted.add_edge("A", "B")
graph_undirected_unweighted.add_edge("A", "C")
graph_undirected_unweighted.add_edge("B", "D")
graph_undirected_unweighted.add_edge("C", "D")

# Display the graph
print("Graph adjacency list:")
graph_undirected_unweighted.display()

# Perform DFS and BFS
print("\nDFS on undirected unweighted graph starting from A:")
graph_undirected_unweighted.dfs("A")

print("\nBFS on undirected unweighted graph starting from A:")
graph_undirected_unweighted.bfs("A")

# Check for cycles
print("\nDoes the undirected unweighted graph have a cycle?")
print(graph_undirected_unweighted.has_cycle())  # Expected output: True (A-B-D-C-A)

# Test 2: Directed, Unweighted Graph
print("\nTest 2: Directed Unweighted Graph")
graph_directed_unweighted = Graph(directed=True, weighted=False)

# Add directed edges (unweighted)
graph_directed_unweighted.add_edge("A", "B")
graph_directed_unweighted.add_edge("A", "C")
graph_directed_unweighted.add_edge("B", "D")
graph_directed_unweighted.add_edge("C", "D")

# Display the graph
print("Graph adjacency list:")
graph_directed_unweighted.display()

# Perform DFS and BFS
print("\nDFS on directed unweighted graph starting from A:")
graph_directed_unweighted.dfs("A")

print("\nBFS on directed unweighted graph starting from A:")
graph_directed_unweighted.bfs("A")

# Check for cycles
print("\nDoes the directed unweighted graph have a cycle?")
print(graph_directed_unweighted.has_cycle())  # Expected output: False (no cycle)

# Test 3: Undirected, Weighted Graph
print("\nTest 3: Undirected Weighted Graph")
graph_undirected_weighted = Graph(directed=False, weighted=True)

# Add weighted, undirected edges
graph_undirected_weighted.add_edge("A", "B", 5)
graph_undirected_weighted.add_edge("A", "C", 10)
graph_undirected_weighted.add_edge("B", "D", 3)
graph_undirected_weighted.add_edge("C", "D", 7)

# Display the graph
print("Graph adjacency list with weights:")
graph_undirected_weighted.display()

# Perform DFS and BFS
print("\nDFS on undirected weighted graph starting from A:")
graph_undirected_weighted.dfs("A")

print("\nBFS on undirected weighted graph starting from A:")
graph_undirected_weighted.bfs("A")

# Check for cycles
print("\nDoes the undirected weighted graph have a cycle?")
print(graph_undirected_weighted.has_cycle())  # Expected output: True (A-B-D-C-A)

# Test 4: Directed, Weighted Graph
print("\nTest 4: Directed Weighted Graph")
graph_directed_weighted = Graph(directed=True, weighted=True)

# Add weighted, directed edges
graph_directed_weighted.add_edge("A", "B", 5)
graph_directed_weighted.add_edge("A", "C", 10)
graph_directed_weighted.add_edge("B", "D", 3)
graph_directed_weighted.add_edge("C", "D", 7)

# Display the graph
print("Graph adjacency list with weights:")
graph_directed_weighted.display()

# Perform DFS and BFS
print("\nDFS on directed weighted graph starting from A:")
graph_directed_weighted.dfs("A")

print("\nBFS on directed weighted graph starting from A:")
graph_directed_weighted.bfs("A")

# Check for cycles
print("\nDoes the directed weighted graph have a cycle?")
print(graph_directed_weighted.has_cycle())  # Expected output: False (no cycle)

# Test Dijkstra and A* algorithm
print("\nDijkstra's shortest path from A:")
print(graph_directed_weighted.dijkstra("A"))

# Heuristic for A* algorithm (simple example: goal is to get to D)
heuristic = {"A": 10, "B": 8, "C": 5, "D": 0}  # Just an example of heuristic values
print("\nA* algorithm path from A to D:")
print(graph_directed_weighted.a_star("A", "D", heuristic))