01: /*
02: * GeoTools - OpenSource mapping toolkit
03: * http://geotools.org
04: * (C) 2002-2006, GeoTools Project Managment Committee (PMC)
05: * (C) 2002, Refractions Reserach Inc.
06: *
07: * This library is free software; you can redistribute it and/or
08: * modify it under the terms of the GNU Lesser General Public
09: * License as published by the Free Software Foundation;
10: * version 2.1 of the License.
11: *
12: * This library is distributed in the hope that it will be useful,
13: * but WITHOUT ANY WARRANTY; without even the implied warranty of
14: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15: * Lesser General Public License for more details.
16: */
17: package org.geotools.graph.path;
18:
19: import java.util.Collection;
20: import java.util.HashSet;
21: import java.util.List;
22:
23: import org.geotools.graph.structure.Edge;
24: import org.geotools.graph.structure.Node;
25:
26: /**
27: *
28: * Represents a cycle in a graph. A <B>cycle</B> C is defined as a closed walk
29: * of size n in which nodes 1 through n-1 form a path.
30: *
31: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
32: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/path/Cycle.java $
33: */
34: public class Cycle extends Walk {
35:
36: //TODO: DOCUMENT ME!
37: public Cycle(Collection nodes) {
38: super (nodes);
39: }
40:
41: /**
42: * Tests if the cycle is valid. A valid cycle satisfies two conditions: <BR>
43: * <BR>
44: * 1. Each pair of adjacent nodes share an edge.<BR>
45: * 2. The first and last nodes share an edge.
46: * 3. The only node repetition is the first and last nodes.
47: */
48: public boolean isValid() {
49: if (super .isValid()) {
50:
51: //ensure first and last nodes are same
52: if (isClosed()) {
53: //ensure no node repetitions except for first and last
54: return (new HashSet(this ).size() == size() - 1);
55: }
56: }
57: return (false);
58: }
59:
60: protected List buildEdges() {
61: List edges = super .buildEdges();
62:
63: //get the edge between the first and last nodes
64: Node first = (Node) get(0);
65: Node last = (Node) get(size() - 1);
66:
67: Edge e = first.getEdge(last);
68: if (e != null) {
69: edges.add(e);
70: return (edges);
71: }
72:
73: return (null);
74: }
75: }
|