Lab4

import java.util.*;

public class CODINGEXERCISE4 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Graph graph = null;

        while (true) {
            // Step 1: User chooses graph representation (Adjacency Matrix or Adjacency List)
            while (graph == null) {
                System.out.println("Select Graph Representation:");
                System.out.println("1. Adjacency Matrix");
                System.out.println("2. Adjacency List");
                System.out.print("Enter your choice: ");
                int choice = scanner.nextInt();
                scanner.nextLine(); // Consume newline

                if (choice == 1) {
                    graph = new AdjacencyMatrixGraph();
                    System.out.println("Graph initialized with Adjacency Matrix.");
                } else if (choice == 2) {
                    graph = new AdjacencyListGraph();
                    System.out.println("Graph initialized with Adjacency List.");
                } else {
                    System.out.println("Invalid choice. Please try again.");
                }
            }

            // Step 2: Add vertices
            System.out.print("Enter the number of vertices: ");
            int numVertices = scanner.nextInt();
            scanner.nextLine(); // Consume newline

            for (int i = 0; i < numVertices; i++) {
                System.out.print("Enter label for vertex " + (i + 1) + ": ");
                String label = scanner.nextLine();
                graph.addVertex(label);
            }

            // Step 3: Add edges (Directed or Undirected)
            while (true) {
                System.out.print("\nAdd an edge? (yes=1 / no=0): ");
                int addEdgeChoice = scanner.nextInt();
                scanner.nextLine(); // Consume newline
                if (addEdgeChoice == 0) break;

                System.out.print("Enter source vertex: ");
                String src = scanner.nextLine();
                System.out.print("Enter destination vertex: ");
                String dest = scanner.nextLine();
                System.out.print("Is this edge directed? (yes=1 / no=0): ");
                int isDirected = scanner.nextInt();
                scanner.nextLine(); // Consume newline
                graph.addEdge(src, dest, isDirected == 1);
            }

            // Step 4: Perform operations (DFS, BFS, or Display Graph)
            while (true) {
                System.out.println("\nGraph Operations Menu:");
                System.out.println("1. Perform DFS Traversal");
                System.out.println("2. Perform BFS Traversal");
                System.out.println("3. Display Graph");
                System.out.println("4. Reset Graph Representation");
                System.out.println("5. Exit");
                System.out.print("Enter your choice: ");
                int choice = scanner.nextInt();
                scanner.nextLine(); // Consume newline

                switch (choice) {
                    case 1:
                        System.out.print("Enter starting vertex for DFS: ");
                        String startDfs = scanner.nextLine();
                        graph.dfs(startDfs);
                        break;
                    case 2:
                        System.out.print("Enter starting vertex for BFS: ");
                        String startBfs = scanner.nextLine();
                        graph.bfs(startBfs);
                        break;
                    case 3:
                        graph.display();
                        break;
                    case 4:
                        graph = null; // Reset graph representation
                        System.out.println("Graph representation reset. Returning to selection menu...");
                        break;
                    case 5:
                        System.out.println("Exiting program...");
                        scanner.close();
                        return;
                    default:
                        System.out.println("Invalid choice. Please try again.");
                }

                if (choice == 4) break; // Break to reset graph
            }
        }
    }

    // Graph interface defining common methods for all graph types
    interface Graph {
        void addVertex(String label); // Add a vertex
        void addEdge(String src, String dest, boolean directed); // Add an edge
        void dfs(String start); // Perform DFS traversal
        void bfs(String start); // Perform BFS traversal
        void display(); // Display the graph
    }

    // Adjacency Matrix Implementation of Graph
    static class AdjacencyMatrixGraph implements Graph {
        private final Map<String, Integer> vertexMap = new HashMap<>();
        private final List<String> vertices = new ArrayList<>();
        private int[][] matrix;

        @Override
        public void addVertex(String label) {
            if (!vertexMap.containsKey(label)) {
                vertexMap.put(label, vertices.size());
                vertices.add(label);
                resizeMatrix();
                System.out.println("Vertex " + label + " added.");
            } else {
                System.out.println("Vertex " + label + " already exists.");
            }
        }

        @Override
        public void addEdge(String src, String dest, boolean directed) {
            if (!vertexMap.containsKey(src) || !vertexMap.containsKey(dest)) {
                System.out.println("One or both vertices not found.");
                return;
            }
            int srcIndex = vertexMap.get(src);
            int destIndex = vertexMap.get(dest);
            matrix[srcIndex][destIndex] = 1;
            if (!directed) {
                matrix[destIndex][srcIndex] = 1;
            }
            System.out.println("Edge added from " + src + " to " + dest + ".");
        }

        @Override
        public void dfs(String start) {
            if (!vertexMap.containsKey(start)) {
                System.out.println("Vertex not found.");
                return;
            }
            boolean[] visited = new boolean[vertices.size()];
            System.out.print("DFS Traversal: ");
            dfsHelper(vertexMap.get(start), visited);
            System.out.println();
        }

        private void dfsHelper(int index, boolean[] visited) {
            visited[index] = true;
            System.out.print(vertices.get(index) + " ");
            for (int i = 0; i < vertices.size(); i++) {
                if (matrix[index][i] == 1 && !visited[i]) {
                    dfsHelper(i, visited);
                }
            }
        }

        @Override
        public void bfs(String start) {
            if (!vertexMap.containsKey(start)) {
                System.out.println("Vertex not found.");
                return;
            }
            boolean[] visited = new boolean[vertices.size()];
            Queue<Integer> queue = new LinkedList<>();
            int startIndex = vertexMap.get(start);
            visited[startIndex] = true;
            queue.add(startIndex);

            System.out.print("BFS Traversal: ");
            while (!queue.isEmpty()) {
                int index = queue.poll();
                System.out.print(vertices.get(index) + " ");
                for (int i = 0; i < vertices.size(); i++) {
                    if (matrix[index][i] == 1 && !visited[i]) {
                        visited[i] = true;
                        queue.add(i);
                    }
                }
            }
            System.out.println();
        }

        @Override
        public void display() {
            System.out.println("Adjacency Matrix:");
            System.out.print("  ");
            for (String vertex : vertices) {
                System.out.print(vertex + " ");
            }
            System.out.println();
            for (int i = 0; i < vertices.size(); i++) {
                System.out.print(vertices.get(i) + " ");
                for (int j = 0; j < vertices.size(); j++) {
                    System.out.print(matrix[i][j] + " ");
                }
                System.out.println();
            }
        }

        private void resizeMatrix() {
            int size = vertices.size();
            int[][] newMatrix = new int[size][size];
            if (matrix != null) {
                for (int i = 0; i < matrix.length; i++) {
                    System.arraycopy(matrix[i], 0, newMatrix[i], 0, matrix[i].length);
                }
            }
            matrix = newMatrix;
        }
    }

    // Adjacency List Implementation of Graph
    static class AdjacencyListGraph implements Graph {
        private final Map<String, List<String>> adjList = new HashMap<>();

        @Override
        public void addVertex(String label) {
            if (!adjList.containsKey(label)) {
                adjList.put(label, new ArrayList<>());
                System.out.println("Vertex " + label + " added.");
            } else {
                System.out.println("Vertex " + label + " already exists.");
            }
        }

        @Override
        public void addEdge(String src, String dest, boolean directed) {
            if (!adjList.containsKey(src) || !adjList.containsKey(dest)) {
                System.out.println("One or both vertices not found.");
                return;
            }
            adjList.get(src).add(dest);
            if (!directed) {
                adjList.get(dest).add(src);
            }
            System.out.println("Edge added from " + src + " to " + dest + ".");
        }

        @Override
        public void dfs(String start) {
            if (!adjList.containsKey(start)) {
                System.out.println("Vertex not found.");
                return;
            }
            Set<String> visited = new HashSet<>();
            System.out.print("DFS Traversal: ");
            dfsHelper(start, visited);
            System.out.println();
        }

        private void dfsHelper(String vertex, Set<String> visited) {
            visited.add(vertex);
            System.out.print(vertex + " ");
            for (String neighbor : adjList.get(vertex)) {
                if (!visited.contains(neighbor)) {
                    dfsHelper(neighbor, visited);
                }
            }
        }

        @Override
        public void bfs(String start) {
            if (!adjList.containsKey(start)) {
                System.out.println("Vertex not found.");
                return;
            }
            Set<String> visited = new HashSet<>();
            Queue<String> queue = new LinkedList<>();
            visited.add(start);
            queue.add(start);

            System.out.print("BFS Traversal: ");
            while (!queue.isEmpty()) {
                String vertex = queue.poll();
                System.out.print(vertex + " ");
                for (String neighbor : adjList.get(vertex)) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.add(neighbor);
                    }
                }
            }
            System.out.println();
        }

        @Override
        public void display() {
            System.out.println("Adjacency List:");
            for (Map.Entry<String, List<String>> entry : adjList.entrySet()) {
                System.out.print(entry.getKey() + ": ");
                for (String neighbor : entry.getValue()) {
                    System.out.print(neighbor + " ");
                }
                System.out.println();
            }
        }
    }
}