[Home] [Next]
Why a New Paradigm?
And why not? :-)
The purpose of object-oriented tecnology is to design and implement
systems that have, among others, the following features:
- extensibility
It must be simple to add new functionalities. The new parts must be
integrated in the old system in a natural way. Extensibility is usually
achieved by using the inheritance.
- flexibility
To avoid code modification and rewriting, each class must be
usable in a variety of situations combined with the others.
The usual object-oriented paradigm can work in a variety of common
applications by providing a good set of primitive concepts.
When the design activity becomes harder, design
patterns can help but, if a problem arise in almost every part of the
system, it is better to extend the paradigm in a convenient way.
Origins of the Project
Our work began with the target of designing a system for graph drawing
to handle a large set of user needs. The need of handling many different
kinds of graphs forced us to concentrate big efforts over a classification
problem. The system had to be extensible in a natural way, so to allow
the users to make experiments with new kinds of graphs.
We were free to choose any paradigm, but, for several reasons, we have
selected the object-oriented one.
Problems with the Usual Object-Oriented
Paradigm
The following is a list of problems encountered during the analysis
phase and taken from the experience done with ALCOM-IT
GDTookit and ALF [P. Bertolazzi et al., "Parametric Graph Drawing",
IEEE Trans. on Software Engineering, vol. 21, no. 8, aug. 1995].
State Extension
- An object can contain other objects (its own elements). A graph
is an example of this concept; it contains vertices and edges.
- If you want to attach additional information on those elements, some
difficulties arise.
- The figure shows a typical design of a little hierarchy to handle graphs
and labelled element graphs. A client of Graph cannot create objects belonging
to Vertex because of internal consistency problem. However, Graph
offers methods for creating and destroying objects (e.g. Add_Vertex
and Del_Vertex).
- An underlying unlabelled graph can be considered when a LabelledGraph
is instantiated. We call it the support for the labelling.
- If this scheme is used, methods in Graph generate Vertex
and Edge, even when LabelledVertex and LabelledEdge must
be created, i.e. when the graph is a LabelledGraph.
- A solution of this problem implies a mechanism to communicate the class
of vertices and edges to the creating methods of Graph. Creating
methods can be overridden in LabelledGraph, but the situation becomes
harder in a larger system where the Crossed classes problem arises.
Crossed Classes
- Complex combinatorial structures like graphs can be classified in a
large number of ways.
-
- If more than one independent classification exists, many classes (crossed
classes) must be created to have a complete classification capability.
A mechanism that allows to manage independent classifications can be helpful
in that situation (i.e. objects can belong to more than one class).
Promotion Efficiency (in Dynamic
Classification)
- When an object is promoted (demoted) from a class into its child (parent),
it usually needs a complete copy of the support. For example, if labels
must be added to a graph, a complete copy of the graph (with its heavy
implementation structures) must be made. If the internal implementation
is the same (i.e. a linked one), the time spent to make the copy is wasted.
- This happens because the membership relation is usually not dynamic.
The class of an object is statically defined at the moment of the object's
creation.
Multiple "Decorations"
Other Systems Related to Graph
Drawing
How other object-oriented systems solve (or
ignore?) the above mentioned problems
LEDA
It gives a class graph but no classification of graphs is given,
the crossed classes problem and the promotion problem do not arise.
Extension of the state and multiple decoration can be simulated by
using classes like node_map and edge_map. This avoids the
problem of promotion, but it is impossible to update the new information
in an automatic way when the support object changes its state. If one needs
an automatic update, one must derive a new class and must override some
methods. However, this approach to the design results in all the problems
described above (crossed classes problem, promotion problem).
Graphlet
It is an extension to LEDA, but no support is added to solve the above
mentioned problems, and no classification of graphs is provided. It only
adds support for algorithm's visualization and animation.
ALCOM-IT GDTookit
It uses LEDA as a base to give a graphs hierarchy. The size of such
hierarchy is limited by the crossed classes problem. Promotion problem
is faced using an underlying implementation object (the LEDA graph) that
can be used in other objects by coping pointers (steal_from method).
LINK
A very little hierarchy of hypergraphs is provided. Crossed classes
problem and promotion problem are not solved. It is possible to add attributes
to graph's elements, but this mechanism does not allow automatic update
of the state of the extension object. Attributes are not classes and thus
they are not useful to solve the multiple decoration problem.
ALF
ALF has a big hierarchy in which the crossed classes problem arise.
Due to that problem, there are classes only for the "most useful"
combination of properties, but this is a very inflexible choice. Very common
features, like labelling or component set management, are handled by the
most important class multigraph. No mechanisms are provided to solve
the other problems.
P. Bertolazzi et al. - "Parametric Graph Drawing"
IEEE Trans. on Software Engineering, vol. 21,
no. 8, aug. 1995
ffgraph
Labels are objects that can be bound to graphs, vertices and
edges. They have its own methods and data but their most interesting feature
is that each modification made to the graph is notified to the label as
an event; thus labels can update their state accordingly. The same
happens for labels of vertices and edges.
Labels make state extension with automatic update possible. Just one
label for each type can be bound to a graph, so the multiple decorations
problem remains. Labels of different types can be bound to the same graph,
instead. ffgraph's labels mechanism is similar to inheritance, but
it can be used only for graphs, vertices and edges.
ffgraph gives no classification of graphs. Classification of
one level depth can be made by using labels. This avoids the crossed class
problem and the promotion efficiency problem. A deeper classification cannot
use label mechanism, therefore the usual problems arise.
Furthermore, the set of notified events is too small. Using label mechanism,
it is impossible to add constraints to operations that user can apply to
a graph, because pre-operation events are not available.
Comparative Tables
(The following evaluations are very subjective (!) and arise
from the above consideration)
With respect to general features:
|
LEDA
|
ALF/DS
DS (Diagram Server)
is a visualization tool
based on ALF.
|
LINK
|
ffgraph
|
|
pure
|
Graphlet
|
GDToolkit
|
|
Visualization
|
*
|
***
|
*
|
***
|
*
|
***
|
|
Layout algorithms
|
-
|
-
|
**
|
***
|
*
|
*
|
|
Classification
|
-
|
-
|
**
|
***
|
*
|
*
|
With respect to analysis problems:
|
LEDA
|
ALF
|
LINK
|
ffgraph
|
|
pure
|
Graphlet
|
GDToolkit
|
|
State extension
|
*
|
*
|
*
|
-
|
*
|
***
|
|
Multiple decorations
|
*
|
*
|
*
|
-
|
-
|
-
|
|
Crossed classes
|
|
|
-
|
*
|
-
|
*
|
|
Promotion
|
|
|
***
|
-
|
-
|
***
|
After all, all the systems being considered have some limitation with
respect to extensibility and flexibility.
Evaluations
|
-
|
not handled
|
|
*
|
fair
|
|
**
|
good
|
|
***
|
very good
|
[Home] [Next]