package com.data.struct;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
import java.util.Set;

public class Johnson {
  private Node[][] graphic;
  private Node[][] origonal;
  private Node [][]result;
  private Node s;
  private Set<Node> nextNodes = new HashSet<Node>();
  private Set<Node> addList = new HashSet<Node>();
  private Set<Node> removeList = new HashSet<Node>();

  public Johnson(int v, int e) {
    origonal = new Node[v][v];
    result=new Node[v][v];
    for (int i = 0; i < e; i++) {
      int v1 = new Random().nextInt(v);
      int v2 = new Random().nextInt(v);
      Node node = new Node();
      node.w = new Random().nextInt(v) + 1;
      node.d = Integer.MAX_VALUE - 1000;
      node.start = v1;
      node.end = v2;
      origonal[v1][v2] = node;
    }
    for (int i = 0; i < v; i++) {
      if (origonal[i][i] == null) {
        Node node = new Node();
        node.d = Integer.MAX_VALUE - 1000;
        node.w = 0;
        node.start = i;
        node.end = i;
        origonal[i][i] = node;
      } else {
        origonal[i][i].w = 0;
      }
    }
    graphic = new Node[v + 1][v + 1];
    for (int i = 0; i < origonal.length; i++) {
      for (int j = 0; j < origonal.length; j++) {
        graphic[i][j] = origonal[i][j];
      }
    }
    for (int i = 0; i < v + 1; i++) {
      Node node = new Node();
      node.start = origonal.length;
      node.d = Integer.MAX_VALUE - 1000;
      node.end = i;
      graphic[origonal.length][i] = node;
    }

    s = graphic[0][0];
    s.d = 0;

  }

  public Node[][] johnson() {
    if (!bellmanFord()) {
      System.out.println("matrix contain negtive cycle");
      return null;
    } else {
      printTmp();
      for (int i = 0; i < graphic.length; i++) {
        graphic[i][i].h = graphic[graphic.length - 1][i].d;
      }
      for (int i = 0; i < graphic.length; i++) {
        for (int j = 0; j < graphic.length; j++) {
          if (graphic[i][j] != null) {
            graphic[i][j].w = graphic[i][j].w + graphic[i][i].h
                - graphic[j][j].h;
          }
        }
      }
      for(int i=0;i<origonal.length;i++){
        dijkstra(origonal[i][i]);
        printResult();
        for (int j = 0; j < graphic.length; j++) {
          if (graphic[i][j] != null) {
            graphic[i][j].d = graphic[i][j].d - graphic[i][i].h
                + graphic[j][j].h;
          }
        }
      }
    }
    return result;
  }

  public Node extractMin() {
    Iterator<Node> it = nextNodes.iterator();
    Node node = null;
    while (it.hasNext()) {
      if (node == null) {
        node = it.next();
      } else {
        Node n = it.next();
        if (n.d < node.d) {
          node = n;
        }
      }
    }
    return node;
  }

  public void dijkstra(Node s) {
    for(int i=0;i<origonal.length;i++){
      for(int j=0;j<origonal.length;j++){
        if(origonal[i][j]!=null){
          origonal[i][j].d=Integer.MAX_VALUE - 1000;
        }
      }
    }
    s.d=0;
    nextNodes.clear();
    for (int i = 0; i < origonal.length; i++) {
      nextNodes.add(origonal[i][i]);
    }
    for (int k = 0; k < origonal.length; k++) {
      if (k != s.start && origonal[s.start][k] != null) {
        relex(s, origonal[k][k]);
      }
    }
    nextNodes.remove(s);
    while (nextNodes.size() > 0) {
      Node node = extractMin();
      for (int k = 0; k < origonal.length; k++) {
        if (k != node.start && origonal[node.start][k] != null) {
          relex(node, origonal[k][k]);
        }
      }
      nextNodes.remove(node);
    }
    for(int i=0;i<origonal.length;i++){
      Node node=new Node();
      node.start=s.start;
      node.end=i;
      node.d=origonal[i][i].d;
      result[s.start][i]=node;
    }
  }

  public void relex(Node u, Node v) {
    if (graphic[v.end][v.end].d > u.d + graphic[u.start][v.start].w) {
      graphic[v.end][v.end].d = u.d + graphic[u.start][v.start].w;
      graphic[v.end][v.end].parent = u;
      addList.add(graphic[v.end][v.end]);
      System.out.println(graphic[v.end][v.end].start + "=>" + u.start
          + "||" + graphic[v.end][v.end].d);
    }
  }

  public boolean bellmanFord() {
    s = graphic[graphic.length - 1][graphic.length - 1];
    s.d = 0;
    addList.clear();
    nextNodes.clear();
    removeList.clear();
    nextNodes.add(s);
    for (int k = 0; k < graphic.length; k++) {
      if (k != s.start && graphic[s.start][k] != null) {
        relex(s, graphic[k][k]);
      }
    }
    nextNodes.addAll(addList);
    nextNodes.remove(s);
    while (nextNodes.size() > 0) {
      addList.clear();
      removeList.clear();
      Iterator<Node> it = nextNodes.iterator();
      while (it.hasNext()) {
        Node node = it.next();
        for (int k = 0; k < graphic.length; k++) {
          if (k != node.start && graphic[node.start][k] != null) {
            relex(node, graphic[k][k]);
          }
        }
        removeList.add(node);
      }
      nextNodes.removeAll(removeList);
      nextNodes.addAll(addList);

    }

    for (int j = 0; j < graphic.length; j++) {
      for (int k = 0; k < graphic.length; k++) {
        if (j != k) {
          if (graphic[j][k] != null
              && graphic[k][k].d > graphic[j][j].d
                  + graphic[j][k].w) {
            return false;
          }
        }
      }
    }
    return true;

  }
  public void printResult() {
    System.out.println("result:");
    for (int i = 0; i < result.length; i++) {
      for (int j = 0; j < result.length; j++) {
        if (result[i][j] != null) {
          System.out.print(result[i][j].d + " ");
        } else {
          System.out.print(" " + " ");
        }
      }
      System.out.println();
    }
  }
  public void printTmp() {
    System.out.println("tmp:");
    for (int i = 0; i < graphic.length; i++) {
      for (int j = 0; j < graphic.length; j++) {
        if (graphic[i][j] != null) {
          System.out.print(graphic[i][j].d + " ");
        } else {
          System.out.print(" " + " ");
        }
      }
      System.out.println();
    }
  }

  public void print() {
    System.out.println("origranal:");
    for (int i = 0; i < graphic.length; i++) {
      for (int j = 0; j < graphic.length; j++) {
        if (graphic[i][j] != null) {
          System.out.print(graphic[i][j].w + " ");
        } else {
          System.out.print(" " + " ");
        }
      }
      System.out.println();
    }

    Node[][] l = johnson();
    System.out.println("result:");
    for (int i = 0; i < l.length; i++) {
      for (int j = 0; j < l.length; j++) {
        if (l[i][j] != null) {
          System.out.print(l[i][j].d + " ");
        } else {
          System.out.print(" " + " ");
        }
      }
      System.out.println();
    }

  }

  private class Node {
    private int d;
    private int w;
    private int start;
    private int end;
    private Node parent;
    private int h;
  }

  public static void main(String[] args) {
    Johnson j = new Johnson(5, 20);
    j.print();

  }

}