praktikum-holons/src/algorithm/objectiveFunction/GraphMetrics.java

package algorithm.objectiveFunction;

import java.util.HashMap;
import java.util.LinkedList;

import classes.AbstractCanvasObject;
import ui.model.Consumer;
import ui.model.DecoratedCable;
import ui.model.DecoratedNetwork;
import ui.model.Passiv;
import ui.model.Supplier;

public class GraphMetrics {
	
	
	public static class Vertex{
		public int id = 0;
		public Vertex(int id){
			this.id = 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;
	}
	
	
	
	/**
	 * Convert a DecoratedNetwork to a Graph
	 * @param net
	 * @return a equivalent Graph to the DecoratedNetwork
	 */
	public static Graph convertDecoratedNetworkToGraph(DecoratedNetwork net) {
		Graph G = new Graph();
		HashMap<AbstractCanvasObject, Integer> objectToId = new HashMap<>();
		int count = 0;
		for(Consumer con: net.getConsumerList()) {
			objectToId.putIfAbsent(con.getModel(), count++);
		}
		for(Consumer con: net.getConsumerSelfSuppliedList()) {
			objectToId.putIfAbsent(con.getModel(), count++);
		}
		for(Passiv pas: net.getPassivNoEnergyList()) {
			objectToId.putIfAbsent(pas.getModel(), count++);
		}
		for(Supplier sup: net.getSupplierList()) {
			objectToId.putIfAbsent(sup.getModel(), count++);
		}
		
		
		
		G.E = new Edge[net.getDecoratedCableList().size()];
		int edgeCount = 0;
		for(DecoratedCable cable : net.getDecoratedCableList()){
			
			AbstractCanvasObject objectA = cable.getModel().getA();
			AbstractCanvasObject objectB = cable.getModel().getB();
			if(objectA == null) {
				System.out.println("Edge: " + cable + "objectA == null");
				continue;
			}
			if(objectB == null) {
				System.out.println("Edge: " + cable + "objectB == null");
				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.getModel().getLength();
			G.E[edgeCount++] = new Edge(idA, idB, length);
		}
		G.V = new Vertex[objectToId.size()];
		for(int i=0;i<G.V.length;i++)
	    {
				G.V[i] =  new Vertex(i);
	    }
		return G;
	}
	
	public static void main(String[] args) {
		System.out.println("Test");
		int amountSwitches = 30;
		double times = Math.pow(2, amountSwitches);
		for(int i = 0; i < times; i++) {
			System.out.print("i(" + i +"):");
			for(int k = 0; k < amountSwitches; k++) {
				boolean result = ((i >> k) & 1) != 0;
				System.out.print(result +  ", ");
			}
			System.out.println();
		}
	}
	
	
// Example Test
//	 public static void main(String[] args){
//		 Graph G = new Graph();
//		 G.V = new Vertex[9];
//		 for(int i=0;i<G.V.length;i++)
//	     {
//				G.V[i] =  new Vertex(i);
//	     }
//		 G.E = new Edge[18];
//		 
//		 G.E[0] = new Edge(0, 1, 4);
//		 G.E[1] = new Edge(1, 2, 4);
//		 G.E[2] = new Edge(2, 3, 4);
//		 G.E[3] = new Edge(0, 4, 4);
//		 G.E[4] = new Edge(0, 5, 4);
//		 G.E[5] = new Edge(1, 4, 4);
//		 G.E[6] = new Edge(1, 5, 4);
//		 G.E[7] = new Edge(2, 6, 4);
//		 G.E[8] = new Edge(2, 7, 4);
//		 G.E[9] = new Edge(3, 6, 4);
//		 G.E[10] = new Edge(3, 7, 4);
//		 G.E[11] = new Edge(4, 5, 4);
//		 G.E[12] = new Edge(5, 6, 4);
//		 G.E[13] = new Edge(6, 7, 4);
//		 G.E[14] = new Edge(3, 8, 4);
//		 G.E[15] = new Edge(6, 8, 4);
//		 G.E[16] = new Edge(7, 8, 4);
//		 G.E[17] = new Edge(2, 5, 4);
//		 
//
//		 System.out.println("k: " + minimumCut(G.V, G.E));
//		 System.out.println("AvgShortestDistance " + averageShortestDistance(G.V, G.E));
//		 
//	 }
	 
	 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;
		}
	 
	 
	 /**
	  * 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 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(Vertex[] V, Edge[] E) {
		 if(V.length <= 1) return 0.0;
		 double[][] D = basicAllPairsShortestPath(V, E);
		 double sum = 0;
		 int maxColumn = 1;
		 for(int row = 1; row < D.length; row++) {
			 for(int column = 0; column < maxColumn; column++) {
				 sum += D[row][column];
			 }
			 maxColumn++;
		 }
		 int numbers = ((D.length - 1) * (D.length)) / 2;
		 return sum / (double)numbers;
	 } 
	/** 
	 * @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 void printMatrix(int[][] matrix) {
		for(int i=0;i<matrix.length;i++)
        {
            for(int j=0;j<matrix.length;j++)
            {
                System.out.print(matrix[i][j] +  " ");
            }
            System.out.println();
        }
	}
	static void printMatrix(double[][] matrix) {
		for(int i=0;i<matrix.length;i++)
        {
            for(int j=0;j<matrix.length;j++)
            {
                System.out.print(matrix[i][j] +  " ");
            }
            System.out.println();
        }
	}
	static double[][] generateWeightMatrix(Vertex[] V, Edge[] E){
		double[][] L = new double[V.length][V.length];
		for(int i = 0; i < E.length; i++) {
			L[E[i].idA][E[i].idB] = E[i].weight;
			L[E[i].idB][E[i].idA] = 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;
	}


}