KickJava   Java API By Example, From Geeks To Geeks.

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


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  * NeighborIndex.java
27  * --------------------------
28  * (C) Copyright 2005-2006, by Charles Fry and Contributors.
29  *
30  * Original Author: Charles Fry
31  *
32  * $Id: NeighborIndex.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.event.*;
45 import org.jgrapht.util.*;
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>Edge direction is ignored when evaluating neighbors; to take edge
55  * direction into account when indexing neighbors, use {@link
56  * DirectedNeighborIndex}.
57  *
58  * <p>A vertex's neighbors are cached the first time they are asked for (i.e.
59  * the index is built on demand). The index will only be updated automatically
60  * if it is added to the associated graph as a listener. If it is added as a
61  * listener to a graph other than the one it indexes, results are undefined.</p>
62  *
63  * @author Charles Fry
64  * @since Dec 13, 2005
65  */
66 public class NeighborIndex<V, E>
67     implements GraphListener<V, E>
68 {
69
70     //~ Instance fields -------------------------------------------------------
71
72     Map<V, Neighbors<V, E>> neighborMap = new HashMap<V, Neighbors<V, E>>();
73     private Graph<V, E> graph;
74
75     //~ Constructors ----------------------------------------------------------
76
77     /**
78      * Creates a neighbor index for the specified undirected graph.
79      *
80      * @param g the graph for which a neighbor index is to be created.
81      */
82     public NeighborIndex(Graph<V, E> g)
83     {
84         // no need to distinguish directedgraphs as we don't do traversals
85 graph = g;
86     }
87
88     //~ Methods ---------------------------------------------------------------
89
90     /**
91      * Returns the set of vertices which are adjacent to a specified vertex. The
92      * returned set is backed by the index, and will be updated when the graph
93      * changes as long as the index has been added as a listener to the graph.
94      *
95      * @param v the vertex whose neighbors are desired
96      *
97      * @return all unique neighbors of the specified vertex
98      */
99     public Set<V> neighborsOf(V v)
100     {
101         return getNeighbors(v).getNeighbors();
102     }
103
104     /**
105      * Returns a list of vertices which are adjacent to a specified vertex. If
106      * the graph is a multigraph, vertices may appear more than once in the
107      * returned list. Because a list of neighbors can not be efficiently
108      * maintained, it is reconstructed on every invocation, by duplicating
109      * entries in the neighbor set. It is thus more effecient to use {@link
110      * #neighborsOf(Object)} unless dupliate neighbors are important.
111      *
112      * @param v the vertex whose neighbors are desired
113      *
114      * @return all neighbors of the specified vertex
115      */
116     public List<V> neighborListOf(V v)
117     {
118         return getNeighbors(v).getNeighborList();
119     }
120
121     /**
122      * @see GraphListener#edgeAdded(GraphEdgeChangeEvent)
123      */
124     public void edgeAdded(GraphEdgeChangeEvent<V, E> e)
125     {
126         E edge = e.getEdge();
127         V source = graph.getEdgeSource(edge);
128         V target = graph.getEdgeTarget(edge);
129         getNeighbors(source).addNeighbor(target);
130         getNeighbors(target).addNeighbor(source);
131     }
132
133     /**
134      * @see GraphListener#edgeRemoved(GraphEdgeChangeEvent)
135      */
136     public void edgeRemoved(GraphEdgeChangeEvent<V, E> e)
137     {
138         E edge = e.getEdge();
139         V source = graph.getEdgeSource(edge);
140         V target = graph.getEdgeTarget(edge);
141         if (neighborMap.containsKey(source)) {
142             neighborMap.get(source).removeNeighbor(target);
143         }
144         if (neighborMap.containsKey(target)) {
145             neighborMap.get(target).removeNeighbor(source);
146         }
147     }
148
149     /**
150      * @see VertexSetListener#vertexAdded(GraphVertexChangeEvent)
151      */
152     public void vertexAdded(GraphVertexChangeEvent<V> e)
153     {
154         // nothing to cache until there are edges
155 }
156
157     /**
158      * @see VertexSetListener#vertexRemoved(GraphVertexChangeEvent)
159      */
160     public void vertexRemoved(GraphVertexChangeEvent<V> e)
161     {
162         neighborMap.remove(e.getVertex());
163     }
164
165     private Neighbors<V, E> getNeighbors(V v)
166     {
167         Neighbors<V, E> neighbors = neighborMap.get(v);
168         if (neighbors == null) {
169             neighbors = new Neighbors<V, E>(v,
170                     Graphs.neighborListOf(graph, v));
171             neighborMap.put(v, neighbors);
172         }
173         return neighbors;
174     }
175
176     //~ Inner Classes ---------------------------------------------------------
177
178     /**
179      * Stores cached neighbors for a single vertex. Includes support for live
180      * neighbor sets and duplicate neighbors.
181      */
182     static class Neighbors<V, E>
183     {
184         private Map<V, ModifiableInteger> neighborCounts =
185             new LinkedHashMap<V, ModifiableInteger>();
186
187         // TODO could eventually make neighborSet modifiable, resulting
188 // in edge removals from the graph
189 private Set<V> neighborSet =
190             Collections.unmodifiableSet(
191                 neighborCounts.keySet());
192
193         public Neighbors(V v, Collection<V> neighbors)
194         {
195             // add all current neighbors
196 for (V neighbor : neighbors) {
197                 addNeighbor(neighbor);
198             }
199         }
200
201         public void addNeighbor(V v)
202         {
203             ModifiableInteger count = neighborCounts.get(v);
204             if (count == null) {
205                 count = new ModifiableInteger(1);
206                 neighborCounts.put(v, count);
207             } else {
208                 count.increment();
209             }
210         }
211
212         public void removeNeighbor(V v)
213         {
214             ModifiableInteger count = neighborCounts.get(v);
215             if (count == null) {
216                 throw new IllegalArgumentException JavaDoc(
217                     "Attempting to remove a neighbor that wasn't present");
218             }
219
220             count.decrement();
221             if (count.getValue() == 0) {
222                 neighborCounts.remove(v);
223             }
224         }
225
226         public Set<V> getNeighbors()
227         {
228             return neighborSet;
229         }
230
231         public List<V> getNeighborList()
232         {
233             List<V> neighbors = new ArrayList<V>();
234             for (
235                 Map.Entry<V, ModifiableInteger> entry
236                 : neighborCounts.entrySet()) {
237                 V v = entry.getKey();
238                 int count = entry.getValue().intValue();
239                 for (int i = 0; i < count; i++) {
240                     neighbors.add(v);
241                 }
242             }
243             return neighbors;
244         }
245     }
246 }
247
Popular Tags