Java > Open Source Codes > websphinx > workbench > GraphLayout


1 /*
2  * WebSphinx web-crawling toolkit
3  *
4  * Copyright (c) 1998-2002 Carnegie Mellon University. All rights
5  * reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * 1. Redistributions of source code must retain the above copyright
12  * notice, this list of conditions and the following disclaimer.
13  *
14  * 2. Redistributions in binary form must reproduce the above copyright
15  * notice, this list of conditions and the following disclaimer in
16  * the documentation and/or other materials provided with the
17  * distribution.
18  *
19  * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
20  * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
21  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
23  * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30  *
31  */
32
33 package websphinx.workbench;
34
35 // Daniel Tunkelang's graph-drawing packages
36 import graph.*;
37 import gd.*;
38
39 import rcm.awt.*;
40
41 import java.util.*;
42 import java.awt.*;
43 import java.awt.image.ImageObserver ;
44
45 public class GraphLayout extends Canvas implements Runnable , ImageObserver {
46
47     Graph graph; // graph to display
48
49     double restLength = 50; // default rest length of an edge
50 double springConstant = 100; // attraction between connected nodes
51 double nodeCharge = 10000; // repulsion between any pair of nodes
52
53     GDAlgorithm algorithm; // algorithm used for automatic graph layout
54
55     boolean running = false; // is repaint thread running?
56 boolean automaticLayout = true; // is automatic graph layout enabled?
57 double threshold = 100; // if an iteration shows less "improvement" than
58 // this threshold, stop iterating
59 boolean quiescent = true; // is the graph stable?
60 boolean dirty = true; // do we need to repaint?
61
62     int interval = 100; // milliseconds between repaints
63 int iterations = 3; // number of layout iterations per repaint
64
65     Color nodeColor = Color.pink; // default background color for a node
66 // (node label text is in Foreground color)
67 Color edgeColor = Color.black; // default color of an edge line
68 Color tipColor = Color.yellow; // background color of a popup tip
69
70     //RenderedNode selectedNode = null; // currently selected node, or null
71 //RenderedEdge selectedEdge = null; // currently selected edge, or null
72 // invariant: selectedNode==null || selectedEdge == null
73
74     Object tipObject = null; // node or edge currently under mouse, or null
75 MultiLineString tip = null; // tip string displayed for tipObject, or null
76 int tipX, tipY, tipWidth, tipHeight; // bounding box of tip
77
78     GraphLayoutControlPanel controlPanel;
79
80     /**
81      * Make a GraphLayout.
82      */
83     public GraphLayout () {
84         graph = new Graph ();
85         resetAlgorithm ();
86         start ();
87     }
88     
89     /**
90      * Erase the graph.
91      */
92     public synchronized void clear () {
93         graph = new Graph ();
94         changedGraph ();
95     }
96
97     /**
98      * Get the graph.
99      */
100     public synchronized Graph getGraph () {
101         return graph;
102     }
103
104     /**
105      * Set the graph.
106      */
107     public synchronized void setGraph (Graph graph) {
108         this.graph = graph;
109         //selectedNode = null;
110 //selectedEdge = null;
111 tipObject = null;
112         tip = null;
113         changedGraph ();
114     }
115
116     /**
117      * Get the graph-drawing algorithm in use.
118      */
119     public synchronized GDAlgorithm getAlgorithm () {
120         return algorithm;
121     }
122
123     /**
124      * Set the graph-drawing algorithm.
125      */
126     public synchronized void setAlgorithm (GDAlgorithm algorithm) {
127         this.algorithm = algorithm;
128         changedGraph ();
129     }
130
131     synchronized void resetAlgorithm () {
132         algorithm = new AllPairsAlgorithm (springConstant, nodeCharge);
133         changedGraph ();
134     }
135
136     /**
137      * Get the default rest length for new edges.
138      */
139     public synchronized double getRestLength () {
140         return restLength;
141     }
142
143     /**
144      * Set the default rest length for new edges.
145      */
146     public synchronized void setRestLength (double restLength) {
147         this.restLength = restLength;
148         changedGraph ();
149     }
150
151     /**
152      * Get the spring constant.
153      */
154     public synchronized double getSpringConstant () {
155         return springConstant;
156     }
157
158     /**
159      * Set the spring constant.
160      */
161     public synchronized void setSpringConstant (double springConstant) {
162         this.springConstant = springConstant;
163         resetAlgorithm ();
164     }
165
166     /**
167      * Get the node charge.
168      */
169     public synchronized double getNodeCharge () {
170         return nodeCharge;
171     }
172
173     /**
174      * Set the node charge.
175      */
176     public synchronized void setNodeCharge (double nodeCharge) {
177         this.nodeCharge = nodeCharge;
178         resetAlgorithm ();
179     }
180
181     /**
182      * Get the refresh interval (measured in seconds).
183      */
184     public synchronized int getInterval () {
185         return interval;
186     }
187
188     /**
189      * Set the refresh interval (in seconds).
190      */
191     public synchronized void setInterval (int interval) {
192         this.interval = interval;
193     }
194
195     /**
196      * Get the layout algorithm iterations per refresh.
197      */
198     public synchronized int getIterations () {
199         return iterations;
200     }
201
202     /**
203      * Set the layout algorithm iterations per refresh.
204      */
205     public synchronized void setIterations (int iterations) {
206         this.iterations = iterations;
207     }
208
209     /**
210      * Test whether the graph is laid out automatically.
211      */
212     public synchronized boolean getAutomaticLayout () {
213         return automaticLayout;
214     }
215
216     /**
217      * Set whether the graph is laid out automatically.
218      */
219     public synchronized void setAutomaticLayout (boolean f) {
220         automaticLayout = f;
221         quiescent = !automaticLayout;
222         if (controlPanel != null)
223             controlPanel.automatic.setState (automaticLayout);
224     }
225
226     /**
227      * Test whether the graph is quiescent (not changing in the background).
228      */
229     public synchronized boolean getQuiescent () {
230         return quiescent;
231     }
232
233     /**
234      * Test whether the graph layout thread is running in the background
235      */
236     public synchronized boolean getRunning () {
237         return running;
238     }
239
240     /**
241      * Get the threshold.
242      */
243     public synchronized double getThreshold () {
244         return threshold;
245     }
246
247     /**
248      * Set the threshold.
249      */
250     public synchronized void setThreshold (double threshold) {
251         this.threshold = threshold;
252         changedGraph ();
253     }
254
255     /**
256      * Get the node background color.
257      */
258     public synchronized Color getNodeColor () {
259         return nodeColor;
260     }
261
262     /**
263      * Set the node background color.
264      */
265     public synchronized void setNodeColor (Color nodeColor) {
266         this.nodeColor = nodeColor;
267     }
268
269     /**
270      * Get the edge color.
271      */
272     public synchronized Color getEdgeColor () {
273         return edgeColor;
274     }
275
276     /**
277      * Set the edge color.
278      */
279     public synchronized void setEdgeColor (Color edgeColor) {
280         this.edgeColor = edgeColor;
281     }
282
283     /**
284      * Get the popup tip color.
285      */
286     public synchronized Color getTipColor () {
287         return tipColor;
288     }
289
290     /**
291      * Set the popup tip color.
292      */
293     public synchronized void setTipColor (Color tipColor) {
294         this.tipColor = tipColor;
295     }
296
297     /**
298      * Get node currently under the mouse pointer, or null if no node is under the mouse.
299      */
300     public synchronized RenderedNode getSelectedNode () {
301         return tipObject instanceof RenderedNode
302             ? (RenderedNode)tipObject
303             : null;
304     }
305
306     /**
307      * Get edge currently under the mouse pointer, or null if no edge is under the mouse.
308      */
309     public synchronized RenderedEdge getSelectedEdge () {
310         return tipObject instanceof RenderedEdge
311             ? (RenderedEdge)tipObject
312             : null;
313     }
314
315     /**
316      * Add a node.
317      */
318     public synchronized void addNode (RenderedNode node) {
319         graph.addNode (node);
320         graph.placeNode (node, node.x, node.y);
321         changedGraph ();
322     }
323
324     /**
325      * Add an edge.
326      */
327     public synchronized void addEdge (RenderedEdge edge) {
328         if (edge.restLength == 0)
329             edge.restLength = restLength;
330         graph.addEdge (edge);
331         changedGraph ();
332     }
333
334     /**
335      * Remove a node.
336      */
337     public synchronized void removeNode (RenderedNode node) {
338         graph.removeNode (node);
339         changedGraph ();
340     }
341
342     /**
343      * Remove an edge.
344      */
345     public synchronized void removeEdge (RenderedEdge edge) {
346         graph.removeEdge (edge);
347         changedGraph ();
348     }
349
350     /**
351      * Handle a loaded image.
352      */
353     public synchronized boolean imageUpdate(Image img,
354                                   int infoflags,
355                                   int x,
356                                   int y,
357                                   int width,
358                                   int height) {
359         if ((infoflags & (ImageObserver.WIDTH | ImageObserver.HEIGHT)) != 0) {
360             for (int i=0; i<graph.sizeNodes; ++i) {
361                 RenderedNode n = (RenderedNode)graph.nodes[i];
362                 if (n.icon == img) {
363                     n.width = width;
364                     n.height = height;
365                     changedGraph ();
366                 }
367             }
368         }
369         return super.imageUpdate (img, infoflags, x, y, width, height);
370     }
371
372     /*
373      * Background thread
374      *
375      */
376
377     Thread iterator;
378
379     /**
380      * Start automatic graph layout (in the background).
381      */
382     public synchronized void start () {
383         if (!running) {
384             running = true;
385             iterator = new Thread (this, "GraphListener");
386             iterator.setDaemon (true);
387             iterator.setPriority (Thread.MIN_PRIORITY);
388             iterator.start ();
389         }
390     }
391
392     /**
393      * Stop automatic graph layout.
394      */
395     public synchronized void stop () {
396         if (running) {
397             running = false;
398             notify ();
399             iterator = null;
400         }
401     }
402
403     /**
404      * The body of the background thread. Clients should not call this
405      * method.
406      */
407     final static int MULTIPLIER = 2;
408     public synchronized void run () {
409         quiescent = false;
410         while (running) {
411             long start = System.currentTimeMillis ();
412
413             if (automaticLayout && !quiescent) {
414                 for (int i=0; i < iterations; ++i) {
415                     double improvement = algorithm.improveGraph (graph);
416                     dirty = true;
417                     if (improvement <= threshold * graph.sizeNodes) {
418                         quiescent = true;
419                         break;
420                     }
421                 }
422             }
423
424             if (dirty)
425                 super.repaint ();
426
427             /*int r = (int) (System.currentTimeMillis() - start);
428             int w = Math.max (interval, r * MULTIPLIER);
429             System.out.println ("ran " + r + " msec, now waiting " + w + " msec");
430             */
431
432             try {
433                 wait (interval);
434             } catch (InterruptedException e) {
435             }
436         }
437         quiescent = true;
438     }
439
440     /**
441      * Notify background thread that the graph has changed.
442      */
443     public synchronized void changedGraph () {
444         if (automaticLayout)
445             quiescent = false;
446         repaint ();
447     }
448
449     /**
450      * Notify background thread that the view has changed.
451      */
452     public synchronized void repaint () {
453         if (!running)
454             super.repaint ();
455         else
456             dirty = true;
457     }
458
459     /**
460      * Show control panel for changing graph layout parameters.
461      */
462     public void showControlPanel () {
463         if (controlPanel == null)
464             controlPanel = new GraphLayoutControlPanel (this);
465         controlPanel.show ();
466     }
467
468     protected void finalize () throws Throwable {
469         super.finalize ();
470         if (controlPanel != null) {
471             controlPanel.dispose();
472             controlPanel = null;
473         }
474     }
475
476     /*
477      * Scale coordinates from graph to screen.
478      */
479     double originX = 0.0, originY = 0.0;
480     double scaleX = 1.0, scaleY = 1.0;
481
482     private void scaleGraph () {
483         Dimension d = size ();
484         double halfScreenWidth = d.width/2.0;
485         double halfScreenHeight = d.height/2.0;
486         
487         double sX = 1.0, sY = 1.0;
488         for (int i=0; i < graph.sizeNodes; ++i) {
489             RenderedNode n = (RenderedNode)graph.nodes[i];
490             sX = Math.min(sX, (halfScreenWidth - n.width/2.0)/(Math.abs(n.x)+1));
491             sY = Math.min(sY, (halfScreenHeight - n.height/2.0)/(Math.abs(n.y)+1));
492         }
493         
494         double oX = halfScreenWidth;
495         double oY = halfScreenHeight;
496         
497         for (int i=0; i < graph.sizeNodes; ++i) {
498             RenderedNode n = (RenderedNode)graph.nodes[i];
499             n.screenX = (int)(n.x*sX + oX);
500             n.screenY = (int)(n.y*sY + oY);
501         }
502
503         // save the translation for use in placeNodeOnScreen
504 originX = oX;
505         originY = oY;
506         scaleX = sX;
507         scaleY = sY;
508     }
509
510     public synchronized void placeNodeOnScreen (RenderedNode n, int x, int y) {
511         graph.placeNode (n, (x - originX)/scaleX, (y - originY)/scaleY);
512         n.screenX = x;
513         n.screenY = y;
514     }
515
516     public synchronized void placeNodeOnGraph (RenderedNode n, double x, double y) {
517         graph.placeNode (n, x, y);
518         n.screenX = (int)(x*scaleX + originX);
519         n.screenY = (int)(y*scaleY + originY);
520     }
521
522     /*
523      * Painting methods
524      *
525      */
526
527     Image offscreen; // offscreen drawing area
528 Dimension offSize; // size of offscreen buffer
529 Graphics offg; // drawonable associated with offscreen buffer
530 FontMetrics fm; // font metrics for offscreen buffer
531
532     public void update (Graphics g) {
533         // don't clear window with background color first
534 //long before = System.currentTimeMillis ();
535 paint (g);
536         //long after = System.currentTimeMillis ();
537 //System.out.println ("repaint: " + (after - before) + " msec");
538 }
539
540     void createOffscreenArea (Dimension d) {
541         offSize = new Dimension (d.width > 0 ? d.width : 1,
542                                  d.height > 0 ? d.height : 1);
543         offscreen = createImage (offSize.width, offSize.height);
544         offg = offscreen.getGraphics ();
545         offg.setFont (getFont ());
546         fm = offg.getFontMetrics ();
547     }
548
549     public synchronized void paint (Graphics g) {
550         Dimension d = size ();
551
552         if (offscreen == null
553             || d.width != offSize.width
554             || d.height != offSize.height)
555             createOffscreenArea (d);
556
557         offg.setColor (getBackground ());
558         offg.fillRect (0, 0, d.width, d.height);
559
560         scaleGraph ();
561         
562         // paint the edges first
563 for (int i=0; i<graph.sizeEdges; ++i) {
564             RenderedEdge e = (RenderedEdge)graph.edges[i];
565             if (e == null)
566                 continue;
567             RenderedNode from = (RenderedNode)e.from;
568             RenderedNode to = (RenderedNode)e.to;
569             if (from == null || to == null)
570                 continue;
571             
572             Color c = e.color;
573             if (c == null)
574                 c = edgeColor;
575             
576             offg.setColor (c);
577             drawArrowToBox (offg, (int)from.screenX, (int)from.screenY,
578                             (int)to.screenX, (int)to.screenY,
579                             (int)(to.width/2), (int)(to.height/2),
580                             6, 3, e.thick);
581         }
582         
583         // paint the nodes on top
584 for (int i=0; i < graph.sizeNodes; ++i) {
585             RenderedNode n = (RenderedNode)graph.nodes[i];
586             if (n == null)
587                 continue;
588             
589             int width = (int)n.width;
590             int height = (int)n.height;
591             int x = (int)n.screenX - width/2;
592             int y = (int)n.screenY - height/2;
593             Color c = n.color;
594             
595             if (n.icon == null) {
596                 if (c == null)
597                     c = nodeColor;
598                 
599                 offg.setColor (c);
600                 offg.fillRect (x, y, width, height);
601                 offg.setColor (getForeground ());
602                 offg.drawRect (x, y, width-1, height-1);
603                 offg.drawString (n.name, x+5, y+2 + fm.getAscent ());
604             }
605             else {
606                 // NIY: scaling
607 if (c == null)
608                     offg.drawImage (n.icon, x, y, this);
609                 else
610                     offg.drawImage (n.icon, x, y, c, this);
611             }
612         }
613         
614         // paint the tip on top
615 if (tip != null) {
616             offg.setColor (tipColor);
617             offg.fillRect (tipX, tipY, tipWidth, tipHeight);
618             offg.setColor (Color.black);
619             offg.drawRect (tipX, tipY, tipWidth-1, tipHeight-1);
620             tip.draw (offg, tipX + 5, tipY + 2, Label.LEFT);
621         }
622         
623         // draw border
624 offg.setColor (quiescent ? getForeground () : Color.red);
625         offg.drawRect (0, 0, d.width-1, d.height-1);
626         
627         // copy to screen
628 g.drawImage (offscreen, 0, 0, null);
629
630         dirty = false;
631     }
632
633     void drawArrowToBox (Graphics g, int x1, int y1, int x2, int y2,
634                          int wHalfBox, int hHalfBox,
635                          int head_length, int head_width, boolean thick) {
636         if (thick) {
637           drawArrowToBox (g, x1, y1, x2, y2,
638                           wHalfBox, hHalfBox, head_length, head_width, false);
639           drawArrowToBox (g, x1-1, y1, x2-1, y2,
640                           wHalfBox, hHalfBox, head_length, head_width, false);
641           drawArrowToBox (g, x1, y1-1, x2, y2-1,
642                           wHalfBox, hHalfBox, head_length, head_width, false);
643           drawArrowToBox (g, x1-1, y1-1, x2-1, y2-1,
644                           wHalfBox, hHalfBox, head_length, head_width, false);
645         }
646         else {
647             double dx = x2 - x1;
648             double dy = y2 - y1;
649             double d = Math.sqrt (dx * dx + dy * dy);
650             if (d < 1.0) {
651                 d = 1.0;
652                 dx = 1;
653             }
654             dx /= d;
655             dy /= d;
656             
657             double lx = head_length * dx;
658             double ly = head_length * dy;
659             double wx = head_width * dx;
660             double wy = head_width * dy;
661
662             double cp1 = dx*hHalfBox - dy*wHalfBox;
663             double cp2 = dx*hHalfBox + dy*wHalfBox;
664             
665             if (cp1 < 0) {
666                     if (cp2 < 0) {
667                         // region I
668 x2 += wHalfBox;
669                         y2 += wHalfBox*dy/dx;
670                     }
671                     else {
672                         // region II
673 y2 -= hHalfBox;
674                         x2 -= hHalfBox*dx/dy;
675                     }
676             }
677             else {
678                     if (cp2 > 0) {
679                         // region III
680 x2 -= wHalfBox;
681                         y2 -= wHalfBox*dy/dx;
682                     }
683                     else {
684                         // region IV
685 y2 += hHalfBox;
686                         x2 += hHalfBox*dx/dy;
687                     }
688             }
689             
690             g.drawLine (x1, y1, x2, y2);
691             g.drawLine (x2, y2, (int)(x2-lx+wy+0.5), (int)(y2-ly-wx+.5));
692             g.drawLine (x2, y2, (int)(x2-lx-wy+0.5), (int)(y2-ly+wx+.5));
693         }
694     }
695
696     public synchronized FontMetrics getFontMetrics () {
697         if (fm == null) {
698             Dimension d = size ();
699             createOffscreenArea (d);
700         }
701         return fm;
702     }
703
704     // intercept font settings and transfer to offscreen buffer
705 public synchronized void setFont (Font f) {
706         super.setFont (f);
707         if (offg != null) {
708             offg.setFont (f);
709             fm = offg.getFontMetrics ();
710         }
711     }
712
713     /*
714     public Dimension preferredSize () {
715         return new Dimension (400, 400);
716     }
717     */
718     
719     /*
720      * Selecting and dragging nodes
721      *
722      */
723      
724     RenderedNode dragNode = null; // node being dragged, or null
725 int dragOffsetX, dragOffsetY;
726         // initial displacement of mouse cursor from dragged object's origin;
727 // the object remains at this displacement throughout the drag
728
729     void point (int x, int y) {
730         Object over = pick (x, y);
731         if (over == null) {
732             if (tipObject != null || tip != null) {
733                 tipObject = null;
734                 tip = null;
735                 super.repaint ();
736             }
737         }
738         else if (over != tipObject) {
739             String [] tipLines = ((Tipped)over).getTip ();
740
741             if (tipLines == null) {
742                 tipObject = null;
743                 tip = null;
744                 super.repaint ();
745             }
746             else {
747                 tipObject = over;
748                 tip = new MultiLineString (tipLines);
749                 tipWidth = tip.getWidth (fm) + 10;
750                 tipHeight = tip.getHeight (fm) + 4;
751                 tipX = Math.max (x - tipWidth/2, 0);
752                 tipY = Math.min (y + 25,
753                                  offSize.height - tipHeight);
754                 super.repaint ();
755             }
756         }
757     }
758     
759     void leave () {
760         if (tipObject != null || tip != null) {
761             tip = null;
762             tipObject = null;
763             super.repaint ();
764         }
765     }
766         
767     void click (int x, int y, boolean rightClick) {
768         requestFocus();
769
770         Object over = pick (x, y);
771         if (over != null) {
772             if (over instanceof RenderedNode) {
773                 RenderedNode n = (RenderedNode)over;
774                 //selectedNode = (RenderedNode)over;
775 //selectedEdge = null;
776
777                 // start dragging the node
778 if (!n.fixed) {
779                     dragNode = n;
780                     dragNode.fixed = true;
781                     dragOffsetX = (int)dragNode.screenX - x;
782                     dragOffsetY = (int)dragNode.screenY - y;
783                 }
784             }
785             //else {
786 // // over instanceof RenderedEdge
787 // selectedNode = null;
788 // selectedEdge = (RenderedEdge)over;
789 //}
790 }
791         else if (rightClick) {
792             // right-click over background
793 showControlPanel ();
794         }
795     }
796     
797     void drag (int x, int y) {
798         if (dragNode != null) {
799             placeNodeOnScreen (dragNode,
800                                x + dragOffsetX,
801                                y + dragOffsetY);
802             changedGraph ();
803         }
804     }
805     
806     void drop (int x, int y) {
807         if (dragNode != null) {
808             placeNodeOnScreen (dragNode,
809                                x + dragOffsetX,
810                                y + dragOffsetY);
811             changedGraph ();
812             dragNode.fixed = false;
813             dragNode = null;
814         }
815     }
816      
817     public boolean handleEvent (Event event) {
818         switch (event.id) {
819             case Event.MOUSE_DOWN:
820                 click (event.x, event.y, event.metaDown());
821                 return true;
822             case Event.MOUSE_UP:
823                 drop (event.x, event.y);
824                 return true;
825             case Event.MOUSE_MOVE:
826                 point (event.x, event.y);
827                 return true;
828             case Event.MOUSE_EXIT:
829                 leave ();
830                 return true;
831             case Event.MOUSE_DRAG:
832                 if (dragNode != null) {
833                     drag (event.x, event.y);
834                     return true;
835                 }
836                 else super.handleEvent (event);
837             default:
838                 return super.handleEvent (event);
839         }
840     }
841     
842     /**
843      * Find the object (Node or Edge) at position (x,y) relative to the window.
844      * @param x X position
845      * @param y Y position
846      * @return topmost object under (x,y), or null if none
847      */
848     public Object pick (int x, int y) {
849         // proceed in reverse display order: nodes first, then edges
850 for (int i=graph.sizeNodes-1; i >= 0; --i) {
851             RenderedNode n = (RenderedNode)graph.nodes[i];
852             if (Math.abs (n.screenX - x) < n.width/2 && Math.abs (n.screenY - y) < n.height/2)
853                 return n;
854         }
855         
856         for (int i=graph.sizeEdges-1; i>=0; --i) {
857             RenderedEdge e = (RenderedEdge)graph.edges[i];
858             RenderedNode to = (RenderedNode)e.to;
859             RenderedNode from = (RenderedNode)e.from;
860             if (inLineSegment (x, y,
861                                (int)to.screenX, (int)to.screenY,
862                                (int)from.screenX, (int)from.screenY, 4))
863                 return e;
864         }
865         
866         return null;
867     }
868     
869     boolean inLineSegment (int x, int y, int x1, int y1, int x2, int y2,
870                            int threshold) {
871         int left, right, top, bottom;
872         if (x1 < x2) {
873             left = x1; right = x2;
874         }
875         else {
876             left = x2; right = x1;
877         }
878         if (y1 < y2) {
879             top = y1; bottom = y2;
880         }
881         else {
882             top = y2; bottom = y1;
883         }
884
885         // check bounding box first
886 if (x < left-threshold || x > right+threshold ||
887             y < top-threshold || y > bottom+threshold) {
888             return false;
889         }
890
891         // equation for line is ax + by + c = 0
892 // d/sqrt(a^2+b^2) is the distance between line and point <x,y>
893 int a = y1 - y2;
894         int b = x2 - x1;
895         int c = x1*y2 - x2*y1;
896         int d = a*x + b*y + c;
897
898         return (d*d <= threshold * threshold * (a*a + b*b));
899     }
900  
901     /*
902      * Testing
903      *
904     public static void main (String[] args) {
905         Frame f = new Frame ();
906         f.addWindowListener (new WindowAdapter () {
907             public void windowClosing (WindowEvent event) {
908                 ((Frame)event.getSource()).dispose();
909             }
910         });
911         f.setSize (100,100);
912         f.setLayout (new BorderLayout ());
913         
914         GraphLayout g = new GraphLayout ();
915         f.add ("Center", g);
916         f.show ();
917         
918         Node last = null;
919         for (int i=0; i<args.length; ++i) {
920             try {
921                 Thread.sleep (200);
922             } catch (InterruptedException e) {}
923             RenderedNode n = new RenderedNode();
924             n.name = args[i];
925             g.addNode (n);
926             g.graph.placeNode (n, 0, 0);
927             
928             if (last != null) {
929                 RenderedEdge e = new RenderedEdge (last, n);
930                 g.addEdge (e);
931             }
932                 
933         }
934     }
935     */
936 }
937
938 class GraphLayoutControlPanel extends ClosableFrame {
939     GraphLayout gl;
940
941     Checkbox automatic;
942
943     Scrollbar threshold;
944     Scrollbar restLength;
945     Scrollbar springConstant;
946     Scrollbar nodeCharge;
947
948     TextField thresholdText;
949     TextField restLengthText;
950     TextField springConstantText;
951     TextField nodeChargeText;
952
953     public GraphLayoutControlPanel (GraphLayout graphLayout) {
954         super ("Graph Layout Control Panel", true);
955         gl = graphLayout;
956
957         setLayout (new GridBagLayout ());
958         Constrain.add (this, automatic = new Checkbox ("Automatic layout"),
959                        Constrain.labelLike (0, 0, 2));
960         automatic.setState (true);
961         Constrain.add (this, new Label ("Threshold:", Label.LEFT), Constrain.labelLike (0,1));
962         Constrain.add (this, thresholdText = new TextField (String.valueOf (gl.getThreshold())),
963                        Constrain.fieldLike (1,1));
964         Constrain.add (this, threshold = new Scrollbar (Scrollbar.HORIZONTAL,
965                                         (int)gl.getThreshold(), 50, 0, 1000),
966                                         Constrain.fieldLike (0,2,2));
967         Constrain.add (this, new Label ("Rest length:", Label.LEFT), Constrain.labelLike (0,3));
968         Constrain.add (this, restLengthText = new TextField (String.valueOf (gl.getRestLength())),
969                        Constrain.fieldLike (1,3));
970         Constrain.add (this, restLength = new Scrollbar (Scrollbar.HORIZONTAL,
971                                          (int)gl.getRestLength(), 50, 0, 1000), Constrain.fieldLike (0,4,2));
972         Constrain.add (this, new Label ("Spring constant:", Label.LEFT), Constrain.labelLike (0,5));
973         Constrain.add (this, springConstantText = new TextField (String.valueOf (gl.getSpringConstant())),
974                        Constrain.fieldLike (1,5));
975         Constrain.add (this, springConstant = new Scrollbar (Scrollbar.HORIZONTAL,
976                                          (int)gl.getSpringConstant(), 50, 0, 1000), Constrain.fieldLike (0,6,2));
977         Constrain.add (this, new Label ("Node charge:", Label.LEFT), Constrain.labelLike (0,7));
978         Constrain.add (this, nodeChargeText = new TextField (String.valueOf (Math.sqrt(gl.getNodeCharge()))),
979                        Constrain.fieldLike (1,7));
980         Constrain.add (this, nodeCharge = new Scrollbar (Scrollbar.HORIZONTAL,
981                                          (int)(Math.sqrt(gl.getNodeCharge())), 50, 0, 1000), Constrain.fieldLike (0,8,2));
982         pack ();
983     }
984     
985     public boolean handleEvent (Event event) {
986         // FIX: doesn't support text entry
987 if (event.target == automatic)
988             gl.setAutomaticLayout (automatic.getState ());
989         else if (event.target == threshold)
990             gl.setThreshold (((Integer )event.arg).intValue());
991         else if (event.target == restLength)
992             gl.setRestLength (((Integer )event.arg).intValue());
993         else if (event.target == springConstant)
994             gl.setSpringConstant (((Integer )event.arg).intValue());
995         else if (event.target == restLength) {
996             int v = ((Integer )event.arg).intValue();
997             gl.setNodeCharge (v*v);
998         }
999         else
1000            return super.handleEvent (event);
1001        return true;
1002    }
1003}
1004

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags