Yesterday, user @lcz , while responding as a third party to one of my Answers regarding GraphTheory, asked about breadth-first search. So, I decided to write a more-interesting example of it than the relatively simple example that was used in that Answer. I think that this is general enough to be worthy of a Post.
This application generates all maximal paths in a graph that begin with a given vertex. (I'm calling a path maximal if it cannot be extended and remain a path.) This code requires Maple 2019 or later and 1D input. This works for both directed and undirected graphs. Weights, if present. are ignored.
restart:
AllMaximalPaths:= proc(G::GRAPHLN, v)
description
"All maximal paths of G starting at v by breadth-first search"
;
option `Author: Carl Love <carl.j.love@gmail.com> 2021-Mar-17`;
uses GT= GraphTheory;
local
P:= [rtable([v])], R:= rtable(1..0),
VL:= GT:-Vertices(G), V:= table(VL=~ [$1..nops(VL)]),
Departures:= {op}~(GT:-Departures(G))
;
while nops(P) <> 0 do
P:= [
for local p in P do
local New:= Departures[V[p[-1]]] minus {seq}(p);
if New={} then R,= [seq](p); next fi;
(
for local u in New do
local p1:= rtable(p); p1,= u
od
)
od
]
od;
{seq}(R)
end proc
:
#large example:
GT:= GraphTheory:
K9:= GT:-CompleteGraph(9):
Pa:= CodeTools:-Usage(AllMaximalPaths(K9,1)):
memory used=212.56MiB, alloc change=32.00MiB,
cpu time=937.00ms, real time=804.00ms, gc time=312.50ms
nops(Pa);
40320
#fun example:
P:= GT:-SpecialGraphs:-PetersenGraph():
Pa:= CodeTools:-Usage(AllMaximalPaths(P,1)):
memory used=0.52MiB, alloc change=0 bytes,
cpu time=0ns, real time=3.00ms, gc time=0ns
nops(Pa);
72
Pa[..9]; #sample paths
{[1, 2, 3, 4, 10, 9, 8, 5], [1, 2, 3, 7, 8, 9, 10, 6],
[1, 2, 9, 8, 7, 3, 4, 5], [1, 2, 9, 10, 4, 3, 7, 6],
[1, 5, 4, 3, 7, 8, 9, 2], [1, 5, 4, 10, 9, 8, 7, 6],
[1, 5, 8, 7, 3, 4, 10, 6], [1, 5, 8, 9, 10, 4, 3, 2],
[1, 6, 7, 3, 4, 10, 9, 2]}
Notes on the procedure:
The two dynamic data structures are
- P: a list of vectors of vertices. Each vector contains a path which we'll attempt to extend.
- R: a vector of lists of vertices. Each list is a maximal path to be returned.
The static data structures are
- V: a table mapping vertices (which may be named) to their index numbers.
- Departures: a list of sets of vertices whose kth set is the possible next vertices from vertex number k.
On each iteration of the outer loop, P is completely reconstructed because each of its entries, a path p, is either determined to be maximal or it's extended. The set New is the vertices that can be appended to the p (connected to vertex p[-1]). If New is empty, then p is maximal, and it gets moved to R.
The following code constructs an array plot of all the maximal paths in the Petersen graph. I can't post the array plot, but you can see it in the attached worksheet: BreadthFirst.mw
#Do an array plot of each path embedded in the graph:
n:= nops(Pa):
c:= 9:
plots:-display(
(PA:= rtable(
(1..ceil(n/c), 1..c),
(i,j)->
if (local k:= (i-1)*ceil(n/c) + j) > n then
plot(axes= none)
else
GT:-DrawGraph(
GT:-HighlightTrail(P, Pa[k], inplace= false),
stylesheet= "legacy", title= typeset(Pa[k])
)
fi
)),
titlefont= [Times, Bold, 12]
);
#And recast that as an animation so that I can post it:
plots:-display(
[seq](`$`~(plots:-display~(PA), 5)),
insequence
);
