KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > experimental > GraphSquare


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  * GraphSquare.java
27  * ----------------------
28  * (C) Copyright 2004-2006, by Michael Behrisch and Contributors.
29  *
30  * Original Author: Michael Behrisch
31  * Contributor(s): -
32  *
33  * $Id: GraphSquare.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 14-Sep-2004 : Initial revision (MB);
38  *
39  */
40 package org.jgrapht.experimental;
41
42 import java.util.*;
43
44 import org.jgrapht.*;
45 import org.jgrapht.event.*;
46 import org.jgrapht.graph.*;
47
48
49 /**
50  * DOCUMENT ME!
51  *
52  * @author Michael Behrisch
53  * @since Sep 14, 2004
54  */
55 public class GraphSquare<V, E>
56     extends AbstractBaseGraph<V, E>
57 {
58
59     //~ Static fields/initializers --------------------------------------------
60
61     private static final long serialVersionUID = -2642034600395594304L;
62     private static final String JavaDoc UNMODIFIABLE = "this graph is unmodifiable";
63
64     //~ Constructors ----------------------------------------------------------
65
66     /**
67      * Constructor for GraphSquare.
68      *
69      * @param g the graph of which a square is to be created.
70      * @param createLoops
71      */
72     public GraphSquare(final Graph<V, E> g, final boolean createLoops)
73     {
74         super(g.getEdgeFactory(), false, createLoops);
75         Graphs.addAllVertices(this, g.vertexSet());
76         addSquareEdges(g, createLoops);
77
78         if (g instanceof ListenableGraph) {
79             ((ListenableGraph<V, E>) g).addGraphListener(
80                 new GraphListener<V, E>() {
81                     public void edgeAdded(GraphEdgeChangeEvent<V, E> e)
82                     {
83                         E edge = e.getEdge();
84                         addEdgesStartingAt(
85                             g,
86                             g.getEdgeSource(edge),
87                             g.getEdgeTarget(edge),
88                             createLoops);
89                         addEdgesStartingAt(
90                             g,
91                             g.getEdgeTarget(edge),
92                             g.getEdgeSource(edge),
93                             createLoops);
94                     }
95
96                     public void edgeRemoved(GraphEdgeChangeEvent<V, E> e)
97                     { // this is not a very performant implementation
98 GraphSquare.super.removeAllEdges(edgeSet());
99                         addSquareEdges(g, createLoops);
100                     }
101
102                     public void vertexAdded(GraphVertexChangeEvent<V> e)
103                     {
104                     }
105
106                     public void vertexRemoved(GraphVertexChangeEvent<V> e)
107                     {
108                     }
109                 });
110         }
111     }
112
113     //~ Methods ---------------------------------------------------------------
114
115     /**
116      * @see Graph#addEdge(Object, Object)
117      */
118     public E addEdge(V sourceVertex, V targetVertex)
119     {
120         throw new UnsupportedOperationException JavaDoc(UNMODIFIABLE);
121     }
122
123     /**
124      * @see Graph#addEdge(Object, Object, E)
125      */
126     public boolean addEdge(V sourceVertex, V targetVertex, E e)
127     {
128         throw new UnsupportedOperationException JavaDoc(UNMODIFIABLE);
129     }
130
131     /**
132      * @see Graph#addVertex(Object)
133      */
134     public boolean addVertex(V v)
135     {
136         throw new UnsupportedOperationException JavaDoc(UNMODIFIABLE);
137     }
138
139     /**
140      * @see Graph#removeAllEdges(Collection)
141      */
142     public boolean removeAllEdges(Collection<? extends E> edges)
143     {
144         throw new UnsupportedOperationException JavaDoc(UNMODIFIABLE);
145     }
146
147     /**
148      * @see Graph#removeAllEdges(V, V)
149      */
150     public Set<E> removeAllEdges(V sourceVertex, V targetVertex)
151     {
152         throw new UnsupportedOperationException JavaDoc(UNMODIFIABLE);
153     }
154
155     /**
156      * @see Graph#removeAllVertices(Collection)
157      */
158     public boolean removeAllVertices(Collection<? extends V> vertices)
159     {
160         throw new UnsupportedOperationException JavaDoc(UNMODIFIABLE);
161     }
162
163     /**
164      * @see Graph#removeEdge(E)
165      */
166     public boolean removeEdge(E e)
167     {
168         throw new UnsupportedOperationException JavaDoc(UNMODIFIABLE);
169     }
170
171     /**
172      * @see Graph#removeEdge(V, V)
173      */
174     public E removeEdge(V sourceVertex, V targetVertex)
175     {
176         throw new UnsupportedOperationException JavaDoc(UNMODIFIABLE);
177     }
178
179     /**
180      * @see Graph#removeVertex(V)
181      */
182     public boolean removeVertex(V v)
183     {
184         throw new UnsupportedOperationException JavaDoc(UNMODIFIABLE);
185     }
186
187     private void addEdgesStartingAt(
188         final Graph<V, E> g,
189         final V v,
190         final V u,
191         boolean createLoops)
192     {
193         if (!g.containsEdge(v, u)) {
194             return;
195         }
196
197         final List<V> adjVertices = Graphs.neighborListOf(g, u);
198
199         for (int i = 0; i < adjVertices.size(); i++) {
200             final V w = adjVertices.get(i);
201
202             if (g.containsEdge(u, w) && ((v != w) || createLoops)) {
203                 super.addEdge(v, w);
204             }
205         }
206     }
207
208     private void addSquareEdges(Graph<V, E> g, boolean createLoops)
209     {
210         for (V v : g.vertexSet()) {
211             List<V> adjVertices = Graphs.neighborListOf(g, v);
212
213             for (int i = 0; i < adjVertices.size(); i++) {
214                 addEdgesStartingAt(g, v, adjVertices.get(i), createLoops);
215             }
216         }
217     }
218 }
219
Popular Tags