218 lines
7.3 KiB
Java
218 lines
7.3 KiB
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;
|
||
}
|
||
}
|
||
}
|