Loops and Routes in Graphs

This is a continuation of the tutorial for the graph theory code which starts here.

On this page we look at how to calculate routes and loops as either sequences of node indexes or sequences of arrow indexes.

First we construct a graph to work with (this page shows how to construct graphs):

(1) -> GS := DirectedGraph(String)
   (1)  DirectedGraph(String)
                                                           Type: Type

(2) -> hs1 := cycleOpen(["a","b","c"],"a")$GS
   (2)  "a,b,c|a1:a->b,a2:b->c"
                                           Type: DirectedGraph(String)

(3) -> hs2 := cycleClosed(["1","2","3"],"b")$GS
   (3)  "1,2,3|b1:1->2,b2:2->3,b3:3->1"
                                          Type: DirectedGraph(String)

(4) -> hs3 := closedCartesian(hs1,hs2,concat)$GS
   (4)
  "a1,a2,a3,b1,b2,b3,c1,c2,c3|b1#1:a1->a2,b2#1:a2->a3,b3#1:a3->a1,
   a1#1:a1->b1,a1#2:a2->b2,a1#3:a3->b3,b1#2:b1->b2,b2#2:b2->b3,
   b3#2:b3->b1,a2#1:b1->c1,a2#2:b2->c2,a2#3:b3->c3,b1#3:c1->c2,
   b2#3:c2->c3,b3#3:c3->c1"
                                          Type: DirectedGraph(String)

(5) -> diagramSvg("testGraph6s1.svg",hs3,true)
                                                           Type: Void
graph theory diagram

The spanning tree and route functions use index numbers to specify vertices, so to make this clearer I have modified the diagram on the left by hand (using Inkscape) to add the green numbers (which are the index numbers of the objects) and the red numbers (which are the index numbers of the arrows)

Spanning Tree

The concept of a spanning tree will be useful later for calculating loops and routes.

'spanningTreeNode(s,i)' constructs a spanning tree for graph 's' rooted at the node indexed by 'i'. The tree will expand out from 'i' only stopping when reaching a vertex that has already been visited (that is: loop detected). Elements in the tree are Integer, a positive Integer represents a vertex and a negative Integer represents a repeated vertex.

We can now construct a spanning tree starting on vertex 1:

(6) -> spanningTreeNode(hs3,1::NNI)$GS
   (6)
   1
      2
         3(- 1,6(4(5(- 6,8(9(7(- 8)))),7(8(9(- 7)))),9(7(8(- 9)))))
     ,
         5(6(4(- 5,7(8(9(- 7)))),9(7(8(- 9)))),8(9(7(- 8))))
  ,
      4(5(6(- 4,9(7(8(- 9)))),8(9(7(- 8)))),7(8(9(- 7))))
                                                   Type: Tree(Integer)

We can also create a spanning tree for every vertex by using 'spanningForest':

(7) -> spanningForestNode(hs3)$GS
   (7)
   [
     1
        2
           3(- 1,6(4(5(- 6,8(9(7(- 8)))),7(8(9(- 7)))),9(7(8(- 9)))))
       ,
           5(6(4(- 5,7(8(9(- 7)))),9(7(8(- 9)))),8(9(7(- 8))))
    ,
        4(5(6(- 4,9(7(8(- 9)))),8(9(7(- 8)))),7(8(9(- 7))))
     ,

     2
        3
           1(- 2,4(5(6(- 4,9(7(8(- 9)))),8(9(7(- 8)))),7(8(9(- 7)))))
       ,
           6(4(5(- 6,8(9(7(- 8)))),7(8(9(- 7)))),9(7(8(- 9))))
    ,
        5(6(4(- 5,7(8(9(- 7)))),9(7(8(- 9)))),8(9(7(- 8))))
     ,

     3
        1
           2(- 3,5(6(4(- 5,7(8(9(- 7)))),9(7(8(- 9)))),8(9(7(- 8)))))
       ,
           4(5(6(- 4,9(7(8(- 9)))),8(9(7(- 8)))),7(8(9(- 7))))
    ,
        6(4(5(- 6,8(9(7(- 8)))),7(8(9(- 7)))),9(7(8(- 9))))
     ,
    4(5(6(- 4,9(7(8(- 9)))),8(9(7(- 8)))),7(8(9(- 7)))),
    5(6(4(- 5,7(8(9(- 7)))),9(7(8(- 9)))),8(9(7(- 8)))),
    6(4(5(- 6,8(9(7(- 8)))),7(8(9(- 7)))),9(7(8(- 9)))), 7(8(9(- 7))),
    8(9(7(- 8))), 9(7(8(- 9)))]
                                            Type: List(Tree(Integer))

'spanningTreeArrow(s,i)' is similar to the spanning tree above except that it is generated in terms of arrows instead of nodes. That is, the index numbers represent arrow indexes instead of node indexes and we expand until we get to repeated arrows instead of repeated nodes.

(8) -> spanningTreeArrow(hs3,1::NNI)$GS
   (8)
   1
      2
         3
            - 1
        ,
            4
               7
                  8(9(- 7,10(13(14(15(- 13))))),12(15(13(14(- 15)))))
              ,
                  11(14(15(13(- 14))))
           ,
               10(13(14(15(- 13))))
     ,
         6
            9
               7(8(- 9,12(15(13(14(- 15))))),11(14(15(13(- 14)))))
           ,
               10(13(14(15(- 13))))
        ,
            12(15(13(14(- 15))))
  ,
      5
         8
            9(7(- 8,11(14(15(13(- 14))))),10(13(14(15(- 13)))))
        ,
            12(15(13(14(- 15))))
     ,
         11(14(15(13(- 14))))
                                                  Type: Tree(Integer)

Loops

In order to work with loops we introduce a domain called 'Loop'. This holds a sequence of indices which form a loop, when constructed 'Loop' rearranges its indices so that the lowest index is first, but without altering the loop sequence. This gives 'Loop' a canonical form so that we can easily check for equivalent loops using '='.

So in the following [5,6,2,8] is = to [2,8,5,6] (they are both stored as [2,8,5,6]) but different to [5,2,6,8] (which is stored as [2,6,8,5])

(9) -> l1 := loop([5::NNI,6::NNI,2::NNI,8::NNI])
   (9)  "[->2->8->5->6]"

                                                           Type: Loop
(10) -> l2 := loop([2::NNI,8::NNI,5::NNI,6::NNI])
   (10)  "[->2->8->5->6]"
   
                                                           Type: Loop
(11) -> l3 := loop([5::NNI,2::NNI,6::NNI,8::NNI])
   (11)  "[->2->6->8->5]"

                                                           Type: Loop
(12) -> (l1 = l2)::Boolean
   (12)  true

                                                        Type: Boolean
(13) -> (l1 = l3)::Boolean
   (13)  false
                                                        Type: Boolean

The function 'loopsNodes' lists all the loops in the given graph, in this case the loops are expressed as a sequence of node indexes.

(14) -> loopsNodes(hs3)$GS
   (14)  ["[->1->2->3]","[->4->5->6]","[->7->8->9]"]
                                                      Type: List(Loop)

The function 'loopsArrows' lists all the loops in the given graph, in this case the loops are expressed as a sequence of arrow indexes. The number of loops given by 'loopsArrows' may possibly be different from that given by 'loopsNodes', for instance, if a loop contains two parallel arrows between adjacent nodes then this will count as two arrow loops even though each loop passes through exactly the same nodes.

(15) -> loopsArrows(hs3)$GS
   (15)  ["[->1->2->3]","[->7->8->9]","[->13->14->15]"]
                                                     Type: List(Loop)

Routes

Given two node indexes 'routeNodes' returns the shortest route between 'a' and 'b' (minimum number of hops) as a sequence of node indexes. Otherwise it returns:

So if we want to find the shortest distance between node 1 and node 2 we enter:

(16) -> routeNodes(hs3,1::NNI,2::NNI)$GS
   (16)  [1,2]
                                        Type: List(NonNegativeInteger)

This tells us that there is a direct link from 1 to 2.

Similarly 'routeArrows' returns the shortest route between 'a' and 'b' as a sequence of arrow indexes, otherwise:

Note that the end points are still entered as node indexes although, in this case, the result is given in terms of node indices:

(17) -> routeArrows(hs3,1::NNI,2::NNI)$GS
   (17)  [1]
                                        Type: List(NonNegativeInteger)

So this is saying that arrow index 1 goes directly between nodes 1 and 2.

Modifying Routes with Weights

So far route will find the route between two given nodes with the minimum number of hops. However we may want to choose some other metric to minimise when choosing a route.

'WeightedGraph' is a specialised Graph which has a value (currently NNI) for each arrow. There is more information about Weighted Graphs here.

First we setup a graph to work with:

(18) -> WG := WeightedGraph(String)
   (18)  WeightedGraph(String)
                                                             Type: Type
(19) -> OBJT ==> Record(value:String,posX:NNI,posY:NNI)
                                                             Type: Void
(20) -> oba:OBJT := ["a",10,30]
   (20)  [value= "a",posX= 10,posY= 30]
                  Type: Record(value: String,posX: NonNegativeInteger,
                                              posY: NonNegativeInteger)
(21) -> obb:OBJT := ["b",30,10]
   (21)  [value= "b",posX= 30,posY= 10]
                  Type: Record(value: String,posX: NonNegativeInteger,
                                              posY: NonNegativeInteger)
(22) -> obc:OBJT := ["c",30,30]
   (22)  [value= "c",posX= 30,posY= 30]
                  Type: Record(value: String,posX: NonNegativeInteger,
                                              posY: NonNegativeInteger)
(23) -> obd:OBJT := ["d",30,50]
   (23)  [value= "d",posX= 30,posY= 50]
                  Type: Record(value: String,posX: NonNegativeInteger,
                                              posY: NonNegativeInteger)
(24) -> obe:OBJT := ["e",50,30]
   (24)  [value= "e",posX= 50,posY= 30]
                  Type: Record(value: String,posX: NonNegativeInteger,
                                              posY: NonNegativeInteger)
(25) -> hs4 := weightedGraph([oba,obb,obc,obd,obe])$WG
   (25)  "a,b,c,d,e"
                                            Type: WeightedGraph(String)
(26) -> addWArrow!(hs4,"a1",1,2,1)$WG
   (26)  "a,b,c,d,e|a1:a->b"
                                            Type: WeightedGraph(String)
(27) -> addWArrow!(hs4,"a2",1,3,4)$WG
   (27)  "a,b,c,d,e|a1:a->b,a2:a->c"
                                            Type: WeightedGraph(String)
(28) -> addWArrow!(hs4,"a3",1,4,9)$WG
   (28)  "a,b,c,d,e|a1:a->b,a2:a->c,a3:a->d"
                                            Type: WeightedGraph(String)
(29) -> addWArrow!(hs4,"b1",2,5,9)$WG
   (29)  "a,b,c,d,e|a1:a->b,a2:a->c,a3:a->d,b1:b->e"
                                            Type: WeightedGraph(String)
(30) -> addWArrow!(hs4,"b2",3,5,4)$WG
   (30)  "a,b,c,d,e|a1:a->b,a2:a->c,a3:a->d,b1:b->e,b2:c->e"
                                            Type: WeightedGraph(String)

(31) -> addWArrow!(hs4,"b3",4,5,1)$WG
   (31)  "a,b,c,d,e|a1:a->b,a2:a->c,a3:a->d,b1:b->e,b2:c->e,b3:d->e"
                                            Type: WeightedGraph(String)
(32) -> diagramSvg("testGraph6s2.svg",hs4,true)
                                                             Type: Void
graph

We want to find a route between nodes 'a' and 'e'. The function 'routeNodes' or 'routeArrows' will find the minimum cost route as we can see below. There are 3 possible routes from 'a' to 'e', they are:

  • a->b->e (or node indexes 1->2->5)
  • a->c->e (or node indexes 1->3->5)
  • a->d->e (or node indexes 1->4->5)

These have cost:

  • 1 + 9 =10
  • 4 + 4 = 8
  • 9 + 1 = 10

So we can see that the middle one is the lowest cost route:

As required this is the route found:

(33) -> routeNodes(hs4,1::NNI,5::NNI)$WG
   (33)  [1,3,5]
                                               Type: List(NonNegativeInteger)

Or we can calculate this using arrow indexes instead of vertex indices.

(34) -> routeArrows(hs4,1::NNI,5::NNI)$WG
   (34)  [2,5]
                                               Type: List(NonNegativeInteger)

That concludes our overview of loops and routes, click here to go to the next stage of the tutorial which is about specialised variants of graph such as function graphs, undirected graphs, multifunction graphs and weighted graphs.


metadata block
see also:
Correspondence about this page

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2023 Martin John Baker - All rights reserved - privacy policy.