Graph


1   /*
2    * Generic graph library
3    * Copyright (C) 2000,2003,2004 University of Maryland
4    * 
5    * This library is free software; you can redistribute it and/or
6    * modify it under the terms of the GNU Lesser General Public
7    * License as published by the Free Software Foundation; either
8    * version 2.1 of the License, or (at your option) any later version.
9    * 
10   * This library is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   * Lesser General Public License for more details.
14   * 
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with this library; if not, write to the Free Software
17   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18   */
19  
20  // $Revision: 1.14 $
21  
22  package edu.umd.cs.findbugs.graph;
23  
24  import java.util.Iterator  ;
25  
26  /**
27   * Graph interface; defines the operations used to access and manipulate
28   * a graph.
29   */
30  public interface Graph
31          <
32          EdgeType extends GraphEdge<EdgeType, VertexType>,
33          VertexType extends GraphVertex<VertexType>
34          > {
35  
36      /**
37       * Get number of edges in the graph.
38       */
39      public int getNumEdges();
40  
41      /**
42       * Get number of vertices in the graph.
43       */
44      public int getNumVertices();
45  
46      /**
47       * Get Iterator over all edges in the graph.
48       */
49      public Iterator  <EdgeType> edgeIterator();
50  
51      /**
52       * Get Iterator over all vertices in the graph.
53       */
54      public Iterator  <VertexType> vertexIterator();
55  
56      /**
57       * Add given vertex to the graph.
58       * The vertex should not be part of any other graph.
59       *
60       * @param v the vertex to add
61       */
62      public void addVertex(VertexType v);
63  
64      /**
65       * Determine if the graph contains the given vertex.
66       *
67       * @param v the vertex
68       * @return true if the vertex is part of the graph, false if not
69       */
70      public boolean containsVertex(VertexType v);
71  
72      /**
73       * Add a new edge to the graph.
74       * Duplicate edges (with same source and target vertices) are allowed.
75       *
76       * @param source the source vertex
77       * @param target the target vertex
78       * @return the new edge
79       */
80      public EdgeType createEdge(VertexType source, VertexType target);
81  
82      /**
83       * Look up an edge by source and target vertex.
84       * If multiple edges with same source and target vertex exist,
85       * one is selected arbitrarily.
86       *
87       * @param source the source vertex
88       * @param target the target vertex
89       * @return a matching edge, or null if there is no matching edge
90       */
91      public EdgeType lookupEdge(VertexType source, VertexType target);
92  
93      /**
94       * Get the number of numeric (integer) labels that have been assigned to vertices
95       * in the graph.  All vertices in the graph are guaranteed to have labels in the
96       * range 0..n, where n is the value returned by this method.
97       */
98      public int getNumVertexLabels();
99  
100     /**
101      * Reset number of (integer) labels.  This might be necessary
102      * if an algorithm has assigned new labels to a graph's vertices.
103      */
104     public void setNumVertexLabels(int numLabels);
105 
106     /**
107      * Get the number of numeric labels that have been assigned to edges.
108      */
109     public int getNumEdgeLabels();
110 
111     /**
112      * Reset the number of edge labels.
113      */
114     public void setNumEdgeLabels(int numLabels);
115 
116     /**
117      * Remove given edge from the graph.
118      */
119     public void removeEdge(EdgeType e);
120 
121     /**
122      * Remove given vertex from the graph.
123      * Note that all edges referencing the vertex will be
124      * removed.
125      */
126     public void removeVertex(VertexType v);
127 
128     /**
129      * Get an Iterator over outgoing edges from given vertex.
130      *
131      * @param source the source vertex
132      * @return an Iterator over outgoing edges
133      */
134     public Iterator  <EdgeType> outgoingEdgeIterator(VertexType source);
135 
136     /**
137      * Get an Iterator over incoming edges to a given vertex.
138      *
139      * @param target the target vertex
140      * @return an Iterator over incoming edges
141      */
142     public Iterator  <EdgeType> incomingEdgeIterator(VertexType target);
143 
144     /**
145      * Get number of edges going into given vertex.
146      *
147      * @param vertex the vertex
148      * @return number of edges going into the vertex
149      */
150     public int getNumIncomingEdges(VertexType vertex);
151 
152     /**
153      * Get number of edges going out of given vertex.
154      *
155      * @param vertex the vertex
156      * @return number of edges going out of the vertex
157      */
158     public int getNumOutgoingEdges(VertexType vertex);
159 
160     /**
161      * Get an iterator over the successors of this vertex;
162      * i.e., the targets of the vertex's outgoing edges.
163      *
164      * @param source the source vertex
165      * @return an Iterator over the successors of the vertex
166      */
167     public Iterator  <VertexType> successorIterator(VertexType source);
168 
169     /**
170      * Get an iterator over the predecessors of this vertex;
171      * i.e., the sources of the vertex's incoming edges.
172      *
173      * @param target the target vertex
174      * @return an Iterator over the predecessors of the vertex
175      */
176     public Iterator  <VertexType> predecessorIterator(VertexType target);
177 
178 }
179 
180 // vim:ts=4
181
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags