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 k^{th} 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
); **