GraphImpl.java

package a6;

import java.util.*;

public class GraphImpl implements Graph {
    Map<String, Node> nodes; //Do not delete.  Use this field to store your nodes.
    // key: name of node. value: a5.Node object associated with name
    private int n;
    private int e;

    public GraphImpl() {
        nodes = new HashMap<>();
    }

    @Override
    public boolean addNode(String name) {
        if (name == null || name.equals("") || nodes.containsKey(name)) {
            return false;
        } else {
            nodes.put(name, new NodeImpl(name));
            this.n ++;
//            System.out.println("-----------------------------");
//            System.out.println("Added node: '" + name + "', " + this.n);
//            System.out.println(this.nodes.toString());
//            System.out.println("-----------------------------");
            return true;
        }
    }

    @Override
    public boolean addEdge(String src, String dest, double weight) {
//        System.out.println("About to add edge! " + src + "," + dest + "," + weight);
        boolean exists = false;

        if (nodes.containsKey(src)) {
            for (Edge e: nodes.get(src).getEdges()) {
                if (e.getDest().equals(dest)) {
                    exists = true;
                }
            }

            if (weight < 0 || !nodes.containsKey(dest) || exists) {
                return false;
            } else {
                nodes.get(src).addEdge(new EdgeImpl(src, dest, weight));
                this.e ++;
                this.nodes.get(dest).setIn(1);
//                System.out.println("-----------------------------");
//                System.out.println("Added edge: '" + src + "," + dest + "', " + weight);
//                System.out.println(this.nodes.get(src).getEdges().toString());
//                System.out.println("-----------------------------");
                return true;
            }
        }
        return false;
    }
    //     * @return false if edge weight is less than 0
//            *         false if source node is not in graph
//     *         false if destination node is not in graph
//     *         false is there already is an edge between these 2 nodes
    @Override
    public boolean deleteNode(String name) {
        if (nodes.containsKey(name)) {
            for (String node : nodes.keySet()) {
                this.deleteEdge(node, name);
            }
            for (Edge e: nodes.get(name).getEdges()) {
                nodes.get(e.getDest()).setIn(-1);
            }
            nodes.remove(name);
            this.n --;
//            System.out.println("-----------------------------");
//            System.out.println("Removed node: '" + name + "', " + this.n);
//            System.out.println(this.nodes.toString());
//            System.out.println("-----------------------------");
            return true;
        }
        return false;
    }

    @Override
    public boolean deleteEdge(String src, String dest) {
        if (nodes.containsKey(src)) {
//            System.out.println("deleted " + dest + nodes.get(dest).getIn());
//            System.out.println("-----------------------------");
//            System.out.println("Removed edge: '" + src + "," + dest + "', " + this.e);
//            System.out.println(this.nodes.get(src).getEdges().toString());
//            System.out.println("-----------------------------");
            if (nodes.get(src).deleteEdge(dest)) {
                this.e --;
                nodes.get(dest).setIn(-1);
                return true;
            } else {
                return false;
            }
        }
        return false;
    }

    @Override
    public int numNodes() {
        return this.n;
    }

    @Override
    public int numEdges() {
        return this.e;
    }

    @Override
    public void printGraph() {
        for (String node : nodes.keySet()) {
            System.out.print(node + ": ");
            for (Edge neighbor : nodes.get(node).getEdges()) {
                System.out.print(neighbor.getDest() + "-" + neighbor.getWeight()+",");
            }
            System.out.println();
        }
    }

    @Override
    public Stack<String> topoSort() {
        // If a graph has a cycle, then it has no topo sort
        Stack<String> sorted = new Stack<String>();
        String next = r_topoSort();
        while (nodes.size() > 0 && next != null) {
            next = r_topoSort();
            sorted.push(next);
            this.deleteNode(next);
//            System.out.println(next);
//            System.out.println(sorted.toString());
        }

        if (next == null) {
            return new Stack<String>();
        }
        return sorted;
    }
    //
    private String r_topoSort() {
        for (String node : nodes.keySet()) {
            if (nodes.get(node).getIn() == 0) {
                return node;
            }
        }

        return null;
    }
    @Override
    public Map<String, Double> dijkstra(String start) {
        // create hashmap to return
        Map<String, Double> res = new HashMap<String, Double>();
        // create priority queue and comparator to prioritize by distance
        Comparator<Node> compare = Comparator.comparingDouble(Node::getDist);
        PriorityQueue<Node> pq = new PriorityQueue<Node>(compare);

        // initialize starting node to distance = 0 and put in priority queue
        this.nodes.get(start).setDist(0);
        pq.add(this.nodes.get(start));

        // loop while priority queue has stuff
        while (pq.size() > 0) {
            // deal with first node from priority queue
            // delete node and place in result hashmap
            Node node = pq.peek();
            pq.remove();
            String n = node.getName();
            res.put(n, node.getDist());

            // dealt with = in the hashmap

            // check if node has been dealt with
            if (!this.nodes.get(n).getKnown()) {
                // switch from false --> true
                this.nodes.get(n).setKnown();
                // get adjacent (out) edges of current node
                LinkedList<Edge> edges = this.nodes.get(n).getEdges();
                // loop through adjacent out edges
                for (Edge edge : edges) {
                    // get the adjacent node
                    Node dest = this.nodes.get(edge.getDest());
                    if (!dest.getKnown()) {
                        // if the adjacent node hasn't been dealt with
                        // calculate new pathLen with the edge's weight and the source node's distance
                        double pathLen = this.nodes.get(n).getDist() + edge.getWeight();
                        if (pathLen < dest.getDist()) {
                            // if the new pathLen is less than the current recorded distance
                            // update distance and previous node
                            dest.setDist(pathLen);
                            dest.setPrev(n);
                        }
                        // add node to the priority queue
                        pq.add(dest);
                    }
                }
            }
        }

        return res;
    }
}