1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
|
/*
* Created on Oct 17, 2005
*
* Copyright (c) 2005, the JUNG Project and the Regents of the University
* of California
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* http://jung.sourceforge.net/license.txt for a description.
*/
package edu.uci.ics.jung.graph;
import java.util.Collection;
import edu.uci.ics.jung.graph.util.EdgeType;
import edu.uci.ics.jung.graph.util.Pair;
/**
* A graph consisting of a set of vertices of type <code>V</code>
* set and a set of edges of type <code>E</code>. Edges of this
* graph type have exactly two endpoints; whether these endpoints
* must be distinct depends on the implementation.
* <P>
* This interface permits, but does not enforce, any of the following
* common variations of graphs:
* <ul>
* <li> directed and undirected edges
* <li> vertices and edges with attributes (for example, weighted edges)
* <li> vertices and edges of different types (for example, bipartite
* or multimodal graphs)
* <li> parallel edges (multiple edges which connect a single set of vertices)
* <li> representations as matrices or as adjacency lists or adjacency maps
* </ul>
* Extensions or implementations of this interface
* may enforce or disallow any or all of these variations.
*
* <p>Definitions (with respect to a given vertex <code>v</code>):
* <ul>
* <li/><b>incoming edge</b> of <code>v</code>: an edge that can be traversed
* from a neighbor of <code>v</code> to reach <code>v</code>
* <li/><b>outgoing edge</b> of <code>v</code>: an edge that can be traversed
* from <code>v</code> to reach some neighbor of <code>v</code>
* <li/><b>predecessor</b> of <code>v</code>: a vertex at the other end of an
* incoming edge of <code>v</code>
* <li/><b>successor</b> of <code>v</code>: a vertex at the other end of an
* outgoing edge of <code>v</code>
* <li/>
* </ul>
*
* @author Joshua O'Madadhain
*/
public interface Graph<V,E> extends Hypergraph<V,E>
{
/**
* Returns a <code>Collection</code> view of the incoming edges incident to <code>vertex</code>
* in this graph.
* @param vertex the vertex whose incoming edges are to be returned
* @return a <code>Collection</code> view of the incoming edges incident
* to <code>vertex</code> in this graph
*/
Collection<E> getInEdges(V vertex);
/**
* Returns a <code>Collection</code> view of the outgoing edges incident to <code>vertex</code>
* in this graph.
* @param vertex the vertex whose outgoing edges are to be returned
* @return a <code>Collection</code> view of the outgoing edges incident
* to <code>vertex</code> in this graph
*/
Collection<E> getOutEdges(V vertex);
/**
* Returns a <code>Collection</code> view of the predecessors of <code>vertex</code>
* in this graph. A predecessor of <code>vertex</code> is defined as a vertex <code>v</code>
* which is connected to
* <code>vertex</code> by an edge <code>e</code>, where <code>e</code> is an outgoing edge of
* <code>v</code> and an incoming edge of <code>vertex</code>.
* @param vertex the vertex whose predecessors are to be returned
* @return a <code>Collection</code> view of the predecessors of
* <code>vertex</code> in this graph
*/
Collection<V> getPredecessors(V vertex);
/**
* Returns a <code>Collection</code> view of the successors of <code>vertex</code>
* in this graph. A successor of <code>vertex</code> is defined as a vertex <code>v</code>
* which is connected to
* <code>vertex</code> by an edge <code>e</code>, where <code>e</code> is an incoming edge of
* <code>v</code> and an outgoing edge of <code>vertex</code>.
* @param vertex the vertex whose predecessors are to be returned
* @return a <code>Collection</code> view of the successors of
* <code>vertex</code> in this graph
*/
Collection<V> getSuccessors(V vertex);
/**
* Returns the number of incoming edges incident to <code>vertex</code>.
* Equivalent to <code>getInEdges(vertex).size()</code>.
* @param vertex the vertex whose indegree is to be calculated
* @return the number of incoming edges incident to <code>vertex</code>
*/
int inDegree(V vertex);
/**
* Returns the number of outgoing edges incident to <code>vertex</code>.
* Equivalent to <code>getOutEdges(vertex).size()</code>.
* @param vertex the vertex whose outdegree is to be calculated
* @return the number of outgoing edges incident to <code>vertex</code>
*/
int outDegree(V vertex);
/**
* Returns <code>true</code> if <code>v1</code> is a predecessor of <code>v2</code> in this graph.
* Equivalent to <code>v1.getPredecessors().contains(v2)</code>.
* @param v1 the first vertex to be queried
* @param v2 the second vertex to be queried
* @return <code>true</code> if <code>v1</code> is a predecessor of <code>v2</code>, and false otherwise.
*/
boolean isPredecessor(V v1, V v2);
/**
* Returns <code>true</code> if <code>v1</code> is a successor of <code>v2</code> in this graph.
* Equivalent to <code>v1.getSuccessors().contains(v2)</code>.
* @param v1 the first vertex to be queried
* @param v2 the second vertex to be queried
* @return <code>true</code> if <code>v1</code> is a successor of <code>v2</code>, and false otherwise.
*/
boolean isSuccessor(V v1, V v2);
/**
* Returns the number of predecessors that <code>vertex</code> has in this graph.
* Equivalent to <code>vertex.getPredecessors().size()</code>.
* @param vertex the vertex whose predecessor count is to be returned
* @return the number of predecessors that <code>vertex</code> has in this graph
*/
int getPredecessorCount(V vertex);
/**
* Returns the number of successors that <code>vertex</code> has in this graph.
* Equivalent to <code>vertex.getSuccessors().size()</code>.
* @param vertex the vertex whose successor count is to be returned
* @return the number of successors that <code>vertex</code> has in this graph
*/
int getSuccessorCount(V vertex);
/**
* If <code>directed_edge</code> is a directed edge in this graph, returns the source;
* otherwise returns <code>null</code>.
* The source of a directed edge <code>d</code> is defined to be the vertex for which
* <code>d</code> is an outgoing edge.
* <code>directed_edge</code> is guaranteed to be a directed edge if
* its <code>EdgeType</code> is <code>DIRECTED</code>.
* @param directed_edge
* @return the source of <code>directed_edge</code> if it is a directed edge in this graph, or <code>null</code> otherwise
*/
V getSource(E directed_edge);
/**
* If <code>directed_edge</code> is a directed edge in this graph, returns the destination;
* otherwise returns <code>null</code>.
* The destination of a directed edge <code>d</code> is defined to be the vertex
* incident to <code>d</code> for which
* <code>d</code> is an incoming edge.
* <code>directed_edge</code> is guaranteed to be a directed edge if
* its <code>EdgeType</code> is <code>DIRECTED</code>.
* @param directed_edge
* @return the destination of <code>directed_edge</code> if it is a directed edge in this graph, or <code>null</code> otherwise
*/
V getDest(E directed_edge);
/**
* Returns <code>true</code> if <code>vertex</code> is the source of <code>edge</code>.
* Equivalent to <code>getSource(edge).equals(vertex)</code>.
* @param vertex the vertex to be queried
* @param edge the edge to be queried
* @return <code>true</code> iff <code>vertex</code> is the source of <code>edge</code>
*/
boolean isSource(V vertex, E edge);
/**
* Returns <code>true</code> if <code>vertex</code> is the destination of <code>edge</code>.
* Equivalent to <code>getDest(edge).equals(vertex)</code>.
* @param vertex the vertex to be queried
* @param edge the edge to be queried
* @return <code>true</code> iff <code>vertex</code> is the destination of <code>edge</code>
*/
boolean isDest(V vertex, E edge);
/**
* Adds edge <code>e</code> to this graph such that it connects
* vertex <code>v1</code> to <code>v2</code>.
* Equivalent to <code>addEdge(e, new Pair<V>(v1, v2))</code>.
* If this graph does not contain <code>v1</code>, <code>v2</code>,
* or both, implementations may choose to either silently add
* the vertices to the graph or throw an <code>IllegalArgumentException</code>.
* If this graph assigns edge types to its edges, the edge type of
* <code>e</code> will be the default for this graph.
* See <code>Hypergraph.addEdge()</code> for a listing of possible reasons
* for failure.
* @param e the edge to be added
* @param v1 the first vertex to be connected
* @param v2 the second vertex to be connected
* @return <code>true</code> if the add is successful, <code>false</code> otherwise
* @see Hypergraph#addEdge(Object, Collection)
* @see #addEdge(Object, Object, Object, EdgeType)
*/
boolean addEdge(E e, V v1, V v2);
/**
* Adds edge <code>e</code> to this graph such that it connects
* vertex <code>v1</code> to <code>v2</code>.
* Equivalent to <code>addEdge(e, new Pair<V>(v1, v2))</code>.
* If this graph does not contain <code>v1</code>, <code>v2</code>,
* or both, implementations may choose to either silently add
* the vertices to the graph or throw an <code>IllegalArgumentException</code>.
* If <code>edgeType</code> is not legal for this graph, this method will
* throw <code>IllegalArgumentException</code>.
* See <code>Hypergraph.addEdge()</code> for a listing of possible reasons
* for failure.
* @param e the edge to be added
* @param v1 the first vertex to be connected
* @param v2 the second vertex to be connected
* @param edgeType the type to be assigned to the edge
* @return <code>true</code> if the add is successful, <code>false</code> otherwise
* @see Hypergraph#addEdge(Object, Collection)
* @see #addEdge(Object, Object, Object)
*/
boolean addEdge(E e, V v1, V v2, EdgeType edgeType);
/**
* Returns the endpoints of <code>edge</code> as a <code>Pair<V></code>.
* @param edge the edge whose endpoints are to be returned
* @return the endpoints (incident vertices) of <code>edge</code>
*/
Pair<V> getEndpoints(E edge);
/**
* Returns the vertex at the other end of <code>edge</code> from <code>vertex</code>.
* (That is, returns the vertex incident to <code>edge</code> which is not <code>vertex</code>.)
* @param vertex the vertex to be queried
* @param edge the edge to be queried
* @return the vertex at the other end of <code>edge</code> from <code>vertex</code>
*/
V getOpposite(V vertex, E edge);
}
|
