Backtracking is an algorithmic technique for searching in combinatorial spaces: For instance, when you need to find a particular function (morphism, coloring, etc) subject to some criterion (isomorphism, proper coloring, etc).
In this chapter we describe the technique and the facilities provided by YAGS to aid in the rapid prototyping of backtracking algorithms. This chapter is written for the non-expert programmer, which is who can benefit the most from these facilities.
While the expert programmers will not have any problem designing their own backtracking algorithms, they can still benefit from YAGS's backtracking facilities since it may still be faster to implement/test/prototype a backtracking algorithm using YAGS's facilities. We recommend the expert programmer to go directly to Backtrack (B.2-1) where a minimal non-trivial example (for computing derangements) is shown.
The kind of combinatorial problems that can be addressed by backtracking are those that can be represented by a decision tree: those where we have to make a succession of choices to find a solution. These include problems where we want to find: morphisms, isomorphisms, cages, colorings, cliques, Hamiltonian cycles, walks, paths, subgraphs, and much, much more. Combinatorial problems that can be represented by a decision tree are truly everywhere. YAGS backtracking facilities are provided by means of the operations BacktrackBag(Opts,Chk,Done,Extra) and Backtrack(L,Opts,Chk,Done,Extra).
Opts and DoneAs a concrete example consider graph colorings: You have a set of colors, say ["red", "green"] and a graph, say g:=PathGraph(3), whose vertices are [1, 2, 3]. Then a coloring is a function f: {1, 2, 3} → {red, green}, which in YAGS would be represented by a List L:=[ f(1), f(2), f(3)]. There are (obviously) eight of such colorings, which are easy to list using BacktrackBag(Opts,Chk,Done,Extra):
gap> colors:=["red","green"]; [ "red", "green" ] gap> BacktrackBag(colors,ReturnTrue,3,[]); [ [ "red", "red", "red" ], [ "red", "red", "green" ], [ "red", "green", "red" ], [ "red", "green", "green" ], [ "green", "red", "red" ], [ "green", "red", "green" ], [ "green", "green", "red" ], [ "green", "green", "green" ] ] gap> Length(last); 8
In the previous example, only two parameters of BacktrackBag are really used, namely: Opts (which stands for options) and Done; when used in this way, Opts is simply the codomain of the sought function and Done is simply the size of the domain. When working with graph colorings it is common to use numbers instead of actual colors or color names, so we could also write even more compactly:
gap> BacktrackBag([0,1],ReturnTrue,3,[]); [ [ 0, 0, 0 ], [ 0, 0, 1 ], [ 0, 1, 0 ], [ 0, 1, 1 ], [ 1, 0, 0 ], [ 1, 0, 1 ], [ 1, 1, 0 ], [ 1, 1, 1 ] ]
Sometimes you just want a few solutions and not the whole bag. This is specially true when the bag is too huge (which is often the case since the bag tend to grow exponentially in the size of the domain). For these cases, we have Backtrack(L,Opts,Chk,Done,Extra):
gap> L:=[]; [ ] gap> Backtrack(L,[0,1],ReturnTrue,3,[]); [ 0, 0, 0 ] gap> L; [ 0, 0, 0 ] gap> Backtrack(L,[0,1],ReturnTrue,3,[]); [ 0, 0, 1 ] gap> L; [ 0, 0, 1 ] gap> L:=[1,1,0]; [ 1, 1, 0 ] gap> Backtrack(L,[0,1],ReturnTrue,3,[]); [ 1, 1, 1 ] gap> L; [ 1, 1, 1 ] gap> Backtrack(L,[0,1],ReturnTrue,3,[]); fail gap> L; [ fail ]
Backtrack(L,Opts,Chk,Done,Extra) returns one solution at a time and it also stores the solution within L, so that L can be used as a starting point for the search of the next solution. Usually, L:=[] is used for the first search. When Calling Backtrack(L,Opts,Chk,Done,Extra), L may also contain a partial solution (i.e. a prefix of a solution like L:=[ 1 ] or L:=[ 1, 0 ]), however Backtrack will trust the user on this and it will not check that L is indeed a partial solution.
Backtrack returns fail when no more solutions are available, but for technical reasons, L must always be a list, so L:=[ fail ] is the final value of L.
Now, so far, the graph itself have not been used and the parameters Chk and Extra have not been explained. Both issues are addressed in the next section.
Chk and ExtraIn Graph Theory we are usually more interested in proper colorings than just in colorings. A proper coloring is a coloring in which no two adjacent vertices have the same color. We can easily accommodate the new requirement within our backtracking operations. We are going to use Chk to check the fulfillment of the condition at each step in the construction of a solution. Moreover, in order to check the new condition we certainly need the extra information contained in the graph we are coloring. This extra information (the graph) is passed in the Extra parameter.
More generally, Chk is a user-provided function Chk(L,Extra) which receives a partial solution L and some extra information Extra; it returns false whenever it knows that L can not be completed to a full solution and it returns true otherwise. Note then that our backtracking operations internally call Chk several times during the process of constructing each solution: once each time L grows in length. In each call to Chk it is safe to assume that all proper prefixes of L have already been verified and approved by Chk.
In our example, L contains the color choices already made for the first vertices: 1, 2, ... Length(L). It is safe to assume that all but the last choice are already checked to satisfy the properness requirement. The last color choice so far is then the one in L[Length(L)] and we have to check (within Chk) if it also satisfy the properness requirement. We can do it like this:
gap> g:=PathGraph(3);; gap> chk:=function(L,g) > local x,y; > if L=[] then return true; fi; > x:=Length(L); > for y in [1..x-1] do > if IsEdge(g,[x,y]) and L[x]=L[y] then > return false; > fi; > od; > return true; > end; function( L, g ) ... end gap> BacktrackBag([0,1],chk,Order(g),g); [ [ 0, 1, 0 ], [ 1, 0, 1 ] ]
Now we get only two solutions, as expected. We emphasize here the fact that Chk is internally called by BacktrackBag each time L grows in length. Therefore (for instance) at some point the partial solution [ 0, 0 ] is tried and since it is found unfeasible by Chk is is discarded and no other partial solution with that prefix is ever tried. This produces huge reductions in execution time as compared to the (naive) approach of computing all the colorings first and then filtering out those which does not satisfy the properness requirement. In particular we can compute proper colorings for graphs where the naive approach fails:
gap> g:=PathGraph(70);; gap> BacktrackBag([0,1],chk,Order(g),g); [ [ 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 ], [ 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 ] ]
Of course, we can now compute proper colorings for many other graphs as well:
gap> g:=CycleGraph(5);; gap> BacktrackBag([0,1],chk,Order(g),g); [ ] gap> BacktrackBag([0,1,2],chk,Order(g),g); [ [ 0, 1, 0, 1, 2 ], [ 0, 1, 0, 2, 1 ], [ 0, 1, 2, 0, 1 ], [ 0, 1, 2, 0, 2 ], [ 0, 1, 2, 1, 2 ], [ 0, 2, 0, 1, 2 ], [ 0, 2, 0, 2, 1 ], [ 0, 2, 1, 0, 1 ], [ 0, 2, 1, 0, 2 ], [ 0, 2, 1, 2, 1 ], [ 1, 0, 1, 0, 2 ], [ 1, 0, 1, 2, 0 ], [ 1, 0, 2, 0, 2 ], [ 1, 0, 2, 1, 0 ], [ 1, 0, 2, 1, 2 ], [ 1, 2, 0, 1, 0 ], [ 1, 2, 0, 1, 2 ], [ 1, 2, 0, 2, 0 ], [ 1, 2, 1, 0, 2 ], [ 1, 2, 1, 2, 0 ], [ 2, 0, 1, 0, 1 ], [ 2, 0, 1, 2, 0 ], [ 2, 0, 1, 2, 1 ], [ 2, 0, 2, 0, 1 ], [ 2, 0, 2, 1, 0 ], [ 2, 1, 0, 1, 0 ], [ 2, 1, 0, 2, 0 ], [ 2, 1, 0, 2, 1 ], [ 2, 1, 2, 0, 1 ], [ 2, 1, 2, 1, 0 ] ] gap> g:=Icosahedron;; gap> Backtrack([],[0,1,2],chk,Order(g),g); fail gap> Backtrack([],[0,1,2,3],chk,Order(g),g); [ 0, 1, 2, 1, 2, 3, 3, 0, 2, 3, 0, 1 ]
Opts and Done are functionsOur backtracking operations BacktrackBag(Opts,Chk,Done,Extra) and Backtrack(L,Opts,Chk,Done,Extra) are even more flexible that shown so far. In our previous examples Opts was always a list and Done was always an integer. Both can also be functions.
When Opts is a function, it receives L and Extra, and then Opts(L,Extra) should return the list of options available to extend the partial solution L at that particular stage. This way the list of options can be different at different times which is useful for instance when the union of all possible options is too big or even unbounded.
When Done is a function, it also receives L and Extra, and then Done(L,Extra) returns true whenever L is a full solution and it returns false otherwise. This is useful when not all the solutions have the same length. Thus the number N we used to put in place of the function Done(L,Extra) is equivalent to the function Done:=function(L,Extra) return Length(L) >= N; end;.
Also, when a number N is used in place of Done, an implicit upper bound Length(L)<= N is added internally to Chk, so it is imperative to add such an explicit bound to Chk when a function is used for Done otherwise the backtracking algorithm will try to find longer and longer solutions without bound or end until the memory of the computer is exhausted.
As an example, assume we want to find all the walks on 5-cycle that start at vertex 1 and end at vertex 2 with length at most 4 (at most 5 vertices). Then we can proceed as follows:
gap> g:=CycleGraph(5); Graph( Category := SimpleGraphs, Order := 5, Size := 5, Adjacencies := [ [ 2, 5 ], [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 1, 4 ] ] ) gap> opts:=function(L,g) > if L=[] then > return [1]; > else > return Adjacency(g,L[Length(L)]); > fi; > end; function( L, g ) ... end gap> chk:=function(L,g) return Length(L)<= 5; end; function( L, g ) ... end gap> done:=function(L,g) return L[Length(L)]=2; end; function( L, g ) ... end gap> BacktrackBag(opts,chk,done,g); [ [ 1, 2 ], [ 1, 2, 1, 2 ], [ 1, 2, 3, 2 ], [ 1, 5, 1, 2 ], [ 1, 5, 4, 3, 2 ] ]
Finally you may wonder why only one extra parameter Extra is allowed, what if I need more than one? Well, the parameter Extra may be any object supported by GAP; indeed YAGS only uses it to pass information to the user-defined functions Opts(L,Extra), Chk(L,Extra) and Done(L,Extra). Hence, if you need pass more than one extra parameter, say two graphs g and h, you just put them in a list (or record, etc) and pass the parameter Extra:=[g,h].
Sooner or later you will need to debug a backtracking algorithm that is not working as expected, or at least, you would like to know how much work your algorithm has done and how much remains to be done to decide if it is worth waiting for an answer (since backtracking techniques easily produce algorithms which may take eons to finish).
All of YAGS's backtracking operations report progress info at InfoLevel 3 to YAGS's info class YAGSInfo.InfoClass (see B.24-3). In short, this means that setting SetInfoLevel(YAGSInfo.InfoClass,3); will cause all backtracking operations to report progress information to the console: The contents of L will be reported each time it grows in length. Revert to the default behavior by setting the InfoLevel to 0 using SetInfoLevel(YAGSInfo.InfoClass,0);
gap> SetInfoLevel(YAGSInfo.InfoClass,3); gap> BacktrackBag([0,1],ReturnTrue,3,[]); #I [ ] #I [ 0 ] #I [ 0, 0 ] #I [ 0, 0, 0 ] #I [ 0, 0, 1 ] #I [ 0, 1 ] #I [ 0, 1, 0 ] #I [ 0, 1, 1 ] #I [ 1 ] #I [ 1, 0 ] #I [ 1, 0, 0 ] #I [ 1, 0, 1 ] #I [ 1, 1 ] #I [ 1, 1, 0 ] #I [ 1, 1, 1 ] [ [ 0, 0, 0 ], [ 0, 0, 1 ], [ 0, 1, 0 ], [ 0, 1, 1 ], [ 1, 0, 0 ], [ 1, 0, 1 ], [ 1, 1, 0 ], [ 1, 1, 1 ] ] gap> SetInfoLevel(YAGSInfo.InfoClass,0); gap> BacktrackBag([0,1],ReturnTrue,3,[]); [ [ 0, 0, 0 ], [ 0, 0, 1 ], [ 0, 1, 0 ], [ 0, 1, 1 ], [ 1, 0, 0 ], [ 1, 0, 1 ], [ 1, 1, 0 ], [ 1, 1, 1 ] ]
The output of the progress info may be redirected to a file or character device by setting the variable YAGSInfo.InfoOutput (B.24-4) accordingly.
The information in this section about progress reporting applies to all YAGS functions that internally use Backtrack (B.2-1) or BacktrackBag (B.2-2), namely CompletesOfGivenOrder (B.3-14), Orientations (B.15-4) and all morphism-related operations in Chapter 5.
generated by GAPDoc2HTML