001/* 002 * Copyright (c) 2016 Chris K Wensel <chris@wensel.net>. All Rights Reserved. 003 * Copyright (c) 2007-2017 Xplenty, Inc. All Rights Reserved. 004 * 005 * Project and contact information: http://www.cascading.org/ 006 * 007 * This file is part of the Cascading project. 008 * 009 * Licensed under the Apache License, Version 2.0 (the "License"); 010 * you may not use this file except in compliance with the License. 011 * You may obtain a copy of the License at 012 * 013 * http://www.apache.org/licenses/LICENSE-2.0 014 * 015 * Unless required by applicable law or agreed to in writing, software 016 * distributed under the License is distributed on an "AS IS" BASIS, 017 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 018 * See the License for the specific language governing permissions and 019 * limitations under the License. 020 */ 021 022package cascading.flow.planner.graph; 023 024import java.io.Serializable; 025import java.util.Collection; 026import java.util.Collections; 027import java.util.IdentityHashMap; 028import java.util.List; 029import java.util.Set; 030 031import cascading.flow.FlowElement; 032import cascading.flow.planner.Scope; 033import cascading.util.Util; 034import org.jgrapht.DirectedGraph; 035import org.jgrapht.Graphs; 036import org.jgrapht.graph.SimpleDirectedGraph; 037 038/** 039 * 040 */ 041public abstract class BaseElementGraph implements ElementGraph, Serializable 042 { 043 public static final ElementGraph NULL = new BaseElementGraph( new SimpleDirectedGraph<FlowElement, Scope>( Scope.class ) ) 044 { 045 @Override 046 public ElementGraph copyElementGraph() 047 { 048 return null; 049 } 050 }; 051 052 protected DirectedGraph<FlowElement, Scope> graph; 053 054 public BaseElementGraph() 055 { 056 } 057 058 public BaseElementGraph( DirectedGraph<FlowElement, Scope> graph ) 059 { 060 this.graph = graph; 061 } 062 063 protected void copyFrom( ElementGraph elementGraph ) 064 { 065 Graphs.addAllVertices( graph, elementGraph.vertexSet() ); 066 Graphs.addAllEdges( graph, ElementGraphs.directed( elementGraph ), elementGraph.edgeSet() ); 067 } 068 069 public boolean containsEdge( FlowElement sourceVertex, FlowElement targetVertex ) 070 { 071 return graph.containsEdge( sourceVertex, targetVertex ); 072 } 073 074 public boolean removeAllEdges( Collection<? extends Scope> edges ) 075 { 076 return graph.removeAllEdges( edges ); 077 } 078 079 public Set<Scope> removeAllEdges( FlowElement sourceVertex, FlowElement targetVertex ) 080 { 081 return graph.removeAllEdges( sourceVertex, targetVertex ); 082 } 083 084 public boolean removeAllVertices( Collection<? extends FlowElement> vertices ) 085 { 086 return graph.removeAllVertices( vertices ); 087 } 088 089 public Set<Scope> getAllEdges( FlowElement sourceVertex, FlowElement targetVertex ) 090 { 091 return graph.getAllEdges( sourceVertex, targetVertex ); 092 } 093 094 public Scope getEdge( FlowElement sourceVertex, FlowElement targetVertex ) 095 { 096 return graph.getEdge( sourceVertex, targetVertex ); 097 } 098 099 public Scope addEdge( FlowElement sourceVertex, FlowElement targetVertex ) 100 { 101// prevent multiple edges from head or to tail 102 if( !allowMultipleExtentEdges() && ( sourceVertex == Extent.head || targetVertex == Extent.tail ) && graph.containsEdge( sourceVertex, targetVertex ) ) 103 return graph.getEdge( sourceVertex, targetVertex ); 104 105 return graph.addEdge( sourceVertex, targetVertex ); 106 } 107 108 public boolean addEdge( FlowElement sourceVertex, FlowElement targetVertex, Scope scope ) 109 { 110 // prevent multiple edges from head or to tail 111 if( !allowMultipleExtentEdges() && ( sourceVertex == Extent.head || targetVertex == Extent.tail ) && graph.containsEdge( sourceVertex, targetVertex ) ) 112 return true; 113 114 return graph.addEdge( sourceVertex, targetVertex, scope ); 115 } 116 117 protected boolean allowMultipleExtentEdges() 118 { 119 return true; 120 } 121 122 @Override 123 public boolean addHeadVertex( FlowElement flowElement ) 124 { 125 if( !graph.containsVertex( Extent.head ) ) 126 graph.addVertex( Extent.head ); 127 128 if( flowElement == Extent.head ) 129 return false; 130 131 boolean result = true; 132 133 if( !graph.containsVertex( flowElement ) ) 134 result = graph.addVertex( flowElement ); 135 136 return result && graph.addEdge( Extent.head, flowElement ) != null; 137 } 138 139 @Override 140 public boolean addTailVertex( FlowElement flowElement ) 141 { 142 if( !graph.containsVertex( Extent.tail ) ) 143 graph.addVertex( Extent.tail ); 144 145 if( flowElement == Extent.tail ) 146 return false; 147 148 boolean result = true; 149 150 if( !graph.containsVertex( flowElement ) ) 151 result = graph.addVertex( flowElement ); 152 153 return result && graph.addEdge( flowElement, Extent.tail ) != null; 154 } 155 156 public boolean addVertex( FlowElement flowElement ) 157 { 158 return graph.addVertex( flowElement ); 159 } 160 161 public FlowElement getEdgeSource( Scope scope ) 162 { 163 return graph.getEdgeSource( scope ); 164 } 165 166 public FlowElement getEdgeTarget( Scope scope ) 167 { 168 return graph.getEdgeTarget( scope ); 169 } 170 171 public boolean containsEdge( Scope scope ) 172 { 173 return graph.containsEdge( scope ); 174 } 175 176 public boolean containsVertex( FlowElement flowElement ) 177 { 178 return graph.containsVertex( flowElement ); 179 } 180 181 public Set<Scope> edgeSet() 182 { 183 return graph.edgeSet(); 184 } 185 186 public Set<Scope> edgesOf( FlowElement vertex ) 187 { 188 return graph.edgesOf( vertex ); 189 } 190 191 public int inDegreeOf( FlowElement vertex ) 192 { 193 return graph.inDegreeOf( vertex ); 194 } 195 196 public Set<Scope> incomingEdgesOf( FlowElement vertex ) 197 { 198 return graph.incomingEdgesOf( vertex ); 199 } 200 201 public int outDegreeOf( FlowElement vertex ) 202 { 203 return graph.outDegreeOf( vertex ); 204 } 205 206 public Set<Scope> outgoingEdgesOf( FlowElement vertex ) 207 { 208 return graph.outgoingEdgesOf( vertex ); 209 } 210 211 public Scope removeEdge( FlowElement sourceVertex, FlowElement targetVertex ) 212 { 213 return graph.removeEdge( sourceVertex, targetVertex ); 214 } 215 216 public boolean removeEdge( Scope scope ) 217 { 218 return graph.removeEdge( scope ); 219 } 220 221 public boolean removeVertex( FlowElement flowElement ) 222 { 223 return graph.removeVertex( flowElement ); 224 } 225 226 public Set<FlowElement> vertexSet() 227 { 228 return graph.vertexSet(); 229 } 230 231 @Override 232 public Set<FlowElement> vertexSetCopy() 233 { 234 Set<FlowElement> result = Collections.newSetFromMap( new IdentityHashMap<FlowElement, Boolean>() ); 235 236 result.addAll( vertexSet() ); 237 238 return result; 239 } 240 241 @Override 242 public List<FlowElement> predecessorListOf( FlowElement flowElement ) 243 { 244 return Graphs.predecessorListOf( graph, flowElement ); 245 } 246 247 @Override 248 public List<FlowElement> successorListOf( FlowElement flowElement ) 249 { 250 return Graphs.successorListOf( graph, flowElement ); 251 } 252 253 @Override 254 public ElementGraph bindExtents() 255 { 256 Set<FlowElement> vertexSet = vertexSetCopy(); 257 258 for( FlowElement flowElement : vertexSet ) 259 { 260 if( inDegreeOf( flowElement ) == 0 ) 261 addHeadVertex( flowElement ); 262 263 if( outDegreeOf( flowElement ) == 0 ) 264 addTailVertex( flowElement ); 265 } 266 267 // be sure to test underlying container 268 if( !vertexSet().contains( Extent.head ) ) 269 throw new IllegalStateException( "did not bind head vertex to graph" ); 270 271 if( !vertexSet().contains( Extent.tail ) ) 272 throw new IllegalStateException( "did not bind tail vertex to graph" ); 273 274 return this; 275 } 276 277 @Override 278 public void writeDOT( String filename ) 279 { 280 boolean success = ElementGraphs.printElementGraph( filename, this, null ); 281 282 if( success ) 283 Util.writePDF( filename ); 284 } 285 286 @Override 287 public boolean equals( Object object ) 288 { 289 return ElementGraphs.equals( this, (ElementGraph) object ); 290 } 291 292 @Override 293 public int hashCode() 294 { 295 int result = graph.hashCode(); 296 result = 31 * result; // parity with AnnotatedGraph types 297 return result; 298 } 299 }