Robust/src/Benchmarks/oooJava/DelaunayRefinement/DirectedEdgeGraph.java

   1 public class DirectedEdgeGraph implements EdgeGraph {
   2
   3   // jjenista - we need this set to find all nodes in a graph
   4   // (as hard a problem as keeping a reference to one node that
   5   // is in the graph from which to do a traversal and find all
   6   // nodes currently in the graph).
   7   //
   8   // Problem: when you add or remove one node, the obvious update
   9   // is to add or remove it to this set as well.  That is a conflict
  10   // for concurrent add and remove ops that don't collide in terms of
  11   // modifying the graph elements though.
  12   //
  13   // SOLUTION: the all-nodes set is invalid after node add/remove ops
  14   // until you run discoverAllNodes(src)
  15   protected HashSet nodes;
  16
  17   // only use when the nodes set is up-to-date
  18   public DirectedEdgeGraph() { nodes = new HashSet();   }
  19   public Iterator iterator() { return nodes.iterator(); }
  20   public int getNumNodes()   { return nodes.size();     }
  21   public Node getRandom()    { return (Node) nodes.iterator().next(); }
  22
  23   // make the node set up to date
  24   public void discoverAllNodes( Node src ) {
  25     nodes.clear();
  26     Stack toVisit = new Stack();
  27     toVisit.push( src );
  28     nodes.add( src );
  29
  30     while( !toVisit.isEmpty() ) {
  31       EdgeGraphNode n =(EdgeGraphNode) toVisit.pop();
  32
  33       if( !n.inGraph ) {
  34         System.out.println( "Error: found a node actual in the graph but not marked!" );
  35         System.exit( -1 );
  36       }
  37
  38       for( Iterator itrInNei = n.getInNeighbors(); itrInNei.hasNext(); ) {
  39         Node nNei = (Node) itrInNei.next();
  40         if (nNei==null) {
  41           System.out.println("NULLIN");
  42           continue;
  43         }
  44
  45         if( !nodes.contains( nNei ) ) {
  46           toVisit.push( nNei );
  47           nodes.add(nNei);
  48         }
  49       }
  50       for( Iterator itrOutNei = n.getOutNeighbors(); itrOutNei.hasNext(); ) {
  51         Node nNei = (Node) itrOutNei.next();
  52         if (nNei==null) {
  53           System.out.println("NULLOUT");
  54           continue;
  55         }
  56         if( !nodes.contains( nNei ) ) {
  57           toVisit.push( nNei );
  58           nodes.add(nNei);
  59         }
  60       }
  61     }
  62   }
  63
  64   // these are the normal methods for truly adding and removing nodes
  65   // from the graph, nodes know locally if they are in and out but they
  66   // haven't been added or removed from the nodes set until ABOVE methods
  67   public boolean addNode(Node n) {
  68     boolean notInAlready = !n.inGraph;
  69     n.inGraph = true;
  70     return notInAlready;
  71   }
  72
  73   public boolean removeNode(Node n) {
  74     boolean wasIn = n.inGraph;
  75     n.inGraph = false;
  76     removeConnectingEdges((EdgeGraphNode) n);
  77     return wasIn;
  78   }
  79
  80   public boolean containsNode(Node n) {
  81     return n.inGraph;
  82   }
  83
  84
  85
  86
  87
  88   public boolean addEdge(Edge_d e) {
  89     GraphEdge ge = (GraphEdge) e;
  90     EdgeGraphNode src = ge.getSrc();
  91     EdgeGraphNode dest = ge.getDest();
  92     return src.addOutEdge(dest, ge) ? dest.addInEdge(src, ge) : false;
  93   }
  94
  95   public Edge_d createEdge(Node src, Node dest, Object e) {
  96     return new GraphEdge((EdgeGraphNode) src, (EdgeGraphNode) dest, e);
  97   }
  98
  99   public Node getDest(Edge_d e) {
 100     return ((GraphEdge) e).getDest();
 101   }
 102
 103   public Edge_d getEdge(Node src, Node dest) {
 104     return ((EdgeGraphNode) src).getOutEdge((EdgeGraphNode) dest);
 105   }
 106
 107   public Iterator getInEdges(Node n) {
 108     return ((EdgeGraphNode) n).getInEdges();
 109   }
 110
 111   public Iterator getOutEdges(Node n) {
 112     return ((EdgeGraphNode) n).getOutEdges();
 113   }
 114
 115   public Node getSource(Edge_d e) {
 116     return ((GraphEdge) e).src;
 117   }
 118
 119   public boolean hasEdge(Edge_d e) {
 120     GraphEdge ge = (GraphEdge) e;
 121     return ge.getSrc().hasOutNeighbor(ge.getDest());
 122   }
 123
 124   public boolean removeEdge(Edge_d e) {
 125     GraphEdge ge = (GraphEdge) e;
 126     EdgeGraphNode src = ge.getSrc();
 127     EdgeGraphNode dest = ge.getDest();
 128     return src.removeOutEdge(dest) ? dest.removeInEdge(src) : false;
 129   }
 130
 131   public boolean addNeighbor(Node src, Node dest) {
 132     throw new UnsupportedOperationException(
 133         "addNeighbor not supported in EdgeGraphs. Use createEdge/addEdge instead");
 134   }
 135
 136   public Node createNode(Object n) {
 137     return new EdgeGraphNode(n);
 138   }
 139
 140   public Iterator getInNeighbors(Node src) {
 141     return ((EdgeGraphNode) src).getInNeighbors();
 142   }
 143
 144   public int getInNeighborsSize(Node node) {
 145     return ((EdgeGraphNode) node).inEdges.size();
 146   }
 147
 148   public Iterator getOutNeighbors(Node src) {
 149     return ((EdgeGraphNode) src).getOutNeighbors();
 150   }
 151
 152   public int getOutNeighborsSize(Node node) {
 153     return ((EdgeGraphNode)node).outEdges.size();
 154   }
 155
 156   public boolean removeNeighbor(Node src, Node dest) {
 157     EdgeGraphNode gsrc = (EdgeGraphNode) src;
 158     EdgeGraphNode gdest = (EdgeGraphNode) dest;
 159     return gsrc.removeOutEdge(gdest) ? gdest.removeInEdge(gsrc) : false;
 160   }
 161
 162   public Object getEdgeData(Edge_d e) {
 163     return ((GraphEdge) e).d;
 164   }
 165
 166   public Object setEdgeData(Edge_d e, Object d) {
 167     GraphEdge ge = (GraphEdge) e;
 168     Object retval = ge.d;
 169     ge.d = d;
 170     return retval;
 171   }
 172
 173   public Object getNodeData(Node n) {
 174     EdgeGraphNode egn = (EdgeGraphNode) n;
 175     return egn.data;
 176   }
 177
 178   public boolean hasNeighbor(Node src, Node dest) {
 179     EdgeGraphNode esrc = (EdgeGraphNode) src;
 180     EdgeGraphNode edest = (EdgeGraphNode) dest;
 181     return esrc.hasOutNeighbor(edest);
 182   }
 183
 184   protected void removeConnectingEdges(EdgeGraphNode n) {
 185     EdgeGraphNode g;
 186     for (Iterator iterator1 = n.getOutNeighborsCopy(); iterator1.hasNext();) {
 187       g = (EdgeGraphNode) iterator1.next();
 188       removeNeighbor(n, g);
 189     }
 190
 191     for (Iterator iterator2 = n.getInNeighborsCopy(); iterator2.hasNext(); ) {
 192       g = (EdgeGraphNode) iterator2.next();
 193       removeNeighbor(g, n);
 194     }
 195
 196   }
 197
 198   public Object setNodeData(Node n, Object d) {
 199     EdgeGraphNode egn = (EdgeGraphNode) n;
 200     Object retval = egn.data;
 201     egn.data = d;
 202     return retval;
 203   }
 204
 205   public boolean isDirected() {
 206     return true;
 207   }
 208 }