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 <input tuple file> ............................ 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 <input tuple file> 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 <input tuple file> 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] <input tuple file> <output layout file>
      


4.0 Description of Arguments to program:
----------------------------------------

<input tuple file>  - 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 <input tuple file>.  The subsystem
                     name is built by concatenating the prefix of the
                     file name part of <input tuple file> with ".ss"
                     
                    e.g
                    
                    <input tuple file> 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 <input tuple file> should only
                     contain relation tuples
                     
                     i.e. 'FACT TUPLE :' header is not required AND
                           $INSTANCE tuples are not required
                      
                      
<output layout file>  - 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<size>    specify height of window ( default is 600 )



-W<size>    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          <input tuple file> should only contains relation tuples


-s <name>   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
                 <input tuple file>
                     
              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 <input tuple file> + ".ta"
           
              e.g.  if <input tuple file> 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 <input tuple file>
----------------------------------

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
<input tuple file> 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