9
$\begingroup$

I am looking for an algorithm to draw a mixed constituency/dependency graph (for a linguistic application). Such a graph would have two different types of vertices (tokens, nodes), and two different types of edges (hierarchical, non-hierarchical).

I'm new to graph theory and algorithms in general, and I hope that this question doesn't collide e.g. with the research-level requirements of this site. It should however generally be in the scope of cstheory.

The graph would have to be drawn bottom-up (I think), as all tokens should be displayed with the same y-coordinate, and the y-coordinates of nodes grouping tokens and/or nodes into constituents will have to be calculated dynamically, e.g., via their longest path to a token.

Hierarchical edges (used for grouping tokens/nodes into constituents) should have a minimum number of bendpoints (ideally 0), but there should also be a minimum number of crossings, overwriting the former requirement if needs be.

Non-hierarchical edges (used for dependencies) should have a minimum number of crossings, and be drawn as Bézier curves.

The next best thing I have come across is the algorithm described by Buchheim et al., improving Walker's algorithm to run in linear time.

Please do let me know should there be any need to improve my question, and thanks a lot in advance for any pointers.

EDIT:

As pointed out in a comment, I should mention that I basically want a default graph layout by an algorithm, which I - in the long run - want to edit and revise within the Eclipse GEF possibilities. I have previously looked into options to get Graphviz to work with GEF, but there seems to be no working solution that preserves all editing functionality inherited from GEF.

Improve this question
$\endgroup$
10
  • $\begingroup$ Do you need an algorithm or an existing tool? Graphviz (graphviz.org) can do this. You specify the graph, possibly some formatting options (for different kinds of nodes and edges) and the tool will output a reasonably rendered graph. $\endgroup$
    – Dave Clarke
    Commented Jun 28, 2012 at 10:14
  • $\begingroup$ @DaveClarke: Thanks. I'm aware of Graphviz being able to do this. Unfortunately it doesn't seem that there's currently no possibility out there to use Graphviz with an editor based on the [Eclipse Graphical Editing Framework](www.eclipse.org/gef). Hence I'm looking for an actual algorithm. Unless somebody knows how to plug/port Graphviz to GEF of course :). $\endgroup$
    – s.d
    Commented Jun 28, 2012 at 10:22
  • $\begingroup$ It sounds like the OP is looking for an algorithm (or a problem formulation that captures the specification) $\endgroup$
    – Suresh Venkat
    Commented Jun 28, 2012 at 16:15
  • $\begingroup$ @SureshVenkat: Yes, thanks for clarifying. $\endgroup$
    – s.d
    Commented Jun 28, 2012 at 16:19
  • 1
    $\begingroup$ Q has no mention of editing & but in comment you turn down graphviz & seem to indicate you want to edit it with GEF. GEF is a general visual editing framework/API on which other "plugins" can build on. you seem to want a default graph layout by an algorithm which you can then revise. suggest you edit your question to reflect that. by the way believe graphviz can be used to generate coordinates which can then feed into a graph editor. re GEF graph editing see eg professional graph layout for GEF $\endgroup$
    – vzn
    Commented Jul 7, 2012 at 17:35

1 Answer 1

Reset to default
1
$\begingroup$

you seem to want the following

  • a graph layout algorithm. many std algorithms typically use force-based methods where nodes are connected by replusive/attractive "springs" and the equilibrium/low energy state is obtained through some amt of iteration (of the corresponding globally-constructed force-related differential equation). the output of the algorithm is a set of 2-d or 3-d coordinates for nodes and (usually) edges.
  • ability to hand-modify the results of that algorithm. typically called a "graph editor". this starts with the coordinates from the layout algorithm and allows adjustment.

re (1) the forefront software seems to be graphviz. re (2) see eg this question "what is the best graph editor" on mathoverflow.

browsing the graphviz gallery, here are two graph types similar to what you want.

ER diagram and traffic light.

you say you have two types of edges. a simple way would be to have directed edges "toward or away" as in the traffic light example. or the edges can be labelled in two ways as in the ER diagram. both examples show two different node types using different shapes or labels, or shading etc. other approaches would be to use coloring.

as the mathoverflow Q/As indicate there are many graph editors. the std one with graphviz is "dotty". see eg pdf "editing graphs with dotty" by Koutsofious.

another technique for graphing, possibly large graphs, is to look at structural compositions eg clique decompositions.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.