Conference rusure::math

1579.0. "paths in directed graph (posted also in algorithms)" by STAR::ABBASI () Tue Mar 10 1992 15:31

many years ago, i've written for a school course project a program that 
generates a requlare expression of the set of all paths between 2 nodes in a 
directed graph.

The program reads the graph from a text file . example given this graph
and we want the set of all paths from say 1 to 3.
offocurse there are many ways we can get from 1 to 3, and some include
loops. this program will find all these paths, i.e it will output
like this : { path1 + path2 + path3 .... }

where + means OR. see below for examples:


               -----------
              |           |
              v           |
   o--------->o---------->o 3
   1         2|           ^
              |           |
              |           |
            4 v           |
              o-----------
             
             
 can be inputed like this  (file 1)
[top of file]
   
 1   = 2;0  
 2 = 3;0  4;0
 3= 2;0
 4= 3;0

[end of file]

 example, the line  1= 2;0  means  from node 1 we have an edge going to
 node 2, the cost is this edge is 0 .  

in general this explains the format of input:

  A typical input can be like this :

  [Top-Of-File]

    2 = 3;50 5;90 8;0    9;0            \
          13;890   55  ; 45  \
          24;0

    3   = 40 ;  0

  [EOF]

  Input is free format , use "\" for line continuation.
  if Syntax error is detected during input then graph is discarded and
  User is informed of error and asked to correct and re-enter
  GET command .

  Production rules for input is:
Goal -> input
input -> stmts ; stmt
       | Empty

stmt -> <node> ; {' '} ; '=' ; {' '} ;  adjancy_list
adjancy_list -> adjancy_list ; {' '}; node ; {' '}; ';' ; {' '} ; COST
             |

node -> 1 to 5 digits number
Cost -> 0 to 5 disgit number
               

Lables:
-------
The program will give lables for every edge, it starts from the top of the
file, and it assign alphanumeric labels to edges, example in file 1 above,
typed here again:

 1   = 2;0  
 2 = 3;0  4;0
 3= 2;0
 4= 3;0

the edge 1->2 is "a0"
    edge 2->3 is "b0"
    edge 2->4 is "c0"
    edge 3->2 is "d0"
    edge 4->3 is "e0"

the requlare expression:
-------------------------         
 if you ask the program to find the requlare expression for the set of all
 paths between from node 1 to 2 above, it will generate this expression:

 THE REQULARE EXPRESSION Representing Set of Paths for 1 -> 2  Is
THE REQULARE EXPRESSION IS .... 

   ((((((a0) ) )+(((a0) b0) ((d0b0) *)(d0) )) )+(((((a0) c0) )+
  (((a0) b0) ((d0b0) *)(d0c0) )) ((e0((d0b0) *)(d0c0) ) *)(e0(
  (d0b0) *)(d0) ) )) 

 Verification checks: 
 number of tokens=118 , left parths =32, Right Parths =32

 to read this, the "+" means OR, the star "*" means an infinite loop.
 example  (d0b0)*  means path d0 followed by b0 forever.  (or 3->2->3)
 
 (a0)(b0) means  a0 path followed by b0 path.

 a0+b0   means path 1->2  OR 2->3

 the order of paranthesis is very important offcourse.

 I think it might have been easier for reader if i had generated the lables
 using   "1->2" notation instead of giving lables to the arcs. i forgot
 know why i did not do that.

 Any way the program is interactive drivedn with simple help on line too,
 it allowes you to read in more than one graph (file) into memory, and 
 switch between them via SET command.

 to start the program do
 $RUN foo
 ready>GET t      ! this reads in a file called t.dat who has the graph data
 ready>GET t1     ! read another graph in file t1.dat
 ready>SET t      ! this sets the program to work on t
 ready>DUMPG      ! This display the graph content
 ready>REX 1 2    ! this genrates the SET of all paths from 1 to 2 in 
                  ! reqular expression format as above
 ready>LOG        ! this starts loging i.e. write every thing that goes
                  ! to sceen to a file too
 ready>UNLOG      ! stops logging to a file
 ready>HELP 
 ready>q          ! quit.

Befor i stopped, i was about to work on shortest path between two nodes (that
is why i had a cost wight on each arc, but i never did that part)

any way, if any one wants the program , the build commands are:

$lib/crea g.olb
$lib/crea/text g.tlb
$ lib g.tlb  g.h
$cc/debug/noop g+g/lib
$cc/debug/noop addxid+g/lib
$cc/debug/noop addxsour+g/lib
$cc/debug/noop getxgrap+g/lib
$cc/debug/noop Simplify.c+g/lib
$lib g.olb g.obj
$lib g.olb addxid.obj
$lib g.olb addxsour.obj
$lib g.olb getxgrap.obj
$lib g.olb Simplify.obj
$link/debug g+g/lib+sys$library:vaxcrtl/lib

The source files are in kit called rex.a  on 
 
  BULOVA::SYS$public:rex.a
  (19.113)

$ dir BULOVA::SYS$public:rex.a

Directory BULOVA::DISK$SYSKITS:[PUBLIC]

REX.A;1

Total of 1 file.


Listing of save set(s)

Save set:          REX.A
Written by:        ABBASI      
UIC:               [000011,014333]
Date:              10-MAR-1992 14:52:30.53
Command:           BACKUP/LOG G.C;,ADDXID.C;,ADDXSOUR.C;,ADDXSOUR.C;,GETXGRAP.C;,SIMPLIFY.C;,G.H;,G.README,REX.EXE REX.A/SAV
Operating system:  VAX/VMS version V5.5
BACKUP version:    V5.5
CPU ID register:   0B000004
Node name:         _DIMOND::
Written on:        _DSA2024:
Block size:        32256
Group size:        10
Buffer count:      8

[ABBASI.G]G.C;2                                           137  10-MAR-1992 09:46
[ABBASI.G]ADDXID.C;1                                        1  22-NOV-1988 16:16
[ABBASI.G]ADDXSOUR.C;1                                      4  22-NOV-1988 16:16
[ABBASI.G]ADDXSOUR.C;1                                      4  22-NOV-1988 16:16
[ABBASI.G]GETXGRAP.C;1                                     30  22-NOV-1988 16:25
[ABBASI.G]SIMPLIFY.C;1                                     53  22-NOV-1988 16:27
[ABBASI.G]G.H;1                                             5  22-NOV-1988 16:21
[ABBASI.G]G.README;1                                        9  10-MAR-1992 14:47
[ABBASI.G]REX.EXE;1                                       189  10-MAR-1992 14:51

Total of 9 files, 432 blocks



    

>   ((((((a0) ) )+(((a0) b0) ((d0b0) *)(d0) )) )+(((((a0) c0) )+
>  (((a0) b0) ((d0b0) *)(d0c0) )) ((e0((d0b0) *)(d0c0) ) *)(e0(
>  (d0b0) *)(d0) ) )) 

With some parentheses removed and 'x0' substitutions made, this is:

	12 + (12 23(32 23)*32)
		+ (12 24 + 12 23(32 23)*32 24)(43(32 23)*32 24)*43(32 23)*32

The regular expression is *also*:

	12 ( 23 32 + 24 43 32 )*

Do you also have a program for simplifying regular expressions?

    the program does simplification , but it is not what you'r looking for
    i did not show the whole output in .0 this is what it does:
    
 Source -> <adjacent><COST> 

 1   ->  <2><0> 
 2   ->  <3><0>  <4><0> 
 3   ->  <2><0> 
 4   ->  <3><0> 

 THE REQULARE EXPRESSION Representing Set of Paths for 1 -> 2  Is
THE REQULARE EXPRESSION IS .... 
   ((((((a0) ) )+(((a0) b0) ((d0b0) *)(d0) )) )+(((((a0) c0) )+
  (((a0) b0) ((d0b0) *)(d0c0) )) ((e0((d0b0) *)(d0c0) ) *)(e0(
  (d0b0) *)(d0) ) )) 
 Verification checks: 
 number of tokens=118 , left parths =32, Right Parths =32


 Further Simplifications... 

(((((a0))+((a0b0)(A0*)d0)))+((((a0c0))+((a0b0)(A0*)B0))((e0(A
0*)B0)*)(e0(A0*)d0)))

Where A0= d0b0
Where B0= d0c0

 Verification checks: 
 number of tokens=82 , left parths =20, Right Parths =20


 Further Simplifications... 

((((a0)+(C0D0d0)))+(((E0)+(C0D0B0))((e0D0B0)*)(e0D0d0)))

Where C0= a0b0
Where D0= A0*
Where E0= a0c0

 Verification checks: 
 number of tokens=56 , left parths =12, Right Parths =12


 Further Simplifications... 

(((a0+F0))+((E0+G0)(H0*)I0))

Where F0= C0D0d0
Where G0= C0D0B0
Where H0= e0D0B0
Where I0= e0D0d0

 Verification checks: 
 number of tokens=28 , left parths =6, Right Parths =6


 Further Simplifications... 

((J0)+(K0L0I0))

Where J0= a0+F0
Where K0= E0+G0
Where L0= H0*

 Verification checks: 
 number of tokens=15 , left parths =3, Right Parths =3


 Further Simplifications... 

(J0+M0)

Where M0= K0L0I0

 Verification checks: 
 number of tokens=7 , left parths =1, Right Parths =1


 Further Simplifications... 

N0

Where N0= J0+M0
    
    -------------------------------------------------------------------
    so this is basically a substition type simplifications, i think it is
    possible to do add to the code to do the type of simplification you'r 
    looking for, the rules for doing that dont seem to be ambiguose , i
    think.
    
    /naser