tools for drawing a DAG

M

Mohun Biswas

Just looking for pointers to likely technologies here ... I have a Java
webapp running in Tomcat. It manages a relational database, in which
some of the tables can be interpreted as a directed acyclic graph (DAG).
For those who aren't familiar with the term, think of it as your family
tree, with you at the bottom, parents above, grandparents above them,
and so on to an arbitrary starting point (though in my app the number of
immediate ancestors is not limited to two). AKA a dependency graph.

I need to display this data graphically within the client browser, so
I'm looking for any SW package that will help draw a DAG nicely. From
what research I've been able to do, I think SVG would be the preferred
output format (this is an intranet app so I have no problem requiring a
browser plugin) but other formats, including server-rendered types like
JPEG, might work too.

So the dream would be something that interfaces with an RDBMS on input
and produces SVG on output though I doubt things will go quite that
smoothly. I've dug up JGraph, jfreechart, and a few others but have seen
no indication they can do a DAG-style format. But if any of you know one
that can, tell me which and I'll dig deeper.

Come to think of it, what with genealogy being an internet killer app, I
wonder if there are actual family-tree charting packages available in
source form?

TIA,
MB
 
H

Harald Hein

Mohun Biswas said:
Just looking for pointers to likely technologies here ... I have a
Java webapp running in Tomcat. It manages a relational database,
in which some of the tables can be interpreted as a directed
acyclic graph (DAG). For those who aren't familiar with the term,
think of it as your family tree, with you at the bottom, parents
above, grandparents above them, and so on to an arbitrary starting
point (though in my app the number of immediate ancestors is not
limited to two). AKA a dependency graph.

Sounds like you are confusing a DAG with a special form of a DAG, a
directed tree. A directed tree is a connected DAG, but not every DAG is
a directed tree. If your family tree is indeed a DAG and not just a
directed tree, then you might want to consider calling the police and
reporting a crime (it depends on the distance of the edges, of course)
:)

If you take such things as divorces and re-marriage into account, your
family tree can become rather interesting, too.
So the dream would be something that interfaces with an RDBMS on
input and produces SVG on output though I doubt things will go
quite that smoothly. I've dug up JGraph, jfreechart, and a few
others but have seen no indication they can do a DAG-style format.
But if any of you know one that can, tell me which and I'll dig
deeper.

Algorithms for tree drawing are relatively simple, and you can find
them in any textbook about graph drawing. Swing's JTree component does
tree drawing, although JTree's layout is limited.

There are also many algorithms for DAG drawing. But AFAIK there is no
general solution to always get the "best" drawing. The algorithms are
more complex, and usually just optimize some aspects of a DAG's
representation. Again many pages of paper have been filled with such
algorithms.
Come to think of it, what with genealogy being an internet killer
app,

Is it? Thanks for waking me up.

HH
 
M

Mohun Biswas

Harald said:
Sounds like you are confusing a DAG with a special form of a DAG, a
directed tree.

A deliberate oversimplification "For those who aren't familiar with the
term ...".
Algorithms for tree drawing are relatively simple, and you can find
them in any textbook about graph drawing. Swing's JTree component does
tree drawing, although JTree's layout is limited.

There are also many algorithms for DAG drawing. But AFAIK there is no
general solution to always get the "best" drawing. The algorithms are
more complex, and usually just optimize some aspects of a DAG's
representation. Again many pages of paper have been filled with such
algorithms.

All true but I'm looking for implementations, not algorithms.
Is it? Thanks for waking me up.

Seriously, this is one of those corner industries that's exploded with
the help the Internet provides in research and publication. Way off
topic here, so let's not go farther with it, and not something I have
any interest in. But you might be surprised how big it is. I certainly was.

MB
 
Y

yGuy

hi there,
All true but I'm looking for implementations, not algorithms.

yFiles, the Java Graph drawing library from yWorks has just the right
tools you are looking for I would say.

I suggest you try the Webstart Application yEd (alternatively the
applet version). This intuitive Java Graph Editor is built on top of
the yFiles API and demonstrates quite a lot of the features yFiles
offers. In your case I would suggest using a the "Hierarchic" layout
style. Just create a graph using the GUI and let yFiles automatically
layout the drawing. I am sure you will be impressed. BTW yEd supports
jpg, gif, and SVG export (through the library and in case of the SVG
export a free extension package), which should be exactly what you
need.

here are the links:

http://www.yworks.com yWorks main page
http://www.yworks.com/products/yfiles the yFiles Java Graph Drawing
library homepage
http://www.yworks.com/products/yed the free graph editor
application

maybe you will want to have a look at the gallery first:
http://www.yworks.com/en/products_yfiles_practicalinfo_gallery.htm

You can evaluate the yFiles API at no cost. Just go to the yFiles
homepage and look for the "evaluate now" button. You will receive an
evaluation version within 24 hours usually.

greetings, sebastian mueller
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,733
Messages
2,569,440
Members
44,832
Latest member
GlennSmall

Latest Threads

Top