praktikum-holons/src/holeg/algorithm/objective_function/GraphMetrics.java

package holeg.algorithm.objective_function;

import holeg.model.AbstractCanvasObject;
import holeg.model.Holon;
import holeg.model.HolonObject;
import holeg.model.HolonSwitch;
import holeg.model.Model;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.logging.Logger;

public class GraphMetrics {

  private static final Logger log = Logger.getLogger(GraphMetrics.class.getName());

  /**
   * Convert a DecoratedNetwork to a Graph
   *
   * @return a equivalent Graph to the DecoratedNetwork
   */
  public static Graph convertDecoratedNetworkToGraph(Model model, Holon holon) {
    Graph G = new Graph();
    HashMap<AbstractCanvasObject, Integer> objectToId = new HashMap<>();
    List<Integer> sourcesList = new ArrayList<Integer>();
    int count = 0;

    for (HolonObject con : holon.holonObjects) {
      objectToId.put(con, count);
      sourcesList.add(count);
      count++;
    }

    //Generate EdgeList
    List<Edge> edgeList = new ArrayList<Edge>();
    for (holeg.model.Edge cable : model.getEdgesOnCanvas()) {

      AbstractCanvasObject objectA = cable.getA();
      AbstractCanvasObject objectB = cable.getB();
      if (objectA == null) {
        log.warning("Edge: " + cable + "objectA == null");
        continue;
      }
      if (objectB == null) {
        log.warning("Edge: " + cable + "objectB == null");
        continue;
      }

      //SpecialCase for open switches
      if (objectA instanceof HolonSwitch sw && !sw.getState().isOpen()) {
        continue;
      }
      if (objectB instanceof HolonSwitch sw && !sw.getState().isOpen()) {
        continue;
      }

      int idA = -1;
      if (objectToId.containsKey(objectA)) {
        idA = objectToId.get(objectA);
      } else {
        idA = count;
        objectToId.put(objectA, count++);
      }
      int idB = -1;
      if (objectToId.containsKey(objectB)) {
        idB = objectToId.get(objectB);
      } else {
        idB = count;
        objectToId.put(objectB, count++);
      }
      double length = cable.getLength();
      edgeList.add(new Edge(idA, idB, length));
    }
    //Generate EdgeArray
    G.E = new Edge[edgeList.size()];
    for (int i = 0; i < edgeList.size(); i++) {
      G.E[i] = edgeList.get(i);
    }
    //Generate VertexArray
    G.V = new Vertex[objectToId.size()];
    int entryCount = 0;
    for (Map.Entry<AbstractCanvasObject, Integer> entry : objectToId.entrySet()) {
      G.V[entryCount] = new Vertex(entry.getValue());
      entryCount++;
    }
    //Generate Sources Array
    int sourceCount = 0;
    G.S = new Vertex[sourcesList.size()];
    for (int source : sourcesList) {
      G.S[sourceCount] = new Vertex(source);
      sourceCount++;
    }
    return G;
  }

  // Example Test
  public static void main(String[] args) {
    Graph G = new Graph();
    G.V = new Vertex[4];
    for (int i = 0; i < G.V.length; i++) {
      G.V[i] = new Vertex(i);
    }
    G.E = new Edge[4];

    G.E[0] = new Edge(0, 1, 1);
    G.E[1] = new Edge(1, 2, 1);
    G.E[2] = new Edge(2, 3, 1);
    G.E[3] = new Edge(3, 0, 1);

    G.S = new Vertex[4];
    G.S[0] = new Vertex(0);
    G.S[1] = new Vertex(1);
    G.S[2] = new Vertex(2);
    G.S[3] = new Vertex(3);
    log.info(G.toString());
    log.info("minimumCut: " + minimumCut(G.V, G.E));
    log.info("AvgShortestDistance " + averageShortestDistance(G));
    log.info("DisjointPath " + averageEdgeDisjointPathProblem(G));
  }

  static int[][] generateDisjointWeightMatrix(Vertex[] V, Edge[] E) {
    int[][] L = new int[V.length][V.length];
    for (int i = 0; i < E.length; i++) {
      L[E[i].idA][E[i].idB] = 1;
      L[E[i].idB][E[i].idA] = 1;
    }
    return L;
  }

  /**
   * find the average s_t disjoint paths between all pairs of s and t
   **/
  static double averageEdgeDisjointPathProblem(Graph G) {
    //This matrix indicates if a Edge is existent between two vertices
    int[][] L = generateDisjointWeightMatrix(G.V, G.E);
    double disjointPathSum = 0.0;
    for (int s = 0; s < G.S.length; s++) {
      for (int t = s; t < G.S.length; t++) {
        disjointPathSum += s_t_EdgeDisjointPath(G.S[s].id, G.S[t].id, L);
      }
    }
    //Returns the Average
    return disjointPathSum / ((G.S.length * (G.S.length - 1)) / 2);
  }

  /**
   * find the amount of s_t disjoint paths between s and t
   **/
  private static double s_t_EdgeDisjointPath(int s, int t, int[][] L_input) {
    if (s == t) {
      return 0;
    }
    //Make Copy of L
    int[][] L = makeCopyOfMatrix(L_input);
    double foundPaths = 0;
    //RepeatBreathFirst search till no path is found
    boolean b_foundpath = true;
    while (b_foundpath) {
      b_foundpath = breathFirstSearch(s, t, L);
      if (b_foundpath) {
        foundPaths++;
      }
    }
    return foundPaths;
  }

  /**
   * execute one breathFirstSearch to find a path between s and t
   **/
  private static boolean breathFirstSearch(int s, int t, int[][] L) {
    //Visited Notes
    Set<Integer> visitedNotes = new HashSet<Integer>();
    //Queue to check which node to search next
    LinkedList<Integer> queue = new LinkedList<Integer>();
    //Map to traverse the path back when found a path
    HashMap<Integer, Integer> noteBeforeMap = new HashMap<Integer, Integer>();
    //Add starting Point
    queue.add(s);
    //Visit all neighbours of the next point in queue
    while (!queue.isEmpty()) {
      int id = queue.pollFirst();
      visitedNotes.add(id);
      //For all neighbors add to queue
      for (int i = 0; i < L[id].length; i++) {
        //Check if edge exist and not visited before
        if (L[id][i] != 0 && !visitedNotes.contains(i)) {

          queue.add(i);
          noteBeforeMap.putIfAbsent(i, id);
          //check if train is found
          if (i == t) {
            //update connectionMatrix l and remove the found path
            int actualID = t;
            while (actualID != s) {
              int nextID = noteBeforeMap.get(actualID);
              //remove edge
              L[nextID][actualID] = 0;
              L[actualID][nextID] = 0;
              actualID = nextID;
            }
            return true;
          }
        }

      }
    }
    //if last queue element is searched but t is not reachable
    return false;
  }

  /**
   * Makes a deep Copy of a Integer Matrix
   *
   * @return
   */
  private static int[][] makeCopyOfMatrix(int[][] matrix) {
    int[][] copyMatrix = new int[matrix.length][matrix[0].length];
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix[0].length; j++) {
        copyMatrix[i][j] = matrix[i][j];
      }
    }
    return copyMatrix;
  }

  /**
   * Stoer Wagner Minimal Cut Algo Source from
   * <a href="https://github.com/hunglvosu/algorithm/blob/master/algorithm/src/Stoer-Wagner.c">
   * https://github.com/hunglvosu/algorithm/blob/master/algorithm/src/Stoer-Wagner.c</a> <br> in C
   * formatted written in java
   *
   * @param V Vertex Array
   * @param E Edge Array
   * @return
   */

  static int minimumCut(Vertex[] V, Edge[] E) {
    int[][] W = generateDisjointWeightMatrix(V, E);
    boolean[] Del = new boolean[V.length];
    int n = V.length;        // the number of veritces
    int m = E.length;
    return StoerWagner(n, m, W, Del);

  }

  static int StoerWagner(int n, int m, int[][] W, boolean[] Del) {
    int C = Integer.MAX_VALUE;
    for (int V = n; V > 1; V--) {
      int cutValue = minCutPhase(V, W, Del, n, m);
      C = (C < cutValue ? C : cutValue);
    }
    return C;
  }

  static int minCutPhase(int V, int[][] W, boolean[] Del, int n, int m) {
    int i = 0, j = 0;
    int[] s = new int[2];
    if (V == 2) {
      for (i = 0; i < n; i++) {
        if (Del[i] == false) {
          s[j] = i;
          j++;
        }
      }
      return W[s[0]][s[1]];
    }
    int[] L = new int[n];
    boolean[] T = new boolean[n];

    i = 1;  // the number of vertices in the tree T
    j = 0;
    int v, u;
    while (i <= V) {
      v = maxStickiness(T, L, Del, n);
      T[v] = true;
      for (u = 0; u < n; u++) {
        if (W[v][u] != 0 && Del[u] == false && T[u] == false) {
          L[u] = L[u] + W[u][v];
        }
      }
      if (i >= V - 1) {
        s[j] = v;
        j++;
      }
      i++;
    }
    merge(s[0], s[1], n, W, Del);
    return L[s[1]];
  }

  static int maxStickiness(boolean[] T, int[] L, boolean[] Del, int n) {
    int i = 0;
    int v = 0;
    int max = 0;
    for (i = 0; i < n; i++) {
      if (Del[i] == false && T[i] == false && max < L[i]) {
        v = i;
        max = L[i];
      }
    }
    return v;
  }

  static void merge(int s, int t, int n, int[][] W, boolean[] Del) {
    int v = 0;
    for (v = 0; v < n; v++) {
      if (Del[v] == false && v != s && v != t) {
        W[s][v] = W[s][v] + W[v][t];
        W[v][s] = W[s][v];
      }
    }
    Del[t] = true;
  }

  static double[][] basicAllPairsShortestPath(Vertex[] V, Edge[] E) {
    double[][] L = generateWeightMatrix(V, E);
    double[][] D = generateDistanceMatrix(V);
    boolean[] flag = generateFlagList(V);
    for (int i = 0; i < V.length; i++) {
      modifiedDikstra(V[i].id, L, D, flag);
    }
    return D;
  }

  static double averageShortestDistance(Graph G) {
    if (G.V.length <= 1) {
      return 0.0;
    }
    double[][] D = basicAllPairsShortestPath(G.V, G.E);
    double sum = 0.0;
    for (int s = 0; s < G.S.length; s++) {
      for (int t = s; t < G.S.length; t++) {
        sum += D[G.S[s].id][G.S[t].id];
      }
    }
    //Returns the Average
    return sum / ((G.S.length * (G.S.length - 1)) / 2);
  }

  /**
   * @return Updated Distance Matrix D and flag List
   */
  static void modifiedDikstra(int source, double[][] L, double[][] D, boolean[] flag) {
    D[source][source] = 0;
    LinkedList<Integer> visitedNotes = new LinkedList<Integer>();
    LinkedList<Integer> minPriorityQueue = new LinkedList<Integer>();
    minPriorityQueue.add(source);

    while (!minPriorityQueue.isEmpty()) {
      minPriorityQueue.sort((a, b) -> Double.compare(D[source][a], D[source][b]));
      int target = minPriorityQueue.pop();
      if (flag[source] == true) {
        for (int outgoingID = 0; outgoingID < L.length; outgoingID++) {
          if (D[source][target] + L[target][outgoingID] < D[source][outgoingID]) {
            D[source][outgoingID] = D[source][target] + L[target][outgoingID];
          }
        }
      } else {
        for (int outgoingID = 0; outgoingID < L.length; outgoingID++) {
          if (L[target][outgoingID] == Double.POSITIVE_INFINITY) {
            continue;
          }
          if (D[source][target] + L[target][outgoingID] < D[source][outgoingID]) {
            D[source][outgoingID] = D[source][target] + L[target][outgoingID];
            if (!visitedNotes.contains(outgoingID)) {
              minPriorityQueue.add(outgoingID);
            }
          }
        }
      }
      visitedNotes.add(target);
    }
    flag[source] = true;
  }

  static double[][] generateWeightMatrix(Vertex[] V, Edge[] E) {
    double[][] L = new double[V.length][V.length];
    for (int i = 0; i < E.length; i++) {
      try {
        L[E[i].idA][E[i].idB] = E[i].weight;
        L[E[i].idB][E[i].idA] = E[i].weight;
      } catch (java.lang.NullPointerException e) {
        log.info("E[i].idA:" + E[i].idA + " E[i].idB:" + E[i].idB + " E[i].weight:" + E[i].weight);
      }
    }
    for (int i = 0; i < L.length; i++) {
      for (int j = 0; j < L.length; j++) {
        if (L[i][j] == 0.0) {
          L[i][j] = Double.POSITIVE_INFINITY;
        }
      }
    }
    for (int i = 0; i < L.length; i++) {
      L[i][i] = 0.0;
    }
    return L;
  }

  static double[][] generateDistanceMatrix(Vertex[] V) {
    double[][] D = new double[V.length][V.length];
    for (int i = 0; i < D.length; i++) {
      for (int j = 0; j < D.length; j++) {
        D[i][j] = Double.POSITIVE_INFINITY;
      }
    }
    return D;
  }

  private static boolean[] generateFlagList(Vertex[] V) {
    boolean[] flag = new boolean[V.length];
    return flag;
  }

  public static class Vertex {

    public int id = 0;

    public Vertex(int id) {
      this.id = id;
    }

    public String toString() {
      return "" + id;
    }
  }

  private static class Edge {

    public int idA, idB;
    public double weight;

    public Edge(int idA, int idB, double weight) {
      this.idA = idA;
      this.idB = idB;
      this.weight = weight;
    }
  }

  public static class Graph {

    Vertex[] V;
    Edge[] E;
    /**
     * Only the Sources/Trains for disjoint Path no Switch or Node
     **/
    Vertex[] S;

    public String toString() {
      String vList = "V" + Arrays.toString(V);
      String sList = "S" + Arrays.toString(S);
      return vList + ", " + sList;
    }
  }


}