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
|
/* GraphView.java
* =========================================================================
* This file is part of the GrInvIn project - http://www.grinvin.org
*
* Copyright (C) 2005-2008 Universiteit Gent
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or (at
* your option) any later version.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* A copy of the GNU General Public License can be found in the file
* LICENSE.txt provided with the source distribution of this program (see
* the META-INF directory in the source jar). This license can also be
* found on the GNU website at http://www.gnu.org/licenses/gpl.html.
*
* If you did not receive a copy of the GNU General Public License along
* with this program, contact the lead developer, or write to the Free
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301, USA.
*/
package org.grinvin.graphs;
import java.util.Iterator;
/**
* <p>
* Interface representing a read-only view of an abstract graph. An abstract
* graph is a collection of vertices
* (of type {@link Vertex}) connected by edges (of type {@link Edge}).
* The endpoints of edges that belong to a graph must be vertices that also belong
* to the graph.
* </p>
*
* <p>
* This interface only provides read access to the graph. Use the interface
* {@link Graph} if you also need write access.
* </p>
*/
public interface GraphView {
/**
* Returns the order, i.e. the number of vertices, of the graph.
*/
public int getNumberOfVertices();
/**
* Returns the vertex with the given index in the graph. Vertices in a graph
* are indexed in the range 0..n-1 where n is the number of vertices.
* Note that the index of a vertex is allowed to change whenever
* the graph is modified. Every graph should honour the following invariant
* whenever {@code index} is in the correct range:
* <pre>
* getVertex(index).getIndex() == index
* </pre>
* @throws IndexOutOfBoundsException when the index is not in the range
* 0..n-1 where n is the number of vertices of the graph.
*/
public Vertex getVertex(int index);
/**
* Returns the size, i.e. the number of edges, of the graph.
*/
public int getNumberOfEdges();
/**
* Iterator over all edges of this graph.
*/
public Iterator<Edge> edgeIterator();
/**
* Set of edges of this graph. This method returns an {@link Iterable}
* and not a {@link java.util.Set} so its main purpose is to be used in
* a 'for each' loop:
* <pre>
* for (Edge e: graph.edges()) {
* // do something with e
* }
* </pre>
*/
public Iterable<Edge> edges();
/**
* Iterator over all vertices of this graph. If this iterator supports
* the {@code remove} operation, it should also remove all edges incident
* with the vertex that is removed.
*/
public Iterator<Vertex> vertexIterator();
/**
* Set of vertices of this graph. This method returns an {@link Iterable}
* and not a {@link java.util.Set} so its main purpose is to be used in
* a 'for each' loop:
* <pre>
* for (Vertex v: graph.vertices()) {
* // do something with v
* }
* </pre>
*/
public Iterable<Vertex> vertices();
/**
* Does the given vertex belong to this graph?
*/
public boolean contains(Vertex vertex);
/**
* Does the given edge belong to this graph?
*/
public boolean contains(Edge edge);
/**
* Return an edge joining the given vertices, or {@code null}
* when no such edge exists.
* @return an edge having {@code first} as its first endpoint and
* {@code second} as its second endpoint.
*/
public Edge getEdge(Vertex first, Vertex second);
/**
* Check whether the given vertices are adjacent in this graph.
* Should return the same result as
* <pre>
* getEdge (first,second) != null || getEgde (second,first) != null
* </pre>
*/
public boolean areAdjacent(Vertex v1, Vertex v2);
}
|
