Suvi

The Suvi-library implements multiple graph layout algorithms and serves as a framework for implementing graph layout algorithms.

See:
          Description

Packages
suvi Classes that have responsibilities over the entire Suvi-library.
suvi.alg Implementation of the overall layout algorithm chassis.
suvi.alg.contracts Design-by-Contract [Meyer1997] decorators [Gamma1995] for the algorithm interfaces.
suvi.alg.interfaces Interfaces between the phases of the algorithm and the overall algorithm chassis.
suvi.alg.policies Various implementations of the policies that the layout algorithm chassis uses.
suvi.alg.util Utilities for graph layout algorithm implementation.
suvi.api.adt.layout Interfaces and classes related to the representation of layout information.
suvi.api.alg Interface to the layout algorithm.
suvi.api.alg.attr Layout attribute interfaces.
suvi.api.geom Interfaces for accessing layouts based on geometric properties.
suvi.api.render Framework for rendering graphs.
suvi.parse Parser for attributed graphs.
suvi.testapp Testing application.
suvi.util.geom Utilities for manipulating geometric objects.

 

The Suvi-library implements multiple graph layout algorithms and serves as a framework for implementing graph layout algorithms.

Example: Computing a layout for a graph

In order to get a concrete contact point into the library, let's start with a simple example that calculates a layout for a very simple graph.

We first need a simple graph. The following code simply uses one of the predefined graphs from the TestGraphConstants-interface. The predefined graphs in that interface are only intended for testing purposes. In general, users simply implement the Graph-adapter interface and use their own existing graph representations.

Graph graph = TestGraphConstants.CLOTHING_GRAPH;

Then we need a graph layout algorithm. The following code uses the GraphLayoutAlgGen-class to generate a graph layout algorithm for us.

GraphLayoutAlg layoutAlg =
  GraphLayoutAlgGen.alg(GraphLayoutAlgGenConstants.LAQ_BEST_VISUAL_QUALITY, 0);

Now we have almost everything we need. We also need to specify layout attributes, or parameters, for the layout algorithm. In this example, we don't have any special attributes that we would like the layout algorithm to consider, so we'll just create an empty attribute map.

GraphLayoutAttrMap attrMap = new GraphLayoutAttrMap();

We are now ready to ask the algorithm to compute a layout for our graph.

final GraphLayout layout = layoutAlg.layout(graph, attrMap);

The next logical step would be to render the graph in some way. The following pseudo code example shows one possible template for rendering a graph according to a computed layout.

new NodesAndEdgesIterTemplate() {
  protected void doNode(Object node) {
    drawNode(node, layout.nodeBox(node));
  }

  protected void doEdge(Object edge) {
    drawEdge(edge, layout.edgeBSpline(edge));
  }
}.iter(layout.graph());

You should now have a basic idea about what this library is all about.

About this documentation

This documentation is aimed at both users of the library and library maintainers. Different parts of the documentation are relevant to users and maintainers.

Documentation for library users

The documentation that is most relevant to users is in:

The API-packages:
suvi.api.alg
suvi.api.alg.attr
suvi.api.adt.layout
The algorithm generator:
GraphLayoutAlgGen

The API specifies the interface, inputs and outputs, between a layout algorithm and the user. In order to understand how to use the library, you should read through most of the API documentation.

As a user, you are probably not interested in how the algorithm implementation is divided into components. The algorithm generator shields users from the implementation details of graph layout algorithms. To use a layout algorithm, you can use the algorithm generator to create a layout algorithm for you.

Users should also read the following overview intended for library maintainers.

Documentation for library maintainers

Almost all of the documentation is naturally relevant to library maintainers. A good starting place to learn about the design of the implementation of graph layout algorithms is the graph layout algorithm chassis GraphLayoutAlgChassis.

Maintenance

Maintenance includes correcting defects in the existing code and adding new functionality. According to statistical evidence collected from many projects, most development work labelled as "maintenance" is actually about adding new functionality or refactoring of existing functionality, which isn't that different from initial design.

Utility classes

The Suvi-library uses many utility classes in the implementation of graph algorithms. If you intend to maintain the library, you probably want to read through the utility package and class documentation to get a sense of what is already implemented. You don't want to waste time reimplementing general algorithms that are already implemented.

While the documentation contains some examples, it may still be difficult to get a sense of how some general utility class or method or some other component is actually used. Good places to look for further examples are the various unit test classes. Reading through the test code (not the test documentation) can be a very effective way to gain an understanding of the component being tested. Links to all the unit test classes can be found from the class CompleteTestSuiteRunnerConstants.

Packages and dependencies

The Suvi-library has been divided into many packages guided by the design principles described in [Martin2002]. Unfortunately there is no one-line summary that would capture the essense of the packaging principles. In particular, simplistic minimization of dependencies is not a driving design force. Instead, dependencies are managed so that harmful dependencies are avoided. Not all dependencies are harmful. It is strongly recommended that you read and seek to understand the packaging principles described in [Martin2002] before changing the package structure.

Adding new classes

In case you need to develop a new class and you need to decide the package into which you place the class, you should read through the package descriptions to understand the intention behind each package. While choosing the package, it should help to consider the following questions.

Is the new class a general utility class, that has very little to do with graph layout algorithms?
If so, you should probably put it into one of the utility packages.
Is the new class a graph layout algorithm policy (or a decorator)?
If so, then put it into the suvi.alg.policies-package.
Is the new class a utility class that is strongly tied to graph layout algorithms?
If so, you should probably put it into the suvi.alg.util-package.
Is the new class a graph layout attribute class?
If so, you should put it into the suvi.api.alg.attr-package.

If your new class does not fit any of the above categories, you should think twice where you put your new class. You should also ask whether the role, or responsibility, of the class is actually well defined. A class should only have a single well defined responsibility.

Naming conventions

The classes and methods in the Suvi-library are named fairly systematically using a relatively small number of naming patterns.

Method naming

The naming conventions used in the Suvi-library are different from the Java naming conventions used by Sun. In Suvi, in general, method names start with a verb if and only if the method is decisively imperative and the client calls the method explicitly for the side-effects of the method. On the other hand, methods that are functional, and do not have externally observable side-effects do not, in general, start with a verb. We feel that these conventions yield short and logical names that communicate the intentions of the methods well.

Class naming patterns

Abstract*
Example: AbstractGraphLayoutAttrBuilder
An abstract class intended to be derived from to form a concrete class that implements some interface.
*Alg
Example: GraphLayoutAlg
An interface for an algorithm. Such an interface is essentially a Strategy [Gamma1995].
*Attr
Example: EdgeLabelAttr
A specific layout attribute interface.
Basic*
Example: BasicGraphLayoutAlgProgressPolicy
A basic implementation of some interface. Usually not intended to serve the needs of all users.
*Builder
Example: AbstractGraphLayoutAttrBuilder
A Builder [Gamma1995] is used for building complex objects.
*Constants
Example: FlowTrendConstants
An interface that defines useful constants. To use the constants, you can "implement" the interface to get convenient access to the constants.
*Contract
Example: GraphLayoutAlgContract
A Design-by-Contract [Meyer1997] Decorator [Gamma1995] for an interface.
*Decorator
Example: NodeOrderingPolicyWithTransposeDecorator
A basic forwarding Decorator [Gamma1995] for an interface that simply forwards all operations to the decorated object.
*Gen
Example: GraphLayoutAlgGen
A Generator [Czarnecki2000] for a complex component.
*Map
Example: GraphLayoutAttrMap
A class the represents a binary relation between keys and values.
*Policy
Example: ComponentLayoutPolicy
A Strategy [Gamma1995]. "Policy" is slightly shorter than "Strategy".
Simplistic*
Example: SimplisticNodeRankingPolicy
A simplistic implementation of an interface intended to be used for testing purposes.
*s (plural)
Example: EdgeRoutingPolicies
A class that contains static utility methods that implement algorithms relating to some concept.
*Test
Example: GraphLayoutAlgGenTest
An automated [JUnit] unit test class.

References

The following is a complete alphabetical listing of references made in the documentation. Please note that this documentation is not intended as an introduction to software design. The references point out to readily available software design, algorithm and programming texts whose material is general enough that it is not worth rephrasing here.

[Abelson1995]
Structure and Interpretation of Computer Programs, 2nd. ed.
Abelson, Sussman and Sussman
ISBN 0-262-01153-0
[Cormen2001]
Introduction to Algorithms, 2nd. ed.
Cormen, Leiserson, Rivest and Stein
ISBN 0-262-53196-8
[Czarnecki2000]
Generative Programming: Methods, Tools and Applications
Czarnecki and Eisenecker
ISBN 0-201-30977-7
[Fowler1999]
Refactoring: Improving the Design of Existing Code
Martin Fowler
ISBN 0-201-48567-2
[Gamma1995]
Design Patterns: Elements of Reusable Object-Oriented Software
Gamma, Helm, Johnson and Vlissides
ISBN 0-201-63361-2
[Gansner1993]
A Technique for Drawing Directed Graphs
Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North and Kiem-Phong Vo
Software Engineering, volume 19, number 3, pages 214-230
[JUnit]
"JUnit is a simple framework to write repeatable tests."
JUnit was originally designed by Erich Gamma and Kent Beck.
[Kühne1999]
A Functional Pattern System for Object-Oriented Design
Thomas Kühne
ISBN 3-86064-770-9
[Martin2002]
Agile Software Development: Principles, Patterns, and Practices
Robert Cecil Martin
ISBN 0-13-597444-5
[Meyer1997]
Object-Oriented Software Construction, 2nd. ed.
Bertrand Meyer
ISBN 0-13-629155-4
[PLOP3]
Pattern Languages of Program Design 3
Edited by Robert Martin, Dirk Riehle and Frank Buschmann.
ISBN 0-201-31011-2
[Siek2001]
The Boost Graph Library: User Guide and Reference Manual
Jeremy Siek, Lie-Quan Lee and Andrew Lumsdaine
ISBN 0-201-72914-8
[Weiss1997]
Data Structures and Algorithm Analysis in C, 2nd. ed.
Mark Allen Weiss
ISBN 0-201-49840-5