BRL-CAD
dag.cpp
Go to the documentation of this file.
1 /* D A G . C P P
2  * BRL-CAD
3  *
4  * Copyright (c) 2012-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 /** @file libged/dag.cpp
21  *
22  * The model for a directed acyclic graph.
23  *
24  */
25 
26 #include "common.h"
27 
28 #ifdef HAVE_ADAPTAGRAMS
29 
30 /* System Header */
31 #include <stdint.h>
32 #include <stdlib.h>
33 #include <vector>
34 
35 #define BRLCAD_PARALLEL PARALLEL
36 #undef PARALLEL
37 #define POSITION_COORDINATE 50.0
38 #define X_WIDTH 30.0
39 #define Y_HEIGHT 30.0
40 
41 /* Maximum dimension of a subcommand's name. */
42 #define NAME_SIZE 10
43 
44 /* Adaptagrams Header */
45 #include "libavoid/libavoid.h"
46 using namespace Avoid;
47 
48 /* Public Header */
49 #include "ged.h"
50 
51 
52 /**
53  * Subcommand name information, for a table of available subcommands.
54  */
55 struct graph_subcmd_tab {
56  char *name;
57 };
58 
59 /**
60  * Table of graph subcommand functions.
61  */
62 static const struct graph_subcmd_tab graph_subcmds[] = {
63  {(char *)"show"},
64  {(char *)"positions"},
65  {(char *)NULL}
66 };
67 
68 /**
69  * This structure has fields that correspond to three lists for primitive, combination and non-geometry type objects of a database.
70  */
71 struct output {
72  std::vector<std::string> primitives;
73  std::vector<std::string> combinations;
74  std::vector<std::string> non_geometries;
75 };
76 
77 
78 /**
79  * This structure has fields related to the representation of a graph with the help of the Adaptagrams library.
80  */
81 struct _ged_dag_data {
82  Avoid::Router *router;
83  struct bu_hash_tbl *ids;
84  struct bu_hash_tbl *object_types;
85  uint16_t object_nr;
86  uint16_t last_connref_id;
87 };
88 
89 
90 /**
91  * Method called when a connector of type Avoid::ConnRef needs to be redrawn.
92  */
93 static void
94 conn_callback(void *ptr)
95 {
96  Avoid::ConnRef *connRef = (Avoid::ConnRef *) ptr;
97  connRef->route();
98 }
99 
100 
101 /**
102  * Routine that returns the root nodes within the graph.
103  */
104 std::vector<unsigned int>
105 find_roots(_ged_dag_data *dag)
106 {
107  std::vector<unsigned int> roots;
108  ObstacleList::const_iterator finish = dag->router->m_obstacles.end();
109 
110  for (ObstacleList::const_iterator it = dag->router->m_obstacles.begin(); it != finish; ++it) {
111  Avoid::IntList shapes_runningFrom;
112  dag->router->attachedShapes(shapes_runningFrom, (*it)->id(), Avoid::runningFrom);
113 
114  /* Check if there is no edge that goes in this node and that there exist edges going out of it. */
115  if (shapes_runningFrom.size() == 0) {
116  roots.push_back((*it)->id());
117  }
118  }
119  return roots;
120 }
121 
122 
123 /**
124  * This routine sets the position of the node depending on its level within the tree
125  * and on the maximum X coordinate on that level.
126  */
127 void
128 position_node(_ged_dag_data *dag, bool has_parent, Avoid::ShapeRef *parent, Avoid::ShapeRef *child, unsigned int &level, std::vector<double> &maxX_level)
129 {
130  double new_x, new_y, new_x1, new_y1;
131 
132 #define LIBAVOID_LATEST_API
133 #if defined LIBAVOID_LATEST_API
134  #define LIBX 0
135  #define LIBY 1
136  Box bbox = child->polygon().offsetBoundingBox(0);
137  new_x = bbox.min[LIBX];
138  new_y = bbox.min[LIBY];
139  new_x1 = bbox.max[LIBX];
140  new_y1 = bbox.max[LIBY];
141 #else
142  child->polygon().getBoundingRect(&new_x, &new_y, &new_x1, &new_y1);
143 #endif
144 
145  /* If it has a parent it means that is not the root node.
146  * Therefore, set the child's position depending on the parent's position.
147  */
148  if (has_parent) {
149  double parent_x, parent_y, parent_x1, parent_y1;
150 
151 #if defined LIBAVOID_LATEST_API
152  Box parent_bbox = parent->polygon().offsetBoundingBox(0);
153  parent_x = bbox.min[LIBX];
154  parent_y = bbox.min[LIBY];
155  parent_x1 = bbox.max[LIBX];
156  parent_y1 = bbox.max[LIBY];
157 #else
158  parent->polygon().getBoundingRect(&parent_x, &parent_y, &parent_x1, &parent_y1);
159 #endif
160  /* If the child node is not already on that level. Reset its y coordinate. */
161  if (!NEAR_EQUAL(new_y, parent_y + POSITION_COORDINATE, 0.001)) {
162  new_y = parent_y + POSITION_COORDINATE;
163  } else {
164  maxX_level[level] = std::max(new_x1, maxX_level[level]);
165  return;
166  }
167  } else {
168  /* This means that it is a root node. */
169  new_y = POSITION_COORDINATE - 20.0;
170  }
171  new_x = maxX_level[level] + POSITION_COORDINATE;
172  new_x1 = new_x + X_WIDTH;
173  new_y1 = new_y + Y_HEIGHT;
174 
175  /* Construct a new polygon. */
176  Avoid::Point srcPt(new_x, new_y);
177  Avoid::Point dstPt(new_x1, new_y1);
178  Avoid::Rectangle shapeRect(srcPt, dstPt);
179 
180  /* Move the shape by setting its new polygon. */
181  dag->router->moveShape(child, shapeRect, true);
182  maxX_level[level] = std::max(new_x1, maxX_level[level]);
183 }
184 
185 
186 /**
187  * Routine that sets the layout of the graph.
188  * It recurses over all nodes of a tree, starting from the root node.
189  */
190 void
191 set_layout(_ged_dag_data *dag, bool has_parent, unsigned long int parent_id, unsigned long int child_id, unsigned int &level, std::vector<double> &maxX_level)
192 {
193  Avoid::ShapeRef *parent = NULL;
194  Avoid::ShapeRef *child = NULL;
195  std::list<unsigned int> children;
196 
197  /* Find references to the parent and child shapes. */
198  ObstacleList::const_iterator finish = dag->router->m_obstacles.end();
199  for (ObstacleList::const_iterator it = dag->router->m_obstacles.begin(); it != finish; ++it) {
200  if (has_parent && (*it)->id() == parent_id) {
201  parent = dynamic_cast<ShapeRef *>(*it);
202  } else if ((*it)->id() == child_id) {
203  child = dynamic_cast<ShapeRef *>(*it);
204 
205  /* Find the child's children. */
206  dag->router->attachedShapes(children, child_id, Avoid::runningTo);
207  }
208  if ((parent && child) || (child && !has_parent)) {
209  break;
210  }
211  }
212 
213  /* Set the position of the child node. */
214  position_node(dag, has_parent, parent, child, level, maxX_level);
215  dag->router->processTransaction();
216 
217  if (children.size() == 0) {
218  return;
219  } else {
220  has_parent = true;
221  std::list<unsigned int>::iterator it;
222 
223  level ++;
224  if (maxX_level.size() <= level) {
225  maxX_level.reserve(level + 1);
226  maxX_level.push_back(0.0);
227  }
228  for ( it=children.begin() ; it != children.end(); it++) {
229  set_layout(dag, has_parent, child_id, *it, level, maxX_level);
230  }
231  level --;
232  }
233 }
234 
235 
236 /**
237  * Add one object to the router of the 'dag' structure.
238  */
239 static Avoid::ShapeRef*
240 add_object(struct _ged_dag_data *dag, unsigned int id)
241 {
242  Avoid::Point srcPt(dag->object_nr * POSITION_COORDINATE + 2.0, dag->object_nr * POSITION_COORDINATE + 2.0);
243  Avoid::Point dstPt(POSITION_COORDINATE + dag->object_nr * POSITION_COORDINATE, POSITION_COORDINATE +
244  dag->object_nr * POSITION_COORDINATE);
245  Avoid::Rectangle shapeRect(srcPt, dstPt);
246  Avoid::ShapeRef *shapeRef = new Avoid::ShapeRef(dag->router, shapeRect, id);
247 
248  return shapeRef;
249 }
250 
251 
252 /**
253  * Method that frees the memory allocated for each value field of a bu_hash_entry structure.
254  */
255 void
256 free_hash_values(struct bu_hash_tbl *htbl)
257 {
258  struct bu_hash_entry *entry;
259  struct bu_hash_record rec;
260 
261  entry = bu_hash_tbl_first(htbl, &rec);
262 
263  while (entry) {
264  bu_free(bu_get_hash_value(entry), "hash entry");
265  entry = bu_hash_tbl_next(&rec);
266  }
267 }
268 
269 
270 /**
271  * Method that "decorates" each object depending on its type: primitive / combination / something else.
272  * A new entry is added into the objects_types hash table with the name of the object as a key and
273  * the type of the object as a value.
274  */
275 void
276 decorate_object(struct _ged_dag_data *dag, char *object_name, int object_type)
277 {
278  int new_entry;
279  struct bu_hash_entry *hsh_entry = bu_hash_tbl_add(dag->object_types, (unsigned char *)object_name, strlen(object_name) + 1, &new_entry);
280 
281  char *type = (char *)bu_malloc((size_t)1, "hash entry value");
282  sprintf(type, "%d", object_type);
283  bu_set_hash_value(hsh_entry, (unsigned char *)type);
284 }
285 
286 
287 /**
288  * Function which processes a combination node. I.e., it adds a new entry into the hash tables, if necessary.
289  * In this case, it also adds a Avoid::ShapeRef object to the graph. It also traverses its subtree, adds
290  * entries into the hash table for solid objects, if necessary. In this case as well, it also adds a
291  * Avoid::ShapeRef object to the graph.
292  */
293 static void
294 dag_comb(struct db_i *dbip, struct directory *dp, void *out, struct _ged_dag_data *dag, struct bu_hash_tbl *objects)
295 {
296  size_t i;
297  struct rt_db_internal intern;
298  struct rt_comb_internal *comb;
299 
300  struct output *o = (struct output *)out;
301  struct bu_hash_entry *prev = NULL;
302  struct bu_hash_entry *hsh_entry_comb = NULL;
303  unsigned long idx;
304  unsigned int comb_id, subnode_id;
305 
306  Avoid::ShapeRef *shapeRef1 = NULL;
307  Avoid::ShapeRef *shapeRef2 = NULL;
308  const unsigned int CENTRE = 1;
309 
310  if (rt_db_get_internal(&intern, dp, dbip, (fastf_t *)NULL, &rt_uniresource) < 0) {
311  bu_log("ERROR: Database read error, skipping %s\n", dp->d_namep);
312  }
313  comb = (struct rt_comb_internal *)intern.idb_ptr;
314 
315  /* Look for the ID of the current combination */
316  if ((hsh_entry_comb = bu_hash_tbl_find(objects, (unsigned char *)dp->d_namep, strlen(dp->d_namep) + 1, &prev, &idx))) {
317  comb_id = atoi((const char*)hsh_entry_comb->value);
318  }
319 
320  /* Add the combination name to the vector */
321  o->combinations.reserve(o->combinations.size() + 1);
322  std::string comb_name(dp->d_namep);
323  o->combinations.push_back(comb_name);
324 
325  /* Check if a shape was already created for this subnode. */
326  bool shape_exists = false;
327  ObstacleList::const_iterator finish = dag->router->m_obstacles.end();
328  for (ObstacleList::const_iterator it = dag->router->m_obstacles.begin(); it != finish; ++it) {
329  if ((*it)->id() == comb_id) {
330  /* Don't create another shape because it already exists a corresponding one.
331  * Get a reference to the shape that corresponds to the current node of the subtree.
332  */
333  shapeRef1 = dynamic_cast<ShapeRef *>(*it);
334  shape_exists = true;
335  break;
336  }
337  }
338  if (!shape_exists) {
339  /* Create a shape for the current node of the subtree */
340  dag->object_nr++;
341  shapeRef1 = add_object(dag, comb_id);
342  }
343 
344  /* FIXME: this is yet-another copy of the commonly-used code that
345  * gets a list of comb members. needs to return tabular data.
346  */
347  if (comb->tree) {
348  size_t node_count = 0;
349  size_t actual_count = 0;
350  struct bu_vls vls = BU_VLS_INIT_ZERO;
351  struct rt_tree_array *rt_tree_array = NULL;
352 
353  if (db_ck_v4gift_tree(comb->tree) < 0) {
355  if (db_ck_v4gift_tree(comb->tree) < 0) {
356  bu_log("INTERNAL_ERROR: Cannot flatten tree of [%s] for listing", dp->d_namep);
357  return;
358  }
359  }
360 
361  node_count = db_tree_nleaves(comb->tree);
362  if (node_count > 0) {
363  rt_tree_array = (struct rt_tree_array *)bu_calloc(node_count, sizeof(struct rt_tree_array), "tree list");
364  actual_count = (struct rt_tree_array *)db_flatten_tree(rt_tree_array, comb->tree, OP_UNION, 1, &rt_uniresource) - rt_tree_array;
365  BU_ASSERT_SIZE_T(actual_count, ==, node_count);
366  comb->tree = TREE_NULL;
367  } else {
368  actual_count = 0;
369  rt_tree_array = NULL;
370  }
371 
372  bu_log("%d subnode(s)\n", actual_count);
373 
374  for (i = 0; i < actual_count; i++) {
375  char op;
376 
377  switch (rt_tree_array[i].tl_op) {
378  case OP_UNION:
379  op = DB_OP_UNION;
380  break;
381  case OP_INTERSECT:
382  op = DB_OP_INTERSECT;
383  break;
384  case OP_SUBTRACT:
385  op = DB_OP_SUBTRACT;
386  break;
387  default:
388  op = '?';
389  break;
390  }
391 
392  bu_log("\t\"%s\" -> \"%s\" [ label=\"%c\" ];\n", dp->d_namep, rt_tree_array[i].tl_tree->tr_l.tl_name, op);
393  struct bu_hash_entry *hsh_entry;
394  hsh_entry = bu_hash_tbl_find(objects, (unsigned char *)rt_tree_array[i].tl_tree->tr_l.tl_name, strlen(rt_tree_array[i].tl_tree->tr_l.tl_name) + 1, &prev, &idx);
395 
396  if (hsh_entry) {
397  subnode_id = atoi((const char*)hsh_entry->value);
398 
399  /* Check if a shape was already created for this subnode. */
400  shape_exists = false;
401  finish = dag->router->m_obstacles.end();
402  for (ObstacleList::const_iterator it = dag->router->m_obstacles.begin(); it != finish; ++it) {
403  if ((*it)->id() == subnode_id) {
404  /* Don't create another shape because it already exists a corresponding one.
405  * Get a reference to the shape that corresponds to the current node of the subtree.
406  */
407  shapeRef2 = dynamic_cast<ShapeRef *>(*it);
408  shape_exists = true;
409  break;
410  }
411  }
412  if (!shape_exists) {
413  /* Create a shape for the current node of the subtree */
414  dag->object_nr++;
415  shapeRef2 = add_object(dag, subnode_id);
416  }
417 
418  /* Create connection pins on shapes for linking the parent node with the subnode. */
419  new Avoid::ShapeConnectionPin(shapeRef1, CENTRE, Avoid::ATTACH_POS_CENTRE, Avoid::ATTACH_POS_CENTRE);
420  new Avoid::ShapeConnectionPin(shapeRef2, CENTRE, Avoid::ATTACH_POS_CENTRE, Avoid::ATTACH_POS_CENTRE);
421 
422  /* Create connector from each shape shapeRef2 to the input pin on shapeRef1. */
423  Avoid::ConnEnd dstEnd(shapeRef1, CENTRE);
424  Avoid::ConnEnd srcEnd(shapeRef2, CENTRE);
425  dag->last_connref_id++;
426  Avoid::ConnRef *connRef = new Avoid::ConnRef(dag->router, srcEnd, dstEnd, dag->last_connref_id);
427 
428  connRef->setCallback(conn_callback, connRef);
429  dag->router->processTransaction();
430  }
431 
432  db_free_tree(rt_tree_array[i].tl_tree, &rt_uniresource);
433  }
434  bu_vls_free(&vls);
435 
436  if (rt_tree_array)
437  bu_free((char *)rt_tree_array, "printnode: rt_tree_array");
438  }
439 
440  rt_db_free_internal(&intern);
441 }
442 
443 
444 /**
445  * Method that figures out the type of an object, constructs its corresponding shape in a graph
446  * and adds it to the corresponding list of names.
447  */
448 void
449 put_me_in_a_bucket(struct directory *dp, struct directory *ndp, struct db_i *dbip, struct bu_hash_tbl *objects, struct output *o, struct _ged_dag_data *dag)
450 {
451  struct bu_hash_entry *prev = NULL;
452  unsigned long idx;
453  unsigned int object_id;
454  struct bu_hash_entry *hsh_entry;
455  struct bu_vls dp_name_vls = BU_VLS_INIT_ZERO;
456 
457  bu_vls_sprintf(&dp_name_vls, "%s%s", "", dp->d_namep);
458 
459  if (dp->d_flags & RT_DIR_SOLID) {
460  bu_log("Adding PRIMITIVE object [%s]\n", bu_vls_addr(&dp_name_vls));
461 
462  /* Check if this solid is in the objects list. */
463  prev = NULL;
464  hsh_entry = bu_hash_tbl_find(objects, (unsigned char *)dp->d_namep, strlen(dp->d_namep) + 1, &prev, &idx);
465 
466  if (hsh_entry) {
467  object_id = atoi((const char*)hsh_entry->value);
468 
469  o->primitives.reserve(o->primitives.size() + 1);
470  std::string name((const char *)dp->d_namep);
471  o->primitives.push_back(name);
472 
473  /* "Decorate" the object. Add its name and type into the hash table. */
474  decorate_object(dag, dp->d_namep, dp->d_flags);
475 
476  /* Check if a shape was already created for this subnode. */
477  bool shape_exists = false;
478  ObstacleList::const_iterator finish = dag->router->m_obstacles.end();
479  for (ObstacleList::const_iterator it = dag->router->m_obstacles.begin(); it != finish; ++it) {
480  if ((*it)->id() == object_id) {
481  /* Don't create another shape because it already exists a corresponding one. */
482  shape_exists = true;
483  break;
484  }
485  }
486  if (!shape_exists) {
487  /* Create a shape for the current node of the subtree */
488  dag->object_nr++;
489  add_object(dag, object_id);
490  dag->router->processTransaction();
491  }
492  }
493  } else if (dp->d_flags & RT_DIR_COMB) {
494  bu_log("Adding COMB object [%s]\n", bu_vls_addr(&dp_name_vls));
495  dag_comb(dbip, ndp, o, dag, objects);
496 
497  /* "Decorate" the object. Add its name and type into the hash table. */
498  decorate_object(dag, dp->d_namep, dp->d_flags);
499  } else {
500  bu_log("Something else: [%s]\n", bu_vls_addr(&dp_name_vls));
501  prev = NULL;
502  hsh_entry = bu_hash_tbl_find(objects, (unsigned char *)dp->d_namep, strlen(dp->d_namep) + 1, &prev, &idx);
503 
504  if (hsh_entry) {
505  o->non_geometries.reserve(o->non_geometries.size() + 1);
506  std::string name((const char *)dp->d_namep);
507  o->non_geometries.push_back(name);
508 
509  /* "Decorate" the object. Add its name and type into the hash table. */
510  decorate_object(dag, dp->d_namep, dp->d_flags);
511  }
512  }
513 
514  bu_vls_free(&dp_name_vls);
515 }
516 
517 
518 /**
519  * Add the list of objects in the master hash table "objects".
520  */
521 int
522 add_objects(struct ged *gedp, struct _ged_dag_data *dag)
523 {
524  struct directory *dp = NULL, *ndp = NULL;
525  struct bu_vls dp_name_vls = BU_VLS_INIT_ZERO;
526  int i, object_nr = 0;
527  struct output o;
528  struct bu_hash_tbl *objects;
529  struct bu_hash_entry *hsh_entry1;
530  struct bu_hash_entry *prev = NULL;
531  unsigned long idx;
532  struct db_i *dbip = gedp->ged_wdbp->dbip;
533 
534  /* Create the master "objects" hash table. It will have at most 64 entries. */
535  objects = bu_hash_tbl_create(1);
536  dag->ids = bu_hash_tbl_create(1);
537  dag->object_types = bu_hash_tbl_create(1);
538 
539  /* Sets a spacing distance for overlapping orthogonal connectors to be nudged apart. */
540 #if defined LIBAVOID_LATEST_API
541  dag->router->setRoutingParameter(idealNudgingDistance, 25);
542 #else
543  dag->router->setOrthogonalNudgeDistance(25);
544 #endif
545 
546  /* Number of Avoid::ShapeRef objects in the graph. These corresponds to the ones in the database. */
547  dag->object_nr = 0;
548 
549  /*
550  * This value is used for establishing the starting id for the Avoid::ConnRef objects.
551  * It starts with the value <nr_of_objects_in_the_database>.
552  * It is incremented every time a new Avoid::ConnRef is added to the graph.
553  * It is needed in order to avoid the overlapping with the Avoid::ShapeRef ids when adding a Avoid::ConnRef to the graph.
554  */
555  dag->last_connref_id = gedp->ged_wdbp->dbip->dbi_nrec;
556 
557  /* Traverse the database 'gedp' and for each object add its name and an ID into the "objects" hash table. */
558  for (i = 0; i < RT_DBNHASH; i++) {
559  for (dp = gedp->ged_wdbp->dbip->dbi_Head[i]; dp != RT_DIR_NULL; dp = dp->d_forw) {
560  bu_vls_sprintf(&dp_name_vls, "%s%s", "", dp->d_namep);
561  ndp = db_lookup(gedp->ged_wdbp->dbip, bu_vls_addr(&dp_name_vls), 1);
562  if (ndp) {
563  /* Check if this object is already in the hash table. If not, add it to the objects hash table. */
564  int new_entry;
565 
566  hsh_entry1 = bu_hash_tbl_find(objects, (unsigned char *)dp->d_namep, strlen(dp->d_namep) + 1, &prev, &idx);
567 
568  if (!hsh_entry1) {
569  bu_log("Adding object [%s]\n", bu_vls_addr(&dp_name_vls));
570 
571  /* This object hasn't been registered yet. Add it into the solids hash table and create a shape for it. */
572  object_nr++;
573 
574  struct bu_hash_entry *hsh_entry = bu_hash_tbl_add(objects, (unsigned char *)dp->d_namep, strlen(dp->d_namep) + 1, &new_entry);
575  char *id = (char *)bu_malloc((size_t)6, "hash entry value");
576  sprintf(id, "%d", object_nr);
577 
578  /* Set the id value for this object */
579  bu_set_hash_value(hsh_entry, (unsigned char *)id);
580 
581  /* Add the ID of this object as a key and its name as a value. */
582  hsh_entry = bu_hash_tbl_add(dag->ids, (unsigned char *)id, strlen(id) + 1, &new_entry);
583  bu_set_hash_value(hsh_entry, (unsigned char *)dp->d_namep);
584  }
585  } else {
586  bu_log("ERROR: Unable to locate [%s] within input database, skipping.\n", bu_vls_addr(&dp_name_vls));
587  }
588  }
589  }
590 
591  /* Traverse the database 'gedp' and for each object check its type (primitive, combination or non-geometry)
592  * and add its name into the corresponding list.
593  */
594  for (i = 0; i < RT_DBNHASH; i++) {
595  for (dp = gedp->ged_wdbp->dbip->dbi_Head[i]; dp != RT_DIR_NULL; dp = dp->d_forw) {
596  bu_vls_sprintf(&dp_name_vls, "%s%s", "", dp->d_namep);
597  ndp = db_lookup(gedp->ged_wdbp->dbip, bu_vls_addr(&dp_name_vls), 1);
598  if (ndp) {
599  put_me_in_a_bucket(dp, ndp, dbip, objects, &o, dag);
600  } else {
601  bu_log("ERROR: Unable to locate [%s] within input database, skipping.\n", bu_vls_addr(&dp_name_vls));
602  }
603  }
604  }
605 
606  bu_log("Added %d objects.\n", dag->object_nr);
607 
608  /* Free memory. */
609  bu_vls_free(&dp_name_vls);
610  free_hash_values(objects);
611  bu_hash_tbl_free(objects);
612 
613  return GED_OK;
614 }
615 
616 
617 /**
618  * This routine provides the name of the objects in a database along with their
619  * type and positions within the graph.
620  */
621 HIDDEN void
622 graph_positions(struct ged *gedp, struct _ged_dag_data *dag)
623 {
624  /* The bounding positions of the rectangle corresponding to one object. */
625  double minX;
626  double minY;
627  double maxX;
628  double maxY;
629 
630  add_objects(gedp, dag);
631 
632  /* Find the root nodes. */
633  std::vector<unsigned int> root_ids = find_roots(dag);
634  std::vector<double> maxX_level;
635  unsigned int level;
636  unsigned int size = root_ids.size();
637 
638  /* Traverse the root nodes and for each tree set the positions of all the nodes. */
639  for (unsigned int i = 0; i < size; i++) {
640  char *root = (char *)bu_malloc((size_t)6, "hash entry value");
641  sprintf(root, "%u", root_ids[i]);
642  struct bu_hash_entry *prev_root = NULL;
643  unsigned long idx_root;
644  struct bu_hash_entry *hsh_entry_root = bu_hash_tbl_find(dag->ids, (unsigned char *)root, strlen(root) + 1, &prev_root, &idx_root);
645 
646  if (hsh_entry_root) {
647  level = 0;
648  if (i == 0) {
649  /* First root node: set the maximum X coordinate to be 0.0. */
650  maxX_level.reserve(1);
651  maxX_level.push_back(0.0);
652  }
653 
654  /* Set the layout for the tree that starts with this root node. */
655  set_layout(dag, false, root_ids[i], root_ids[i], level, maxX_level);
656  }
657  }
658 
659  /* Traverse each shape within the graph and pass on the name, type and coordinates
660  * of the object.
661  */
662  ObstacleList::const_iterator finish = dag->router->m_obstacles.end();
663  for (ObstacleList::const_iterator it = dag->router->m_obstacles.begin(); it != finish; ++it) {
664  char *id = (char *)bu_malloc((size_t)6, "hash entry value");
665  sprintf(id, "%d", (*it)->id());
666 
667  struct bu_hash_entry *prev = NULL;
668  unsigned long idx;
669  struct bu_hash_entry *hsh_entry = bu_hash_tbl_find(dag->ids, (unsigned char *)id, strlen(id) + 1, &prev, &idx);
670  if (hsh_entry) {
671 #if defined LIBAVOID_LATEST_API
672  Box bbox = (*it)->polygon().offsetBoundingBox(0);
673  minX = bbox.min[LIBX];
674  minY = bbox.min[LIBY];
675  maxX = bbox.max[LIBX];
676  maxY = bbox.max[LIBY];
677 #else
678  (*it)->polygon().getBoundingRect(&minX, &minY, &maxX, &maxY);
679 #endif
680  prev = NULL;
681  struct bu_hash_entry *hsh_entry_type = bu_hash_tbl_find(dag->object_types, hsh_entry->value,
682  strlen((char *)hsh_entry->value) + 1, &prev, &idx);
683  if (hsh_entry_type) {
684  bu_vls_printf(gedp->ged_result_str, "%s %s %f %f %f %f\n", hsh_entry->value, hsh_entry_type->value, minX,
685  minY, maxX, maxY);
686  }
687  }
688  }
689 }
690 
691 
692 /**
693  * Routine that sets a list of names, types, and positions that correspond to the objects in the gedp database.
694  * The positions refer to the coordinates that determine the nodes within the graph.
695  * This routine is called when the "positions" subcommand is used.
696  */
697 int
698 _ged_graph_positions(struct ged *gedp)
699 {
700  struct _ged_dag_data *dag;
701 
702  BU_ALLOC(dag, struct _ged_dag_data);
703  dag->router = new Avoid::Router(Avoid::PolyLineRouting);
704 
705  /* Get the name, type and position within the graph for each object. */
706  graph_positions(gedp, dag);
707  bu_free(dag, "free DAG");
708 
709  return GED_OK;
710 }
711 
712 
713 /**
714  * Routine that sets a list of names, types, and positions that correspond to the objects in the gedp database,
715  * along with the positions of the edges that connect the nodes from the graph.
716  * The positions refer to the coordinates that determine the nodes within the graph.
717  * This routine is called when the "show" subcommand is used.
718  */
719 int
720 _ged_graph_show(struct ged *gedp)
721 {
722  struct _ged_dag_data *dag;
723 
724  BU_ALLOC(dag, struct _ged_dag_data);
725  dag->router = new Avoid::Router(Avoid::PolyLineRouting);
726 
727  /* Get the name, type and position within the graph for each object. */
728  graph_positions(gedp, dag);
729 
730  /* Provide the positions of the points via which the connection's route passes. */
731  double x, y;
732  Avoid::ConnRefList::const_iterator fin = dag->router->connRefs.end();
733  for (Avoid::ConnRefList::const_iterator i = dag->router->connRefs.begin(); i != fin; ++i) {
734  bu_vls_printf(gedp->ged_result_str, "edge\n");
735  Avoid::Polygon polyline = (*i)->displayRoute();
736  unsigned int size = polyline.ps.size();
737 
738  for (unsigned int j = 0; j < size; j ++) {
739  x = polyline.ps[j].x;
740  y = polyline.ps[j].y;
741  bu_vls_printf(gedp->ged_result_str, "%f %f\n", x, y);
742  }
743  }
744  bu_free(dag, "free DAG");
745 
746  return GED_OK;
747 }
748 
749 
750 /**
751  * The libged graph function.
752  * This function constructs the graph structure corresponding to the given database.
753  */
754 int
755 ged_graph(struct ged *gedp, int argc, const char *argv[])
756 {
757  const char *cmd = argv[0];
758  const char *subcommand;
759  static const char *usage = "subcommand\n";
760 
763  GED_CHECK_ARGC_GT_0(gedp, argc, GED_ERROR);
764 
765  /* initialize result */
766  bu_vls_trunc(gedp->ged_result_str, 0);
767 
768  /* Didn't provide any subcommand. Must be wanting help */
769  if (argc != 2) {
770  bu_vls_printf(gedp->ged_result_str, "Usage: %s %sAvailable subcommands: ", cmd, usage);
771 
772  /* Output the available subcommands. */
773  for (int i = 0; graph_subcmds[i].name; ++i) {
774  bu_vls_printf(gedp->ged_result_str, "%s ", graph_subcmds[i].name);
775  }
776  return GED_ERROR;
777  } else if (argc == 2) {
778  /* Determine subcommand. */
779  subcommand = argv[1];
780 
781  /* Check if it's the "show" subcommand. */
782  if (BU_STR_EQUAL(graph_subcmds[0].name, subcommand)) {
783  return _ged_graph_show(gedp);
784  } else if (BU_STR_EQUAL(graph_subcmds[1].name, subcommand)) {
785  /* It is the "positions" subcommand. */
786  return _ged_graph_positions(gedp);
787  } else {
788  bu_vls_printf(gedp->ged_result_str, "%s: %s is not a known subcommand!\nAvailable subcommands: ", cmd, subcommand);
789 
790  /* Output the available subcommands. */
791  for (int i = 0; graph_subcmds[i].name; ++i) {
792  bu_vls_printf(gedp->ged_result_str, "%s ", graph_subcmds[i].name);
793  }
794  return GED_ERROR;
795  }
796  }
797  return GED_OK;
798 }
799 #define PARALLEL BRLCAD_PARALLEL
800 #undef BRLCAD_PARALLEL
801 
802 
803 #else
804 
805 #include "ged_private.h"
806 
807 /**
808  * Dummy graph function in case no Adaptagrams library is found.
809  */
810 int
811 ged_graph(struct ged *gedp, int argc, const char *argv[])
812 {
814  GED_CHECK_ARGC_GT_0(gedp, argc, GED_ERROR);
815 
816  /* Initialize result */
817  bu_vls_trunc(gedp->ged_result_str, 0);
818 
819  bu_vls_printf(gedp->ged_result_str, "%s : ERROR This command is disabled due to the absence of Adaptagrams library",
820  argv[0]);
821  return GED_ERROR;
822 }
823 
824 
825 #endif
826 
827 
828 /*
829  * Local Variables:
830  * tab-width: 8
831  * mode: C
832  * indent-tabs-mode: t
833  * c-file-style: "stroustrup"
834  * End:
835  * ex: shiftwidth=4 tabstop=8
836  */
void usage(struct ged *gedp)
Definition: coil.c:315
#define GED_OK
Definition: ged.h:55
char * d_namep
pointer to name string
Definition: raytrace.h:859
Definition: raytrace.h:800
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
int rt_db_get_internal(struct rt_db_internal *ip, const struct directory *dp, const struct db_i *dbip, const mat_t mat, struct resource *resp)
Definition: dir.c:76
#define RT_DBNHASH
hash table is an array of linked lists with this many array pointer elements (Memory use for 32-bit: ...
Definition: raytrace.h:755
unsigned char * bu_get_hash_value(const struct bu_hash_entry *hsh_entry)
Definition: hash.c:170
size_t db_tree_nleaves(const union tree *tp)
Definition: db_comb.c:99
void bu_hash_tbl_free(struct bu_hash_tbl *hsh_tbl)
Definition: hash.c:263
Definition: ged.h:338
struct db_i * dbip
Definition: raytrace.h:1266
Definition: clone.c:90
void bu_vls_trunc(struct bu_vls *vp, int len)
Definition: vls.c:198
#define GED_CHECK_ARGC_GT_0(_gedp, _argc, _flags)
Definition: ged.h:202
struct directory * db_lookup(const struct db_i *, const char *name, int noisy)
Definition: db_lookup.c:153
void bu_set_hash_value(struct bu_hash_entry *hsh_entry, unsigned char *value)
Definition: hash.c:160
struct bu_hash_entry * bu_hash_tbl_first(const struct bu_hash_tbl *hsh_tbl, struct bu_hash_record *rec)
Definition: hash.c:296
union tree * tl_tree
Definition: raytrace.h:1247
struct rt_wdb * ged_wdbp
Definition: ged.h:340
Header file for the BRL-CAD common definitions.
unsigned char * value
Definition: hash.h:47
int ged_graph(struct ged *gedp, int argc, const char *argv[])
Definition: dag.cpp:811
Definition: hash.h:44
struct directory * d_forw
link to next dir entry
Definition: raytrace.h:864
#define GED_ERROR
Definition: ged.h:61
#define HIDDEN
Definition: common.h:86
void * bu_malloc(size_t siz, const char *str)
Definition: malloc.c:314
struct rt_tree_array * db_flatten_tree(struct rt_tree_array *rt_tree_array, union tree *tp, int op, int avail, struct resource *resp)
Definition: db_comb.c:138
if(share_geom)
Definition: nmg_mod.c:3829
void bu_vls_free(struct bu_vls *vp)
Definition: vls.c:248
#define OP_SUBTRACT
Binary: L subtract R.
Definition: raytrace.h:1129
void db_non_union_push(union tree *tp, struct resource *resp)
Definition: db_tree.c:1426
size_t dbi_nrec
PRIVATE: # records after db_scan()
Definition: raytrace.h:817
#define OP_INTERSECT
Binary: L intersect R.
Definition: raytrace.h:1128
struct resource rt_uniresource
default. Defined in librt/globals.c
Definition: globals.c:41
#define GED_CHECK_DATABASE_OPEN(_gedp, _flags)
Definition: ged.h:114
#define BU_ALLOC(_ptr, _type)
Definition: malloc.h:223
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
#define RT_DIR_SOLID
this name is a solid
Definition: raytrace.h:883
void bu_vls_sprintf(struct bu_vls *vls, const char *fmt,...) _BU_ATTR_PRINTF23
Definition: vls.c:707
#define TREE_NULL
Definition: raytrace.h:1181
void db_free_tree(union tree *tp, struct resource *resp)
Definition: db_tree.c:1296
char * tl_name
Name of this leaf (bu_strdup'ed)
Definition: raytrace.h:1174
struct bu_hash_entry * bu_hash_tbl_add(struct bu_hash_tbl *hsh_tbl, const unsigned char *key, int key_len, int *new_entry)
Definition: hash.c:188
goto out
Definition: nmg_mod.c:3846
char * bu_vls_addr(const struct bu_vls *vp)
Definition: vls.c:111
struct bu_vls * ged_result_str
Definition: ged.h:357
struct tree::tree_db_leaf tr_l
struct bu_hash_entry * bu_hash_tbl_next(struct bu_hash_record *rec)
Definition: hash.c:327
#define RT_DIR_COMB
combination
Definition: raytrace.h:884
struct directory * dbi_Head[RT_DBNHASH]
Definition: raytrace.h:814
Definition: op.h:35
union tree * tree
Leading to tree_db_leaf leaves.
Definition: raytrace.h:938
void bu_vls_printf(struct bu_vls *vls, const char *fmt,...) _BU_ATTR_PRINTF23
Definition: vls.c:694
#define RT_DIR_NULL
Definition: raytrace.h:875
#define BU_ASSERT_SIZE_T(_lhs, _relation, _rhs)
Definition: defines.h:253
bn_poly_t output[3]
Definition: bn_poly_add.c:36
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
#define BU_VLS_INIT_ZERO
Definition: vls.h:84
struct bu_hash_tbl * bu_hash_tbl_create(unsigned long tbl_size)
Definition: hash.c:48
#define GED_CHECK_READ_ONLY(_gedp, _flags)
Definition: ged.h:181
int d_flags
flags
Definition: raytrace.h:869
struct bu_hash_entry * bu_hash_tbl_find(const struct bu_hash_tbl *hsh_tbl, const unsigned char *key, int key_len, struct bu_hash_entry **prev, unsigned long *idx)
Definition: hash.c:95
Definition: vls.h:56
double fastf_t
Definition: defines.h:300
#define OP_UNION
Binary: L union R.
Definition: raytrace.h:1127
int db_ck_v4gift_tree(const union tree *tp)
Definition: db_comb.c:927
void rt_db_free_internal(struct rt_db_internal *ip)
Definition: dir.c:216
#define BU_STR_EQUAL(s1, s2)
Definition: str.h:126