KOProject/Graph.java

package com.collibra.server;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Directed weighted graph, to which nodes and edges can be added, and removed asynchronically.
 * Some calculations can be made like getting the shortest path and retrieving all the nodes
 * that are closer to node X than the given weight.
 * For the calculations an implementation of the algorithm of Dijkstra with a priority queue is used.
 *
 * @param <Node> The type of the nodes in the graph.
 * @version 1.0
 * @author Yordan Kirov
 * @since 21/11/2018
 */
class Graph<Node> {
    /** A list of all nodes of the graph */
    private final ArrayList<Node> nodes;

    /** A list of all edges of the graph */
    private final ArrayList<Edge> edges;

    /** Constructor initializing the lists of nodes or edges */
    public Graph() {
        this.nodes = new ArrayList<>();
        this.edges = new ArrayList<>();
    }

    /**
     * Checks if a given node exist in the GRAPH.
     * @param name the name of the node
     * @return Indicates whether a node exists in the GRAPH.
     */
    public boolean containsNode(Node name) {
        return this.nodes.contains(name);
    }

    /**
     * Adds a node to the graph.
     * The method is synchronized.
     * @param name the name of the node
     * @return Indicates whether a node exists in the GRAPH.
     */
    public synchronized void addNode(Node name) {
        nodes.add(name);
    }

    /**
     * Removes a node by the name of it and also removes all edges which are connected to it.
     * The method is synchronized.
     * @param name the name of the node to be removed.
     */
    public synchronized void removeNode(Node name) {
        nodes.remove(name);
        edges.removeIf(edge -> edge.getTo().equals(name) || edge.getFrom().equals(name));
    }

    /**
     * Adds a directed edge to the GRAPH.
     * The method is synchronized.
     * @param from the node which is the tail of the edge.
     * @param to the node which is the head of the edge.
     * @param weight the weight of the edge. Should be a positive integer.
     */
    public synchronized void addEdge(Node from, Node to, int weight) {
        Edge edge = new Edge(from, to, weight);
        this.edges.add(edge);
    }

    /**
     * Removes all directed edges from the GRAPH which are having the same tail node and head node.
     * The method is synchronized.
     * @param from the node which is the tail of the edge.
     * @param to the node which is the head of the edge.
     */
    public synchronized void removeEdge(String from, String to) {
        this.edges.removeIf(edge -> edge.getFrom().equals(from) && edge.getTo().equals(to));
    }

    /**
     * Calculates the sum of the weights of the shortest path between two nodes in the GRAPH.
     * The method is synchronized.
     * @param from source node.
     * @param to target node.
     * @return the sum of the weights of the shortest path between two nodes in the GRAPH.
     * If there is no path between the nodes Integer.MAX_VALUE is returned.
     */
    public synchronized int getShortestPathDistance(Node from, Node to) {
        Map<Node, Integer> distances = getShortestPathDistances(from);

        return distances.get(to);
    }

    /**
     * Finds all the nodes that are closer to a node from the client message than the given weight.
     *
     * For example:
     * Simple graph: Mark -­ 5 -­> Michael -­ 2 -­> Madeleine -­ 8 -­> Mufasa
     * CLOSER THAN 8 Mark
     * Would return: Madeleine,Michael
     * Because Michael is at weight 5 from Mark and Madeleine is at weight 7 (5+2) from Mark.
     *
     * @param distance the max distance (sum of weight) from the source node for which the closer nodes will be listed.
     * @param source the node from which the search will start.
     * @return a comma separated list(no spaces) of found nodes, that are closer to a node from the client message,
     *  sorted alphabetically by name, not including the source node.
     */
    public synchronized String getNodesCloserThan(int distance, Node source) {
        Map<Node, Integer> distances = getShortestPathDistances(source);
        List<String> nodes = new ArrayList<>();
        for (Map.Entry<Node, Integer> nodeToDistance : distances.entrySet()) {
            if (nodeToDistance.getValue() < distance && !nodeToDistance.getKey().equals(source)) {
                nodes.add(nodeToDistance.getKey().toString());
            }
        }

        String nodeNames = nodes.stream().sorted().collect(Collectors.joining(","));

        return nodeNames;
    }

    private int getSmallestWeight(Node from, Node to) {
        int weight = Integer.MAX_VALUE;
        for (Edge e : edges) {
            if (e.getFrom().equals(from) && e.getTo().equals(to)) {
                if (weight > e.getWeight()) {
                    weight = e.getWeight();
                }
            }
        }

        return weight;
    }

    private List<Node> getNeighbours(Node from) {
        List<Node> neighbours = new ArrayList<>();
        for (Edge e : edges) {
            if (e.getFrom().equals(from) && !neighbours.contains(e.getTo())) {
                neighbours.add(e.getTo());
            }
        }

        return neighbours;
    }

    private Map<Node, Integer> getShortestPathDistances(Node source) {
        Map<Node, Integer> distances = new HashMap<>();
        distances.put(source, 0);

        for (Node node : nodes) {
            if (!node.equals(source)) {
                distances.put(node, Integer.MAX_VALUE);
            }
        }
        PriorityQueue<PrioritisedNode> queue = new PriorityQueue<>();
        queue.add(new PrioritisedNode(source, 0));

        while (!queue.isEmpty()) {
            PrioritisedNode currentNode = queue.poll();

            for (Node neighbour : getNeighbours(currentNode.node)) {
                int newDistance =
                        distances.get(currentNode.node) + getSmallestWeight(currentNode.node, neighbour);

                if (newDistance < distances.get(neighbour)) {
                    distances.put(neighbour, newDistance);
                    queue.add(new PrioritisedNode(neighbour, newDistance));
                }
            }
        }

        return distances;
    }

    private class PrioritisedNode implements Comparable<PrioritisedNode> {
        final Node node;
        final int priority;

        PrioritisedNode(Node node, int priority) {
            this.node = node;
            this.priority = priority;
        }

        public int compareTo(PrioritisedNode other) {
            return Integer.compare(this.priority, other.priority);
        }
    }

    private class Edge {
        private final Node from;
        private final Node to;
        private final int weight;

        Edge(Node from, Node to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        Node getFrom() {
            return from;
        }

        Node getTo() {
            return to;
        }

        int getWeight() {
            return weight;
        }

        public String toString() {
            return from + "->" + to + " " + weight;
        }
    }
}