Advanced Search
All Posts : Applications, Examples and Libraries

Recently Mapleprimes user @vs140580  asked here about finding the shortest returning walk in a graph (explained more below). I provided an answer using the labelled adjacency matrix. @Carl Love pointed out that the storage requirements are significant. They can be reduced by storing only the vertices in the walks and not the walks themselves. This can be done surprisingly easily by redefining how matrix multiplication is done using Maple's LinearAlgebra:-Generic package.

(The result is independent of the chosen vertex.)

> 

restart
> 

with(GraphTheory)

Consider the following graph. We want to find, for a given vertex v, the shortest walk that visits all vertices and returns to v. A walk traverses the graph along the edges, and repeating an edge is allowed (as distinct from a path, in which an edge can be used only once).

> 

G := AddVertex(PathGraph(5), [6, 7]); AddEdge(G, {{3, 7}, {4, 6}, {6, 7}}); DrawGraph(G, layout = circle, size = [250, 250])

GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7], Array(1..7, {(1) = {2}, (2) = {1, 3}, (3) = {2, 4}, (4) = {3, 5}, (5) = {4}, (6) = {}, (7) = {}}), `GRAPHLN/table/2`, 0)

> 

n := NumberOfVertices(G)

7

> 

A := AdjacencyMatrix(G)

As is well known, the (i, j) entry of A^k gives the number of walks of length k between vertices i and j. The labelled adjacency matrix shows the actual walks.

> 

Alab := `~`[`*`](A, Matrix(n, n, symbol = omega))

Matrix(%id = 36893490455680637396)

For example, the (3,3) entry of Alab^2 has 3 terms, one for each walk of length 2 that starts and ends at vertex 3. The `ω__i,j` factors in a term give the edges visited.

So the algorithm to find the shortest walk is to raise Alab to successively higher powers until one of the terms in the diagonal entry for the vertex of interest has indices for all the vertices.

> 

Alab^2

Matrix(%id = 36893490455709504684)

The expressions for higher powers get very large quickly, so an algorithm that only retains the sets of vertices in each term as a set of sets will use less storage space. So we can consider the following modified labelled adjacency matrix.

> 

B := Matrix(n, n, proc (i, j) options operator, arrow; if A[i, j] = 1 then {{i, j}} else {} end if end proc)

Matrix(%id = 36893490455703852204)

Now we need to modify how we do matrix multiplication, but Maple has the LinearAlgebra:-Generic package to do this. We can redefine addition and multiplication to operate correctly on the sets of sets.

Consider two sets of sets of vertices for walks.

> 

a := {{7}, {1, 3}, {2, 6, 7}}; b := {{1, 2}, {2, 3, 8}}

{{7}, {1, 3}, {2, 6, 7}}

{{1, 2}, {2, 3, 8}}

Addition is just combining the possibilities, and set union will do this. And addition of "zero" should add no possibilities, so we take {} as zero.

> 

`union`(a, b); `union`(a, {})

{{7}, {1, 2}, {1, 3}, {2, 3, 8}, {2, 6, 7}}

{{7}, {1, 3}, {2, 6, 7}}

Multiplication is just combining all pairs by union. Notice here that {7} union {1,3,5} and {1,5} union {3,7} give the same result, but that we do not get duplicates in the set.

> 

{seq(seq(`union`(i, j), `in`(i, a)), `in`(j, b))}

{{1, 2, 3}, {1, 2, 7}, {1, 2, 3, 8}, {1, 2, 6, 7}, {2, 3, 7, 8}, {2, 3, 6, 7, 8}}

The unit for multiplication should leave the set of sets unchanged, so {{}} can be used

> 

{seq(seq(`union`(i, j), `in`(i, a)), `in`(j, {{}}))}

{{7}, {1, 3}, {2, 6, 7}}

And we should check that zero multiplied by a is zero

> 

{seq(seq(`union`(i, j), `in`(i, a)), `in`(j, {}))}

{}

Define these operations for the LinearAlgebraGeneric package:

> 

F[`=`] := `=`; F[`/`] := `/`; F[`0`] := {}; F[`1`] := {{}}; F[`+`] := `union`; F[`*`] := proc (x, y) options operator, arrow; {seq(seq(`union`(i, j), `in`(i, x)), `in`(j, y))} end proc

Warning, (in F[*]) `j` is implicitly declared local

Warning, (in F[*]) `i` is implicitly declared local

Compare B^2 with Alab^2. We have lost information about the details of the walks except for the vertices visited.

> 

LinearAlgebra:-Generic:-MatrixMatrixMultiply[F](B, B)

Matrix(%id = 36893490455680647164)

So here is a procedure for finding the length of the shortest walk starting and ending at vertex v.

> 

WalkLength:=proc(G::Graph,v)
  uses GraphTheory;
  local x,y,i,j,vv,A,B,F,n,vertset;
  if IsDirected(G) then error "graph must be undirected" end if;
  if not member(v,Vertices(G),'vv') then error "vertex not in graph" end if;
  if not IsConnected(G) then return infinity end if;
  F[`=`]:=`=`:F[`/`]:=`/`: # not required but have to be specified
  F[`0`]:={}:
  F[`1`]:={{}}:
  F[`+`]:=`union`;
  F[`*`]:=(x,y)->{seq(seq(i union j, i in x), j in y)};
  n:=NumberOfVertices(G);
  vertset:={$(1..n)};
  A:=Matrix(n,n, (i, j)-> if AdjacencyMatrix(G)[i, j] = 1 then {{i, j}} else {} end if);
  B:=copy(A);
  for i from 2 do
    B:=LinearAlgebra:-Generic:-MatrixMatrixMultiply[F](B,A);
  until vertset in B[vv,vv];
  i;
end proc:
> 

WalkLength(G, 1)

10

> 

NULL

Download WalksGenericSetOfSets.mw
linearalgebra graphtheory walk adjacency-matrix generic

Please Wait...