Manhattan layout algorithm

Question

I am looking for any of the following (in order of preference):

• A Manhattan layout EdgeRenderer for prefuse.
• A Manhattan layout for prefuse.
• An algorithm to produce Manhattan layouts for hierarchical, directed acyclic graphs.
• An organizational chart implementation.

Sample implementations include:

• NodeLinkTreeLayout (for prefuse) is close, but edge style is not orthogonal.
• Easy Graph for Perl
• Graphical JavaScript Tree

Do you know where to find something (warning: incoming pun) along those lines?

Answer 1

The answer turned out to be trivial. Using prefuse, create an EdgeRenderer subclass:

/**
 * Responsible for drawing orthogonal edges between two nodes.
 */
public class OrthogonalEdgeRenderer
  extends EdgeRenderer {
  /**
   * Creates a new edge renderer with a given arrowType. The edgeType is
   * ignored -- the edges are drawn orthogonally, as per the responsibility
   * of this class. The arrowType is one of the Constants.EDGE_ARROW_* values.
   *
   * @param edgeType Ignored.
   * @param arrowType One of Constants.EDGE_ARROW_*.
   * @see prefuse.Constants
   */
  public OrthogonalEdgeRenderer( int edgeType, int arrowType ) {
    super( edgeType, arrowType );
  }

  /**
   * Creates a new instance with no arrow head.
   */
  public OrthogonalEdgeRenderer() {
    this( Constants.EDGE_TYPE_LINE, Constants.EDGE_ARROW_NONE );
  }

  /**
   * Creates an orthogonal shape (an edge) to draw between two nodes.
   *
   * @param vi The visual item with start and end points.
   * @return The shape to draw between the nodes for this edge.
   */
  protected Shape getRawShape( VisualItem vi ) {
    Path2D.Double result = new Path2D.Double();

    if( vi instanceof EdgeItem ) {
      EdgeItem ei = ( EdgeItem )vi;

      double sx = ei.getSourceItem().getX();
      double sy = ei.getSourceItem().getY();
      double tx = ei.getTargetItem().getX();
      double ty = ei.getTargetItem().getY();

      double midy = ( sy + ty ) / 2;

      if( midy != sy && midy != ty ) {
        result.moveTo( sx, sy );
        result.lineTo( sx, midy );
        result.lineTo( tx, midy );
        result.lineTo( tx, ty );
      }
    }

    return result;
  }
}

Other details (such as the arrow and padding) are beyond the question's scope.