uopspop

Untitled

Sep 21st, 2019
78
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.LinkedList;
  2. import java.util.Queue;
  3.  
  4. public class GraphAdjacentMatrix_TopologicalSort_BFS {
  5.  
  6.     private boolean adjMatrix[][];
  7.     private int numVertices;
  8.     private boolean visited[];
  9.  
  10.     public GraphAdjacentMatrix_TopologicalSort_BFS(int numVertices) {
  11.         this.numVertices = numVertices;
  12.         adjMatrix = new boolean[numVertices][numVertices];
  13.         visited = new boolean[numVertices];
  14.     }
  15.  
  16.     public void setEdge(int i, int j) {
  17.         adjMatrix[i][j] = true;
  18. //        adjMatrix[j][i] = true; // directed
  19.     }
  20.  
  21.     public void delEdge(int i, int j) {
  22.         adjMatrix[i][j] = false;
  23. //        adjMatrix[j][i] = false; // directed
  24.     }
  25.  
  26.     public boolean isEdge(int i, int j) {
  27.         return adjMatrix[i][j];
  28.     }
  29.  
  30.     public int first(int v1){
  31.         boolean[] ary = this.adjMatrix[v1];
  32.         int firstNeighborIndex = this.numVertices; // return n if none
  33.         for (int i = 0; i < ary.length; i++) {
  34.             if (ary[i] != false){
  35.                 firstNeighborIndex = i;
  36.                 break;
  37.             }
  38.         }
  39.         return firstNeighborIndex;
  40.     }
  41.  
  42.     public int next(int v1, int v2){
  43.         boolean[] ary = this.adjMatrix[v1];
  44.         int nextNeighborIndex = this.numVertices; // return n if none
  45.         for (int i = v2 + 1; i < ary.length; i++) {
  46.             if (ary[i] != false){
  47.                 nextNeighborIndex = i;
  48.                 break;
  49.             }
  50.         }
  51.         return nextNeighborIndex; // return n if none
  52.     }
  53.  
  54.     // we are processing an "directed" graph here
  55.     public void topsort_BFS(){
  56.         int[] prerequisiteCount = new int[this.numVertices];
  57.         Queue<Integer> queue = new LinkedList<>();
  58.  
  59.         // add prerequisites - process every edge
  60.         for (int v = 0; v < this.numVertices; v++) {
  61.             for (int nextV = this.first(v); nextV < this.numVertices; nextV = this.next(v, nextV)) {
  62.                 prerequisiteCount[nextV]++;
  63.             }
  64.         }
  65.  
  66.         // add vertices that has no prerequisites now
  67.         for (int v = 0; v < this.numVertices; v++) {
  68.             if (prerequisiteCount[v] == 0) {
  69.                 queue.add(v);
  70.             }
  71.         }
  72.  
  73.         while(queue.peek() != null){
  74.             Integer currV = queue.remove();
  75.             Previsit(adjMatrix, currV);
  76.             for (int nextV = this.first(currV); nextV < this.numVertices; nextV = this.next(currV, nextV)) {
  77.                 prerequisiteCount[nextV]--; // becuase the current vertes v is being proccessed/taken already
  78.                 if (prerequisiteCount[nextV] == 0) {
  79.                     queue.add(nextV); // it means no prerequisite left, so we are good to go with this course
  80.                 }
  81.             }
  82.             Postvisit(adjMatrix, currV);
  83.         }
  84.     }
  85.  
  86.     private void Previsit(boolean[][] graph, int v) {
  87.         System.out.println("Previsit: " + v);
  88.     }
  89.  
  90.     private void Postvisit(boolean[][] graph, int v) {
  91.         System.out.println("Postvisit: " + v);
  92.     }
  93.  
  94.     public String toString() {
  95.         StringBuilder s = new StringBuilder();
  96.         for (int i = 0; i < numVertices; i++) {
  97.             s.append(i + ": ");
  98.             for (boolean j : adjMatrix[i]) {
  99.                 s.append((j?1:0) + " ");
  100.             }
  101.             s.append("\n");
  102.         }
  103.         return s.toString();
  104.     }
  105.  
  106.     public static void main(String[] args) {
  107.         GraphAdjacentMatrix_TopologicalSort_BFS gam = new GraphAdjacentMatrix_TopologicalSort_BFS(8);
  108.  
  109.         // directed graph
  110.         gam.setEdge(1, 2);
  111.         gam.setEdge(1, 3);
  112.         gam.setEdge(2, 6);
  113.         gam.setEdge(2, 5);
  114.         gam.setEdge(2, 4);
  115.         gam.setEdge(3, 4);
  116.         gam.setEdge(4, 5);
  117.         gam.setEdge(5, 7);
  118.  
  119.         gam.topsort_BFS();
  120.  
  121.         System.out.println();
  122.     }
  123.  
  124. }
RAW Paste Data