001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2002-2006, GeoTools Project Managment Committee (PMC)
005: * (C) 2002, Refractions Reserach Inc.
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation;
010: * version 2.1 of the License.
011: *
012: * This library is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: */
017: package org.geotools.graph.structure;
018:
019: import java.util.Collection;
020: import java.util.List;
021:
022: /**
023: *
024: * Represents a graph.
025: *
026: * A graph is a collection of nodes (verticies) connected by links called
027: * edges (arcs). <BR>
028: * <BR>
029: * In most applications nodes of a graph represent the
030: * objects being modelled, and the edges represent the
031: * relationships between the objects. An example could be a polygon coverage in
032: * which one wishes to model a boundary sharing relationship. The following is
033: * an illustration.<BR>
034: * <BR>
035: * <IMG src="doc-files/poly_coverage.gif"><BR>
036: * <BR>
037: * In the above figure, the objects (nodes) are the polygons themselves, and the
038: * relationship (edges) between them is boundary sharing.<BR>
039: * <BR>
040: * However, there exists types of graphs in which the roles are reversed and the
041: * edges are the objects, and the nodes are the relationships. An example of
042: * such a graph is the stream network shown below.<BR>
043: * <BR>
044: * <IMG src="doc-files/stream_network.gif"><BR>
045: * <BR>
046: * In the above figure, the objects (edges) are the stream segments and the
047: * relationship (nodes) between them is endpoint sharing. However, if
048: * desirable one could model the second case similar to the first. The
049: * resulting graph is shown below.<BR>
050: * <BR>
051: * <IMG src="doc-files/stream_network2.gif"><BR>
052: * <BR>
053: * The Graph object is intended to serve as a container for a collection
054: * of nodes and edges. It does dont define or manage the relationship among the
055: * components it contains.
056: *
057: * @see Node
058: * @see Edge
059: *
060: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
061: *
062: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/structure/Graph.java $
063: */
064: public interface Graph {
065:
066: /**
067: * Signal to indicate that a graph component meets the requirements of a
068: * query against a graph and that the query should continue.
069: */
070: public static final int PASS_AND_CONTINUE = 1;
071:
072: /**
073: * Signal to indicate that a graph component meets the requirements of a
074: * query against a graph and that the query should end.
075: */
076: public static final int PASS_AND_STOP = 2;
077:
078: /**
079: * Signal to indicate that a graph component does NOT meet the requirements
080: * of a query made against the graph.
081: */
082: public static final int FAIL_QUERY = 0;
083:
084: /**
085: * Returns the nodes of the graph.
086: *
087: * @return A collection of Node objects.
088: *
089: * @see Node
090: */
091: public Collection getNodes();
092:
093: /**
094: * Returns the edges of the graph.
095: *
096: * @return A collection of Edge objects.
097: *
098: * @see Edge
099: */
100: public Collection getEdges();
101:
102: /**
103: * Performs a query against the nodes of the graph. Each Node object
104: * contained in the graph is passed to a GraphVisitor to determine if it
105: * meets the query criteria.
106: *
107: * @param visitor Determines if node meets query criteria.
108: * Returns MEET_AND_CONTINUE to signal that the node meets the query criteria
109: * and the query should continue.<BR>
110: * Returns MEET_AND_STOP to signal that the node meest the query criteria and
111: * the query should stop.<BR>
112: * FAIL_QUERY to signal that the node does NOT meet the query criteria.
113: *
114: * @return A collection of nodes that meet the query criteria.
115: *
116: * @see Node
117: * @see GraphVisitor
118: */
119: public List queryNodes(GraphVisitor visitor);
120:
121: /**
122: * Performs a query against the edges of the graph. Each Edge object
123: * contained in the graph is passed to a GraphVisitor to determine if it
124: * meets the query criteria.
125: *
126: * @param visitor Determines if the meets the query criteria. <BR>
127: * Returns MEET_AND_CONTINUE to signal that the edge meets the query criteria
128: * and the query should continue.<BR>
129: * Returns MEET_AND_STOP to signal that the edge meest the query criteria and
130: * the query should stop.<BR>
131: * FAIL_QUERY to signal that the edge does NOT meet the query criteria.
132: *
133: * @return A collection of edges that meet the query criteria.
134: *
135: * @see Edge
136: * @see GraphVisitor
137: */
138: public List queryEdges(GraphVisitor visitor);
139:
140: /**
141: * Applies the visitor pattern to the nodes of the graph.
142: *
143: * @param visitor
144: */
145: public void visitNodes(GraphVisitor visitor);
146:
147: /**
148: * Applies the visitor pattern to the edges of the graph.
149: *
150: * @param visitor
151: */
152: public void visitEdges(GraphVisitor visitor);
153:
154: /**
155: * Returns all the nodes in the graph of a specified degree. The degree of
156: * a node is the number of edges that are adjacent to the node.
157: *
158: * @param n The desired degree of nodes to be returned.
159: *
160: * @return A collection of nodes of degree n.
161: *
162: * @see Node#getDegree()
163: */
164: public List getNodesOfDegree(int n);
165:
166: /**
167: * Returns all the nodes in the graph that have been marked as visited or
168: * non-visited.
169: *
170: * @param visited True if node is visited, false if node is unvisited.
171: *
172: * @return List of nodes marked as visited / non-visited.
173: *
174: * @see Graphable#isVisited()
175: */
176: public List getVisitedNodes(boolean visited);
177:
178: /**
179: * Returns all the edges in the graph that have been marked as visited or
180: * non-visited.
181: *
182: * @param visited True if edge is visited, false if edge is unvisited.
183: *
184: * @return List of edges marked as visited / non-visited.
185: *
186: * @see Graphable#isVisited()
187: */
188: public List getVisitedEdges(boolean visited);
189:
190: }
|