Guest User

Graph class for reverse-delete mst

a guest
Mar 15th, 2018
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.77 KB | None | 0 0
  1. package reverse_delete;
  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 beenvisited
  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 void printGraph() {
  110.         for (int i = 0; i < vCount; i++) {
  111.             PriorityQueue<Edge> edges = neighbours(i);
  112.             Iterator<Edge> it = edges.iterator();
  113.             System.out.print(i + ": ");
  114.             for (int j = 0; j < edges.size(); j++) {
  115.                 System.out.print(it.next() + " ");
  116.             }
  117.             System.out.println();
  118.         }
  119.     }
  120. }
Add Comment
Please, Sign In to add comment