Page History

Since you won't want to directly work on the input KGraph, you will need a custom data structure to represent graphs, called the MrTGraph. For examples of such data structures, you can have a look at some of the following layout algorithms:

• KLay Layered uses the LGraph structure.
• KLay Force uses the FGraph structure.
• KLay Planar uses the PGraph structure.

All of these structures have in common that they don't necessarily model every property that might conceivably be used in the algorithm. Instead, graph structure members are property holders, which makes it easy to set an arbitrary amount of properties on them. To understand why this might make sense, look at KIML's LayoutOptions class or KLay Layered's Properties class. Both classes define a bunch of properties that can be set on graph elementsThe MrTGraph data structure is best explained by looking at the following diagram:

tree-graph.png

The basic data structure constis of the three classes TNode, TGraph and TEdge, which contain all the necessary properties to model a tree data structure. Therefore a TGraph consits of sets of TEdges and TNodes.

The TNodes are objects of the type TShape. That means that a nodes' size and position is defined by the attributes defined in the class TShape. The class TShape is an abstract superclass for the class TGraphElement. So the class TGrahpElement provides the utilites to declare any generic graph element of which a TGraph consits of.

Since an input KGraph is transformed into a TGraph, so that our algorithms can work on that TGraph, we do want to have the opportunity to set specific properties on graph elements. That is what the class TGraphElement is for. This specific way of implementation allows us not to model every property itself, but to model a class which can set an abritrary amount of properties on the graphs' elements. This data structure provides all the needs to perform a transformation from a KGraph to a TGraph that is as easy and therefore as evident as possible.