public class Main {
    public static void main(String[] args)
    {
        WeightedGraph<Vertex<Integer>> graph = new WeightedGraph<>();

        Scanner scanner = new Scanner(System.in);
        boolean exit = false;

        while (!exit)
        {
            System.out.println("Enter your choice:");
            System.out.println("1. Add vertex\n2. Add edge\n3. Print graph\n4. Breadth-First Search\n5. Dijkstra's Algorithm");
            System.out.println("6. Exit");

            int choice = scanner.nextInt();
            switch (choice)
            {
                case 1 -> {
                    System.out.println("Enter vertex value:");
                    int vertexValue = scanner.nextInt();
                    Vertex<Integer> vertex = new Vertex<>(vertexValue);
                    graph.addVertex(vertex);
                    System.out.println("Vertex added.");
                }
                case 2 -> {
                    System.out.println("Enter source vertex value:");
                    int sourceValue = scanner.nextInt();
                    System.out.println("Enter destination vertex value:");
                    int desValue = scanner.nextInt();
                    System.out.println("Enter edge weight:");
                    double weight = scanner.nextDouble();
                    Vertex<Integer> source = new Vertex<>(sourceValue);
                    Vertex<Integer> destination = new Vertex<>(desValue);
                    graph.addEdge(source, destination, weight);
                    System.out.println("Edge added.");
                }
                case 3 -> {
                    System.out.println("Graph:");
                    graph.printGraph();
                }
                case 4 -> {
                    System.out.println("Enter starting vertex value for BreadthFirstSearch:");
                    int startBFSValue = scanner.nextInt();
                    Vertex<Integer> startBFS = new Vertex<>(startBFSValue);
                    BreadthFirstSearch<Vertex<Integer>> bfs = new BreadthFirstSearch<>();
                    System.out.println("Breadth-First Search traversal:");
                    System.out.println(bfs.traverse(graph, startBFS));
                }
                case 5 -> {
                    System.out.println("Enter starting vertex value for DijkstraSearch:");
                    int startDijkstraValue = scanner.nextInt();
                    Vertex<Integer> startDijkstra = new Vertex<>(startDijkstraValue);
                    DijkstraSearch<Vertex<Integer>> dijkstra = new DijkstraSearch<>();
                    System.out.println("DijkstraSearch Algorithm traversal:");
                    System.out.println(dijkstra.traverse(graph, startDijkstra));
                }
                case 6 -> exit = true;
                default -> System.out.println("Why can't you not be a 🤡");
            }
            System.out.println();
        }

        System.out.println("BYE BYE!");
    }
}

import java.util.*;

public class WeightedGraph<Vertex> {
    private Map<Vertex, List<Edge<Vertex>>> map = new HashMap<>();
    /*
    Methods
    */
}

    public void addVertex(Vertex vertex) {
        if (!map.containsKey(vertex)) {
            map.put(vertex, new ArrayList<>());
        }
    }

    public Set<Vertex> getVertices() {
        return map.keySet();
    }

    public void addEdge(Vertex source, Vertex destination, double weight) {
        Edge<Vertex> edge = new Edge<>(source, destination, weight);
        map.get(source).add(edge);
        if (!map.containsKey(destination)) {
            map.put(destination, new ArrayList<>());
        }
        map.get(destination).add(edge);
    }

    public List<Edge<Vertex>> getEdges(Vertex vertex) {
        return map.getOrDefault(vertex, new ArrayList<>());
    }

    public void printGraph() {
        for (Map.Entry<Vertex, List<Edge<Vertex>>> entry : map.entrySet()) {
            Vertex vertex = entry.getKey();
            List<Edge<Vertex>> edges = entry.getValue();
            System.out.print("Vertex: " + vertex + " Edges: ");
            for (Edge<Vertex> edge : edges) {
                System.out.print(edge + " ");
            }
            System.out.println();
        }
    }

    public void removeVertex(Vertex vertex) {
        if (map.containsKey(vertex)) {
            map.remove(vertex);
        }
        for (List<Edge<Vertex>> edges : map.values()) {
            edges.removeIf(edge -> edge.getDes().equals(vertex));
        }
    }

    public void removeEdge(Vertex source, Vertex destination) {
        List<Edge<Vertex>> edges = map.get(source);
        edges.removeIf(edge -> edge.getDes().equals(destination));
    }

public class BreadthFirstSearch<V> implements Search<V> {
    private List<V> visit;
    /*
    Methods
    */
}    

    @Override
    public List<V> traverse(WeightedGraph<V> graph, V start) {
        visit = new ArrayList<>();
        Queue<V> queue = new LinkedList<>();
        queue.offer(start);
        visit.add(start);

        bfs(graph, queue);

        return visit;
    }    

    private void bfs(WeightedGraph<V> graph, Queue<V> queue) {
        if (queue.isEmpty()) {
            return;
        }
        V current = queue.poll();
        List<Edge<V>> edges = graph.getEdges(current);
        for (Edge<V> edge : edges) {
            V des = edge.getDes();
            if (!visit.contains(des) && !queue.contains(des)) {
                queue.offer(des);
                visit.add(des);
            }
        }
        bfs(graph, queue);
    }

import java.util.List;
  
public interface Search<V> {
    List<V> traverse(WeightedGraph<V> graph, V start);
}

public class DijkstraSearch<V> implements Search<V> {
    private WeightedGraph<V> graph;
    private Map<V, Double> distance;
    private Map<V, V> parentMap;
    private Set<V> visited;
    /*
    Methods
    */
}  

    @Override
    public List<V> traverse(WeightedGraph<V> graph, V start) {
        this.graph = graph;
        distance = new HashMap<>();
        parentMap = new HashMap<>();
        visited = new HashSet<>();

        for (V vertex : graph.getVertices()) {
            if (vertex.equals(start)) {
                distance.put(vertex, 0.0);
            } else {
                distance.put(vertex, Double.POSITIVE_INFINITY);
            }
        }

        dijkstra(start);

        return getPath(start);
    }

    private void dijkstra(V current) {
        visited.add(current);

        List<Edge<V>> edges = graph.getEdges(current);
        for (Edge<V> edge : edges)
        {
            V destination = edge.getDes();
            double newDistance = distance.get(current) + edge.getWeight();
            if (newDistance < distance.get(destination)) {
                distance.put(destination, newDistance);
                parentMap.put(destination, current);
            }
        }

        V next = getMinVertexDistance();
        if (next != null) {
            dijkstra(next);
        }
    }

    private List<V> getPath(V start) {
        List<V> path = new ArrayList<>();
        V current = start;

        while (parentMap.containsKey(current)) {
            path.add(current);
            current = parentMap.get(current);
        }

        Collections.reverse(path);
        return path;
    }                                                    

    private V getMinVertexDistance() {
        double minDistance = Double.POSITIVE_INFINITY;
        V minVertex = null;
        for (Map.Entry<V, Double> entry : distance.entrySet()) {
            V vertex = entry.getKey();
            double dist = entry.getValue();
            if (!visited.contains(vertex) && dist < minDistance) {
                minDistance = dist;
                minVertex = vertex;
            }
        }
        return minVertex;
    }                                                    

public class Edge<V> {
    private V source;
    private V destination;
    private Double weight;

    public Edge(V source, V destination, Double weight) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }

    public V getSource() {
        return source;
    }

    public V getDes() {
        return destination;
    }

    public Double getWeight() {
        return weight;
    }

    @Override
    public String toString() {
        return "(" + source + " -> " + destination + ", weight: " + weight + ")";
    }
}