A path in a graph is defined by edges joining a number of nodes which must be greater
than two. A path with n nodes will have length of n-1. In the adjacency matrix method,
we are interested to find unidirectional flow paths between pairs of starting and ending
nodes in a digraph network [1]. For example two edges defined by v1->v3 and v3->v5 can
represent unidirectional flow whereas v1->v3 and v5->v3 represent mixed directional flow
along a path.
The algorithm described in this paper will search for both unidirectional and mixed
directional flow paths with or without loops. The options can be changed by using
mixed mode filters or MMFs. Computations are carried out using program lines
written in Macsyma 2.2.1.[3].
2.
Finding Paths In Undirected Graphs Using Macsyma 2.2.1
- Huen Y.K. (Date Released 12/3/98, 24 Kbytes)
========================================================
11. Evaluations Of Normc( ) Function
In Macsyma 2.2
- Huen Y.K. (Date Released 17/12/97, 14 Kbytes)
================================================
12.
List Processing In Sequence Algebra
- Huen Y.K. (Date Released 23/12/97, 20 Kbytes)
================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
21. The Throwing Power Of
Oddcomp(z).
- by Huen Y.K. (date released : 24.9.97 ) (15 Kbytes).
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
1. Introduction
A set of unconnected vertices or nodes
v1:sum(1/v(i),i,1,k);
An algebraic representations of independent vertices such as shown in equation (1)
is not useful in graphs since one must start with a representation of the interconnections
of an actual graph network. The next equation represents interconnections by edges
by pairs of symbols for vertices or nodes as shown in equation (2) where 1/(v(i)*v(j))
represents an undirected edge joining the two vertices. This means that if v(i) = v(j), the
term represents a loop. Therefore in sequence algebra, networks are represented
by an edge sequence rather than a node sequence. This formulation was used in
a previous paper for finding paths of undirected graph network [2]. The reason that
a typical term such as 1/(v(i)*v(j)) cannot be used to represent vector direction is
because the product of v(i)*v(j) is commutative.
....k
====
\............1
. )......------ ..............(1).
/...........v(i)
====....
i = 1
v1:sum(sum(1/(v(i)*v(j),i,1,k),j,1,k);
By making use of string representations, it is possible to represent vector directions of
edges as
shown in equation (3). This is because an edge represented by the string V1V2 is
distinctly different from one represented by V2V1. Note that only capital letters are used
to represent strings in this paper.
....k........k
==== ====
\..........\..................1
. )..........)......-------------- ..............(2).
/........../..............v(i)*v(j)
==== ====....
i = 1....j = 1
v1:sum(sum(1/(v(I)*v(J),I,1,K),J,1,K);
In equation (3) above, string representation of a directed edge is given by the string
data type VIVJ which
represents the directed edge of v(I)->v(J) where I and J are integer
numbers which must be
converted to string data type and concatenated into a single string. This is done as
shown in equation (4).
....k........K
==== ====
\..........\..................1
. )..........)......-------------- ..............(3).
/........../..............VIVJ
==== ====....
I = 1....J = 1
VIVJ = concat(string(V),string(I),string(V),string(J)); ...........................(4).
2. Finding Flow Paths Between Two Nodes
To demonstrate how to count paths of various lengths from a graph we use a simple
textbook example drawn from reference [1]. Figure 1 shows
the digraph with five nodes as v(1), v(2), v(3), v(4), and v(5).
v1--------------------v2
Fig.1 - Digraph Network.
0.................................0
^..\.........................^...^^
|........\................/.........|.......\
|.............\....../..............|............\
|...............X.................|...............0 v3
|............./.....\...............|............^
|......../................\.........|........./
|../...........................v...|..../
0<--------------------0
v5-------------------v4
A naive representation where v1,v2,... represent
nodes and 0 represents node-point. X represents cross-over and symbols like / and \
represent edges, and ^, <, >, V are directed arrowheads. ----> represents a directed
edge.
In figure 1 suppose one wants to find all the paths between nodes v4 and v5. There is
one unidirectional path given by v5->v1->v4 and a mixed directional path given by
v5->v2<-v4. If a user presents the latter path to the search program and if the digraph
network has such a path, it will be returned. The option is left to the user to decide
whether he will accept mixed directional paths or not. This is different from the
adjacency matrix method which is conventionally programmed to returns unidirectional
paths.
3. Finding Directed Paths Using A Symbolic Package
Directed paths in this paper include both unidrectional and mixed directional paths.
From figure 1, the sequence representations for directed edges are given by
equation (5):
x1:1/string(v1v4)+1/string(v2v3)+1/string(v3v2)+1/string(v4v2)+1/string(v4v3)
+1/string(v4v5)+1/string(v5v1)+1/string(v5v2);
x1 =
Each denominator string represents clearly the vector flow from the first vertex
to the second vertex, e.g., V3V2 and V2V3 represent opposite directional flow which
are both loops. Equation (5) is the sequence algebraic representation of
the connectedness of the digraph network in figure 1. To check whether a given
flow path exists, the user will input the chosen path and the predicate function
member_terms in equation (6) will only
return true if such a path exists in the above digraph.
...1...........1.............1...........1...........1............1.............1.............1
------ + ------ + ------ + ------ + ------- + ------- + ------- + -------.....(5).
V5V2....V5V1....V4V5....V4V3....V4V2....V3V2......V2V3......V1V4
member_terms(x1,x2):=(if op(x1) # "+" then x1:[x1],if op(x2) # "+" then x2:[x2],block
([args_x1:args(x1), args_x2:args(x2), ans:true],for args:args_x1 next rest(args) unless
args=[] do (if not member(first(args),args_x2) then return(ans:false)),return(ans)))$
.....................(6).
For general search of all possible paths from the digraph in figure 1, we generate all
possible paths of length 2 using equation (7).
x3:makelist(makelist(makelist((1/concat("V",string(i),"V",string(k))+1/concat("V",string
(k),"V",string(j))),k,1,5),i,1,5),j,1,5);.................................(7).
The output sequence from equation (7) contains a compound list nested three levels deep.
The innermost list contains five list items as shown highlighted in equation (8).
[[ [(2/V1V1), (1/V2V1) + (1/V1V2), (1/V3V1) + (1/V1V3),
(1/V4V1) + (1/V1V4), (1/V5V1) + (1/V1V5)], [(1/V2V1) + (1/V1V1),
(1/V2V2) + (1/V2V1), (1/V3V1) + (1/V2V3), (1/V4V1) + (1/V2V4),
(1/V5V1) + (1/V2V5)], [(1/V3V1) + (1/V1V1), (1/V3V2) + (1/V2V1),
(1/V3V3) + (1/V3V1), (1/V4V1) + (1/V3V4), (1/V5V1) + (1/V3V5)],
[(1/V4V1) + (1/V1V1), (1/V4V2) + (1/V2V1), (1/V4V3) + (1/V3V1),
(1/V4V4) + (1/V4V1), (1/V5V1) + (1/V4V5)], [(1/V5V1) + (1/V1V1),
(1/V5V2) + (1/V2V1), (1/V5V3) + (1/V3V1), (1/V5V4) + (1/V4V1),
(1/V5V5) + (1/V5V1)]], [[(1/V1V2) + (1/V1V1), (1/V2V2) + (1/V1V2),
(1/V3V2) + (1/V1V3), (1/V4V2) + (1/V1V4), (1/V5V2) + (1/V1V5)],
[(1/V2V1) + (1/V1V2), (2/V2V2), (1/V3V2) + (1/V2V3), (1/V4V2) + (1/V2V4),
(1/V5V2) + (1/V2V5)], [(1/V3V1) + (1/V1V2), (1/V3V2) + (1/V2V2),
(1/V3V3) + (1/V3V2), (1/V4V2) + (1/V3V4), (1/V5V2) + (1/V3V5)],
[(1/V4V1) + (1/V1V2), (1/V4V2) + (1/V2V2), (1/V4V3) + (1/V3V2),
(1/V4V4) + (1/V4V2), (1/V5V2) + (1/V4V5)], [(1/V5V1) + (1/V1V2),
(1/V5V2) + (1/V2V2), (1/V5V3) + (1/V3V2), (1/V5V4) + (1/V4V2),
(1/V5V5) + (1/V5V2)]], [[(1/V1V3) + (1/V1V1), (1/V2V3) + (1/V1V2),
(1/V3V3) + (1/V1V3), (1/V4V3) + (1/V1V4), (1/V5V3) + (1/V1V5)],
[(1/V2V1) + (1/V1V3), (1/V2V3) + (1/V2V2), (1/V3V3) + (1/V2V3),
(1/V4V3) + (1/V2V4), (1/V5V3) + (1/V2V5)], [(1/V3V1) + (1/V1V3),
(1/V3V2) + (1/V2V3), (2/V3V3), (1/V4V3) + (1/V3V4), (1/V5V3) + (1/V3V5)],
[(1/V4V1) + (1/V1V3), (1/V4V2) + (1/V2V3), (1/V4V3) + (1/V3V3),
(1/V4V4) + (1/V4V3), (1/V5V3) + (1/V4V5)], [(1/V5V1) + (1/V1V3),
(1/V5V2) + (1/V2V3), (1/V5V3) + (1/V3V3), (1/V5V4) + (1/V4V3),
(1/V5V5) + (1/V5V3)]], [[(1/V1V4) + (1/V1V1), (1/V2V4) + (1/V1V2),
(1/V3V4) + (1/V1V3), (1/V4V4) + (1/V1V4), (1/V5V4) + (1/V1V5)],
[(1/V2V1) + (1/V1V4), (1/V2V4) + (1/V2V2), (1/V3V4) + (1/V2V3),
(1/V4V4) + (1/V2V4), (1/V5V4) + (1/V2V5)], [(1/V3V1) + (1/V1V4),
(1/V3V2) + (1/V2V4), (1/V3V4) + (1/V3V3), (1/V4V4) + (1/V3V4),
(1/V5V4) + (1/V3V5)], [(1/V4V1) + (1/V1V4), (1/V4V2) + (1/V2V4),
(1/V4V3) + (1/V3V4), (2/V4V4), (1/V5V4) + (1/V4V5)], [(1/V5V1) + (1/V1V4),
(1/V5V2) + (1/V2V4), (1/V5V3) + (1/V3V4), (1/V5V4) + (1/V4V4),
(1/V5V5) + (1/V5V4)]], [[(1/V1V5) + (1/V1V1), (1/V2V5) + (1/V1V2),
(1/V3V5) + (1/V1V3), (1/V4V5) + (1/V1V4), (1/V5V5) + (1/V1V5)],
[(1/V2V1) + (1/V1V5), (1/V2V5) + (1/V2V2), (1/V3V5) + (1/V2V3),
(1/V4V5) + (1/V2V4), (1/V5V5) + (1/V2V5)], [(1/V3V1) + (1/V1V5),
(1/V3V2) + (1/V2V5), (1/V3V5) + (1/V3V3), (1/V4V5) + (1/V3V4),
(1/V5V5) + (1/V3V5)], [(1/V4V1) + (1/V1V5), (1/V4V2) + (1/V2V5),
(1/V4V3) + (1/V3V5), (1/V4V5) + (1/V4V4), (1/V5V5) + (1/V4V5)],
[(1/V5V1) + (1/V1V5), (1/V5V2) + (1/V2V5), (1/V5V3) + (1/V3V5),
(1/V5V4) + (1/V4V5), (2/V5V5)]]]................(8)
By submitting each of the above list item to the search using the program line
shown below, we get the output in equation (9).
sum(sum(sum(f(k,i,j)*part(part(part(x3,k),i),j)*(member_terms(part(part(part(x3,k),i),j),
x1)-false)/(true-false)*(zerop(abs(k-i))-true)/(false-true)*(zerop(abs(k-j))-true)/(false
-true)*(zerop(abs(i-j))-true)/(false-true),k,1,5),i,1,5),j,1,5);
Note that in the above program line, three MMFs are used to suppress paths with
idential nodes, e.g, f(1,1,1) or f(1,5,1) or f(1,1,5). This means that loops are excluded
as paths. If these are to be included, then the above MMFs must be removed from
the program line.
...................1...........1.............................1...........1
The paths reported by equation (9) are checked physically
using figure 1 and listed below. These agree with
those found from equation (9). Note that the two loop paths V2V3->V3V2 and
V3V2->V2V3 are not included because
these are deliberately excluded using the three MMFs in equation (9) above. One
advantage of the present method is that paths are reported in total
instead of merely as an adjacency matrix.
f(2, 4, 5) (------ + ------) + f(3, 5, 2) (------ + ------)
...............V5V2...V4V5.......................V5V2....V2V3
......................1...........1.............................1...........1
+ f(1, 4, 5) (------ + ------) + f(4, 5, 1) (------ + ------)
...................V5V1....V4V5.....................V5V1....V1V4
......................1............1..............................1.............1
+ f(5, 1, 4) (------- + -------) + f(2, 4, 3) (------- + -------)
...................V4V5....V1V4......................V4V3.....V3V2
......................1............1..............................1.............1
+ f(3, 1, 4) (------- + -------) + f(3, 4, 2) (------- + -------)
...................V4V3.....V1V4......................V4V2......V2V3
.......................1.............1.
+ f(2, 1, 4) (------- + -------)...........................(9).
...................V4V2.....V1V4
V4V5->V5V2,
V5V2->V2V3,
V4V5->V5V1,
V5V1->V1V4,
V1V4->V4V5,
V4V3->V3V2,
V1V4->V4V3,
V4V2->V2V3,
V1V4->V4V2
To confirm that loops will be included, we remove three MMFs from equation (9)
as shown in equation (10). The outputs are shown in equation (11).
sum(sum(sum(f(k,i,j)*part(part(part(x3,k),i),j)*(member_terms(part(part(part(x3,k),i),j),x1)
-false)/(true-false),k,1,5),i,1,5),j,1,5);.......................(10).
...................1...........1.............................1...........1
f(2, 4, 5) (------ + ------) + f(3, 5, 2) (------ + -------)
...............V5V2.....V4V5.....................V5V2....V2V3
......................1...........1.............................1...........1
+ f(1, 4, 5) (------ + ------) + f(4, 5, 1) (------ + -------)
...................V5V1....V4V5.....................V5V1....V1V4
......................1...........1.............................1...........1
+ f(5, 1, 4) (------ + ------) + f(2, 4, 3) (------ + -------)
...................V4V5....V1V4.....................V4V3....V3V2
......................1...........1.............................1...........1
+ f(3, 1, 4) (------ + ------) + f(3, 4, 2) (------ + -------)
..................V4V3.....V1V4.....................V4V2....V2V3
......................1...........1.............................1...........1
+ f(2, 1, 4) (------ + ------) + f(3, 3, 2) (------ + ------)
...................V4V2....V1V4.....................V3V2...V2V3
......................1...........1
+ f(2, 2, 3) (------ + ------).............................(11).
...................V3V2.....V2V3
One can immediately see that by the two loops shown highlighted in the above
equation are now included which are as expected.
One can use the same method to find paths with path lengths greater than 2 but
at the expense of increased nested levels and amount of search effort. The
problem of limitations in memory resources for large graph network will have to be
addressed just like in the adjacency matrix method.
4. Acknowledgements
The author thanks Dr. J.P.Golden of Macsyma who contributed the program
line in equation (6).
5. Conclusions
This paper describes briefly an algebraic method for finding the number of
directed paths with or without loops of a graph network given by figure 1 by
controlling the number of MMFs used. Once
the graph is converted into sequence representations, finding these paths can
be automated. The results are
presented in a sequence which is easier to read than that from an adjacency
matrix. It is especially difficult to read a high ordered adjacency matrix because
only the row and column numbers of the final matrix are accessible unless one
is willing to work backward [1] or using elaborate programming aids. In the case
of the present method, the correct paths are presented algebraically with
all necessary information included.
5 References
Since no standard textbooks have been published on topics on sequence algebra,
we include more references than is deemed necessary in a research paper. Readers
who have no previous background in this topic will find some of these papers helpful.
All references, with the exception of those published in journals are accessible
from this URL-site.
1. Grassman W.K. and Tremblay J.P.( ): Logic And Discrete Mathematics -
A Computer Science Perspective, Prentice-Hall, chapter 7, graphs and tree, pp 353 to
421.
3. Macsyma: Symbolic/numeric/graphical mathematics software, Mathematics and
System Reference Manual, 16th edition, relevant sections.
Published Papers:
4. Huen Y.K.: A Matrix Map for Prime and Non-prime Numbers, INT. J. Math. Educ. Sci.
Technol., 1994, VOL. 25, NO.6, pp 913-920.
5. Huen Y.K.: Some Interesing Properties Of The Natural Number System, Int. J. Math. Educ.
Sci. Technol., 1996, VOL.27, NO. 5, 685-691.
6. Huen Y.K.: Visual algebra and its applications, INT. J. Math. Educ. Sci. Technol.,
1997, VOL.28, NO.3, pp 333-344.
7. Huen Y.K.: The twin prime problem revisited, INT. J. Math. Educ. Sci. Technol.,1997, VOL.28,
NO. 6, pp 825-834.
8. Huen Y.K.: Is Pie Periodic?, INT. J. Math. Educ. Sci. Technol.,199?,VOL.??,NO.?,???-???. (in the press).
9. Huen Y.K.: Final value theorem in number sequences., INT. J. Math. Educ. Sci. Technol.,199?,VOL.-??,NO.?,???-???. (accepted).
Papers posted in this website.
30.
Sequence Algebra - A Tutorial Paper
- Huen Y.K. (Date Released 2/2/98, 46 Kbytes)
========================================================
=====================END OF PAPER ======================