001: /*
002: * Copyright (c) 2003-2008, Franz-Josef Elmer, All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * - Redistributions of source code must retain the above copyright notice,
008: * this list of conditions and the following disclaimer.
009: * - Redistributions in binary form must reproduce the above copyright notice,
010: * this list of conditions and the following disclaimer in the documentation
011: * and/or other materials provided with the distribution.
012: *
013: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
014: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
015: * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
016: * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
017: * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
018: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
019: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
020: * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
021: * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
022: * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
023: * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
024: */
025: package classycle.graph;
026:
027: import java.util.Vector;
028:
029: /**
030: * The base class for any type of vertex in a directed graph.
031: * <p>
032: * A <tt>Vertex</tt> holds an {@link Attributes} object which encapsulates
033: * all properties of the vertex which are not necessary to know for
034: * parsing a graph in a {@link GraphProcessor}. Only the visited flag will
035: * be manipulated during parsing.
036: * <p>
037: * A <tt>Vertex</tt> knows the head and tail vertices of all its outgoing
038: * and incoming arcs. When a head vertex is added by the method
039: * {@link #addOutgoingArcTo} also the corresponding incoming arc is built
040: * in the head vertex. The same is true the other way around. Note,
041: * that multi-arcs are not possible. That is, adding an already added
042: * head/tail vertex again as a head/tail vertex will be ignored.
043: *
044: * @author Franz-Josef Elmer
045: */
046: public class Vertex implements Comparable {
047: private final Vector _heads = new Vector();
048: private final Vector _tails = new Vector();
049: private final Attributes _attributes;
050: private boolean _visited;
051:
052: /** Create a new instance for the specified attributes. */
053: public Vertex(Attributes attributes) {
054: _attributes = attributes;
055: }
056:
057: /** Returns the attributes. */
058: public Attributes getAttributes() {
059: return _attributes;
060: }
061:
062: /**
063: * Returns the number of outgoing arcs. This is equivalent to the number
064: * of head vertices.
065: */
066: public int getNumberOfOutgoingArcs() {
067: return _heads.size();
068: }
069:
070: /** Returns the head vertex of the specified outgoing arc. */
071: public Vertex getHeadVertex(int index) {
072: return (Vertex) _heads.elementAt(index);
073: }
074:
075: /**
076: * Adds an outgoing arc to the specified vertex. Also calls
077: * {@link #addIncomingArcTo} for <tt>headVertex</tt> with <tt>this</tt> as
078: * the argument. Does nothing if <tt>headVertex</tt> is the head
079: * vertex of an already existing outgoing arc.
080: * @param headVertex Head vertex to be added to establish a new outgoing arc.
081: * <tt>Null</tt> is not allowed.
082: */
083: public void addOutgoingArcTo(Vertex headVertex) {
084: if (!_heads.contains(headVertex)) {
085: _heads.addElement(headVertex);
086: headVertex.addIncomingArcTo(this );
087: }
088: }
089:
090: /**
091: * Returns the number of incoming arcs. This is equivalent to the number
092: * of tail vertices.
093: */
094: public int getNumberOfIncomingArcs() {
095: return _tails.size();
096: }
097:
098: /** Returns the tail vertex of the specified outgoing arc. */
099: public Vertex getTailVertex(int index) {
100: return (Vertex) _tails.elementAt(index);
101: }
102:
103: /**
104: * Adds an incoming arc to the specified vertex. Also calls
105: * {@link #addOutgoingArcTo} for <tt>tailVertex</tt> with <tt>this</tt> as
106: * the argument. Does nothing if <tt>tailVertex</tt> is the
107: * tail vertex of an already existing incoming arc.
108: * @param tailVertex Tail vertex to be added to establish a new incoming arc.
109: * <tt>Null</tt> is not allowed.
110: */
111: public void addIncomingArcTo(Vertex tailVertex) {
112: if (!_tails.contains(tailVertex)) {
113: _tails.addElement(tailVertex);
114: tailVertex.addOutgoingArcTo(this );
115: }
116: }
117:
118: /** Reset this vertex. That is, the visited flag is set to <tt>false</tt>. */
119: public void reset() {
120: _visited = false;
121: }
122:
123: /**
124: * Marks this instance as visited.
125: * That is, the visited flag becomes <tt>true</tt>.
126: */
127: public void visit() {
128: _visited = true;
129: }
130:
131: /** Returns the visited flag. */
132: public boolean isVisited() {
133: return _visited;
134: }
135:
136: /**
137: * Returns <tt>toString()</tt> of the attributes and the number of
138: * incoming and outgoing arcs.
139: */
140: public String toString() {
141: StringBuffer result = new StringBuffer();
142: result.append(
143: getAttributes() == null ? super .toString()
144: : getAttributes().toString()).append(": ")
145: .append(getNumberOfIncomingArcs()).append(
146: " incoming arc(s), ").append(
147: getNumberOfOutgoingArcs()).append(
148: " outgoing arc(s).");
149: return new String(result);
150: }
151:
152: public int compareTo(Object object) {
153: int result = 1;
154: if (object instanceof Vertex && _attributes != null) {
155: result = _attributes
156: .compareTo(((Vertex) object)._attributes);
157: }
158: return result;
159: }
160:
161: } //class
|