My company is developing a graph drawing too in java, but we have
found it to be difficult to find good, suitable layout algorithms to
automatically arrange the graphs. So I would need help to find
specifications for good algorithms. We have engineers in-house who can
write the java implementation based on those algorithms. |
Request for Question Clarification by
mathtalk-ga
on
25 Jun 2003 14:04 PDT
Hi, kkilpi-ga:
By "graph drawing" I assume you mean two-dimensional layouts for nodes
and edges. This is a very interesting topic, but I'd like to know
what a priori restrictions will exist (if any) on the graphs to be
drawn.
Not all graphs are planar. That is, some graphs cannot be drawn in
two-dimensions unless edges are allowed to intersect (crossover) in
some manner. While certain special kinds of graphs, like trees, are
always planar, one might want to start with an efficient algorithm to
determine whether a graph is planar or not.
Many graph-drawing tasks have some implied "parallelisms" that are
important to communicate visually. I know that if I were "shopping"
for a graph-drawing tool, I'd want to be able to apply "hints" that
help the layout algorithm to succeed in displaying such parallel nodes
clearly.
I'd be happy to perform an algorithmic literature search for you,
sprinkled with my own thoughts. If there are any special requirements
that need to be addressed, I'd appreciate having your input.
regards, mathtalk-ga
|
Clarification of Question by
kkilpi-ga
on
26 Jun 2003 04:04 PDT
Hello Mathtalk-ga,
Yes, by "graph drawing" I ment two-dimensional layout for nodes and
edges. There are no restrictions how the nodes can be positioned or
the edges crossover each others. The only limitation is that edges
(that we call links) are always direct lines, so curves or multipoint
paths/lines are not allowed. Infact I could use a similar product
(desgned for a little bit different purpose) as an example, please see
http://www.anacubis.com/googledemo/googledemo.html# .
I didn't quite understand what "applying hints" means in practice,
could you explain the idea please?
I'll be looking forward to hear more from you and review the
algorithms you recommend.
Best regards,
Kalle Kilpi
|
Request for Question Clarification by
mathtalk-ga
on
26 Jun 2003 08:05 PDT
Hi, Kalle:
Thanks for the prompt clarification. What I'm thinking of with
"hints" are aspects of the diagram that a human user might want to
emphasize in the layout. Of course I'm speaking now at a heuristic
rather than algorithmic level, but consider that a "graph drawing
tool" could be designed according to your description which always
draws a very similar picture -- place all the nodes in a circular
arrangement and simply connect the appropriate edges with chords that
cross the circle. Something of the sort is being used in one of the
diagrams shown at that illustrative link you provided.
While any graph could be drawn in this fashion, I'd question its
usefulness as a communications device. In the anacubis GoogleDemo the
information is provided without any specific human "conceptualization"
as a machine constructed map. In that setting perhaps a "one size
fits all" approach is acceptable.
Consider a different sort of layout problem, involving the tables of a
relational database. Between tables (as nodes) one may have foreign
key relationships (as edges). Most automated drawing routines, e.g.
those bundled into MS Access, do a poor job of "grouping" tables that
have a common purpose, as is quite understandable. Visually grouping
tables which collectively define an "entity" in the logical database
schema is an important property of a layout meant to communicate the
database's conceptual design.
What is at issue are the considerations that make a "good algorithm".
Perhaps the "all nodes in a circle" approach will work well for you,
but if not then it may help you to identify these extra
considerations.
regards, mathtalk-ga
|
Clarification of Question by
kkilpi-ga
on
26 Jun 2003 08:49 PDT
Thanks for your reply.
Did I understood correctly that simplified meaning of giving hints
would be that user could maually drag nodes to certain positions and
the algorithm would use those "hits" when it arranges the nodes? If so
that would be a good idea, but the algorithm is also often applied to
graphs before the user even gets to see the graph (if new data -nodes
& edges- are loaded from to the application) in addition to arranging
graphs that user has already modified.
I agree that the single circle layout in the example reference isn't
very usefull approach, but they also have some other algorithms that
provide pretty good result.
As one pilot client put it in to words "our development team is pretty
technology oriented" and I would be very glad if you could recommend
an user friendly approach for the arrangement.
Thank you,
Kalle
|
Request for Question Clarification by
mathtalk-ga
on
26 Jun 2003 10:13 PDT
Two more questions!
What is the size of nodes? Will these be pointlike, or will they have
their own "shapes" (such as boxes or circles)? This is in part a
concern about where the labels will go, and partly a concern (if the
nodes have a substantial size) about trying to avoid edges passing
through nodes to which they are not "attached".
Will the edges have their own labels?
regards, mathtalk-ga
|
Clarification of Question by
kkilpi-ga
on
26 Jun 2003 23:16 PDT
Hello,
A node can consist of multiple graphical elements (images, shapes,
labels, etc), but the application is able to count the size of the
nodes automatically (so they can be threatead as a single retangle).
Also the edges may have labels, but the application is capable of
counting the position for the edge labels (automatically place the
labels in the right place).
Thanks,
kkilpi
|
