KickJava   Java API By Example, From Geeks To Geeks.

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


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  * BellmanFordPathElement.java
27  * -------------------------
28  * (C) Copyright 2006-2006, by France Telecom and Contributors.
29  *
30  * Original Author: Guillaume Boulmier and Contributors.
31  * Contributor(s): John V. Sichi
32  *
33  * $Id: BellmanFordPathElement.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 org.jgrapht.*;
44
45
46 /**
47  * Helper class for {@link BellmanFordShortestPath}; not intended for general
48  * use.
49  */
50 final class BellmanFordPathElement<V, E>
51     extends AbstractPathElement<V, E>
52 {
53
54     //~ Static fields/initializers --------------------------------------------
55
56     private static final double epsilon = 0.000000001;
57
58     //~ Instance fields -------------------------------------------------------
59
60     private double cost = 0;
61
62     //~ Constructors ----------------------------------------------------------
63
64     /**
65      * Creates a path element by concatenation of an edge to a path element.
66      *
67      * @param pathElement
68      * @param edge edge reaching the end vertex of the path element created.
69      * @param cost total cost of the created path element.
70      */
71     protected BellmanFordPathElement(
72         Graph<V, E> graph,
73         BellmanFordPathElement<V, E> pathElement,
74         E edge,
75         double cost)
76     {
77         super(graph, pathElement, edge);
78
79         this.cost = cost;
80     }
81
82     /**
83      * Copy constructor.
84      *
85      * @param original source to copy from
86      */
87     BellmanFordPathElement(BellmanFordPathElement<V, E> original)
88     {
89         super(original);
90         this.cost = original.cost;
91     }
92
93     /**
94      * Creates an empty path element.
95      *
96      * @param vertex end vertex of the path element.
97      */
98     protected BellmanFordPathElement(V vertex)
99     {
100         super(vertex);
101
102         this.cost = 0;
103     }
104
105     //~ Methods ---------------------------------------------------------------
106
107     /**
108      * Returns the total cost of the path element.
109      *
110      * @return .
111      */
112     public double getCost()
113     {
114         return this.cost;
115     }
116
117     /**
118      * Returns <code>true</code> if the path has been improved, <code>
119      * false</code> otherwise. We use an "epsilon" precision to check whether
120      * the cost has been improved (because of many roundings, a formula equal to
121      * 0 could unfortunately be evaluated to 10^-14).
122      *
123      * @param candidatePrevPathElement
124      * @param candidateEdge
125      * @param candidateCost
126      *
127      * @return .
128      */
129     protected boolean improve(
130         BellmanFordPathElement<V, E> candidatePrevPathElement,
131         E candidateEdge,
132         double candidateCost)
133     {
134         // to avoid improvement only due to rounding errors.
135 if (candidateCost < (getCost() - epsilon)) {
136             this.prevPathElement = candidatePrevPathElement;
137             this.prevEdge = candidateEdge;
138             this.cost = candidateCost;
139             this.nHops = candidatePrevPathElement.getHopCount() + 1;
140
141             return true;
142         } else {
143             return false;
144         }
145     }
146 }
147
Popular Tags