Guest User

Graph class for Boruvka MST

a guest
Mar 15th, 2018
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.49 KB | None | 0 0
  1. package boruvka_mst;
  2.  
  3. import java.util.Iterator;
  4. import java.util.PriorityQueue;
  5.  
  6. public class Graph {
  7.     private int vCount;
  8.     private PriorityQueue<Edge>[] adj;
  9.  
  10.     public int getvCount() {
  11.         return vCount;
  12.     }
  13.  
  14.     public Graph(int vCount) {
  15.         this.vCount = vCount;
  16.         adj = new PriorityQueue[vCount];
  17.         for (int i = 0; i < vCount; i++)
  18.             adj[i] = new PriorityQueue<Edge>();
  19.     }
  20.  
  21.     public void addEdge(int i, int j, float weight) {
  22.         if (!hasEdge(new Edge(i, j, weight))) {
  23.             adj[i].add(new Edge(i, j, weight));
  24.             adj[j].add(new Edge(j, i, weight));
  25.         }
  26.     }
  27.  
  28.     public void addEdge(Edge e) {
  29.         if (!hasEdge(e)) {
  30.             adj[e.getStartPoint()].add(e);
  31.             adj[e.getEndPoint()].add(e.opposite());
  32.         }
  33.     }
  34.  
  35.     public void removeEdge(int i, int j) {
  36.         Iterator<Edge> it = adj[i].iterator();
  37.         Edge other = new Edge(i, j, 0);
  38.         while (it.hasNext()) {
  39.             if (it.next().equals(other)) {
  40.                 it.remove();
  41.                 break;
  42.             }
  43.         }
  44.  
  45.         Iterator<Edge> it2 = adj[j].iterator();
  46.         Edge other2 = new Edge(j, i, 0);
  47.         while (it2.hasNext()) {
  48.             if (it2.next().equals(other2)) {
  49.                 it2.remove();
  50.                 break;
  51.             }
  52.         }
  53.     }
  54.  
  55.     public boolean hasEdge(Edge e) {
  56.         Iterator<Edge> it = adj[e.getStartPoint()].iterator();
  57.         while (it.hasNext()) {
  58.             if (it.next().equals(e)) {
  59.                 return true;
  60.             }
  61.         }
  62.         return false;
  63.     }
  64.  
  65.     public PriorityQueue<Edge> neighbours(int vertex) {
  66.         return adj[vertex];
  67.     }
  68.  
  69.     public boolean isConnected() {
  70.         // array to store if vertices where visited
  71.         boolean visited[] = new boolean[vCount];
  72.  
  73.         // initialze all to non-visited
  74.         int i;
  75.         for (i = 0; i < vCount; i++) {
  76.             visited[i] = false;
  77.         }
  78.  
  79.         // check for vertex with non-zero degree
  80.         for (i = 0; i < vCount; i++) {
  81.             if (neighbours(i).size() == 0)
  82.                 return false; // if there is one return false
  83.         }
  84.  
  85.         // DFS Traversal starting from non-zero vertex
  86.         DFS(0, visited);
  87.  
  88.         // Check if all vertices have been visited
  89.         for (i = 0; i < vCount; i++)
  90.             if (visited[i] == false)
  91.                 return false;
  92.         // if at least one was not visited false, else we return true
  93.         return true;
  94.     }
  95.  
  96.     public void DFS(int sourceVertex, boolean visited[]) {
  97.         // Mark source node as visited
  98.         visited[sourceVertex] = true;
  99.  
  100.         // recursion for all the vertices adjacent to this one
  101.         Iterator<Edge> it = neighbours(sourceVertex).iterator();
  102.         while (it.hasNext()) {
  103.             Edge nextVertex = it.next();
  104.             if (!visited[nextVertex.getEndPoint()])
  105.                 DFS(nextVertex.getEndPoint(), visited);
  106.         }
  107.     }
  108.  
  109.     public int CountReachableNodes(int sourceVertex) {
  110.         // array to store if vertices where visited
  111.         boolean visited[] = new boolean[vCount];
  112.  
  113.         // initialze all to non-visited
  114.         for (int i = 0; i < vCount; i++) {
  115.             visited[i] = false;
  116.         }
  117.  
  118.         DFS(sourceVertex, visited);
  119.  
  120.         int count = 0;
  121.         for (int i = 0; i < vCount; i++) {
  122.             if(visited[i] == true)
  123.                 count++;
  124.         }
  125.         return count;
  126.     }
  127.    
  128.     public boolean Reachable(int sourceVertex, int destVertex){
  129.         // array to store if vertices where visited
  130.         boolean visited[] = new boolean[vCount];
  131.  
  132.         // initialze all to non-visited
  133.         for (int i = 0; i < vCount; i++) {
  134.             visited[i] = false;
  135.         }
  136.        
  137.         DFS(sourceVertex, visited);
  138.  
  139.         return visited[destVertex];
  140.     }
  141.  
  142.     public void printGraph() {
  143.         for (int i = 0; i < vCount; i++) {
  144.             PriorityQueue<Edge> edges = neighbours(i);
  145.             Iterator<Edge> it = edges.iterator();
  146.             System.out.print(i + ": ");
  147.             for (int j = 0; j < edges.size(); j++) {
  148.                 System.out.print(it.next() + " ");
  149.             }
  150.             System.out.println();
  151.         }
  152.     }
  153. }
Add Comment
Please, Sign In to add comment