1 /*
2 * Copyright (c) 2007-2010 Hypertriton, Inc. <http://hypertriton.com/>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
15 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
18 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
20 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
21 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
22 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
23 * USE OF THIS SOFTWARE EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26 #include <agar/core/core.h>
27 #include <agar/gui/graph.h>
28 #include <agar/gui/primitive.h>
29 #include <agar/gui/menu.h>
30 #include <agar/gui/gui_math.h>
31
32 #include <stdarg.h>
33 #include <string.h>
34
35 AG_Graph *
AG_GraphNew(void * parent,Uint flags)36 AG_GraphNew(void *parent, Uint flags)
37 {
38 AG_Graph *gf;
39
40 gf = Malloc(sizeof(AG_Graph));
41 AG_ObjectInit(gf, &agGraphClass);
42 gf->flags |= flags;
43
44 if (flags & AG_GRAPH_HFILL) { AG_ExpandHoriz(gf); }
45 if (flags & AG_GRAPH_VFILL) { AG_ExpandVert(gf); }
46
47 AG_ObjectAttach(parent, gf);
48 return (gf);
49 }
50
51 static void
KeyDown(AG_Event * event)52 KeyDown(AG_Event *event)
53 {
54 AG_Graph *gf = AG_SELF();
55 int keysym = AG_INT(1);
56 const int scrollIncr = 10;
57
58 switch (keysym) {
59 case AG_KEY_LEFT:
60 gf->xOffs -= scrollIncr;
61 break;
62 case AG_KEY_RIGHT:
63 gf->xOffs += scrollIncr;
64 break;
65 case AG_KEY_UP:
66 gf->yOffs -= scrollIncr;
67 break;
68 case AG_KEY_DOWN:
69 gf->yOffs += scrollIncr;
70 break;
71 case AG_KEY_0:
72 gf->xOffs = 0;
73 gf->yOffs = 0;
74 break;
75 }
76 AG_Redraw(gf);
77 }
78
79 static __inline__ int
MouseOverVertex(AG_GraphVertex * vtx,int x,int y)80 MouseOverVertex(AG_GraphVertex *vtx, int x, int y)
81 {
82 return (abs(x - vtx->x + vtx->graph->xOffs) <= vtx->w/2 &&
83 abs(y - vtx->y + vtx->graph->yOffs) <= vtx->h/2);
84 }
85
86 static __inline__ void
GetEdgeLabelCoords(AG_GraphEdge * edge,int * x,int * y)87 GetEdgeLabelCoords(AG_GraphEdge *edge, int *x, int *y)
88 {
89 *x = (edge->v1->x + edge->v2->x)/2;
90 *y = (edge->v1->y + edge->v2->y)/2;
91 }
92
93 static __inline__ int
MouseOverEdge(AG_GraphEdge * edge,int x,int y)94 MouseOverEdge(AG_GraphEdge *edge, int x, int y)
95 {
96 int lx, ly;
97 AG_Surface *lbl;
98
99 if (edge->labelSu == -1) {
100 return (0);
101 }
102 GetEdgeLabelCoords(edge, &lx, &ly);
103 lbl = WSURFACE(edge->graph,edge->labelSu);
104 return (abs(x - lx + edge->graph->xOffs) <= lbl->w/2 &&
105 abs(y - ly + edge->graph->yOffs) <= lbl->h/2);
106 }
107
108 static void
MouseMotion(AG_Event * event)109 MouseMotion(AG_Event *event)
110 {
111 AG_Graph *gf = AG_SELF();
112 int x = AG_INT(1);
113 int y = AG_INT(2);
114 int dx = AG_INT(3);
115 int dy = AG_INT(4);
116 AG_GraphVertex *vtx;
117 AG_GraphEdge *edge;
118
119 if (gf->flags & AG_GRAPH_PANNING) {
120 gf->xOffs -= dx;
121 gf->yOffs -= dy;
122 AG_Redraw(gf);
123 return;
124 }
125 if (gf->flags & AG_GRAPH_DRAGGING) {
126 TAILQ_FOREACH(vtx, &gf->vertices, vertices) {
127 if (vtx->flags & AG_GRAPH_SELECTED) {
128 AG_GraphVertexPosition(vtx,
129 vtx->x + dx,
130 vtx->y + dy);
131 }
132 }
133 } else {
134 TAILQ_FOREACH(vtx, &gf->vertices, vertices) {
135 AG_SETFLAGS(vtx->flags, AG_GRAPH_MOUSEOVER,
136 MouseOverVertex(vtx,x,y));
137 }
138 TAILQ_FOREACH(edge, &gf->edges, edges) {
139 AG_SETFLAGS(edge->flags, AG_GRAPH_MOUSEOVER,
140 MouseOverEdge(edge,x,y));
141 }
142 if (!TAILQ_EMPTY(&gf->vertices) ||
143 !TAILQ_EMPTY(&gf->edges))
144 AG_Redraw(gf);
145 }
146 }
147
148 static void
MouseButtonUp(AG_Event * event)149 MouseButtonUp(AG_Event *event)
150 {
151 AG_Graph *gf = AG_SELF();
152 int button = AG_INT(1);
153
154 switch (button) {
155 case AG_MOUSE_LEFT:
156 gf->flags &= ~(AG_GRAPH_DRAGGING);
157 break;
158 case AG_MOUSE_MIDDLE:
159 gf->flags &= ~(AG_GRAPH_PANNING);
160 break;
161 }
162 }
163
164 /* Widget must be locked */
165 AG_GraphEdge *
AG_GraphEdgeFind(AG_Graph * gf,void * userPtr)166 AG_GraphEdgeFind(AG_Graph *gf, void *userPtr)
167 {
168 AG_GraphEdge *edge;
169
170 TAILQ_FOREACH(edge, &gf->edges, edges) {
171 if (edge->userPtr == userPtr)
172 return (edge);
173 }
174 return (NULL);
175 }
176
177 AG_GraphEdge *
AG_GraphEdgeNew(AG_Graph * gf,AG_GraphVertex * v1,AG_GraphVertex * v2,void * userPtr)178 AG_GraphEdgeNew(AG_Graph *gf, AG_GraphVertex *v1, AG_GraphVertex *v2,
179 void *userPtr)
180 {
181 AG_GraphEdge *edge;
182
183 AG_ObjectLock(gf);
184 TAILQ_FOREACH(edge, &gf->edges, edges) {
185 if (edge->v1 == v1 && edge->v2 == v2) {
186 AG_SetError(_("Existing edge"));
187 AG_ObjectUnlock(gf);
188 return (NULL);
189 }
190 }
191 edge = Malloc(sizeof(AG_GraphEdge));
192 edge->labelTxt[0] = '\0';
193 edge->labelSu = -1;
194 edge->edgeColor = AG_ColorRGB(0,0,0);
195 edge->labelColor = AG_ColorRGB(0,0,0);
196 edge->flags = 0;
197 edge->v1 = v1;
198 edge->v2 = v2;
199 edge->userPtr = userPtr;
200 edge->graph = gf;
201 edge->popupMenu = NULL;
202 TAILQ_INSERT_TAIL(&gf->edges, edge, edges);
203 gf->nedges++;
204
205 edge->v1->edges = Realloc(edge->v1->edges,
206 (edge->v1->nedges + 1)*sizeof(AG_GraphEdge *));
207 edge->v2->edges = Realloc(edge->v2->edges,
208 (edge->v2->nedges + 1)*sizeof(AG_GraphEdge *));
209 edge->v1->edges[edge->v1->nedges++] = edge;
210 edge->v2->edges[edge->v2->nedges++] = edge;
211
212 AG_ObjectUnlock(gf);
213 AG_Redraw(gf);
214 return (edge);
215 }
216
217 void
AG_GraphEdgeFree(AG_GraphEdge * edge)218 AG_GraphEdgeFree(AG_GraphEdge *edge)
219 {
220 if (edge->labelSu != -1) {
221 AG_WidgetUnmapSurface(edge->graph, edge->labelSu);
222 }
223 Free(edge);
224 }
225
226 void
AG_GraphEdgeLabelS(AG_GraphEdge * ge,const char * s)227 AG_GraphEdgeLabelS(AG_GraphEdge *ge, const char *s)
228 {
229 AG_ObjectLock(ge->graph);
230 Strlcpy(ge->labelTxt, s, sizeof(ge->labelTxt));
231 if (ge->labelSu >= 0) {
232 AG_WidgetUnmapSurface(ge->graph, ge->labelSu);
233 }
234 AG_TextColor(ge->labelColor);
235 ge->labelSu = AG_WidgetMapSurface(ge->graph, AG_TextRender(ge->labelTxt));
236 AG_ObjectUnlock(ge->graph);
237 AG_Redraw(ge->graph);
238 }
239
240 void
AG_GraphEdgeLabel(AG_GraphEdge * ge,const char * fmt,...)241 AG_GraphEdgeLabel(AG_GraphEdge *ge, const char *fmt, ...)
242 {
243 va_list ap;
244
245 AG_ObjectLock(ge->graph);
246 va_start(ap, fmt);
247 Vsnprintf(ge->labelTxt, sizeof(ge->labelTxt), fmt, ap);
248 va_end(ap);
249 if (ge->labelSu >= 0) {
250 AG_WidgetUnmapSurface(ge->graph, ge->labelSu);
251 }
252 AG_TextColor(ge->labelColor);
253 ge->labelSu = AG_WidgetMapSurface(ge->graph, AG_TextRender(ge->labelTxt));
254 AG_ObjectUnlock(ge->graph);
255 AG_Redraw(ge->graph);
256 }
257
258 void
AG_GraphEdgeColorLabel(AG_GraphEdge * edge,Uint8 r,Uint8 g,Uint8 b)259 AG_GraphEdgeColorLabel(AG_GraphEdge *edge, Uint8 r, Uint8 g, Uint8 b)
260 {
261 AG_ObjectLock(edge->graph);
262 edge->labelColor = AG_ColorRGB(r,g,b);
263 AG_ObjectUnlock(edge->graph);
264 AG_Redraw(edge->graph);
265 }
266
267 void
AG_GraphEdgeColor(AG_GraphEdge * edge,Uint8 r,Uint8 g,Uint8 b)268 AG_GraphEdgeColor(AG_GraphEdge *edge, Uint8 r, Uint8 g, Uint8 b)
269 {
270 AG_ObjectLock(edge->graph);
271 edge->edgeColor = AG_ColorRGB(r,g,b);
272 AG_ObjectUnlock(edge->graph);
273 AG_Redraw(edge->graph);
274 }
275
276 void
AG_GraphEdgePopupMenu(AG_GraphEdge * edge,struct ag_popup_menu * pm)277 AG_GraphEdgePopupMenu(AG_GraphEdge *edge, struct ag_popup_menu *pm)
278 {
279 AG_ObjectLock(edge->graph);
280 edge->popupMenu = pm;
281 AG_ObjectUnlock(edge->graph);
282 AG_Redraw(edge->graph);
283 }
284
285 static void
SetVertexStyle(AG_Event * event)286 SetVertexStyle(AG_Event *event)
287 {
288 AG_GraphVertex *vtx = AG_PTR(1);
289 int style = AG_INT(2);
290
291 AG_GraphVertexStyle(vtx, (enum ag_graph_vertex_style)style);
292 }
293
294 static void
UnselectEdge(AG_Graph * gf,AG_GraphEdge * edge)295 UnselectEdge(AG_Graph *gf, AG_GraphEdge *edge)
296 {
297 edge->flags &= ~(AG_GRAPH_SELECTED);
298 AG_PostEvent(NULL, gf, "graph-edge-unselected", "%p", edge);
299 AG_Redraw(gf);
300 }
301
302 static void
SelectEdge(AG_Graph * gf,AG_GraphEdge * edge)303 SelectEdge(AG_Graph *gf, AG_GraphEdge *edge)
304 {
305 edge->flags |= AG_GRAPH_SELECTED;
306 AG_PostEvent(NULL, gf, "graph-edge-selected", "%p", edge);
307 AG_Redraw(gf);
308 }
309
310 static void
UnselectVertex(AG_Graph * gf,AG_GraphVertex * vtx)311 UnselectVertex(AG_Graph *gf, AG_GraphVertex *vtx)
312 {
313 vtx->flags &= ~(AG_GRAPH_SELECTED);
314 AG_PostEvent(NULL, gf, "graph-vertex-unselected", "%p", vtx);
315 AG_Redraw(gf);
316 }
317
318 static void
SelectVertex(AG_Graph * gf,AG_GraphVertex * vtx)319 SelectVertex(AG_Graph *gf, AG_GraphVertex *vtx)
320 {
321 vtx->flags |= AG_GRAPH_SELECTED;
322 AG_PostEvent(NULL, gf, "graph-vertex-selected", "%p", vtx);
323 AG_Redraw(gf);
324 }
325
326 static void
MouseButtonDown(AG_Event * event)327 MouseButtonDown(AG_Event *event)
328 {
329 AG_Graph *gf = AG_SELF();
330 int button = AG_INT(1);
331 int x = AG_INT(2);
332 int y = AG_INT(3);
333 AG_KeyMod kmod = AG_GetModState(gf);
334 AG_GraphVertex *vtx, *vtx2;
335 AG_GraphEdge *edge, *edge2;
336 AG_PopupMenu *pm;
337
338 if (!AG_WidgetIsFocused(gf))
339 AG_WidgetFocus(gf);
340
341 switch (button) {
342 case AG_MOUSE_MIDDLE:
343 gf->flags |= AG_GRAPH_PANNING;
344 break;
345 case AG_MOUSE_LEFT:
346 if (gf->flags & AG_GRAPH_NO_SELECT) {
347 break;
348 }
349 if (kmod & (AG_KEYMOD_CTRL|AG_KEYMOD_SHIFT)) {
350 TAILQ_FOREACH(edge, &gf->edges, edges) {
351 if (!MouseOverEdge(edge, x, y)) {
352 continue;
353 }
354 if (edge->flags & AG_GRAPH_SELECTED) {
355 UnselectEdge(gf, edge);
356 } else {
357 SelectEdge(gf, edge);
358 }
359 }
360 TAILQ_FOREACH(vtx, &gf->vertices, vertices) {
361 if (!MouseOverVertex(vtx, x, y)) {
362 continue;
363 }
364 if (vtx->flags & AG_GRAPH_SELECTED) {
365 UnselectVertex(gf, vtx);
366 } else {
367 SelectVertex(gf, vtx);
368 }
369 }
370 } else {
371 TAILQ_FOREACH(edge, &gf->edges, edges) {
372 if (MouseOverEdge(edge, x, y))
373 break;
374 }
375 if (edge != NULL) {
376 TAILQ_FOREACH(edge2, &gf->edges, edges) {
377 UnselectEdge(gf, edge2);
378 }
379 SelectEdge(gf, edge);
380 }
381 TAILQ_FOREACH(vtx, &gf->vertices, vertices) {
382 if (MouseOverVertex(vtx, x, y))
383 break;
384 }
385 if (vtx != NULL) {
386 TAILQ_FOREACH(vtx2, &gf->vertices, vertices) {
387 UnselectVertex(gf, vtx2);
388 }
389 SelectVertex(gf, vtx);
390 }
391 }
392 if (!(gf->flags & AG_GRAPH_NO_MOVE)) {
393 gf->flags |= AG_GRAPH_DRAGGING;
394 }
395 break;
396 case AG_MOUSE_RIGHT:
397 if (gf->flags & AG_GRAPH_NO_MENUS) {
398 break;
399 }
400 TAILQ_FOREACH(vtx, &gf->vertices, vertices) {
401 if (!MouseOverVertex(vtx, x, y)) {
402 continue;
403 }
404 if (vtx->popupMenu != NULL) {
405 AG_PopupShowAt(vtx->popupMenu, x,y);
406 } else {
407 pm = AG_PopupNew(gf);
408 AG_MenuUintFlags(pm->root, _("Hide vertex"), NULL,
409 &vtx->flags, AG_GRAPH_HIDDEN, 1);
410 AG_MenuSeparator(pm->root);
411 AG_MenuAction(pm->root, _("Rectangular"), NULL,
412 SetVertexStyle, "%p,%i", vtx,
413 AG_GRAPH_RECTANGLE);
414 AG_MenuAction(pm->root, _("Circular"), NULL,
415 SetVertexStyle, "%p,%i", vtx,
416 AG_GRAPH_CIRCLE);
417 AG_PopupShowAt(pm, x,y);
418 }
419 break;
420 }
421 TAILQ_FOREACH(edge, &gf->edges, edges) {
422 if (!MouseOverEdge(edge, x, y)) {
423 continue;
424 }
425 if (edge->popupMenu != NULL) {
426 AG_PopupShowAt(edge->popupMenu, x,y);
427 } else {
428 pm = AG_PopupNew(gf);
429 AG_MenuUintFlags(pm->root, _("Hide edge"), NULL,
430 &edge->flags, AG_GRAPH_HIDDEN, 1);
431 AG_PopupShowAt(pm, x,y);
432 }
433 break;
434 }
435 }
436 }
437
438 static void
Init(void * obj)439 Init(void *obj)
440 {
441 AG_Graph *gf = obj;
442
443 WIDGET(gf)->flags |= AG_WIDGET_FOCUSABLE;
444
445 gf->flags = 0;
446 gf->wPre = 128;
447 gf->hPre = 128;
448 gf->xOffs = 0;
449 gf->yOffs = 0;
450 gf->xMin = 0;
451 gf->yMin = 0;
452 gf->xMax = 0;
453 gf->yMax = 0;
454 TAILQ_INIT(&gf->vertices);
455 TAILQ_INIT(&gf->edges);
456 gf->nvertices = 0;
457 gf->nedges = 0;
458 gf->pxMin = 0;
459 gf->pxMax = 0;
460 gf->pyMin = 0;
461 gf->pyMax = 0;
462 gf->r = AG_RECT(0,0,0,0);
463
464 #if 0
465 gf->hbar = AG_ScrollbarNew(gf, AG_SCROLLBAR_HORIZ, 0);
466 gf->vbar = AG_ScrollbarNew(gf, AG_SCROLLBAR_VERT, 0);
467 AG_BindInt(gf->hbar, "value", &gf->xOffs);
468 AG_BindInt(gf->hbar, "min", &gf->xMin);
469 AG_BindInt(gf->hbar, "max", &gf->xMax);
470 AG_BindInt(gf->hbar, "visible", &WIDGET(gf)->w);
471
472 AG_BindInt(gf->vbar, "value", &gf->yOffs);
473 AG_BindInt(gf->vbar, "min", &gf->yMin);
474 AG_BindInt(gf->vbar, "max", &gf->yMax);
475 AG_BindInt(gf->vbar, "visible", &WIDGET(gf)->h);
476 #endif
477
478 AG_SetEvent(gf, "key-down", KeyDown, NULL);
479 AG_SetEvent(gf, "mouse-button-down", MouseButtonDown, NULL);
480 AG_SetEvent(gf, "mouse-button-up", MouseButtonUp, NULL);
481 AG_SetEvent(gf, "mouse-motion", MouseMotion, NULL);
482
483 #ifdef AG_DEBUG
484 AG_BindInt(gf, "xOffs", &gf->xOffs);
485 AG_BindInt(gf, "yOffs", &gf->yOffs);
486 AG_BindInt(gf, "xMin", &gf->xMin);
487 AG_BindInt(gf, "yMin", &gf->yMin);
488 AG_BindInt(gf, "xMax", &gf->xMax);
489 AG_BindInt(gf, "yMax", &gf->yMax);
490 #endif /* AG_DEBUG */
491 }
492
493 void
AG_GraphFreeVertices(AG_Graph * gf)494 AG_GraphFreeVertices(AG_Graph *gf)
495 {
496 AG_GraphVertex *vtx, *vtxNext;
497 AG_GraphEdge *edge, *edgeNext;
498
499 AG_ObjectLock(gf);
500
501 for (vtx = TAILQ_FIRST(&gf->vertices);
502 vtx != TAILQ_END(&gf->vertices);
503 vtx = vtxNext) {
504 vtxNext = TAILQ_NEXT(vtx, vertices);
505 AG_GraphVertexFree(vtx);
506 }
507 for (edge = TAILQ_FIRST(&gf->edges);
508 edge != TAILQ_END(&gf->edges);
509 edge = edgeNext) {
510 edgeNext = TAILQ_NEXT(edge, edges);
511 AG_GraphEdgeFree(edge);
512 }
513 TAILQ_INIT(&gf->vertices);
514 TAILQ_INIT(&gf->edges);
515 gf->nvertices = 0;
516 gf->nedges = 0;
517 gf->xMin = 0;
518 gf->xMax = 0;
519 gf->yMin = 0;
520 gf->yMax = 0;
521 gf->flags &= ~(AG_GRAPH_DRAGGING);
522
523 AG_ObjectUnlock(gf);
524 AG_Redraw(gf);
525 }
526
527 static void
Destroy(void * p)528 Destroy(void *p)
529 {
530 AG_GraphFreeVertices((AG_Graph *)p);
531 }
532
533 void
AG_GraphSizeHint(AG_Graph * gf,Uint w,Uint h)534 AG_GraphSizeHint(AG_Graph *gf, Uint w, Uint h)
535 {
536 AG_ObjectLock(gf);
537 gf->wPre = w;
538 gf->hPre = h;
539 AG_ObjectUnlock(gf);
540 }
541
542 static void
SizeRequest(void * obj,AG_SizeReq * r)543 SizeRequest(void *obj, AG_SizeReq *r)
544 {
545 AG_Graph *gf = obj;
546
547 r->w = gf->wPre;
548 r->h = gf->hPre;
549 }
550
551 static int
SizeAllocate(void * obj,const AG_SizeAlloc * a)552 SizeAllocate(void *obj, const AG_SizeAlloc *a)
553 {
554 AG_Graph *gf = obj;
555
556 if (a->w < 1 || a->h < 1)
557 return (-1);
558
559 gf->xOffs = -(a->w/2);
560 gf->yOffs = -(a->h/2);
561 gf->r = AG_RECT(0, 0, a->w, a->h);
562
563 return (0);
564 }
565
566 static void
Draw(void * obj)567 Draw(void *obj)
568 {
569 AG_Graph *gf = obj;
570 AG_GraphVertex *vtx;
571 AG_GraphEdge *edge;
572
573 AG_PushClipRect(gf, gf->r);
574
575 /* Draw the bounding box */
576 AG_DrawRectOutline(gf,
577 AG_RECT(gf->pxMin - gf->xOffs, gf->pyMin - gf->yOffs,
578 gf->pxMax - gf->pxMin, gf->pyMax - gf->pyMin),
579 AG_ColorRGB(128,128,128));
580
581 /* Draw the edges */
582 TAILQ_FOREACH(edge, &gf->edges, edges) {
583 if (edge->flags & AG_GRAPH_HIDDEN) {
584 continue;
585 }
586 AG_DrawLine(gf,
587 edge->v1->x - gf->xOffs,
588 edge->v1->y - gf->yOffs,
589 edge->v2->x - gf->xOffs,
590 edge->v2->y - gf->yOffs,
591 edge->edgeColor);
592
593 if (edge->labelSu >= 0) {
594 AG_Surface *su = WSURFACE(gf,edge->labelSu);
595 int lblX, lblY;
596
597 GetEdgeLabelCoords(edge, &lblX, &lblY);
598 lblX -= gf->xOffs + su->w/2;
599 lblY -= gf->yOffs + su->h/2;
600
601 if (edge->flags & AG_GRAPH_SELECTED) {
602 AG_DrawRectOutline(gf,
603 AG_RECT(lblX-1, lblY-1,
604 su->w+2, su->h+2),
605 edge->labelColor);
606 }
607 if (edge->flags & AG_GRAPH_MOUSEOVER) {
608 AG_DrawRectOutline(gf,
609 AG_RECT(lblX-2, lblY-2,
610 su->w+4, su->h+4),
611 WCOLOR_HOV(gf,LINE_COLOR));
612 }
613 AG_DrawRect(gf,
614 AG_RECT(lblX, lblY, su->w, su->h),
615 AG_ColorRGBA(128,128,128,128));
616 AG_WidgetBlitSurface(gf, edge->labelSu, lblX, lblY);
617 }
618 }
619
620 /* Draw the vertices. */
621 TAILQ_FOREACH(vtx, &gf->vertices, vertices) {
622 AG_Surface *lbl = WSURFACE(gf,vtx->labelSu);
623
624 if (vtx->flags & AG_GRAPH_HIDDEN) {
625 continue;
626 }
627 switch (vtx->style) {
628 case AG_GRAPH_RECTANGLE:
629 AG_DrawRect(gf,
630 AG_RECT(vtx->x - vtx->w/2 - gf->xOffs,
631 vtx->y - vtx->h/2 - gf->yOffs,
632 vtx->w,
633 vtx->h),
634 vtx->bgColor);
635 if (vtx->flags & AG_GRAPH_SELECTED) {
636 AG_DrawRectOutline(gf,
637 AG_RECT(vtx->x - vtx->w/2 - gf->xOffs - 1,
638 vtx->y - vtx->h/2 - gf->yOffs - 1,
639 vtx->w + 2,
640 vtx->h + 2),
641 AG_ColorRGB(0,0,255));
642 }
643 if (vtx->flags & AG_GRAPH_MOUSEOVER) {
644 AG_DrawRectOutline(gf,
645 AG_RECT(vtx->x - vtx->w/2 - gf->xOffs - 2,
646 vtx->y - vtx->h/2 - gf->yOffs - 2,
647 vtx->w + 4,
648 vtx->h + 4),
649 AG_ColorRGB(255,0,0));
650 }
651 break;
652 case AG_GRAPH_CIRCLE:
653 AG_DrawCircle(gf,
654 vtx->x - gf->xOffs,
655 vtx->y - gf->yOffs,
656 MAX(vtx->w,vtx->h)/2,
657 vtx->bgColor);
658 break;
659 }
660 if (vtx->labelSu >= 0) {
661 AG_WidgetBlitSurface(gf, vtx->labelSu,
662 vtx->x - lbl->w/2 - gf->xOffs,
663 vtx->y - lbl->h/2 - gf->yOffs);
664 }
665 }
666
667 AG_PopClipRect(gf);
668 }
669
670 /* Graph must be locked. */
671 AG_GraphVertex *
AG_GraphVertexFind(AG_Graph * gf,void * userPtr)672 AG_GraphVertexFind(AG_Graph *gf, void *userPtr)
673 {
674 AG_GraphVertex *vtx;
675
676 TAILQ_FOREACH(vtx, &gf->vertices, vertices) {
677 if (vtx->userPtr == userPtr)
678 return (vtx);
679 }
680 return (NULL);
681 }
682
683 AG_GraphVertex *
AG_GraphVertexNew(AG_Graph * gf,void * userPtr)684 AG_GraphVertexNew(AG_Graph *gf, void *userPtr)
685 {
686 AG_GraphVertex *vtx;
687
688 vtx = Malloc(sizeof(AG_GraphVertex));
689 vtx->labelTxt[0] = '\0';
690 vtx->labelSu = -1;
691 vtx->labelColor = AG_ColorRGB(0,0,0);
692 vtx->bgColor = AG_ColorRGBA(255,255,255,128);
693 vtx->style = AG_GRAPH_RECTANGLE;
694 vtx->flags = 0;
695 vtx->x = 0;
696 vtx->y = 0;
697 vtx->w = 32;
698 vtx->h = 32;
699 vtx->graph = gf;
700 vtx->userPtr = userPtr;
701 vtx->edges = NULL;
702 vtx->nedges = 0;
703 vtx->popupMenu = NULL;
704
705 AG_ObjectLock(gf);
706 TAILQ_INSERT_TAIL(&gf->vertices, vtx, vertices);
707 gf->nvertices++;
708 AG_ObjectUnlock(gf);
709
710 AG_Redraw(gf);
711 return (vtx);
712 }
713
714 void
AG_GraphVertexFree(AG_GraphVertex * vtx)715 AG_GraphVertexFree(AG_GraphVertex *vtx)
716 {
717 if (vtx->labelSu != -1) {
718 AG_WidgetUnmapSurface(vtx->graph, vtx->labelSu);
719 }
720 Free(vtx->edges);
721 Free(vtx);
722 }
723
724 void
AG_GraphVertexColorLabel(AG_GraphVertex * vtx,Uint8 r,Uint8 g,Uint8 b)725 AG_GraphVertexColorLabel(AG_GraphVertex *vtx, Uint8 r, Uint8 g, Uint8 b)
726 {
727 AG_ObjectLock(vtx->graph);
728 vtx->labelColor = AG_ColorRGB(r,g,b);
729 AG_ObjectUnlock(vtx->graph);
730 AG_Redraw(vtx->graph);
731 }
732
733 void
AG_GraphVertexColorBG(AG_GraphVertex * vtx,Uint8 r,Uint8 g,Uint8 b)734 AG_GraphVertexColorBG(AG_GraphVertex *vtx, Uint8 r, Uint8 g, Uint8 b)
735 {
736 AG_ObjectLock(vtx->graph);
737 vtx->bgColor = AG_ColorRGB(r,g,b);
738 AG_ObjectUnlock(vtx->graph);
739 AG_Redraw(vtx->graph);
740 }
741
742 void
AG_GraphVertexLabel(AG_GraphVertex * vtx,const char * fmt,...)743 AG_GraphVertexLabel(AG_GraphVertex *vtx, const char *fmt, ...)
744 {
745 char s[AG_GRAPH_LABEL_MAX];
746 va_list ap;
747
748 va_start(ap, fmt);
749 Vsnprintf(s, sizeof(s), fmt, ap);
750 va_end(ap);
751
752 AG_GraphVertexLabelS(vtx, s);
753 }
754
755 void
AG_GraphVertexLabelS(AG_GraphVertex * vtx,const char * s)756 AG_GraphVertexLabelS(AG_GraphVertex *vtx, const char *s)
757 {
758 AG_ObjectLock(vtx->graph);
759 Strlcpy(vtx->labelTxt, s, sizeof(vtx->labelTxt));
760 if (vtx->labelSu >= 0) {
761 AG_WidgetUnmapSurface(vtx->graph, vtx->labelSu);
762 }
763 AG_TextColor(vtx->labelColor);
764 vtx->labelSu = AG_WidgetMapSurface(vtx->graph, AG_TextRender(vtx->labelTxt));
765 AG_ObjectUnlock(vtx->graph);
766 AG_Redraw(vtx->graph);
767 }
768
769 void
AG_GraphVertexPosition(AG_GraphVertex * vtx,int x,int y)770 AG_GraphVertexPosition(AG_GraphVertex *vtx, int x, int y)
771 {
772 AG_Graph *gf = vtx->graph;
773
774 AG_ObjectLock(gf);
775
776 vtx->x = x;
777 vtx->y = y;
778
779 if (x < gf->xMin) { gf->xMin = x; }
780 if (y < gf->yMin) { gf->yMin = y; }
781 if (x > gf->xMax) { gf->xMax = x; }
782 if (y > gf->yMax) { gf->yMax = y; }
783
784 AG_ObjectUnlock(gf);
785 AG_Redraw(gf);
786 }
787
788 void
AG_GraphVertexSize(AG_GraphVertex * vtx,Uint w,Uint h)789 AG_GraphVertexSize(AG_GraphVertex *vtx, Uint w, Uint h)
790 {
791 AG_ObjectLock(vtx->graph);
792 vtx->w = w;
793 vtx->h = h;
794 AG_ObjectUnlock(vtx->graph);
795 AG_Redraw(vtx->graph);
796 }
797
798 void
AG_GraphVertexStyle(AG_GraphVertex * vtx,enum ag_graph_vertex_style style)799 AG_GraphVertexStyle(AG_GraphVertex *vtx, enum ag_graph_vertex_style style)
800 {
801 AG_ObjectLock(vtx->graph);
802 vtx->style = style;
803 AG_ObjectUnlock(vtx->graph);
804 AG_Redraw(vtx->graph);
805 }
806
807 void
AG_GraphVertexPopupMenu(AG_GraphVertex * vtx,struct ag_popup_menu * pm)808 AG_GraphVertexPopupMenu(AG_GraphVertex *vtx, struct ag_popup_menu *pm)
809 {
810 AG_ObjectLock(vtx->graph);
811 vtx->popupMenu = pm;
812 AG_ObjectUnlock(vtx->graph);
813 }
814
815 static int
CompareVertices(const void * p1,const void * p2)816 CompareVertices(const void *p1, const void *p2)
817 {
818 const AG_GraphVertex *v1 = *(const void **)p1;
819 const AG_GraphVertex *v2 = *(const void **)p2;
820
821 return (v2->nedges - v1->nedges);
822 }
823
824 static AG_GraphVertex *
VertexAtCoords(AG_Graph * gf,int x,int y)825 VertexAtCoords(AG_Graph *gf, int x, int y)
826 {
827 AG_GraphVertex *vtx;
828
829 TAILQ_FOREACH(vtx, &gf->vertices, vertices) {
830 if (vtx->x == x && vtx->y == y)
831 return (vtx);
832 }
833 return (NULL);
834 }
835
836 static void
PlaceVertex(AG_Graph * gf,AG_GraphVertex * vtx,AG_GraphVertex ** vSorted,int x,int y)837 PlaceVertex(AG_Graph *gf, AG_GraphVertex *vtx, AG_GraphVertex **vSorted,
838 int x, int y)
839 {
840 int ox, oy;
841 int i;
842
843 vtx->x = x;
844 vtx->y = y;
845 vtx->flags |= AG_GRAPH_AUTOPLACED;
846
847 if (x < gf->pxMin) { gf->pxMin = x; }
848 if (x > gf->pxMax) { gf->pxMax = x; }
849 if (y < gf->pyMin) { gf->pyMin = y; }
850 if (y > gf->pyMax) { gf->pyMax = y; }
851
852 for (i = 0; i < vtx->nedges; i++) {
853 AG_GraphEdge *edge = vtx->edges[i];
854 AG_GraphVertex *oVtx;
855 float r = 128.0;
856 float theta = 0.0;
857
858 if (edge->v1 == vtx) { oVtx = edge->v2; }
859 else { oVtx = edge->v1; }
860
861 if (oVtx->flags & AG_GRAPH_AUTOPLACED) {
862 continue;
863 }
864 for (;;) {
865 ox = (int)(r*Cos(theta));
866 oy = (int)(r*Sin(theta));
867 if (VertexAtCoords(gf, ox, oy) == NULL) {
868 PlaceVertex(gf, oVtx, vSorted, ox, oy);
869 break;
870 }
871 theta += (float)(AG_PI*2.0)/6;
872 if (theta >= (AG_PI*2.0)) {
873 r += 64.0;
874 }
875 }
876 }
877 }
878
879 /*
880 * Try to position the vertices such that they are distributed evenly
881 * throughout a given bounding box, with a minimal number of edges
882 * crossing each other.
883 */
884 void
AG_GraphAutoPlace(AG_Graph * gf,Uint w,Uint h)885 AG_GraphAutoPlace(AG_Graph *gf, Uint w, Uint h)
886 {
887 AG_GraphVertex **vSorted, *vtx;
888 int nSorted = 0, i;
889 int tx, ty;
890
891 AG_ObjectLock(gf);
892
893 if (gf->nvertices == 0 || gf->nedges == 0) {
894 AG_ObjectUnlock(gf);
895 return;
896 }
897
898 /* Sort the vertices based on their number of connected edges. */
899 vSorted = Malloc(gf->nvertices*sizeof(AG_GraphVertex *));
900 TAILQ_FOREACH(vtx, &gf->vertices, vertices) {
901 vtx->flags &= ~(AG_GRAPH_AUTOPLACED);
902 vSorted[nSorted++] = vtx;
903 }
904 qsort(vSorted, (size_t)nSorted, sizeof(AG_GraphVertex *),
905 CompareVertices);
906 gf->pxMin = 0;
907 gf->pxMax = 0;
908 gf->pyMin = 0;
909 gf->pyMax = 0;
910 for (i = 0; i < nSorted; i++) {
911 if (vSorted[i]->flags & AG_GRAPH_AUTOPLACED) {
912 continue;
913 }
914 for (tx = gf->pxMax+128, ty = 0;
915 ty <= gf->pyMax;
916 ty += 64) {
917 if (VertexAtCoords(gf, tx, ty) == NULL) {
918 PlaceVertex(gf, vSorted[i], vSorted, tx, ty);
919 break;
920 }
921 }
922 if (ty <= gf->pyMax) {
923 continue;
924 }
925 for (tx = gf->pxMin-128, ty = 0;
926 ty <= gf->pyMax;
927 ty += 64) {
928 if (VertexAtCoords(gf, tx, ty) == NULL) {
929 PlaceVertex(gf, vSorted[i], vSorted, tx, ty);
930 break;
931 }
932 }
933 if (ty <= gf->pyMax) {
934 continue;
935 }
936 }
937 AG_ObjectUnlock(gf);
938 AG_Redraw(gf);
939 Free(vSorted);
940 }
941
942 AG_WidgetClass agGraphClass = {
943 {
944 "Agar(Widget:Graph)",
945 sizeof(AG_Graph),
946 { 0,0 },
947 Init,
948 NULL, /* free */
949 Destroy,
950 NULL, /* load */
951 NULL, /* save */
952 NULL /* edit */
953 },
954 Draw,
955 SizeRequest,
956 SizeAllocate
957 };
958