1 /*
2 * Created on Oct 17, 2005
3 *
4 * Copyright (c) 2005, the JUNG Project and the Regents of the University
5 * of California
6 * All rights reserved.
7 *
8 * This software is open-source under the BSD license; see either
9 * "license.txt" or
10 * http://jung.sourceforge.net/license.txt for a description.
11 */
12 package edu.uci.ics.jung.graph;
13
14 import java.util.Collection;
15
16 import edu.uci.ics.jung.graph.util.EdgeType;
17
18 /**
19 * A hypergraph, consisting of a set of vertices of type <code>V</code>
20 * and a set of hyperedges of type <code>E</code> which connect the vertices.
21 * This is the base interface for all JUNG graph types.
22 * <P>
23 * This interface permits, but does not enforce, any of the following
24 * common variations of graphs:
25 * <ul>
26 * <li/>hyperedges (edges which connect a set of vertices of any size)
27 * <li/>edges (these have have exactly two endpoints, which may or may not be distinct)
28 * <li/>self-loops (edges which connect exactly one vertex)
29 * <li> directed and undirected edges
30 * <li> vertices and edges with attributes (for example, weighted edges)
31 * <li> vertices and edges with different constraints or properties (for example, bipartite
32 * or multimodal graphs)
33 * <li> parallel edges (multiple edges which connect a single set of vertices)
34 * <li> internal representations as matrices or as adjacency lists or adjacency maps
35 * </ul>
36 * Extensions or implementations of this interface
37 * may enforce or disallow any or all of these variations.
38 * <p><b>Notes</b>:
39 * <ul>
40 * <li/> The collections returned by <code>Hypergraph</code> instances
41 * should be treated in general as if read-only. While they are not contractually
42 * guaranteed (or required) to be immutable,
43 * this interface does not define the outcome if they are mutated.
44 * Mutations should be done via <code>{add,remove}{Edge,Vertex}</code>, or
45 * in the constructor.
46 * <li/>
47 * </ul>
48 *
49 * @author Joshua O'Madadhain
50 */
51 public interface Hypergraph<V, E>
52 {
53 /**
54 * Returns a view of all edges in this graph. In general, this
55 * obeys the <code>Collection</code> contract, and therefore makes no guarantees
56 * about the ordering of the vertices within the set.
57 * @return a <code>Collection</code> view of all edges in this graph
58 */
59 Collection<E> getEdges();
60
61 /**
62 * Returns a view of all vertices in this graph. In general, this
63 * obeys the <code>Collection</code> contract, and therefore makes no guarantees
64 * about the ordering of the vertices within the set.
65 * @return a <code>Collection</code> view of all vertices in this graph
66 */
67 Collection<V> getVertices();
68
69 /**
70 * Returns true if this graph's vertex collection contains <code>vertex</code>.
71 * Equivalent to <code>getVertices().contains(vertex)</code>.
72 * @param vertex the vertex whose presence is being queried
73 * @return true iff this graph contains a vertex <code>vertex</code>
74 */
75 boolean containsVertex(V vertex);
76
77 /**
78 * Returns true if this graph's edge collection contains <code>edge</code>.
79 * Equivalent to <code>getEdges().contains(edge)</code>.
80 * @param edge the edge whose presence is being queried
81 * @return true iff this graph contains an edge <code>edge</code>
82 */
83 boolean containsEdge(E edge);
84
85 /**
86 * Returns the number of edges in this graph.
87 * @return the number of edges in this graph
88 */
89 int getEdgeCount();
90
91 /**
92 * Returns the number of vertices in this graph.
93 * @return the number of vertices in this graph
94 */
95 int getVertexCount();
96
97 /**
98 * Returns the collection of vertices which are connected to <code>vertex</code>
99 * via any edges in this graph.
100 * If <code>vertex</code> is connected to itself with a self-loop, then
101 * it will be included in the collection returned.
102 *
103 * @param vertex the vertex whose neighbors are to be returned
104 * @return the collection of vertices which are connected to <code>vertex</code>,
105 * or <code>null</code> if <code>vertex</code> is not present
106 */
107 Collection<V> getNeighbors(V vertex);
108
109 /**
110 * Returns the collection of edges in this graph which are connected to <code>vertex</code>.
111 *
112 * @param vertex the vertex whose incident edges are to be returned
113 * @return the collection of edges which are connected to <code>vertex</code>,
114 * or <code>null</code> if <code>vertex</code> is not present
115 */
116 Collection<E> getIncidentEdges(V vertex);
117
118 /**
119 * Returns the collection of vertices in this graph which are connected to <code>edge</code>.
120 * Note that for some graph types there are guarantees about the size of this collection
121 * (i.e., some graphs contain edges that have exactly two endpoints, which may or may
122 * not be distinct). Implementations for those graph types may provide alternate methods
123 * that provide more convenient access to the vertices.
124 *
125 * @param edge the edge whose incident vertices are to be returned
126 * @return the collection of vertices which are connected to <code>edge</code>,
127 * or <code>null</code> if <code>edge</code> is not present
128 */
129 Collection<V> getIncidentVertices(E edge);
130
131 /**
132 * Returns an edge that connects this vertex to <code>v</code>.
133 * If this edge is not uniquely
134 * defined (that is, if the graph contains more than one edge connecting
135 * <code>v1</code> to <code>v2</code>), any of these edges
136 * may be returned. <code>findEdgeSet(v1, v2)</code> may be
137 * used to return all such edges.
138 * Returns null if either of the following is true:
139 * <ul>
140 * <li/><code>v2</code> is not connected to <code>v1</code>
141 * <li/>either <code>v1</code> or <code>v2</code> are not present in this graph
142 * </ul>
143 * <p><b>Note</b>: for purposes of this method, <code>v1</code> is only considered to be connected to
144 * <code>v2</code> via a given <i>directed</i> edge <code>e</code> if
145 * <code>v1 == e.getSource() && v2 == e.getDest()</code> evaluates to <code>true</code>.
146 * (<code>v1</code> and <code>v2</code> are connected by an undirected edge <code>u</code> if
147 * <code>u</code> is incident to both <code>v1</code> and <code>v2</code>.)
148 *
149 * @return an edge that connects <code>v1</code> to <code>v2</code>,
150 * or <code>null</code> if no such edge exists (or either vertex is not present)
151 * @see Hypergraph#findEdgeSet(Object, Object)
152 */
153 E findEdge(V v1, V v2);
154
155 /**
156 * Returns all edges that connects this vertex to <code>v</code>.
157 * If this edge is not uniquely
158 * defined (that is, if the graph contains more than one edge connecting
159 * <code>v1</code> to <code>v2</code>), any of these edges
160 * may be returned. <code>findEdgeSet(v1, v2)</code> may be
161 * used to return all such edges.
162 * Returns null if <code>v2</code> is not connected to <code>v1</code>.
163 * <br/>Returns an empty collection if either <code>v1</code> or <code>v2</code> are not present in this graph.
164 *
165 * <p><b>Note</b>: for purposes of this method, <code>v1</code> is only considered to be connected to
166 * <code>v2</code> via a given <i>directed</i> edge <code>d</code> if
167 * <code>v1 == d.getSource() && v2 == d.getDest()</code> evaluates to <code>true</code>.
168 * (<code>v1</code> and <code>v2</code> are connected by an undirected edge <code>u</code> if
169 * <code>u</code> is incident to both <code>v1</code> and <code>v2</code>.)
170 *
171 * @return a collection containing all edges that connect <code>v1</code> to <code>v2</code>,
172 * or <code>null</code> if either vertex is not present
173 * @see Hypergraph#findEdge(Object, Object)
174 */
175 Collection<E> findEdgeSet(V v1, V v2);
176
177 /**
178 * Adds <code>vertex</code> to this graph.
179 * Fails if <code>vertex</code> is null or already in the graph.
180 *
181 * @param vertex the vertex to add
182 * @return <code>true</code> if the add is successful, and <code>false</code> otherwise
183 * @throws IllegalArgumentException if <code>vertex</code> is <code>null</code>
184 */
185 boolean addVertex(V vertex);
186
187 /**
188 * Adds <code>edge</code> to this graph.
189 * Fails under the following circumstances:
190 * <ul>
191 * <li/><code>edge</code> is already an element of the graph
192 * <li/>either <code>edge</code> or <code>vertices</code> is <code>null</code>
193 * <li/><code>vertices</code> has the wrong number of vertices for the graph type
194 * <li/><code>vertices</code> are already connected by another edge in this graph,
195 * and this graph does not accept parallel edges
196 * </ul>
197 *
198 * @param edge
199 * @param vertices
200 * @return <code>true</code> if the add is successful, and <code>false</code> otherwise
201 * @throws IllegalArgumentException if <code>edge</code> or <code>vertices</code> is null,
202 * or if a different vertex set in this graph is already connected by <code>edge</code>,
203 * or if <code>vertices</code> are not a legal vertex set for <code>edge</code>
204 */
205 boolean addEdge(E edge, Collection<? extends V> vertices);
206
207 /**
208 * Adds <code>edge</code> to this graph with type <code>edge_type</code>.
209 * Fails under the following circumstances:
210 * <ul>
211 * <li/><code>edge</code> is already an element of the graph
212 * <li/>either <code>edge</code> or <code>vertices</code> is <code>null</code>
213 * <li/><code>vertices</code> has the wrong number of vertices for the graph type
214 * <li/><code>vertices</code> are already connected by another edge in this graph,
215 * and this graph does not accept parallel edges
216 * <li/><code>edge_type</code> is not legal for this graph
217 * </ul>
218 *
219 * @param edge
220 * @param vertices
221 * @return <code>true</code> if the add is successful, and <code>false</code> otherwise
222 * @throws IllegalArgumentException if <code>edge</code> or <code>vertices</code> is null,
223 * or if a different vertex set in this graph is already connected by <code>edge</code>,
224 * or if <code>vertices</code> are not a legal vertex set for <code>edge</code>
225 */
226 boolean addEdge(E edge, Collection<? extends V> vertices, EdgeType
227 edge_type);
228
229 /**
230 * Removes <code>vertex</code> from this graph.
231 * As a side effect, removes any edges <code>e</code> incident to <code>vertex</code> if the
232 * removal of <code>vertex</code> would cause <code>e</code> to be incident to an illegal
233 * number of vertices. (Thus, for example, incident hyperedges are not removed, but
234 * incident edges--which must be connected to a vertex at both endpoints--are removed.)
235 *
236 * <p>Fails under the following circumstances:
237 * <ul>
238 * <li/><code>vertex</code> is not an element of this graph
239 * <li/><code>vertex</code> is <code>null</code>
240 * </ul>
241 *
242 * @param vertex the vertex to remove
243 * @return <code>true</code> if the removal is successful, <code>false</code> otherwise
244 */
245 boolean removeVertex(V vertex);
246
247 /**
248 * Removes <code>edge</code> from this graph.
249 * Fails if <code>edge</code> is null, or is otherwise not an element of this graph.
250 *
251 * @param edge the edge to remove
252 * @return <code>true</code> if the removal is successful, <code>false</code> otherwise
253 */
254 boolean removeEdge(E edge);
255
256
257 /**
258 * Returns <code>true</code> if <code>v1</code> and <code>v2</code> share an incident edge.
259 * Equivalent to <code>getNeighbors(v1).contains(v2)</code>.
260 *
261 * @param v1 the first vertex to test
262 * @param v2 the second vertex to test
263 * @return <code>true</code> if <code>v1</code> and <code>v2</code> share an incident edge
264 */
265 boolean isNeighbor(V v1, V v2);
266
267 /**
268 * Returns <code>true</code> if <code>vertex</code> and <code>edge</code>
269 * are incident to each other.
270 * Equivalent to <code>getIncidentEdges(vertex).contains(edge)</code> and to
271 * <code>getIncidentVertices(edge).contains(vertex)</code>.
272 * @param vertex
273 * @param edge
274 * @return <code>true</code> if <code>vertex</code> and <code>edge</code>
275 * are incident to each other
276 */
277 boolean isIncident(V vertex, E edge);
278
279 /**
280 * Returns the number of edges incident to <code>vertex</code>.
281 * Special cases of interest:
282 * <ul>
283 * <li/> Incident self-loops are counted once.
284 * <li> If there is only one edge that connects this vertex to
285 * each of its neighbors (and vice versa), then the value returned
286 * will also be equal to the number of neighbors that this vertex has
287 * (that is, the output of <code>getNeighborCount</code>).
288 * <li> If the graph is directed, then the value returned will be
289 * the sum of this vertex's indegree (the number of edges whose
290 * destination is this vertex) and its outdegree (the number
291 * of edges whose source is this vertex), minus the number of
292 * incident self-loops (to avoid double-counting).
293 * </ul>
294 * <p>Equivalent to <code>getIncidentEdges(vertex).size()</code>.
295 *
296 * @param vertex the vertex whose degree is to be returned
297 * @return the degree of this node
298 * @see Hypergraph#getNeighborCount(Object)
299 */
300 int degree(V vertex);
301
302 /**
303 * Returns the number of vertices that are adjacent to <code>vertex</code>
304 * (that is, the number of vertices that are incident to edges in <code>vertex</code>'s
305 * incident edge set).
306 *
307 * <p>Equivalent to <code>getNeighbors(vertex).size()</code>.
308 * @param vertex the vertex whose neighbor count is to be returned
309 * @return the number of neighboring vertices
310 */
311 int getNeighborCount(V vertex);
312
313 /**
314 * Returns the number of vertices that are incident to <code>edge</code>.
315 * For hyperedges, this can be any nonnegative integer; for edges this
316 * must be 2 (or 1 if self-loops are permitted).
317 *
318 * <p>Equivalent to <code>getIncidentVertices(edge).size()</code>.
319 * @param edge the edge whose incident vertex count is to be returned
320 * @return the number of vertices that are incident to <code>edge</code>.
321 */
322 int getIncidentCount(E edge);
323
324 /**
325 * Returns the edge type of <code>edge</code> in this graph.
326 * @param edge
327 * @return the <code>EdgeType</code> of <code>edge</code>, or <code>null</code> if <code>edge</code> has no defined type
328 */
329 EdgeType getEdgeType(E edge);
330
331 /**
332 * Returns the default edge type for this graph.
333 *
334 * @return the default edge type for this graph
335 */
336 EdgeType getDefaultEdgeType();
337
338 /**
339 * Returns the collection of edges in this graph which are of type <code>edge_type</code>.
340 * @param edge_type the type of edges to be returned
341 * @return the collection of edges which are of type <code>edge_type</code>, or
342 * <code>null</code> if the graph does not accept edges of this type
343 * @see EdgeType
344 */
345 Collection<E> getEdges(EdgeType edge_type);
346
347 /**
348 * Returns the number of edges of type <code>edge_type</code> in this graph.
349 * @param edge_type the type of edge for which the count is to be returned
350 * @return the number of edges of type <code>edge_type</code> in this graph
351 */
352 int getEdgeCount(EdgeType edge_type);
353
354 /**
355 * Returns a <code>Collection</code> view of the incoming edges incident to <code>vertex</code>
356 * in this graph.
357 * @param vertex the vertex whose incoming edges are to be returned
358 * @return a <code>Collection</code> view of the incoming edges incident
359 * to <code>vertex</code> in this graph
360 */
361 Collection<E> getInEdges(V vertex);
362
363 /**
364 * Returns a <code>Collection</code> view of the outgoing edges incident to <code>vertex</code>
365 * in this graph.
366 * @param vertex the vertex whose outgoing edges are to be returned
367 * @return a <code>Collection</code> view of the outgoing edges incident
368 * to <code>vertex</code> in this graph
369 */
370 Collection<E> getOutEdges(V vertex);
371
372 /**
373 * Returns the number of incoming edges incident to <code>vertex</code>.
374 * Equivalent to <code>getInEdges(vertex).size()</code>.
375 * @param vertex the vertex whose indegree is to be calculated
376 * @return the number of incoming edges incident to <code>vertex</code>
377 */
378 int inDegree(V vertex);
379
380 /**
381 * Returns the number of outgoing edges incident to <code>vertex</code>.
382 * Equivalent to <code>getOutEdges(vertex).size()</code>.
383 * @param vertex the vertex whose outdegree is to be calculated
384 * @return the number of outgoing edges incident to <code>vertex</code>
385 */
386 int outDegree(V vertex);
387
388 /**
389 * If <code>directed_edge</code> is a directed edge in this graph, returns the source;
390 * otherwise returns <code>null</code>.
391 * The source of a directed edge <code>d</code> is defined to be the vertex for which
392 * <code>d</code> is an outgoing edge.
393 * <code>directed_edge</code> is guaranteed to be a directed edge if
394 * its <code>EdgeType</code> is <code>DIRECTED</code>.
395 * @param directed_edge
396 * @return the source of <code>directed_edge</code> if it is a directed edge in this graph, or <code>null</code> otherwise
397 */
398 V getSource(E directed_edge);
399
400 /**
401 * If <code>directed_edge</code> is a directed edge in this graph, returns the destination;
402 * otherwise returns <code>null</code>.
403 * The destination of a directed edge <code>d</code> is defined to be the vertex
404 * incident to <code>d</code> for which
405 * <code>d</code> is an incoming edge.
406 * <code>directed_edge</code> is guaranteed to be a directed edge if
407 * its <code>EdgeType</code> is <code>DIRECTED</code>.
408 * @param directed_edge
409 * @return the destination of <code>directed_edge</code> if it is a directed edge in this graph, or <code>null</code> otherwise
410 */
411 V getDest(E directed_edge);
412
413 /**
414 * Returns a <code>Collection</code> view of the predecessors of <code>vertex</code>
415 * in this graph. A predecessor of <code>vertex</code> is defined as a vertex <code>v</code>
416 * which is connected to
417 * <code>vertex</code> by an edge <code>e</code>, where <code>e</code> is an outgoing edge of
418 * <code>v</code> and an incoming edge of <code>vertex</code>.
419 * @param vertex the vertex whose predecessors are to be returned
420 * @return a <code>Collection</code> view of the predecessors of
421 * <code>vertex</code> in this graph
422 */
423 Collection<V> getPredecessors(V vertex);
424
425 /**
426 * Returns a <code>Collection</code> view of the successors of <code>vertex</code>
427 * in this graph. A successor of <code>vertex</code> is defined as a vertex <code>v</code>
428 * which is connected to
429 * <code>vertex</code> by an edge <code>e</code>, where <code>e</code> is an incoming edge of
430 * <code>v</code> and an outgoing edge of <code>vertex</code>.
431 * @param vertex the vertex whose predecessors are to be returned
432 * @return a <code>Collection</code> view of the successors of
433 * <code>vertex</code> in this graph
434 */
435 Collection<V> getSuccessors(V vertex);
436 }