KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > alg > AbstractPathElement


1 /* ==========================================
2  * JGraphT : a free Java graph-theory library
3  * ==========================================
4  *
5  * Project Info: http://jgrapht.sourceforge.net/
6  * Project Creator: Barak Naveh (http://sourceforge.net/users/barak_naveh)
7  *
8  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9  *
10  * This library is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this library; if not, write to the Free Software Foundation,
22  * Inc.,
23  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24  */
25 /* -------------------------
26  * AbstractPathElement.java
27  * -------------------------
28  * (C) Copyright 2006-2006, by France Telecom
29  *
30  * Original Author: Guillaume Boulmier and Contributors.
31  * Contributor(s): John V. Sichi
32  *
33  * $Id: AbstractPathElement.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 05-Jan-2006 : Initial revision (GB);
38  * 14-Jan-2006 : Added support for generics (JVS);
39  *
40  */
41 package org.jgrapht.alg;
42
43 import java.util.*;
44
45 import org.jgrapht.*;
46
47
48 /**
49  * A new path is created from a path concatenated to an edge. It's like a linked
50  * list.<br>
51  * The empty path is composed only of one vertex.<br>
52  * In this case the path has no previous path element.<br>
53  * .
54  *
55  * <p>NOTE jvs 14-Jan-2006: This is currently an internal data structure for use
56  * in algorithms. If we want to promote it to public, we should first clean it
57  * up and move it to the parent package, making a Path a first-class concept.
58  */
59 abstract class AbstractPathElement<V, E>
60 {
61
62     //~ Instance fields -------------------------------------------------------
63
64     /**
65      * Number of hops of the path.
66      */
67     protected int nHops;
68
69     /**
70      * Edge reaching the target vertex of the path.
71      */
72     protected E prevEdge;
73
74     /**
75      * Previous path element.
76      */
77     protected AbstractPathElement<V, E> prevPathElement;
78
79     /**
80      * Target vertex.
81      */
82     private V vertex;
83
84     //~ Constructors ----------------------------------------------------------
85
86     /**
87      * Creates a path element by concatenation of an edge to a path element.
88      *
89      * @param pathElement
90      * @param edge edge reaching the end vertex of the path element created.
91      */
92     protected AbstractPathElement(
93         Graph<V, E> graph,
94         AbstractPathElement<V, E> pathElement,
95         E edge)
96     {
97         this.vertex =
98             Graphs.getOppositeVertex(
99                 graph,
100                 edge,
101                 pathElement.getVertex());
102         this.prevEdge = edge;
103         this.prevPathElement = pathElement;
104
105         this.nHops = pathElement.getHopCount() + 1;
106     }
107
108     /**
109      * Copy constructor.
110      *
111      * @param original source to copy from
112      */
113     protected AbstractPathElement(AbstractPathElement<V, E> original)
114     {
115         this.nHops = original.nHops;
116         this.prevEdge = original.prevEdge;
117         this.prevPathElement = original.prevPathElement;
118         this.vertex = original.vertex;
119     }
120
121     /**
122      * Creates an empty path element.
123      *
124      * @param vertex end vertex of the path element.
125      */
126     protected AbstractPathElement(V vertex)
127     {
128         this.vertex = vertex;
129         this.prevEdge = null;
130         this.prevPathElement = null;
131
132         this.nHops = 0;
133     }
134
135     //~ Methods ---------------------------------------------------------------
136
137     /**
138      * Returns the path as a list of edges.
139      *
140      * @return list of <code>Edge</code>.
141      */
142     public List<E> createEdgeListPath()
143     {
144         List<E> path = new ArrayList<E>();
145         AbstractPathElement<V, E> pathElement = this;
146
147         // while start vertex is not reached.
148 while (pathElement.getPrevEdge() != null) {
149             path.add(pathElement.getPrevEdge());
150
151             pathElement = pathElement.getPrevPathElement();
152         }
153
154         Collections.reverse(path);
155
156         return path;
157     }
158
159     /**
160      * Returns the number of hops (or number of edges) of the path.
161      *
162      * @return .
163      */
164     public int getHopCount()
165     {
166         return this.nHops;
167     }
168
169     /**
170      * Returns the edge reaching the target vertex of the path.
171      *
172      * @return <code>null</code> if the path is empty.
173      */
174     public E getPrevEdge()
175     {
176         return this.prevEdge;
177     }
178
179     /**
180      * Returns the previous path element.
181      *
182      * @return <code>null</code> is the path is empty.
183      */
184     public AbstractPathElement<V, E> getPrevPathElement()
185     {
186         return this.prevPathElement;
187     }
188
189     /**
190      * Returns the target vertex of the path.
191      *
192      * @return .
193      */
194     public V getVertex()
195     {
196         return this.vertex;
197     }
198 }
199
Popular Tags