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

package holeg.algorithm.objective_function;

import java.util.*;
import java.util.logging.Logger;

import holeg.model.*;

//TODO(Tom2022-01-13) Fix GraphMetrics
public class GraphMetrics {
	private static final Logger log = Logger.getLogger(GraphMetrics.class.getName());
	
	
	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;
		}
	}
	
	
	
	/**
	 * 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;
	}


}