001: /*
002: * Copyright 2006-2007 Pentaho Corporation. All rights reserved.
003: * This software was developed by Pentaho Corporation and is provided under the terms
004: * of the Mozilla Public License, Version 1.1, or any later version. You may not use
005: * this file except in compliance with the license. If you need a copy of the license,
006: * please go to http://www.mozilla.org/MPL/MPL-1.1.txt.
007: *
008: * Software distributed under the Mozilla Public License is distributed on an "AS IS"
009: * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. Please refer to
010: * the license for the specific language governing your rights and limitations.
011: *
012: * Additional Contributor(s): Martin Schmid gridvision engineering GmbH
013: */
014: package org.pentaho.reportdesigner.lib.common.graph;
015:
016: import org.jetbrains.annotations.NotNull;
017: import org.jetbrains.annotations.Nullable;
018:
019: import java.util.HashMap;
020: import java.util.HashSet;
021: import java.util.Iterator;
022: import java.util.LinkedList;
023: import java.util.List;
024:
025: /**
026: * User: Martin
027: * Date: 05.03.2006
028: * Time: 14:12:10
029: */
030: public class ShortestPath {
031: @SuppressWarnings({"UseOfSystemOutOrSystemErr"})
032: public static void main(@NotNull
033: String[] args) {
034: //Vertex a = new DummyVertex("a");
035: //Vertex b = new DummyVertex("b");
036: //Vertex c = new DummyVertex("c");
037: //Vertex d = new DummyVertex("d");
038: //
039: //Edge e1 = new Edge(a, b, 4);
040: //Edge e2 = new Edge(a, c, 2);
041: //Edge e3 = new Edge(c, a, 2);
042: //Edge e4 = new Edge(b, c, 3);
043: //Edge e5 = new Edge(c, b, 1);
044: //Edge e6 = new Edge(b, d, 1);
045: //Edge e7 = new Edge(c, d, 5);
046: //
047: //Graph graph = new Graph();
048: //graph.addVertex(a);
049: //graph.addVertex(b);
050: //graph.addVertex(c);
051: //graph.addVertex(d);
052: //
053: //graph.addEdge(e1);
054: //graph.addEdge(e2);
055: //graph.addEdge(e3);
056: //graph.addEdge(e4);
057: //graph.addEdge(e5);
058: //graph.addEdge(e6);
059: //graph.addEdge(e7);
060:
061: Vertex a = new DummyVertex("a");//NON-NLS
062: Vertex b = new DummyVertex("b");//NON-NLS
063: Vertex c = new DummyVertex("c");//NON-NLS
064: Vertex d = new DummyVertex("d");//NON-NLS
065:
066: Edge e1 = new Edge(a, b, 2);
067: Edge e2 = new Edge(a, c, 1);
068: Edge e3 = new Edge(b, d, 1);
069: Edge e4 = new Edge(c, d, 1);
070:
071: Graph graph = new Graph();
072: graph.addVertex(a);
073: graph.addVertex(b);
074: graph.addVertex(c);
075: graph.addVertex(d);
076:
077: graph.addEdge(e1);
078: graph.addEdge(e2);
079: graph.addEdge(e3);
080: graph.addEdge(e4);
081:
082: ShortestPath shortestPath = new ShortestPath(graph, a);
083: HashMap<Vertex, Vertex> pre = shortestPath.getPre();
084: System.out.println("pre = " + pre);//NON-NLS
085:
086: System.out.println("shortestPath.getPath() = "
087: + shortestPath.getPath(d));//NON-NLS
088: System.out.println("shortestPath.getPath() = "
089: + shortestPath.getPath(c));//NON-NLS
090: System.out.println("shortestPath.getPath() = "
091: + shortestPath.getPath(b));//NON-NLS
092: System.out.println("shortestPath.getPath() = "
093: + shortestPath.getPath(a));//NON-NLS
094: }
095:
096: @NotNull
097: private Graph graph;
098: @NotNull
099: private Vertex start;
100:
101: @NotNull
102: private HashMap<Vertex, Integer> d;//cost to reach each vertex
103: @NotNull
104: private HashMap<Vertex, Vertex> pre;//predecessor dor each vertex
105:
106: @NotNull
107: private HashSet<Vertex> s;//settled
108: @NotNull
109: private HashSet<Vertex> q;//unsettled
110:
111: public ShortestPath(@NotNull
112: Graph graph, @NotNull
113: Vertex start) {
114: this .graph = graph;
115: this .start = start;
116:
117: d = new HashMap<Vertex, Integer>();
118: pre = new HashMap<Vertex, Vertex>();
119:
120: s = new HashSet<Vertex>();
121:
122: q = new HashSet<Vertex>();
123: Iterator<Vertex> vertexIterator = graph.getVertexIterator();
124: while (vertexIterator.hasNext()) {
125: Vertex vertex = vertexIterator.next();
126: q.add(vertex);
127: d.put(vertex, Integer.valueOf(999999));
128: }
129:
130: s.add(start);
131: d.put(start, Integer.valueOf(0));
132:
133: while (!q.isEmpty()) {
134: Vertex u = extractMinimum(q);
135: if (u != null) {
136: s.add(u);
137: relaxNeigbours(u);
138: }
139: }
140: }
141:
142: private void relaxNeigbours(@NotNull
143: Vertex u) {
144: Iterator<Edge> outIncidentEdges = graph.getOutIncidentEdges(u);
145: while (outIncidentEdges.hasNext()) {
146: Edge edge = outIncidentEdges.next();
147: Vertex v = edge.getToVertex();
148: if (!s.contains(v)) {
149: if (d.get(v).intValue() > d.get(u).intValue()
150: + edge.getCost()) {
151: d.put(v, Integer.valueOf(d.get(u).intValue()
152: + edge.getCost()));
153: pre.put(v, u);
154: q.add(v);
155: }
156: }
157: }
158: }
159:
160: @Nullable
161: private Vertex extractMinimum(@NotNull
162: HashSet<Vertex> q) {
163: Vertex smallest = null;
164: int c = 0;
165: for (Vertex vertex : q) {
166: if (smallest == null) {
167: smallest = vertex;
168: c = d.get(vertex).intValue();
169: } else {
170: int c2 = d.get(vertex).intValue();
171:
172: if (c2 < c) {
173: smallest = vertex;
174: c = c2;
175: }
176: }
177: }
178: q.remove(smallest);
179: return smallest;
180: }
181:
182: @NotNull
183: public HashMap<Vertex, Vertex> getPre() {
184: return pre;
185: }
186:
187: @Nullable
188: public List<Vertex> getPath(@NotNull
189: Vertex endVertex) {
190: LinkedList<Vertex> path = new LinkedList<Vertex>();
191: Vertex last = endVertex;
192: path.addLast(last);
193: //noinspection ObjectEquality
194: while (last != start) {
195: last = pre.get(last);
196: if (last == null) {
197: return null;//no path from start-->endVertex
198: }
199: path.addLast(last);
200: }
201: return path;
202: }
203:
204: }
|