KickJava   Java API By Example, From Geeks To Geeks.

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


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  * DirectedNeighborIndex.java
27  * --------------------------
28  * (C) Copyright 2005-2006, by Charles Fry and Contributors.
29  *
30  * Original Author: Charles Fry
31  *
32  * $Id: DirectedNeighborIndex.java 504 2006-07-03 02:37:26Z perfecthash $
33  *
34  * Changes
35  * -------
36  * 13-Dec-2005 : Initial revision (CF);
37  *
38  */
39 package org.jgrapht.alg;
40
41 import java.util.*;
42
43 import org.jgrapht.*;
44 import org.jgrapht.alg.NeighborIndex.*;
45 import org.jgrapht.event.*;
46
47
48 /**
49  * Maintains a cache of each vertex's neighbors. While lists of neighbors can be
50  * obtained from {@link Graphs}, they are re-calculated at each invocation by
51  * walking a vertex's incident edges, which becomes inordinately expensive when
52  * performed often.
53  *
54  * <p>A vertex's neighbors are cached the first time they are asked for (i.e.
55  * the index is built on demand). The index will only be updated automatically
56  * if it is added to the associated graph as a listener. If it is added as a
57  * listener to a graph other than the one it indexes, results are undefined.</p>
58  *
59  * @author Charles Fry
60  * @since Dec 13, 2005
61  */
62 public class DirectedNeighborIndex<V, E>
63     implements GraphListener<V, E>
64 {
65
66     //~ Instance fields -------------------------------------------------------
67
68     Map<V, Neighbors<V, E>> predecessorMap = new HashMap<V, Neighbors<V, E>>();
69     Map<V, Neighbors<V, E>> successorMap = new HashMap<V, Neighbors<V, E>>();
70     private DirectedGraph<V, E> graph;
71
72     //~ Constructors ----------------------------------------------------------
73
74     /**
75      * Creates a neighbor index for the specified directed graph.
76      *
77      * @param g the graph for which a neighbor index is to be created.
78      */
79     public DirectedNeighborIndex(DirectedGraph<V, E> g)
80     {
81         graph = g;
82     }
83
84     //~ Methods ---------------------------------------------------------------
85
86     /**
87      * Returns the set of vertices which are the predecessors of a specified
88      * vertex. The returned set is backed by the index, and will be updated when
89      * the graph changes as long as the index has been added as a listener to
90      * the graph.
91      *
92      * @param v the vertex whose predecessors are desired
93      *
94      * @return all unique predecessors of the specified vertex
95      */
96     public Set<V> predecessorsOf(V v)
97     {
98         return getPredecessors(v).getNeighbors();
99     }
100
101     /**
102      * Returns the set of vertices which are the predecessors of a specified
103      * vertex. If the graph is a multigraph, vertices may appear more than once
104      * in the returned list. Because a list of predecessors can not be
105      * efficiently maintained, it is reconstructed on every invocation by
106      * duplicating entries in the neighbor set. It is thus more efficient to use
107      * {@link #predecessorsOf(Object)} unless duplicate neighbors are required.
108      *
109      * @param v the vertex whose predecessors are desired
110      *
111      * @return all predecessors of the specified vertex
112      */
113     public List<V> predecessorListOf(V v)
114     {
115         return getPredecessors(v).getNeighborList();
116     }
117
118     /**
119      * Returns the set of vertices which are the successors of a specified
120      * vertex. The returned set is backed by the index, and will be updated when
121      * the graph changes as long as the index has been added as a listener to
122      * the graph.
123      *
124      * @param v the vertex whose successors are desired
125      *
126      * @return all unique successors of the specified vertex
127      */
128     public Set<V> successorsOf(V v)
129     {
130         return getSuccessors(v).getNeighbors();
131     }
132
133     /**
134      * Returns the set of vertices which are the successors of a specified
135      * vertex. If the graph is a multigraph, vertices may appear more than once
136      * in the returned list. Because a list of successors can not be efficiently
137      * maintained, it is reconstructed on every invocation by duplicating
138      * entries in the neighbor set. It is thus more effecient to use {@link
139      * #successorsOf(Object)} unless dupliate neighbors are required.
140      *
141      * @param v the vertex whose successors are desired
142      *
143      * @return all successors of the specified vertex
144      */
145     public List<V> successorListOf(V v)
146     {
147         return getSuccessors(v).getNeighborList();
148     }
149
150     /**
151      * @see GraphListener#edgeAdded(GraphEdgeChangeEvent)
152      */
153     public void edgeAdded(GraphEdgeChangeEvent<V, E> e)
154     {
155         E edge = e.getEdge();
156         V source = graph.getEdgeSource(edge);
157         V target = graph.getEdgeTarget(edge);
158         getSuccessors(source).addNeighbor(target);
159         getPredecessors(target).addNeighbor(source);
160     }
161
162     /**
163      * @see GraphListener#edgeRemoved(GraphEdgeChangeEvent)
164      */
165     public void edgeRemoved(GraphEdgeChangeEvent<V, E> e)
166     {
167         E edge = e.getEdge();
168         V source = graph.getEdgeSource(edge);
169         V target = graph.getEdgeTarget(edge);
170         if (successorMap.containsKey(source)) {
171             successorMap.get(source).removeNeighbor(target);
172         }
173         if (predecessorMap.containsKey(target)) {
174             predecessorMap.get(target).removeNeighbor(source);
175         }
176     }
177
178     /**
179      * @see VertexSetListener#vertexAdded(GraphVertexChangeEvent)
180      */
181     public void vertexAdded(GraphVertexChangeEvent<V> e)
182     {
183         // nothing to cache until there are edges
184 }
185
186     /**
187      * @see VertexSetListener#vertexRemoved(GraphVertexChangeEvent)
188      */
189     public void vertexRemoved(GraphVertexChangeEvent<V> e)
190     {
191         predecessorMap.remove(e.getVertex());
192         successorMap.remove(e.getVertex());
193     }
194
195     private Neighbors<V, E> getPredecessors(V v)
196     {
197         Neighbors<V, E> neighbors = predecessorMap.get(v);
198         if (neighbors == null) {
199             neighbors =
200                 new Neighbors<V, E>(v,
201                     Graphs.predecessorListOf(graph, v));
202             predecessorMap.put(v, neighbors);
203         }
204         return neighbors;
205     }
206
207     private Neighbors<V, E> getSuccessors(V v)
208     {
209         Neighbors<V, E> neighbors = successorMap.get(v);
210         if (neighbors == null) {
211             neighbors =
212                 new Neighbors<V, E>(v,
213                     Graphs.successorListOf(graph, v));
214             successorMap.put(v, neighbors);
215         }
216         return neighbors;
217     }
218 }
219
Popular Tags