0

I have a database with information about many hypothetical people. This data is oriented for creating a graph connecting related people together. This graph is to represent a genealogical tree, in an appropriate c++ data structure. So far, so good. I have my data structure holding information about a family, with each person being a node, all connected appropriately in a tree.

Now, here is the problem, I am lost in how to go about generating visual data for this family graph. For any given family, I need to generate a typical graph as you would see in a traditional genealogical tree. I intend to render the data with OpenGL and have everything set up in order to do it. My only problem is how to generate the correct positions and sizes for each person's rectangle, so in the end there are no overlaps and every generation of people sits at the same vertical position. Then, I have to add the traditional lines connecting each node in visual data, but that shouldnt be a big problem.

Are there any lightweight libraries prepared to do this function or can someone help me achieve the algorithm to solve this? Thanks

DevilWithin
  • 103
  • 2
  • Whenever I'm working in C++, I always try and look to see if Qt has anything I can use. That library has been very, very helpful to me. They have a nice 2D graphing library that would help you out. It looks like some of the Qt 5 functionality is 3D, but I'm not positive. – Brian Stinar Oct 22 '13 at 04:31

2 Answers2

1

I recommend AT&T GraphVis library. This library is used by Doxygen to draw its inheritance diagrams, and call trees.

You could also search for "c++ tree draw".

Thomas Matthews
  • 56,849
  • 17
  • 98
  • 154
  • This is what I use by default when I have a nice collection of nodes and edges in Python - I haven't tried the C++ bindings yet. – Brian Stinar Oct 22 '13 at 04:27
-1

Another way to state the problem would be: how to determine node layout in a hierarchal directed graph such that there is no overlap and nodes at the same hierarchy are placed at the same level? (Here nodes correspond to family members and generation specifies the hierarchy).

While GraphVis can provide a layout solution, a newer approach than algorithms used in GraphVis is the Dig-CoLa (directed graph layout through constrained energy minimization) method described in Dwyer et al. 2005. The advantage of Dig-Cola is that it also deals with certain corner cases (e.g cycles) gracefully and avoids introducing hierarchy not induced by the original data in such cases.

The underlying idea of this method is to formulate and solve the layout problem as a constrained optimization problem by minimizing the stress (or energy) function based on the node positions under constraints induced by the hierarchy information.

Original Dig-Cola paper for more information:

Dwyer, Tim, and Yehuda Koren. "Dig-CoLa: directed graph layout through constrained energy minimization." IEEE Symposium on Information Visualization, 2005. INFOVIS 2005.. IEEE, 2005. (Full text currently available here)

The author also provides some examples and code for this method (and later extensions) here.

Glorfindel
  • 21,988
  • 13
  • 81
  • 109
Mukund Raj
  • 19
  • 6
  • While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - [From Review](/review/low-quality-posts/13406165) – eisbehr Aug 21 '16 at 14:13
  • Okay, I edited the answer to add details from the referenced paper. – Mukund Raj Aug 22 '16 at 00:42