001 /*
002 Galois, a framework to exploit amorphous data-parallelism in irregular
003 programs.
004
005 Copyright (C) 2010, The University of Texas at Austin. All rights reserved.
006 UNIVERSITY EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES CONCERNING THIS SOFTWARE
007 AND DOCUMENTATION, INCLUDING ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR ANY
008 PARTICULAR PURPOSE, NON-INFRINGEMENT AND WARRANTIES OF PERFORMANCE, AND ANY
009 WARRANTY THAT MIGHT OTHERWISE ARISE FROM COURSE OF DEALING OR USAGE OF TRADE.
010 NO WARRANTY IS EITHER EXPRESS OR IMPLIED WITH RESPECT TO THE USE OF THE
011 SOFTWARE OR DOCUMENTATION. Under no circumstances shall University be liable
012 for incidental, special, indirect, direct or consequential damages or loss of
013 profits, interruption of business, or related expenses which may arise from use
014 of Software or Documentation, including but not limited to those resulting from
015 defects in Software and/or Documentation, or loss or inaccuracy of data of any
016 kind.
017
018 File: Graph.java
019
020 */
021
022 package galois.objects.graph;
023
024 import galois.objects.GObject;
025 import galois.objects.Mappable;
026 import util.fn.LambdaVoid;
027
028 /**
029 * Root interface in the graph hierarchy. A graph is a set of nodes connected by edges. Two nodes can be connected by at
030 * most one edge (i.e., this graph is <b>not</b> a multigraph), but self edges are allowed. <br/>
031 * This interface supports the storage of data in the nodes of the graph, but not in the edges. Use
032 * {@link galois.objects.graph.ObjectGraph} if you need to store values on the edges too.
033 *
034 * @param <N> the type of the data contained in a node
035 */
036 public interface Graph<N extends GObject> extends Mappable<GNode<N>>, GObject {
037 /**
038 * Creates a new node holding the indicated data.
039 * The new node is <b>not</b> automatically added to the graph (use {@link #add(GNode, byte)}),
040 *
041 * @param n data contained in the new node.
042 * @return the newly created node.
043 */
044 public GNode<N> createNode(N n);
045
046 /**
047 * Creates a new node holding the indicated data.
048 * The new node is <b>not</b> automatically added to the graph (use {@link #add(GNode, byte)}),
049 *
050 * @param n data contained in the new node.
051 * @param flags Galois runtime actions (e.g., conflict detection) that need to be executed
052 * upon invocation of this method. See {@link galois.objects.MethodFlag}
053 * @return the newly created node.
054 */
055 public GNode<N> createNode(N n, byte flags);
056
057 /**
058 * Adds a node to the graph.
059 * All the Galois runtime actions (e.g., conflict detection) will be performed when
060 * the method is executed.
061 *
062 * @param n node created by the current graph
063 * @return true if the node was not already in the graph
064 * @throws IllegalArgumentException if the node has been created by another graph
065 */
066 public boolean add(GNode<N> n);
067
068 /**
069 * Adds a node to the graph.
070 *
071 * @param n node created by the current graph
072 * @param flags Galois runtime actions (e.g., conflict detection) that need to be executed
073 * upon invocation of this method. See {@link galois.objects.MethodFlag}
074 * @return true if the node was not already in the graph
075 * @throws IllegalArgumentException if the node has been created by another graph
076 */
077 public boolean add(GNode<N> n, byte flags);
078
079 /**
080 * Removes a node from the graph along with all its outgoing/incoming edges.
081 * All the Galois runtime actions (e.g., conflict detection) will be performed when
082 * the method is executed.
083 *
084 * @param n node to be removed
085 * @return true if the node was removed from the graph
086 */
087 public boolean remove(GNode<N> n);
088
089 /**
090 * Removes a node from the graph along with all its outgoing/incoming edges.
091 *
092 * @param n node to be removed
093 * @param flags Galois runtime actions (e.g., conflict detection) that need to be executed
094 * upon invocation of this method. See {@link galois.objects.MethodFlag}
095 * @return true if the node was removed from the graph
096 */
097 public boolean remove(GNode<N> n, byte flags);
098
099 /**
100 * Checks if a node is in the graph
101 * All the Galois runtime actions (e.g., conflict detection) will be performed when
102 * the method is executed.
103 *
104 * @param n the node to check for
105 * @return true if the node is part of this graph
106 */
107 public boolean contains(GNode<N> n);
108
109 /**
110 * Checks if a node is in the graph
111 *
112 * @param n the node to check for
113 * @param flags Galois runtime actions (e.g., conflict detection) that need to be executed
114 * upon invocation of this method. See {@link galois.objects.MethodFlag}
115 * @return true if the node is part of this graph
116 */
117 public boolean contains(GNode<N> n, byte flags);
118
119 /**
120 * Returns the number of nodes in this graph.
121 * All the Galois runtime actions (e.g., conflict detection) will be performed when
122 * the method is executed.
123 *
124 * @return the number of nodes (vertices) in this graph
125 */
126 public int size();
127
128 /**
129 * Returns the number of nodes in this graph.
130 *
131 * @param flags Galois runtime actions (e.g., conflict detection) that need to be executed
132 * upon invocation of this method. See {@link galois.objects.MethodFlag}
133 * @return the number of nodes (vertices) in this graph
134 */
135 public int size(byte flags);
136
137 /**
138 * Adds an edge between the two nodes. If the graph is directed, the first node is interpreted
139 * to be the source of the edge.
140 * All the Galois runtime actions (e.g., conflict detection) will be performed when
141 * the method is executed.
142 *
143 * @param src the source of the edge
144 * @param dst the destination of the edge
145 * @return true if the edge was not already in the graph
146 */
147 public boolean addNeighbor(GNode<N> src, GNode<N> dst);
148
149 /**
150 * Adds an edge between the two nodes. If the graph is directed, the first node is interpreted
151 * to be the source of the edge.
152 *
153 * @param src the source of the edge
154 * @param dst the destination of the edge
155 * @param flags Galois runtime actions (e.g., conflict detection) that need to be executed
156 * upon invocation of this method. See {@link galois.objects.MethodFlag}
157 * @return true if the edge was not already in the graph
158 */
159 public boolean addNeighbor(GNode<N> src, GNode<N> dst, byte flags);
160
161 /**
162 * Removes the edge between the two nodes from this graph. If the graph is directed, the first node is interpreted
163 * to be the source of the edge.
164 * All the Galois runtime actions (e.g., conflict detection) will be performed when
165 * the method is executed.
166 *
167 * @param src the source of the edge
168 * @param dst the target of the edge
169 * @return true if the edge was removed from this graph
170 */
171 public boolean removeNeighbor(GNode<N> src, GNode<N> dst);
172
173 /**
174 * Removes the edge between the two nodes from this graph. If the graph is directed, the first node is interpreted
175 * to be the source of the edge.
176 *
177 * @param src the source of the edge
178 * @param dst the target of the edge
179 * @param flags Galois runtime actions (e.g., conflict detection) that need to be executed
180 * upon invocation of this method. See {@link galois.objects.MethodFlag}
181 * @return true if the edge was removed from this graph
182 */
183 public boolean removeNeighbor(GNode<N> src, GNode<N> dst, byte flags);
184
185 /**
186 * Checks if there is an edge between the two nodes in this graph. If the graph is directed, the first node is interpreted
187 * to be the source of the edge.
188 * All the Galois runtime actions (e.g., conflict detection) will be performed when
189 * the method is executed.
190 *
191 * @param src the source of the edge
192 * @param dst the target of the edge
193 * @return true if the two nodes are neighbors in this graph
194 */
195 public boolean hasNeighbor(GNode<N> src, GNode<N> dst);
196
197 /**
198 * Checks if there is an edge between the two nodes in this graph. If the graph is directed, the first node is interpreted
199 * to be the source of the edge.
200 *
201 * @param src the source of the edge
202 * @param dst the target of the edge
203 * @param flags Galois runtime actions (e.g., conflict detection) that need to be executed
204 * upon invocation of this method. See {@link galois.objects.MethodFlag}
205 * @return true if the two nodes are neighbors in this graph
206 */
207 public boolean hasNeighbor(GNode<N> src, GNode<N> dst, byte flags);
208
209 /**
210 * Applies the function passed as parameter to every <i>in neighbor</i> of the given node exactly once.
211 * For example, if we assume that each node contains an integer and we want to print the integer contained in each incoming
212 * neighbor of <code>node</code> in <code>graph</code>
213 * <pre>
214 * graph.mapInNeighbors(node, new LambdaVoid<GNode<Integer>>() {
215 * public void call(GNode<Integer> inNeighbor) {
216 * System.out.println(inNeighbor.getData());
217 * }
218 * }
219 * </pre>
220 * If you wish to apply a function to the <i>out neighbors</i>, please use GNode#map
221 *
222 * All the Galois runtime actions (e.g., conflict detection) will be performed when
223 * the method is executed.
224
225 * @param src a node in the graph
226 * @param body the function to be applied once to each incoming neighbor
227 * @throws java.util.ConcurrentModificationException
228 * if the function modifies the set of in neighbors
229 * of the node
230 * @see GNode#map
231 */
232 public void mapInNeighbors(GNode<N> src, LambdaVoid<GNode<N>> body);
233
234 /**
235 * Applies the function passed as parameter to every <i>in neighbor</i> of the given node exactly once.
236 * For example, if we assume that each node contains an integer and we want to print the integer contained in each incoming
237 * neighbor of <code>node</code> in <code>graph</code>
238 * <pre>
239 * graph.mapInNeighbors(node, new LambdaVoid<GNode<Integer>>() {
240 * public void call(GNode<Integer> inNeighbor) {
241 * System.out.println(inNeighbor.getData());
242 * }
243 * }
244 * </pre>
245 * If you wish to apply a function to the <i>out neighbors</i>, please use GNode#map
246 *
247 * @param src a node in the graph
248 * @param body the function to be applied once to each incoming neighbor
249 * @param flags Galois runtime actions (e.g., conflict detection) that need to be executed
250 * upon invocation of this method. See {@link galois.objects.MethodFlag}
251 * @throws java.util.ConcurrentModificationException
252 * if the function modifies the set of in neighbors
253 * of the node
254 * @see GNode#map
255 */
256 public void mapInNeighbors(GNode<N> src, LambdaVoid<GNode<N>> body, byte flags);
257
258 /**
259 * Computes the number of <i>in neighbors</i> of the node, i.e., the number of different vertices that have an outgoing edge
260 * that ends at the indicated node.
261 *
262 * All the Galois runtime actions (e.g., conflict detection) will be performed when
263 * the method is executed.
264 *
265 * @param src a node in the graph
266 * @return the number of incoming neighbors
267 */
268 public int inNeighborsSize(GNode<N> src);
269
270 /**
271 * Computes the number of <i>in neighbors</i> of the node, i.e., the number of different vertices that have an outgoing edge
272 * that ends at the indicated node.
273 *
274 * @param src a node in the graph
275 * @param flags Galois runtime actions (e.g., conflict detection) that need to be executed
276 * upon invocation of this method. See {@link galois.objects.MethodFlag}
277 * @return the number of incoming neighbors
278 */
279 public int inNeighborsSize(GNode<N> src, byte flags);
280
281 /**
282 * Computes the number of <i>out neighbors</i> of the node, i.e., the number of different vertices that have an incoming edge
283 * that starts at the indicated node.
284 *
285 * All the Galois runtime actions (e.g., conflict detection) will be performed when
286 * the method is executed.
287 *
288 * @param src a node in the graph
289 * @return the number of outgoing neighbors
290 */
291 public int outNeighborsSize(GNode<N> src);
292
293 /**
294 * Computes the number of <i>out neighbors</i> of the node, i.e., the number of different vertices that have an incoming edge
295 * that starts at the indicated node.
296 *
297 * @param src a node in the graph
298 * @param flags Galois runtime actions (e.g., conflict detection) that need to be executed
299 * upon invocation of this method. See {@link galois.objects.MethodFlag}
300 * @return the number of outgoing neighbors
301 */
302 public int outNeighborsSize(GNode<N> src, byte flags);
303
304 /**
305 * Tests if the current graph is directed.
306 *
307 * @return true if the graph uses directed edges
308 */
309 public boolean isDirected();
310 }