Networks / RELCALC
Relational Calculator


See also a description (PostScript) part1 and part2.

*                    PROGRAM: RC - RELATIONAL CALCULATOR                    *
*                                                                           *
*                    Author:  Andrej Mrvar                                  *
*                             Faculty of Social Sciences                    *
*                             University of Ljubljana                       *
*                             E-mail:                *
*                        *
*                             july 1994 - may 1995                          *

                   Shortcuts for changing menus:

                   *  - Main menu
                   R  - Relation menu
                   RB - Basic Relation operations
                   RC - Complex Relation operations
                   RP - Relation properties
                   RA - Additional Relation operations
                   P  - Permutation menu
                   PO - Permutation operations
                   C  - Clustering menu
                   CO - Clustering operations

                   Executable commands:

                   * - Main menu

LC                 - show list of contents (relations, clusterings,
RF file            - select report file (default extension=.rep)
                     (default selection=report.rep, but be careful:
                     this file is rewritten every time you run the program!)
LF file            - select log file (default extension=.log)
                     (default selection=logfile.log, be careful again:
                     this file is rewritten every time you run the program!)
Run file           - run macro (log) file (default extension=.log)
                     explanation follows
Inf                - information about available space and program
CA                 - clear all (dispose all objects)
Msg message        - write message in the bottom row

                   R - Relation menu

CT value           - change threshold value for reading relations
                     (number bigger than the selected value is transformed
                     to one, smaller to 0, default value of threshold is 0)
RDR file           - read ascii file with relation definition
SR r (p)           - show relation r (using permutation p)
WR r file type     - write relation r on ascii file (extension .net)
                     type M (Matrix), A (Adjacency) form
RpR r type         - report relation r onto current report file
                     type M (Matrix), A (Adjacency) form
DR r               - dispose relation r

                   RB - Basic Relation operations

Id dim             - create identity relation of dimension dim
RndR dim pr        - create random relation of dimension dim and probability
                     of 1 equal to pr
Tr r               - transpose of relation r
Comp r             - complement of relation r
Pow r x            - x-th power of relation r
Cl r               - strict (transitive) closure of relation r
Sk r               - transitive skeleton of relation r (R-R*R)
UnR r1 r2          - union of relations r1 and r2
InR r1 r2          - intersection of relations r1 and r2
Dif r1 r2          - difference of relations r1 and r2
Sum r1 r2          - symmetric sum of relations r1 and r2
Mul r1 r2          - multiply relations r1 and r2

                   RC - Complex Relation operations

Per r p            - physicaly permute relation r using permutation p
Ext r c            - extract from relation r clustering c,
                     result is relation with dimension equal to number of 1s
                     in clustering c (extract elements that correspond to
                     values 1 in clustering)
Shr r c links      - shrink in relation r clustering c
                     (shrink elements that correspond to values 1 in
                     clustering c into one element, links is the minimal
                     number of links between given vertex and shrinked
                     vertex that gives an arc in a new (shrinked) relation)
F r                - factorisation of relation r, results are:
                       1. clustering with strongly connected components,
                       2. factor relation (relations between components)
Dep r              - depth clustering of relation r,
                     (r must be acyclic)
Degr r type        - degree clustering of relation r
                     (type I, O or A  -  In/Out/All degree)
Core r type        - core clustering of relation r
                     (type I, O or A  -  In/Out/All degree)
Bic r              - biconnected components of relation r
                     (results are so many clusterings as there are
                      biconnected components)
CpR r1 r2          - comparison of relations r1 and r2 (<, >, <>, =)
Dist r1 r2         - distances between relations r1 and r2 (Heming ...)

                   RA - Additional Relation operations

Exd r c n          - extend relation r to new(higher) dimension n
                     clustering c determines transformation of elements
                     in first relation r into elements in resulting relation
                     c(a) = b - a corresponds to b in new relation
                     c(a) = 0 - element is omitted
Lex r1 r2 c        - concatenation of relations r1 and r2 with intersection
                     c into new (higher dimensional) relation
                     c(a) = b - identify element a from m1 with element
                                b from r2;
                     c(a) = 0 - a is not in r2
Sub r1 r2 c x      - substitution of element x from relation r1
                     in relation r2, c dertermines interception elements
                     in both relations (x cannot be in intersection)
                     c(a) = b - identify element a from r1 with element
                                b from r2;
                     c(a) = 0 - a is not in r2

                   P - Permutation menu

RDP file           - read ascii file with permutation definition
                     (default extension=.per)
SP p               - show permutation p
WP p file type     - write permutation p on ascii file (extension .per)
                     type 1 (One line), M (Many lines) form
RpP p type         - report permutation p on current report file
                     type 1 (One line), M (Many lines) form
DP p               - dispose permutation p

                   PO - Permutation operations

RndP dim           - create random permutation of dimension dim
Orb p              - create orbital clustering from permutation p
Mirr p             - create mirror permutation from permutation p
                     (reversed order of original permutation)
CpP p1 p2          - comparison of permutations p1 and p2 (<>, =)

                   C - Clustering menu

RdC file           - read ascii file with clustering definition
                     (default extension=.clu)
SC c               - show clustering c
WC c file type     - write clustering c on ascii file (extension .clu)
                     type 1 (One line), M (Many lines) form
RpC c type         - report clustering c on current report file
                     type 1 (One line), M (Many lines) form
DC c               - dispose clustering c

                   CO - Clustering operations

RndC dim n min max, type
                   - create random clustering of dimension dim,
                     n clusters, with at least min values in each cluster,
                     maximal number of elements in each cluster is max,
                     type Y or N (0 possible class number or not)
Can c type         - create canonical clustering from clustering c
                     type=Y (0 legal class number
                            (transform it to other (positive) value)
                     type=N (0 not legal class number (stays 0)))
Bin c n1 n2        - create binary (0,1) clustering from clustering c
                     (class 1 consists of classes from n1 to n2 in c,
                     others come in class 0)
UnC c1 c2          - union of clusterings c1 and c2
InC c1 c2          - intersection of clusterings c1 and c2
ClP c              - create permutation from clustering c
ClR c              - create relation (equivalence relation) from clustering c
RelC r c           - multiply relation r with clustering c - extracting column
                     (r and c must be of equal dimension,
                      c must be binary - with values 0 and 1 only)
CRel r m           - multiply clustering c with relation r - extracting row
                     (r and c must be of equal dimension,
                      c must be binary - with values 0 and 1 only)
Put c v x          - put vertex v into class x in clustering c
CpC c1 c2          - comparison of clusterings c1 and c2 (<, >, <>, =)
HiC c              - the highest class number in clustering c

                   MP - Relation properties

Test if relation that is represented by a given matrix is:
 1. Reflexive
 2. Irreflexive
 3. Symmetric
 4. Asymmetric
 5. Antisymmetric
 6. Transitive
 7. Intransitive
 8. Comparable
 9. Exact Comparable
10. Partial ordering
11. Equivalence rel.
12. Cardinality of relation (No. of ones in corresponding matrix).

                   Special characters

%            - last object (relation, permutation, partition -
               depends on context when it is used). Example:
               sr %
               means: show last relation

?            - program has to ask us what is the vaule of parameter

#1, #2, etc. - parameters used in macro file
               (#1 - first parameter, #2 - second, ...)
               detailed explanation follows

                   Run - Running macro file

During execution of program all steps that are made are written to
log file. The default log file is 'logfile.log'. This file is created and
rewritten every time you start the program. If you want to use the log file
later select the other name of log file. I suggest:
Every time you start the program first select your log file (and report file)!
You can call program specifying log nad report file. For example call:
rc my_log my_rep
means: call program rc, program will use file my_log.log for log file,
all reports will be written to file my_rep.rep.
Macro file can be used for (at least) two purposes:

1. For continuing your work at the point you finished it last time.
   Explanation: If you run your macro file that was created during your
   work the situation which you reached at the end of your work will be
   established again.

2. Creating your own procedures (sequences of elementary steps).
   If we look at typical sequence of steps that we usually make
   we can notice, that we first read some object (usually relation)
   and then make some transformations on it (elementary relation
   operations, clusterings of relation, ...).

   Example: we want to decrease the size of the relation, so that we
   keep only the most important vertices (for instance vertices that
   are cores of level k or higher). The sequence of steps (written in
   macro language) that we get if we do it interactively on graph with
   name is:
       1.   RDR sample13             %%%  R   1  (8)
       2.   Core-1(A)                %%%  C   1  (8)
       3.   Bin-1(2-99)              %%%  C   2  (8)
       4.   Ext-1|2                  %%%  R   2  (7)
   We read file with relation definition in line 1.
   In line 2 we get core clustering (1) of this relation (according to All
   degree). In line 3 we make binary clustering of clustering (1) with
   vertices that are cores higher than 2 in class 1 and others in class 0.
   In line 4 we extract from relation only parts that correspond to class 1
   in clustering (2).
   We can easily see that steps 2, 3 and 4 use results that were obtained
   in previous steps. If we want to execute the same sequence of steps
   on another relation all that we have to change is line 1.
   So we have to change above log file into following form:
       1.   RDR ?                    %%%  R   1  (8)
       2.   Core-1(A)                %%%  C   1  (8)
       3.   Bin-1(2-99)              %%%  C   2  (8)
       4.   Ext-1|2                  %%%  R   2  (7)
   All we have to change is to change name of file to ?.
   Character ? means that program has to ask us for the value of parameter.
   Now we can use this macro file as procedure with one parameter:
   When we run this macro file the program asks us what is the name of
   ASCII file, but other steps are executed automatically (without asking).
   Relation that is defined in file that we select can of course have different
   dimension that the one that was used for creating macro file.
   This was simple example of creating your own procedure.

   In general you can create procedure in two steps:
   1. First execute sequence of steps interactively to get macro file.
   2. Replace all parameters (in commands) that are not obtained from
      previous steps in the same procedure with ?.
      Example: If you need identity relation with the same dimension as is the
      dimension of previous relation you must change dimension in command for
      creating identity relation into ?. But you can use trick to avoid it:
      Instead of using command for creating identity relation you can use
      command for powering previous relation to the power 0.

   You do not have to run macro file only at the start of the program.
   You can use it also later, because relation and other labels are used
   relativelly. Instead of using labels 1, 2 in above example program
   will use appropriate relative labels depending on the current
   labels that were already used.

   Procedures with parameters:
   In some examples we want to tell the procedure explicitely which object
   (relation, ...) to use. We can do that using parameters. Example:

        Msg Example of procedure with parameters.
        RDR wirth                %%%  R   1  (10)
        Id(10)                   %%%  R   2  (10)
        msg Input relations for calculation!
        Dif(#1,#2)               %%%  R   3  (10)
        Pow-#1,3                 %%%  R   4  (10)
        Dif(4,#2)                %%%  R   5  (10)

   If we run this log file, the program will ask us for the value of
   parameters #1 and #2 only once (when calculating difference)
   later it will know what the values are.
   If we compare parameters # to parameters ? we can find the difference:
   Value of parameter ? is used only once and then forgotten while
   parameters # are memorized and used in entire procedure.

                   Aborting program

If we want to abort program we can do that by pressing .
Example: We do not want to wait until active command is finished.
We can repeat everything what we have done (except last command)
by running log file which was active during last execution of program.