1
2
3
4 package edu.uci.ics.jung.samples;
5
6 import java.awt.BasicStroke;
7 import java.awt.BorderLayout;
8 import java.awt.Color;
9 import java.awt.Component;
10 import java.awt.Graphics;
11 import java.awt.Paint;
12 import java.awt.Stroke;
13 import java.awt.event.ActionEvent;
14 import java.awt.event.ActionListener;
15 import java.awt.geom.Point2D;
16 import java.util.HashSet;
17 import java.util.Set;
18 import java.util.TreeSet;
19
20 import javax.swing.BorderFactory;
21 import javax.swing.BoxLayout;
22 import javax.swing.JComboBox;
23 import javax.swing.JFrame;
24 import javax.swing.JLabel;
25 import javax.swing.JPanel;
26 import javax.swing.SwingConstants;
27
28 import org.apache.commons.collections15.Factory;
29 import org.apache.commons.collections15.Transformer;
30
31 import edu.uci.ics.jung.algorithms.generators.random.EppsteinPowerLawGenerator;
32 import edu.uci.ics.jung.algorithms.layout.FRLayout;
33 import edu.uci.ics.jung.algorithms.layout.Layout;
34 import edu.uci.ics.jung.algorithms.shortestpath.BFSDistanceLabeler;
35 import edu.uci.ics.jung.graph.Graph;
36 import edu.uci.ics.jung.graph.SparseMultigraph;
37 import edu.uci.ics.jung.graph.util.Pair;
38 import edu.uci.ics.jung.visualization.Layer;
39 import edu.uci.ics.jung.visualization.VisualizationViewer;
40 import edu.uci.ics.jung.visualization.control.DefaultModalGraphMouse;
41 import edu.uci.ics.jung.visualization.decorators.ToStringLabeller;
42 import edu.uci.ics.jung.visualization.renderers.Renderer;
43
44
45
46
47
48
49
50 public class ShortestPathDemo extends JPanel {
51
52
53
54
55 private static final long serialVersionUID = 7526217664458188502L;
56
57
58
59
60 private String mFrom;
61
62
63
64
65 private String mTo;
66 private Graph<String,Number> mGraph;
67 private Set<String> mPred;
68
69 public ShortestPathDemo() {
70
71 this.mGraph = getGraph();
72 setBackground(Color.WHITE);
73
74 final Layout<String,Number> layout = new FRLayout<String,Number>(mGraph);
75 final VisualizationViewer<String,Number> vv = new VisualizationViewer<String,Number>(layout);
76 vv.setBackground(Color.WHITE);
77
78 vv.getRenderContext().setVertexDrawPaintTransformer(new MyVertexDrawPaintFunction<String>());
79 vv.getRenderContext().setVertexFillPaintTransformer(new MyVertexFillPaintFunction<String>());
80 vv.getRenderContext().setEdgeDrawPaintTransformer(new MyEdgePaintFunction());
81 vv.getRenderContext().setEdgeStrokeTransformer(new MyEdgeStrokeFunction());
82 vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<String>());
83 vv.setGraphMouse(new DefaultModalGraphMouse<String, Number>());
84 vv.addPostRenderPaintable(new VisualizationViewer.Paintable(){
85
86 public boolean useTransform() {
87 return true;
88 }
89 public void paint(Graphics g) {
90 if(mPred == null) return;
91
92
93 for (Number e : layout.getGraph().getEdges()) {
94
95 if(isBlessed(e)) {
96 String v1 = mGraph.getEndpoints(e).getFirst();
97 String v2 = mGraph.getEndpoints(e).getSecond();
98 Point2D p1 = layout.transform(v1);
99 Point2D p2 = layout.transform(v2);
100 p1 = vv.getRenderContext().getMultiLayerTransformer().transform(Layer.LAYOUT, p1);
101 p2 = vv.getRenderContext().getMultiLayerTransformer().transform(Layer.LAYOUT, p2);
102 Renderer<String,Number> renderer = vv.getRenderer();
103 renderer.renderEdge(
104 vv.getRenderContext(),
105 layout,
106 e);
107 }
108 }
109 }
110 });
111
112 setLayout(new BorderLayout());
113 add(vv, BorderLayout.CENTER);
114
115 add(setUpControls(), BorderLayout.SOUTH);
116 }
117
118 boolean isBlessed( Number e ) {
119 Pair<String> endpoints = mGraph.getEndpoints(e);
120 String v1= endpoints.getFirst() ;
121 String v2= endpoints.getSecond() ;
122 return v1.equals(v2) == false && mPred.contains(v1) && mPred.contains(v2);
123 }
124
125
126
127
128 public class MyEdgePaintFunction implements Transformer<Number,Paint> {
129
130 public Paint transform(Number e) {
131 if ( mPred == null || mPred.size() == 0) return Color.BLACK;
132 if( isBlessed( e )) {
133 return new Color(0.0f, 0.0f, 1.0f, 0.5f);
134 } else {
135 return Color.LIGHT_GRAY;
136 }
137 }
138 }
139
140 public class MyEdgeStrokeFunction implements Transformer<Number,Stroke> {
141 protected final Stroke THIN = new BasicStroke(1);
142 protected final Stroke THICK = new BasicStroke(1);
143
144 public Stroke transform(Number e) {
145 if ( mPred == null || mPred.size() == 0) return THIN;
146 if (isBlessed( e ) ) {
147 return THICK;
148 } else
149 return THIN;
150 }
151
152 }
153
154
155
156
157 public class MyVertexDrawPaintFunction<V> implements Transformer<V,Paint> {
158
159 public Paint transform(V v) {
160 return Color.black;
161 }
162
163 }
164
165 public class MyVertexFillPaintFunction<V> implements Transformer<V,Paint> {
166
167 public Paint transform( V v ) {
168 if ( v == mFrom) {
169 return Color.BLUE;
170 }
171 if ( v == mTo ) {
172 return Color.BLUE;
173 }
174 if ( mPred == null ) {
175 return Color.LIGHT_GRAY;
176 } else {
177 if ( mPred.contains(v)) {
178 return Color.RED;
179 } else {
180 return Color.LIGHT_GRAY;
181 }
182 }
183 }
184
185 }
186
187
188
189
190 private JPanel setUpControls() {
191 JPanel jp = new JPanel();
192 jp.setBackground(Color.WHITE);
193 jp.setLayout(new BoxLayout(jp, BoxLayout.PAGE_AXIS));
194 jp.setBorder(BorderFactory.createLineBorder(Color.black, 3));
195 jp.add(
196 new JLabel("Select a pair of vertices for which a shortest path will be displayed"));
197 JPanel jp2 = new JPanel();
198 jp2.add(new JLabel("vertex from", SwingConstants.LEFT));
199 jp2.add(getSelectionBox(true));
200 jp2.setBackground(Color.white);
201 JPanel jp3 = new JPanel();
202 jp3.add(new JLabel("vertex to", SwingConstants.LEFT));
203 jp3.add(getSelectionBox(false));
204 jp3.setBackground(Color.white);
205 jp.add( jp2 );
206 jp.add( jp3 );
207 return jp;
208 }
209
210 private Component getSelectionBox(final boolean from) {
211
212 Set<String> s = new TreeSet<String>();
213
214 for (String v : mGraph.getVertices()) {
215 s.add(v);
216 }
217 final JComboBox choices = new JComboBox(s.toArray());
218 choices.setSelectedIndex(-1);
219 choices.setBackground(Color.WHITE);
220 choices.addActionListener(new ActionListener() {
221
222 public void actionPerformed(ActionEvent e) {
223 String v = (String)choices.getSelectedItem();
224
225 if (from) {
226 mFrom = v;
227 } else {
228 mTo = v;
229 }
230 drawShortest();
231 repaint();
232 }
233 });
234 return choices;
235 }
236
237
238
239
240 protected void drawShortest() {
241 if (mFrom == null || mTo == null) {
242 return;
243 }
244 BFSDistanceLabeler<String,Number> bdl = new BFSDistanceLabeler<String,Number>();
245 bdl.labelDistances(mGraph, mFrom);
246 mPred = new HashSet<String>();
247
248
249 String v = mTo;
250 Set<String> prd = bdl.getPredecessors(v);
251 mPred.add( mTo );
252 while( prd != null && prd.size() > 0) {
253 v = prd.iterator().next();
254 mPred.add( v );
255 if ( v == mFrom ) return;
256 prd = bdl.getPredecessors(v);
257 }
258 }
259
260 public static void main(String[] s) {
261 JFrame jf = new JFrame();
262 jf.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
263 jf.getContentPane().add(new ShortestPathDemo());
264 jf.pack();
265 jf.setVisible(true);
266 }
267
268
269
270
271 Graph<String,Number> getGraph() {
272
273 Graph<String,Number> g =
274 new EppsteinPowerLawGenerator<String,Number>(
275 new GraphFactory(), new VertexFactory(), new EdgeFactory(), 26, 50, 50).create();
276 Set<String> removeMe = new HashSet<String>();
277 for (String v : g.getVertices()) {
278 if ( g.degree(v) == 0 ) {
279 removeMe.add( v );
280 }
281 }
282 for(String v : removeMe) {
283 g.removeVertex(v);
284 }
285 return g;
286 }
287
288 static class GraphFactory implements Factory<Graph<String,Number>> {
289 public Graph<String,Number> create() {
290 return new SparseMultigraph<String,Number>();
291 }
292 }
293
294 static class VertexFactory implements Factory<String> {
295 char a = 'a';
296 public String create() {
297 return Character.toString(a++);
298 }
299
300 }
301 static class EdgeFactory implements Factory<Number> {
302 int count;
303 public Number create() {
304 return count++;
305 }
306
307 }
308
309 }