Main.java

import java.util.*;

/**
 * Graph implementation using adjacency matrix representation.
 * Supports weighted directed graphs with various algorithms for pathfinding and analysis.
 */
class Graph {
    private static final int INFINITY = Integer.MAX_VALUE;
    
    private final int[][] adjacencyMatrix;
    private final int vertexCount;

    /**
     * Creates a new graph with the specified number of vertices.
     * 
     * @param vertexCount the number of vertices in the graph
     */
    public Graph(int vertexCount) {
        this.vertexCount = vertexCount;
        this.adjacencyMatrix = new int[vertexCount][vertexCount];
        initializeMatrix();
    }

    private void initializeMatrix() {
        for (int i = 0; i < vertexCount; i++) {
            Arrays.fill(adjacencyMatrix[i], INFINITY);
        }
    }

    /**
     * Adds a weighted directed edge to the graph.
     * 
     * @param source the source vertex
     * @param destination the destination vertex
     * @param weight the edge weight
     */
    public void addEdge(int source, int destination, int weight) {
        validateVertex(source);
        validateVertex(destination);
        adjacencyMatrix[source][destination] = weight;
    }

    /**
     * Prints the adjacency matrix representation of the graph.
     */
    public void printAdjacencyMatrix() {
        System.out.println("Adjacency Matrix:");
        for (int i = 0; i < vertexCount; i++) {
            for (int j = 0; j < vertexCount; j++) {
                if (adjacencyMatrix[i][j] == INFINITY) {
                    System.out.print("∞\t");
                } else {
                    System.out.print(adjacencyMatrix[i][j] + "\t");
                }
            }
            System.out.println();
        }
    }

    private void validateVertex(int vertex) {
        if (vertex < 0 || vertex >= vertexCount) {
            throw new IllegalArgumentException("Vertex " + vertex + " is out of bounds");
        }
    }

    /**
     * Finds the shortest paths from a source vertex using the Bellman-Ford algorithm.
     * Detects negative cycles if present.
     * 
     * @param source the source vertex
     */
    public void findShortestPathsBellmanFord(int source) {
        validateVertex(source);
        
        int[] distances = initializeDistances(source);
        
        relaxEdges(distances);
        
        if (hasNegativeCycle(distances)) {
            System.out.println("The graph contains a negative cycle.");
            return;
        }
        
        printShortestPaths(source, distances);
    }

    private int[] initializeDistances(int source) {
        int[] distances = new int[vertexCount];
        Arrays.fill(distances, INFINITY);
        distances[source] = 0;
        return distances;
    }

    private void relaxEdges(int[] distances) {
        for (int k = 0; k < vertexCount - 1; k++) {
            for (int i = 0; i < vertexCount; i++) {
                for (int j = 0; j < vertexCount; j++) {
                    if (canRelaxEdge(i, j, distances)) {
                        distances[j] = distances[i] + adjacencyMatrix[i][j];
                    }
                }
            }
        }
    }

    private boolean canRelaxEdge(int from, int to, int[] distances) {
        return adjacencyMatrix[from][to] != INFINITY 
            && distances[from] != INFINITY 
            && distances[from] + adjacencyMatrix[from][to] < distances[to];
    }

    private boolean hasNegativeCycle(int[] distances) {
        for (int i = 0; i < vertexCount; i++) {
            for (int j = 0; j < vertexCount; j++) {
                if (canRelaxEdge(i, j, distances)) {
                    return true;
                }
            }
        }
        return false;
    }

    private void printShortestPaths(int source, int[] distances) {
        System.out.println("Shortest paths from vertex " + (source + 1) + ":");
        for (int i = 0; i < vertexCount; i++) {
            if (distances[i] == INFINITY) {
                System.out.println("No path from vertex " + (source + 1) + " to vertex " + (i + 1));
            } else {
                System.out.println("Distance to vertex " + (i + 1) + ": " + distances[i]);
            }
        }
    }

    /**
     * Finds all cycles in the graph using Depth-First Search (DFS).
     * 
     * @return a list of cycles, where each cycle is represented as a list of vertices
     */
    public List<List<Integer>> findCycles() {
        List<List<Integer>> cycles = new ArrayList<>();
        boolean[] visited = new boolean[vertexCount];
        
        for (int i = 0; i < vertexCount; i++) {
            if (!visited[i]) {
                List<Integer> currentPath = new ArrayList<>();
                dfsFindCycles(i, visited, new boolean[vertexCount], currentPath, cycles);
            }
        }
        return cycles;
    }

    private void dfsFindCycles(int vertex, boolean[] visited, boolean[] inPath, 
                               List<Integer> currentPath, List<List<Integer>> cycles) {
        visited[vertex] = true;
        inPath[vertex] = true;
        currentPath.add(vertex);

        for (int i = 0; i < vertexCount; i++) {
            if (adjacencyMatrix[vertex][i] != INFINITY) {
                if (inPath[i]) {
                    cycles.add(extractCycle(currentPath, i));
                } else if (!visited[i]) {
                    dfsFindCycles(i, visited, inPath, currentPath, cycles);
                }
            }
        }

        inPath[vertex] = false;
        currentPath.remove(currentPath.size() - 1);
    }

    private List<Integer> extractCycle(List<Integer> path, int cycleStart) {
        List<Integer> cycle = new ArrayList<>();
        int startIndex = path.indexOf(cycleStart);
        for (int j = startIndex; j < path.size(); j++) {
            cycle.add(path.get(j));
        }
        return cycle;
    }

    /**
     * Calculates the height of the tree structure from a given node.
     * 
     * @param node the starting node
     * @return the height of the tree from the given node
     */
    public int calculateHeight(int node) {
        validateVertex(node);
        boolean[] visited = new boolean[vertexCount];
        return calculateHeightRecursive(node, visited);
    }

    private int calculateHeightRecursive(int node, boolean[] visited) {
        visited[node] = true;
        int maxHeight = 0;
        
        for (int i = 0; i < vertexCount; i++) {
            if (adjacencyMatrix[node][i] != INFINITY && !visited[i]) {
                maxHeight = Math.max(maxHeight, calculateHeightRecursive(i, visited));
            }
        }
        return maxHeight + 1;
    }

    /**
     * Performs a pre-order traversal of the graph starting from a given node.
     * 
     * @param node the starting node
     */
    public void preOrderTraversal(int node) {
        validateVertex(node);
        boolean[] visited = new boolean[vertexCount];
        System.out.print("Pre-order traversal from node " + (node + 1) + ": ");
        preOrderTraversalRecursive(node, visited);
        System.out.println();
    }

    private void preOrderTraversalRecursive(int node, boolean[] visited) {
        visited[node] = true;
        System.out.print((node + 1) + " ");
        
        for (int i = 0; i < vertexCount; i++) {
            if (adjacencyMatrix[node][i] != INFINITY && !visited[i]) {
                preOrderTraversalRecursive(i, visited);
            }
        }
    }

    /**
     * Finds the shortest path between two vertices using Dijkstra's algorithm.
     * 
     * @param source the source vertex
     * @param destination the destination vertex
     */
    public void findShortestPathDijkstra(int source, int destination) {
        validateVertex(source);
        validateVertex(destination);
        
        DijkstraResult result = runDijkstra(source);
        printDijkstraPath(source, destination, result);
    }

    private DijkstraResult runDijkstra(int source) {
        int[] distances = new int[vertexCount];
        boolean[] visited = new boolean[vertexCount];
        int[] predecessors = new int[vertexCount];
        
        Arrays.fill(distances, INFINITY);
        Arrays.fill(predecessors, -1);
        distances[source] = 0;

        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(v -> distances[v]));
        queue.add(source);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            if (visited[current]) continue;
            visited[current] = true;

            relaxAdjacentEdges(current, distances, visited, predecessors, queue);
        }

        return new DijkstraResult(distances, predecessors);
    }

    private void relaxAdjacentEdges(int current, int[] distances, boolean[] visited, 
                                    int[] predecessors, PriorityQueue<Integer> queue) {
        for (int neighbor = 0; neighbor < vertexCount; neighbor++) {
            if (adjacencyMatrix[current][neighbor] != INFINITY && !visited[neighbor]) {
                int newDistance = distances[current] + adjacencyMatrix[current][neighbor];
                if (newDistance < distances[neighbor]) {
                    distances[neighbor] = newDistance;
                    predecessors[neighbor] = current;
                    queue.add(neighbor);
                }
            }
        }
    }

    private void printDijkstraPath(int source, int destination, DijkstraResult result) {
        if (result.distances[destination] == INFINITY) {
            System.out.println("No path from vertex " + (source + 1) + " to vertex " + (destination + 1));
        } else {
            System.out.println("Shortest path (Dijkstra) from vertex " + (source + 1) + " to vertex " + (destination + 1) + ":");
            List<Integer> path = reconstructPath(destination, result.predecessors);
            printPath(path);
            System.out.println("\nTotal distance: " + result.distances[destination]);
        }
    }

    private List<Integer> reconstructPath(int destination, int[] predecessors) {
        List<Integer> path = new ArrayList<>();
        for (int v = destination; v != -1; v = predecessors[v]) {
            path.add(v);
        }
        Collections.reverse(path);
        return path;
    }

    private void printPath(List<Integer> path) {
        for (int i = 0; i < path.size(); i++) {
            System.out.print((path.get(i) + 1));
            if (i < path.size() - 1) {
                System.out.print(" -> ");
            }
        }
    }

    private static class DijkstraResult {
        final int[] distances;
        final int[] predecessors;

        DijkstraResult(int[] distances, int[] predecessors) {
            this.distances = distances;
            this.predecessors = predecessors;
        }
    }
}

/**
 * Main class demonstrating graph operations and algorithms.
 */
public class Main {
    public static void main(String[] args) {
        Graph graph = createSampleGraph();
        
        demonstrateGraphOperations(graph);
    }

    private static Graph createSampleGraph() {
        Graph graph = new Graph(13);
        
        addEdges(graph);
        
        return graph;
    }

    private static void addEdges(Graph graph) {
        graph.addEdge(0, 1, 200);
        graph.addEdge(0, 12, 250);
        graph.addEdge(0, 8, 290);
        graph.addEdge(1, 5, 360);
        graph.addEdge(1, 2, 190);
        graph.addEdge(2, 5, 250);
        graph.addEdge(2, 4, 190);
        graph.addEdge(2, 0, 300);
        graph.addEdge(3, 2, 180);
        graph.addEdge(4, 5, 300);
        graph.addEdge(4, 9, 400);
        graph.addEdge(5, 10, 350);
        graph.addEdge(5, 11, 300);
        graph.addEdge(6, 3, 300);
        graph.addEdge(6, 2, 250);
        graph.addEdge(6, 0, 150);
        graph.addEdge(7, 6, 200);
        graph.addEdge(7, 0, 220);
        graph.addEdge(8, 7, 180);
        graph.addEdge(8, 12, 180);
        graph.addEdge(9, 3, 200);
        graph.addEdge(10, 9, 700);
        graph.addEdge(10, 4, 200);
        graph.addEdge(11, 1, 150);
        graph.addEdge(12, 11, 100);
        graph.addEdge(12, 1, 200);
    }

    private static void demonstrateGraphOperations(Graph graph) {
        graph.printAdjacencyMatrix();
        System.out.println();

        graph.findShortestPathsBellmanFord(0);
        System.out.println();

        demonstrateCycleDetection(graph);

        int height = graph.calculateHeight(0);
        System.out.println("Tree height from vertex 1: " + height);
        System.out.println();

        graph.preOrderTraversal(0);
        System.out.println();

        graph.findShortestPathDijkstra(0, 2);
        System.out.println();
    }

    private static void demonstrateCycleDetection(Graph graph) {
        List<List<Integer>> cycles = graph.findCycles();
        System.out.println("Cycles found:");
        for (List<Integer> cycle : cycles) {
            printCycle(cycle);
        }
        System.out.println();
    }

    private static void printCycle(List<Integer> cycle) {
        for (int i = 0; i < cycle.size(); i++) {
            System.out.print((cycle.get(i) + 1));
            if (i < cycle.size() - 1) {
                System.out.print(" -> ");
            }
        }
        System.out.println();
    }
}