Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Collections;
- import java.util.HashMap;
- import java.util.HashSet;
- import java.util.Hashtable;
- import java.util.LinkedList;
- import java.util.List;
- import java.util.Map;
- import java.util.Objects;
- import java.util.PriorityQueue;
- import java.util.Queue;
- import java.util.Scanner;
- import java.util.Set;
- class Vertex<E extends Comparable<E>> implements Comparable<Vertex<E>>{
- private E data;
- private double minDistance;
- private Vertex predecessor;
- public Vertex(E data){
- this.data = data;
- this.minDistance = Double.MAX_VALUE;
- this.predecessor = null;
- }
- public boolean hasPredecessor(){
- return this.predecessor != null;
- }
- public double getMinDistance() {
- return minDistance;
- }
- public void setMinDistance(double minDistance) {
- this.minDistance = minDistance;
- }
- public Vertex<E> getPredecessor() {
- return predecessor;
- }
- public void setPredecessor(Vertex predecessor) {
- this.predecessor = predecessor;
- }
- public E getData() {
- return data;
- }
- public void setData(E data) {
- this.data = data;
- }
- @Override
- public int compareTo(Vertex<E> v) {
- return Double.compare(minDistance, v.getMinDistance());
- }
- @Override
- public int hashCode() {
- int hash = 3;
- hash = 29 * hash + Objects.hashCode(this.data);
- return hash;
- }
- @Override
- public boolean equals(Object obj) {
- if (this == obj) {
- return true;
- }
- if (obj == null) {
- return false;
- }
- if (getClass() != obj.getClass()) {
- return false;
- }
- final Vertex<E> other = (Vertex<E>) obj;
- if (!this.data.equals(other.data)) {
- return false;
- }
- return true;
- }
- @Override
- public String toString(){
- StringBuilder sb = new StringBuilder();
- sb.append("Vertex with data: ")
- .append(this.data)
- .append(" minDist: ")
- .append(this.minDistance)
- .append(" Pred: ");
- if (this.hasPredecessor())
- sb.append(this.predecessor.getData());
- else{
- sb.append("None");
- }
- return sb.toString();
- }
- }
- class Edge<E extends Comparable<E>>{
- private Vertex<E> source;
- private Vertex<E> destination;
- private double weight;
- public Edge(Vertex<E> source, Vertex<E> destination, double weight) {
- this.source = source;
- this.destination = destination;
- this.weight = weight;
- }
- public Vertex<E> getSource() {
- return source;
- }
- public void setSource(Vertex<E> source) {
- this.source = source;
- }
- public Vertex<E> getDestination() {
- return destination;
- }
- public void setDestination(Vertex<E> destination) {
- this.destination = destination;
- }
- public double getWeight() {
- return weight;
- }
- public void setWeight(double weight) {
- this.weight = weight;
- }
- @Override
- public String toString(){
- StringBuilder sb = new StringBuilder();
- sb.append("Edge from: ")
- .append(this.source.toString())
- .append("\nTo: ")
- .append(this.destination.toString())
- .append("\nWith weight: " + this.weight);
- return sb.toString();
- }
- @Override
- public int hashCode() {
- int hash = 7;
- hash = 11 * hash + Objects.hashCode(this.source);
- hash = 11 * hash + Objects.hashCode(this.destination);
- return hash;
- }
- @Override
- public boolean equals(Object obj) {
- if (this == obj) {
- return true;
- }
- if (obj == null) {
- return false;
- }
- if (getClass() != obj.getClass()) {
- return false;
- }
- final Edge<?> other = (Edge<?>) obj;
- if (!Objects.equals(this.source, other.source)) {
- return false;
- }
- if (!Objects.equals(this.destination, other.destination)) {
- return false;
- }
- return true;
- }
- }
- class Graph<E extends Comparable<E>>{
- List<Vertex<E>> vertices;
- List<Edge<E>> edges;
- Map<E,Integer> indexes; // E( name of the vertex) -> Integer (position in list vertices)
- public Graph(){
- vertices = new ArrayList<>();
- edges = new ArrayList<>();
- indexes = new HashMap<>();
- }
- public void addVertex(E data){
- Vertex<E> vertex = new Vertex<>(data);
- vertices.add(vertex);
- int index = vertices.size() - 1;
- indexes.put(data, index);
- }
- public Vertex<E> getVertex(E data){
- return vertices.get(indexes.get(data));
- }
- private boolean addEdge(Vertex<E> source,Vertex<E> destination,double weight){
- return edges.add(new Edge<E>(source,destination,weight));
- }
- public boolean addDirectedEdge(E source,E destination,double weight){
- Vertex<E> s = vertices.get(indexes.get(source));
- Vertex<E> d = vertices.get(indexes.get(destination));
- return addEdge(s,d,weight);
- }
- public boolean addUndirectedEdge(E source,E destination,double weight){
- Vertex<E> s = vertices.get(indexes.get(source));
- Vertex<E> d = vertices.get(indexes.get(destination));
- return addEdge(s,d,weight) && addEdge(d,s,weight);
- }
- public List<Vertex<E>> getVertices(){
- return this.vertices;
- }
- public List<Edge<E>> getEdges(){
- return this.edges;
- }
- @Override
- public String toString(){
- StringBuilder sb = new StringBuilder();
- for (Vertex<E> v : this.getVertices()){
- sb.append(v.toString() + "\n");
- }
- return sb.toString();
- }
- public double getMinDistanceBetweenDijkstra(E start,E end){
- Vertex<E> source = vertices.get(indexes.get(start));
- Vertex<E> destination = vertices.get(indexes.get(end));
- Dijkstra<E> dijkstra = new Dijkstra<>();
- dijkstra.run(this, source);
- return destination.getMinDistance();
- }
- public List<List<Double>> getMinimumDistanceJohnsonButSlower(){
- double minWeight = Double.MAX_VALUE;
- for (Edge<E> edge : this.getEdges()){
- if (edge.getWeight() < minWeight){
- minWeight = edge.getWeight();
- }
- }
- minWeight = Math.abs(minWeight);
- for (Edge<E> edge : this.getEdges()){
- edge.setWeight(edge.getWeight() + minWeight);
- }
- List<List<Double>> matrix = new ArrayList<>();
- List<Double> resultRow;
- Dijkstra<E> dijkstra = new Dijkstra<>();
- for (Vertex<E> source : this.getVertices()){
- dijkstra.run(this,source);
- resultRow = new ArrayList<>();
- for (Vertex<E> vertex : this.getVertices()){
- int counter = 0;
- Vertex<E> tempVertex = vertex;
- while(tempVertex.hasPredecessor()){
- counter++;
- tempVertex = tempVertex.getPredecessor();
- }
- double result = vertex.getMinDistance() - (counter * minWeight);
- resultRow.add(result);
- }
- matrix.add(resultRow);
- }
- return matrix;
- }
- public double getMinDistanceBetweenBellmanFord(E start,E end){
- Vertex<E> source = vertices.get(indexes.get(start));
- Vertex<E> destination = vertices.get(indexes.get(end));
- BellmanFord<E> bellmanFord = new BellmanFord<>();
- if (bellmanFord.run(this, source))
- return destination.getMinDistance();
- else{
- return -1;
- }
- }
- /*
- MatrixPair class
- */
- ////////////////////////////////////////////////////////////////////////////
- class Matrix{
- double[][] adjMatrix;
- Integer[][] parrentMatrix;
- public Matrix(double[][] adjMatrix, Integer[][] parrentMatrix) {
- this.adjMatrix = adjMatrix;
- this.parrentMatrix = parrentMatrix;
- }
- public double[][] getAdjMatrix() {
- return adjMatrix;
- }
- public Integer[][] getParrentMatrix() {
- return parrentMatrix;
- }
- public List<Integer> getPathBetween(int source,int destination){
- int start = source - 1;
- int finish = destination - 1;
- List<Integer> path = new ArrayList<>();
- while(parrentMatrix[start][finish] != start){
- path.add(parrentMatrix[start][finish] + 1);
- finish = parrentMatrix[start][finish];
- }
- path.add(parrentMatrix[start][finish] + 1);
- Collections.reverse(path);
- return path;
- }
- public double getDistanceBetween(int source,int destination){
- int start = source - 1;
- int finish = destination - 1;
- return this.adjMatrix[start][finish];
- }
- }
- ////////////////////////////////////////////////////////////////////////////
- public Matrix getMinDistanceFloydWarshall(double[][] adjMat){
- int N = adjMat.length;
- Integer[][] parentMatrix = new Integer[N][N];
- for (int i = 0; i < N; i++){
- for (int j = 0; j < N; j++){
- parentMatrix[i][j] = null;
- }
- }
- for (int i = 0; i < N; i++){
- for (int j = 0; j < N; j++){
- if (adjMat[i][j] != Double.MAX_VALUE / 2 && adjMat[i][j] != 0.0){
- parentMatrix[i][j] = i;
- }
- }
- }
- for(int k = 0; k < N; ++k) {
- for(int i = 0; i < N; ++i) {
- for(int j = 0; j < N; ++j) {
- if ( adjMat[i][k] + adjMat[k][j] < adjMat[i][j] ){
- parentMatrix[i][j] = parentMatrix[k][j];
- }
- adjMat[i][j] = Math.min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]);
- }
- }
- }
- return new Matrix(adjMat,parentMatrix);
- }
- public double[][] getAdjMatrix(){
- int N = vertices.size();
- double[][] matrix = new double[N][N];
- for (int i = 0; i < N; i++){
- for (int j = 0; j < N; j++){
- if (i == j)
- continue;
- else{
- matrix[i][j] = Double.MAX_VALUE / 2.0;
- }
- }
- }
- List<Edge<E>> egdes = this.getEdges();
- for (Edge<E> e : edges){
- matrix[indexes.get(e.getSource().getData())][indexes.get(e.getDestination().getData())] = e.getWeight();
- }
- return matrix;
- }
- }
- class Dijkstra<E extends Comparable<E>>{
- public Dijkstra(){
- }
- private Hashtable<Vertex<E>, List<Edge<E> > > makeHashtable(Graph<E> graph){
- Hashtable<Vertex<E>, List<Edge<E> > > table = new Hashtable<>();
- List<Edge<E>> lst;
- for (Vertex<E> v : graph.getVertices()){
- lst = new LinkedList<>();
- table.put(v,lst);
- }
- for (Edge<E> e : graph.getEdges()){
- table.get(e.getSource()).add(e);
- }
- return table;
- }
- public void run(Graph<E> graph, Vertex<E> startVertex){
- if (graph == null || startVertex == null)
- return;
- for (Vertex<E> v : graph.getVertices()){
- v.setMinDistance(Double.MIN_VALUE);
- v.setPredecessor(null);
- }
- double result = Double.MAX_VALUE;
- for (Edge<E> edge : graph.getEdges()){
- if (edge.equals(new Edge<E>(startVertex,startVertex,0))){
- result = edge.getWeight();
- }
- }
- startVertex.setMinDistance(result);
- PriorityQueue<Vertex<E>> queue = new PriorityQueue<>(graph.getVertices());
- Hashtable<Vertex<E>, List<Edge<E>>> table = makeHashtable(graph);
- while (!queue.isEmpty()){
- Vertex<E> u = queue.poll();
- for (Edge<E> e : table.get(u)){
- Vertex<E> v = e.getDestination();
- if (v.getMinDistance() < Math.min(u.getMinDistance(),e.getWeight())){
- v.setMinDistance(Math.min(u.getMinDistance(),e.getWeight()));
- v.setPredecessor(u);
- queue.add(v);
- }
- }
- }
- }
- }
- class BellmanFord<E extends Comparable<E>>{
- private void relax(Edge<E> edge){
- if (edge.getDestination().getMinDistance() < Math.min(edge.getSource().getMinDistance(),edge.getWeight())){
- edge.getDestination().setMinDistance(Math.min(edge.getSource().getMinDistance(),edge.getWeight()));
- edge.getDestination().setPredecessor(edge.getSource());
- }
- }
- public boolean run(Graph<E> graph, Vertex<E> startVertex){
- if (graph == null || startVertex == null)
- return false;
- for (Vertex<E> v : graph.getVertices()){
- v.setMinDistance(Double.MIN_VALUE);
- v.setPredecessor(null);
- }
- startVertex.setMinDistance(Double.MAX_VALUE);
- for (int i = 0; i < graph.getVertices().size(); i++){
- for (Edge<E> edge : graph.getEdges()){
- relax(edge);
- }
- }
- for (Edge<E> edge : graph.getEdges()){
- if (edge.getDestination().getMinDistance() < Math.min(edge.getSource().getMinDistance(),edge.getWeight())){
- return false;
- }
- }
- return true;
- }
- }
- public class Main{
- public static void main(String[] args){
- /*Graph<Integer> g = new Graph<>();
- double[][] d = new double[5][5];
- d[0][0] = 0;
- d[0][1] = 3;
- d[0][2] = 8;
- d[0][3] = Double.MAX_VALUE / 2;
- d[0][4] = -4;
- d[1][0] = Double.MAX_VALUE / 2;;
- d[1][1] = 0;
- d[1][2] = Double.MAX_VALUE / 2;;
- d[1][3] = 1;
- d[1][4] = 7;
- d[2][0] = Double.MAX_VALUE / 2;;
- d[2][1] = 4;
- d[2][2] = 0;
- d[2][3] = Double.MAX_VALUE / 2;;
- d[2][4] = Double.MAX_VALUE / 2;;
- d[3][0] = 2;
- d[3][1] = Double.MAX_VALUE / 2;;
- d[3][2] = -5;
- d[3][3] = 0;
- d[3][4] = Double.MAX_VALUE / 2;;
- d[4][0] = Double.MAX_VALUE / 2;;
- d[4][1] = Double.MAX_VALUE / 2;;
- d[4][2] = Double.MAX_VALUE / 2;;
- d[4][3] = 6;
- d[4][4] = 0;
- System.out.println(g.getMinDistanceFloydWarshall(d).getPathBetween(1, 2));
- System.out.println(g.getMinDistanceFloydWarshall(d).getDistanceBetween(1, 2));
- for (int i = 1; i <= 5; i++){
- g.addVertex(i);
- }
- g.addDirectedEdge(1, 2, 3);
- g.addDirectedEdge(1, 5, -4);
- g.addDirectedEdge(1, 3, 8);
- g.addDirectedEdge(2, 4, 1);
- g.addDirectedEdge(2, 5, 7);
- g.addDirectedEdge(3, 2, 4);
- g.addDirectedEdge(4, 1, 2);
- g.addDirectedEdge(4, 3, -5);
- g.addDirectedEdge(5, 4, 6);
- System.out.println(g.getMinDistanceFloydWarshall(g.getAdjMatrix()).getPathBetween(1, 2));
- System.out.println(g.getMinDistanceFloydWarshall(g.getAdjMatrix()).getDistanceBetween(1, 2));
- */
- Graph<Integer> graph = new Graph<>();
- graph.addVertex(1);
- graph.addVertex(2);
- graph.addVertex(3);
- graph.addDirectedEdge(1, 1, 2);
- graph.addDirectedEdge(1, 2, 1);
- graph.addDirectedEdge(1, 3, -1);
- graph.addDirectedEdge(2, 1, 1);
- graph.addDirectedEdge(2, 2, 2);
- graph.addDirectedEdge(2, 3, 2);
- graph.addDirectedEdge(3, 1, 2);
- graph.addDirectedEdge(3, 2, 1);
- graph.addDirectedEdge(3, 3, 2);
- /*for (List<Double> lst : graph.getMinDistanceBetweenEveryDijkstra()){
- System.out.println(lst);
- }*/
- System.out.println(graph.getMinimumDistanceJohnsonButSlower());
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement