Relational Calculator

Download.

See also a description (PostScript) part1 and part2.

***************************************************************************** * PROGRAM: RC - RELATIONAL CALCULATOR * * * * Author: Andrej Mrvar * * Faculty of Social Sciences * * University of Ljubljana * * E-mail: andrej.mrvar@uni-lj.si * * http://www.uni-lj.si/~fdmrvar/andrej.html * * 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, permutations) 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 (default extension=.net) 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 sample13.net 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 sample13.net 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) msg 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.