123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370 |
- 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;
- }
- }
|