Project : Bookshelf
Program : lslayout
Date Updated : August 28, 1997
Author: Gerry Kovan, University of Toronto
Table of Contents
-----------------
How to read this document.................................. 1.0
Purpose of Program ........................................ 2.0
Syntax of Program ......................................... 3.0
Description of Argumentemts to program .................... 4.0
Description of Nested Layout Model ........................ 5.0
Description of Client Server Layout Model.................. 6.0
Example TA tuple file ..................................... 7.0
Example TA layout file .................................... 8.0
Parsing the ............................ 9.0
Description of Program ................................... 10.0
References ............................................... 11.0
1.0 How to read this document :
-------------------------------
This document is a combination of a man page, and a technical document.
Sections 1.0 through 9.0 contain information on the purpose and
usage of the program. Section 10.0 gives a thorough description
of how the program works.
2.0 Purpose of Program:
-----------------------
There are two types of Layout Models that this program supports. The
type of model used is determined by an argument passed to the program
(an explanation of the two models is given later in this document).
1) Nested Layout Model:
Given an that represents a graph,
the program attempts to layout the entities in each nesting
level in order to make its visualization as aesthetically
pleasing as possible. This means, reducing the number of
edge crossings, minimizing length of edges etc.
2) Client Server Model:
Given an that represents a graph,
the program attempts to layout the entities in the subsystem
in order to make its visualization as aesthetically pleasing
as possible. This means, reducing the number of edge crossings,
minimizing length of edges etc.
The program also attempts to position the clients and servers
in it's most natural positions.
3.0 Syntax of Program:
----------------------
lslayout [options]
4.0 Description of Arguments to program:
----------------------------------------
- graph file that must contain the FACT TUPLE section
of the TA grammer
- the FACT TUPLE section consists of '$INSTANCE' tuples
and relation tuples.
note : (only relevant for client server layout model)
if -s option is not used then the subsystem name
is taken from the . The subsystem
name is built by concatenating the prefix of the
file name part of with ".ss"
e.g
is "./../bookshelf/LINUX/kernel.tup"
the name of the subsystem would be "kernel.ss"
note: Once the name of the subsystem is determined
the program searches its symbol/entity table to
find an entity with that name. If it does
not find one then the program ends with an
error message.
note : with -r option the should only
contain relation tuples
i.e. 'FACT TUPLE :' header is not required AND
$INSTANCE tuples are not required
- the contents of this file is the output of the program
- layout file will contain the position attributes for
each entity in the layout
- layout entry is of the form:
entity_name {
x = ?
y = ?
height = ?
width = ?
}
[options]
-H specify height of window ( default is 600 )
-W specify width of window ( default is 800 )
-e output parse warnings
- Examples of a parse warnings are:
1) An "$INSTANCE" is declared twice for the same entity
2) AN "$INSTANCE" is NOT declared for an entity but the
entity exists in one or more relation tuples.
-m<1 | 2> select a layout model ( default is 1 )
1 - nested layout
2 - client, server, subsystem layout
-r should only contains relation tuples
-s name of subsystem (only for client/server layout model)
- The program must know what the name of the subsystem
entity is. The program finds out in 1 of 2 ways:
1) if -s option is used the subsystem name is directly
passed to the program.
2) if -s option NOT USED then see description for
NOTE: Once the name of the subsystem is determined the program
searches its symbol table to find an entity with that
name. If it does not find one then the program ends
with an error message.
-t emit ta file called: prefix of + ".ta"
e.g. if is called "kernel.tup"
then ta file will be called "kernel.ta"
-x debug mode (creates a file called lslayout.debug)
5.0 Description of Nested Layout Model :
----------------------------------------
--------------------------------------
| |
| |
| -------------- |
| | A ----- | |
| | |A.a | | |
| | | | | |
| | ----- | |
| | | |
| | ----- | |
| | |A.B | | |
| | | | | |
| | ----- | |
| -------------- |
| |
| |
| |
| -------------- |
| | B ----- | |
| | |B.a | | |
| | | | | |
| | ----- | |
| | | |
| | ----- | |
| | |B.b | | |
| | | | | |
| | ----- | |
| -------------- |
| |
| |
--------------------------------------
- This is the most general layout model. The model consists of a number
of entites that may or may not contain other entities that may or may not
contain other entities and so on.
Note: A flat layout is the same as a nested layout with a nesting
level of 0.
6.0 Description of Client Server Layout Model:
----------------------------------------------
-----------------------------------------
| ---- ---- ---- |
| | | | | | | <-----|--------- client entities
| ---- ---- ---- |
| -------------------------------- |
| | | |
| | ---- | |
| | | | | |
| | ---- | |
| | | |
| | ---- ---- ---- | |
| | | | | | | | |<---|---------- subsystem
| | ---- ---- ---- | |
| | | |
| | ---- ---- | |
| | | | | |<------------|----|---------- subsystem entities
| | ---- ---- | |
| | | |
| -------------------------------- |
| ---- ---- ---- |
| | | | | | | <-----|---------- server entities
| ---- ---- ---- |
------------------------------------------
-In this model the top level view (shown in the diagram above) consists
of the subsystem, subsystem entities, client entities and server entities.
The subsystem is the focal point of this layout model.
-Clients are those entities that USE the subsystem - i.e. one or more
relations exist between a client entity and a subsystem entity.
-Servers are those entities that are USED BY the subsystem - i.e. one
or more relations exist between a subsystem entity and a server entity.
-The client, server and subsystem entities can contain other entities
as well. These will be layed out using the nested layout model
(i.e only the top level view will use the client server layout model).
7.0 Example TA tuple file:
--------------------------
1) when program run WITHOUT -r option
FACT TUPLE :
// Instances
$INSTANCE foo.ss subsystem
$INSTANCE foo.include module
$INSTANCE foo.pl9 module
$INSTANCE fooclient.pl9 module
$INSTANCE fooserver.ss subsystem
//relations
contain foo.ss foo.include
contain foo.ss foo.pl9
usevar foo.pl9 foo.include
useproc fooclient.pl9 foo.pl9
useproc foo.pl9 fooserver.ss
2) when program run WITH -r option
//relations
contain foo.ss foo.include
contain foo.ss foo.pl9
usevar foo.pl9 foo.include
useproc fooclient.pl9 foo.pl9
useproc foo.pl9 fooserver.ss
8.0 Example TA layout file:
---------------------------
Layout file produced from above graph data (2) using the following command :
lslayout -r -s foo.ss -m2 tuple.data tuple.layout
or, if the name of the file was foo.tup then
lslayout -r -m2 foo.tup foo.lyt
$ROOT {
x = 0
y = 0
width = 600
height = 800
}
fooserver.ss {
x = 150
y = 725
width = 83.3
height = 50
}
fooclient.pl9 {
x = 150
y = 25
width = 83.3
height = 50
}
foo.ss {
x = 25
y = 100
width = 550
height = 600
}
foo.pl9 {
x = 110
y = 101
width = 165
height = 99
}
foo.include {
x = 110
y = 301
width = 165
height = 99
}
note: the numbers might be different as changes have been made to
the algorithm
9.0 Parsing the
----------------------------------
When executing the program with the -r option the program reads in
the tuples representing relations and produces a layout.
When the -r switch is not used then the program expects the
to have the following format:
FACT TUPLE : // This is the section header
$INSTANCE a module // declare $INSTANCE for each entity
$INSTANCE b module
$INSTANCE ss subsystem
// relation tuples ( the order of the relations
does not matter )
contain ss a // relation tuples
contain ss b
call a b
If the "FACT TUPLE :" header is not read and EOF has been reached the
program ends with an error message.
The $INSTANCE tuples must come before the relation tuples.
If a $INSTANCE is not declared for an entity and that entity is used
in a relation then the program treats the entity as if it were decalred and
continues. If the -e switch was specified then the program will output
an appropriate warning message then continue.
The philosophy taken is to be as lenient as possible when parsing
the input file.
10.0 Description of Program :
----------------------------
1) Nested Model
This program takes as input a tuple file of the form described
in section 'Example TA tuple file' and produces a layout of each
of the nesting levels.
A modified version of Sugiyama's algorithm [1] was applied
to layout each nesting level. The algorithm involves :
1) assigning each entity within a nesting level a number
corresponding to its level within the container
- implemented using a modified topological sort algorithm
- the algorithm detects and removes cycles ( this approach
was observed to produce superior layouts)
2) reducing the edge crossings within a nesting level
- implemented using Sugiyama's Barycentric method [1]
3) determining the horizontal position of entities
- this reduces the average length of the edges between entities
2) Client Server Model
This program takes as input a tuple file of the form described
in section 'Example TA tuple file' and produces a layout of
the subsystem according to the client server layout model.
The algorithm to layout the subsystem is exactly the same as
the algorithm described in the Nested Model.
In addition, the clients and servers must be layed as well. The criteria
for positioning these entities is to minimize the length of the edges
(assuming an edge is drawn from a client/server entity to a
subsystem entity).
11 References;
--------------
[1] Sugiyama, K., Tagawa, S., and Toda, M. Methods for Visual Understanding
of Hierarchical System Structures. IEEE Transactions on Systems, Man, and
Cybernetics 11,2 (February 1981), pp. 109-125