## Maximal paths via breadth-first search

by: Maple 2019

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 (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
);

``` ## RE: rewriting an expression with substitution...

Hello there,

Would you allow me to ask this (perhaps simple) question?

My goal is to express an equation as 'desired', but with no success with algsubs()/subs()/simplify().

Would you please show me the correct way?

 > restart:
 > PowerBalanceEq := 0 = e1(t) * i1(t) + e2(t) * i2(t) + e3(t) * i3(t); (1)
 > eq_i1 := i1(t) = solve(PowerBalanceEq, i1(t)); (2)
 > n21eq := n21 = e2(t) / e1(t); (3)
 > eq_i2 := algsubs(n21eq, eq_i1); (4)
 > eq_i3 := subs(n21eq, eq_i1); (5)
 > eq_i4 := simplify(eq_i1, {e2(t) / e1(t) = n21}); (6)
 > desired := i1(t) = -n21*i2(t) - e3(t)*i3(t)/e1(t); (7)
 >

Best Regards,

In Kwon Park

## Detect and print the operating system....

Is there a means of getting Maple to detect and print the operating system which it is being run on? Searching for this topic is awkward as it returns page after page of troubleshooting guides on how to get Maple running on different operating systems.

Conventionally in Bash I would use something like: echo \$(uname)

## how to find Derivative in loop?...

PLs, correct my code about how to find the derivative by using the loop concept in maple?

help_derivative_in_loop.mw

## indefinite definite easily evaluated, definite int...

Can anyone look at this worksheet, and explain why maple seems to complicate an easily evaluated integral? Hyper.mw

## system hanged on doing integration...

Hi, I am trying to integrate a lengthy-expression but maple does not give a result and got hanged even after waiting 1 hour and more, pls help me to handle this or is this any other way to get a result?

Help_of_Integration.mw

## how to write loop and solve the algebric expressi...

Hi, how to write a loop and solve the algebraic expression? is the loop and do loop are the same thing? if different then pls mention how to solve the same question by using do loop?

solution_loop_help.mw

## Test solutions of a polynomial equation...

Suppose I have the equation C := y^2*z + yz^2 = x^2, then I want to test for which triples (x,y,z) with x,y,z in {0,1} the equation is satisfied? Is there a quick way of doing this in Maple?

## How to rearrange an equation by coefficients' val...

I am trying to rearrange the elements of an equation by the absolute value of their coefficients. eg -3y^2 x+2x z^2+6z^2 to

2x z^2 -3y^2 +6z^2

## How and why did Maple do this Sum correctly?...

1. How did Maple come up with this answer?

I've tried all the packages in SumTools and none of them give an answer except Hypergeometric.

2. Is there a way to trace the steps Maple is using so I can try and answer this myself?

3. Why did it sum the series when I didn't even ask - I deliberately used the inert form (no arguments though - I like what it did).

Thank you.

______________________________________________________________________________

H1a := Sum(GAMMA(2*b - 1 + 2*n)*GAMMA(2*n - s)*(b - 1/2 + 2*n)/(GAMMA(2*b + 2*n + s)*GAMMA(2*n + 1)), n = 0 .. infinity);

H1b:=convert(H1a,Hypergeom);

The answer H1b it came up with is

GAMMA(-s)*2^(1 + 2*b)*GAMMA(b)/(8*GAMMA(b + s)*2^(2*b));

which seems to be correct.

## RE: How to pick up the numerical values from the s...

Hello there,

Would please tell me how to pick up numerical vaules from answers given by 'solve()' command?

If you look at the worksheet (sorry for the error), one possible way is labeled by 'solution 1'. However, when I tried the expression in the 'attempt 1' label, I got an error. Therefore, I'm wondering if there is a way to extract the values from the answers, instead of using the 'rhs()' command.

Maple Worksheet - Error

Failed to load the worksheet /maplenet/convert/q20210206.mw .

Best Regards,

In Kwon Park

## RE: How to ask Maple not to automatically convert...

Hello all,

When I enter the following expression:

eqaux_2 := l__bb = L__aa0 + L__aa2 * cos(2*theta - 4/3*Pi);

the cos function got converted an equivalent sin function automatically and the result was displayed like this:

l__bb = L__aa0 - L__aa2*sin(2*theta + Pi/6)

Is there any way to ask Maple not to do this automatic conversion?

Maple Worksheet - Error

Failed to load the worksheet /maplenet/convert/q20210204.mw .

## RE: solving a set of non-linear equations...

Hello there,

The equations described below are third-order equations. Therefore, the number of solutions would be 3.

However, when I tried to solve them using the 'solve' command, only two solutions came out.

Is there any chance to find the last one?

Maple Worksheet - Error

Failed to load the worksheet /maplenet/convert/Q20210201.mw .

## RE: how Maple solve an equation...

Hello there,

When I tried to solve an equation using the 'solve' command in Maple, I got an answer.

However, I could not understand how Maple got to the answer. Would you tell me what steps Maple might have gone through in order to come to the answer?

Here is my worksheet:

q20210130.mw

Maple Worksheet - Error

Failed to load the worksheet /maplenet/convert/q20210130.mw .

PS) Perhaps this editbox began to dislike Google Chrome.

## How to get map to work?...

Hi,

I was able to get Procedure 2 to work using a for - do loop. I was wondering if it is possible to speed up the calculation by using map to find the number of roots? I do not fully understand map and passing data.

tgf := proc(a, b, c, d, t, m, n)

local X;

X := [solve(abs(a*x + b) + abs(c*x + d) - t*x^2 + m*x - n = 0)];

return nops(X);

end proc;

res := CodeTools:-Usage(map(tgf, L));
Error, (in CodeTools:-Usage) invalid input: tgf uses a 2nd argument, b, which is missing

The L Array is tripping me up, here is a partial display of the array:

Array(1..262, 1..7, [[5,2,3,9,1,1,1],[5,2,3,9,2,1,1],[5,4,3,7,1,1,1],[5,4,3,7,2,1,1],[5,5,3,6,1,1,1],[5,5,3,6,2,1,1],[5,5,4,8,1,1,2],[5,5,4,8,2,1,2], ... ,[10,10,5,10,2,2,2]], datatype = integer).

I made L Array into a list of list, R. Somewhat works.

Here is the script:

Thanks for any help.

﻿