Bug 220029

Comment 1 Alex Boyko 2008-02-22 15:47:33 EST

Created attachment 90514 [details]
public GraphVisitor and Edge#setPoints()

Draw2D patch with:
1) public Edge#setPoints() 
2) public GraphVisitor class

Comment 2 Randy Hudson 2008-02-24 16:27:55 EST

Before exposing new API, one question to ask is why shouldn't the problem you want to solve with new API be solved inside the "black box" (as opposed to outside)? If the routing results are better, then I guess everyone using the black box would want these improvements. Sow how would the client code route the edges?

Since edge routing is done last and has no impact on the other steps of the algorithm, couldn't an alternative approach just be performed after DirectedGraphLayout has finished? Just ignore the bendpoints from the algorithm and create your own. I guess this is what your patch is hinting at, but I don't see why a post-processor would need to implement the GraphVisitor interface to do this.

You can already use ShortestPathConnectionRouter in a post-processing step after DGL completed to create better edge routing.  But without making setPoints() public, you can't store your alternative bendpoints on the Edge, so you'd currently have to store them externally, which seems inconvenient.

It would be great if we could define API for alternative steps in the algorithm, but I think we should consider additional scenarios, like horizontal edges (within the same rank) and sortvalues for bendpoints, so that we don't commit to an API which prevents adding such future enhancements.

Comment 3 Alex Boyko 2008-02-25 12:15:26 EST

Hi Randy,
Thanks for the reply.

(In reply to comment #2)
> Before exposing new API, one question to ask is why shouldn't the problem you
> want to solve with new API be solved inside the "black box" (as opposed to
> outside)? If the routing results are better, then I guess everyone using the
> black box would want these improvements. Sow how would the client code route
> the edges?

Draw2D DGL modifies the height of most of the nodes. When Rank#(int location, int rowHeight) is called heights of all nodes within the rank are assigned the same height = max height of all nodes within the rank. This affects the start points of the edges. Since GMF uses Draw2D DGL to locate the nodes only and not resize them, GMF has edges overlapping intersecting nodes because of problem above, which we fix by routing edges differently.

> 
> Since edge routing is done last and has no impact on the other steps of the
> algorithm, couldn't an alternative approach just be performed after
> DirectedGraphLayout has finished? Just ignore the bendpoints from the algorithm
> and create your own. I guess this is what your patch is hinting at, but I don't
> see why a post-processor would need to implement the GraphVisitor interface to
> do this.

It's inconvenient to do the edge routing after DGL is done, because graph could be laid out vertically or horizontally. Edge routing is done always on the vertical graph and transpose metrics performs the necessary graph transformation after edges are routed.
GraphVisitor could remain package public - it's simply convenient to use it because I introduced a light transpose metrics visitor for directed graph only in GMF, which fits very well into GraphVisitor concept. It felt that there is no harm done if this template class becomes public, yet no big deal if it'd better not become public

> 
> You can already use ShortestPathConnectionRouter in a post-processing step
> after DGL completed to create better edge routing.  But without making
> setPoints() public, you can't store your alternative bendpoints on the Edge, so
> you'd currently have to store them externally, which seems inconvenient.
> 
> It would be great if we could define API for alternative steps in the
> algorithm, but I think we should consider additional scenarios, like horizontal
> edges (within the same rank) and sortvalues for bendpoints, so that we don't
> commit to an API which prevents adding such future enhancements.
> 

I'll describe briefly what I've done in GMF:
Subclassed Node to store original size of the node
Subclassed Edge to store edge style (default, orthogonal)

Created 3 graph visitors:
1. StoreOriginalNodeSizes. Caches x, y, width, height
2. TransposeDirectedGRaph. Tranposes the directed graph only. Transposes edge and nodes. Cached x, y, width, height are transposed too.
3. RouteEdges. Routes edges either orthogonally (vertical and horizontal line segments only - a good looking hierarchy layout is the result) or obliquely. Oblique routing is essentially Draw2D original results, just the start point of an edge is added to account for nodes modified height.

Is there any chance that I can modify the Draw2D DGL not to change the nodes height such that the algorithm would still work or the algorithm depends on this? (this could be implemented as an option) I modified Rank#setDimensions() such that the nodes height is left untouched, but then the algorithm stopped working - I didn't investigate any further. Need an advice from you here: is it worth investigating further?
Also, if you don't mind me introducing a style option on the edge to route an edge orthogonally I can do that too and then I don't need to subclass anything from Draw2D graph API meaning that nothing needs to be exposed any more.

There are more things planned for the layout in GMF to deal with border items. We're thinking about spacing out edges end points along the shape's edge, so there could be more option-like things we'd want to put in GEF or GMF layout.

Comment 4 Alex Boyko 2008-02-25 13:37:49 EST

BTW, I think the height of the nodes changes, because we want virtual nodes to have a height == row height. If I only set the height for virtual nodes and none of the others - the algortihm works. Perhaps the height should be changes for virtual nodes only or even for a node where node.height == 0?
Anyway, if this is acceptable as well as the routing changes from the previous comment, I'm willing to make the changes in Draw2D without introducing any API changes.
Thanks!

Comment 5 Alex Boyko 2008-03-03 10:53:00 EST

Resolving as invalid. A patch for graph layout that doesn't modify nodes sizes to be uploaded in a separate bugzilla