Skip to end of metadata
Go to start of metadata

Meeting Details

  • Moderator: cds
  • Protocol: cds
  • Author: cds
  • Reviewers:
    • chsch
    • grh
  • Start: 12:30
  • End: 14:20


Objectives and Introduction

The objective of this design meeting is to validate the basic design of KLay Layered.

The basic design and the class design is described on this Confluence page. You should read it to understand how KLay Layered is structured. During the meeting, we will basically be walking through all classes mentioned in the bottom-most diagram on that page. I would also like to have all intermediate processors as well as the different implementations for phases 1, 2, and 4 reviewed. That should not take long, since those are all just straightforward implementations of the interfaces and abstract classes we will have looked at before. The implementations for phases 3 and 5 are a bit more complex and should probably be reviewed during a second design review, along with the leftovers of this one.

Meeting Minutes

We go through every one of the grouped parts in the architecture diagram, understanding how the different parts work together and finding design problems.

  • In ComponentsProcessor, the pack(...) method should be changed to combine(...): its work is delegated to AbstractGraphPlacer.combine(...), both methods should therefore have the same name and combine(...) was found to be more intuitive than pack(...).
  • In LayeredLayoutProvider, getIntermediateProcessorList(final int slotIndex) is responsible for returning the list of intermediate processors in slot slotIndex. This list is expected to be in a valid order, that is, in an order that satisfies the dependencies among the layout processors. However, how this order is arrived at was not clear from the code. In fact, the code relied on a feature particular to the EnumSet returned by IntermediateProcessingStrategy: an iterator over an EnumSet returns its members in the natural order in which they occur in the enumeration, which in this case is designed to satisfy the dependencies. The correct order was thus implicitly guaranteed, without anyone understanding that behaviour. In fact, the IntermediateProcessingStrategy officially only returned a Set, not an EnumSet, making this situation all the more complex and even dangerous ("wherever there's danger he'll be there, DANGER MOUSE!"). This was now solved by having IntermediateProcessingStrategy explicitly return an EnumSet instance, and by documenting this stuff in getIntermediateProcessorList(...).

This were all the changes required. Afterwards, chsch came up with a use case he'd like to be supported. We talked about whether the design would be flexible enough to handle that one.

The Use Case of chsch

 Use case:

  1. Compute a layout for a graph.
  2. Replace multiple edges between any two given nodes by a single edge. This is done to reduce the level of detail when zooming out.
  3. Compute only the layout of the new set of edges.

This is a very restricted use case in which we can guarantee certain properties for the edges in the second layout. The most prominent is that we know that the number of edges can only shrink compared to the first graph. The following could be an idea for implementing this case:

  1. Use the interactive cycle breaker.
  2. Use the interactive layerer.
  3. Use the interactive crossing minimizer.
  4. Use a fixed node placement.
  5. Use the orthogonal edge router to compute bend points while not modifying the x coordinates of nodes.

There are a few problematic points:

  • The interactive crossing minimizer cannot infer the placement of long edge dummies of the edges since the edges weren't there in the first layout and thus have no coordinates assigned to them. This must be solved somehow.
  • The edge router might find that the spacing between layers is not enough to accommodate the edge routing.

All in all, however, this case might just be solvable. We'll keep that in mind for the future.

  • No labels