Help:=proc(): print(`Ham(G), IsLegal(G,P), EulerB(G), `): print(`Fleury(G,u),CC(G,V), FindFollower(G,u) `): end: #IsLegal(G,P): is the path P feasible in the graph G? IsLegal:=proc(G,P) local i: evalb({seq(member([P[i],P[i+1]],G[2]),i=1..nops(P)-1)}={true}): end: with(combinat): #Ham(G): Inputs a directed graph (in the form [V,E]) #and outputs all Hamiltinian paths Ham:=proc(G) local V,E,n,S,Sg,i: V:=G[1]: E:=G[2]: S:=permute(V): Sg:={}: for i from 1 to nops(S) do if IsLegal(G,S[i]) then Sg:=Sg union {S[i]}: fi: od: Sg: end: #IsLegalE(G,P): Is the sequence of edges P #feasible in the graph G? IsLegalE:=proc(G,P) local i: evalb({seq(evalb(P[i][2]=P[i+1][1]),i=1..nops(P)-1)}={true}): end: #EulerB(G): Inputs a directed graph (in the form [V,E]) #and outputs all Eulerian paths by stupid brute force EulerB:=proc(G) local V,E,n,S,Sg,i: V:=G[1]: E:=G[2]: S:=permute(E): Sg:={}: for i from 1 to nops(S) do if IsLegalE(G,S[i]) then Sg:=Sg union {S[i]}: fi: od: Sg: end: #CC(G,v): Inputs a directed graph G=[V,E] #and a vertex v in V and outputs #the set of vertices reachable from v #via a legal path of any length CC:=proc(G,v) local i,V,E,OutN,InN,V1,V2: V:=G[1]: E:=G[2]: for i from 1 to nops(V) do InN[V[i]]:={}: OutN[V[i]]:={}: od: for i from 1 to nops(E) do OutN[E[i][1]]:= OutN[E[i][1]] union {E[i][2]}: InN[E[i][2]]:= InN[E[i][2]] union {E[i][1]}: od: V1:={v}: V2:= V1 union OutN[v]: while V1<>V2 do V1:=V2: V2:=V2 union {seq(op(OutN[V2[i]]),i=1..nops(V2))}: od: V2: end: #Given a directed graph G=[V,E] and a vertex #u in V finds a good follower #(a vertex v such that [u,v] is in E and #does not disconnet the graph FindFollower:=proc(G,u) local V,E,InN,OutN,f,i,Nu,G1,E1: V:=G[1]: E:=G[2]: for i from 1 to nops(V) do InN[V[i]]:={}: OutN[V[i]]:={}: od: for i from 1 to nops(E) do OutN[E[i][1]]:= OutN[E[i][1]] union {E[i][2]}: InN[E[i][2]]:= InN[E[i][2]] union {E[i][1]}: od: Nu:=OutN[u]: if nops(Nu)=1 then RETURN(Nu[1]): fi: for i from 1 to nops(Nu) do E1:=E minus {[u,Nu[i]]}: G1:=[V,E1]: if CC(G1,Nu[i])=V then RETURN(Nu[i]): fi: od: FAIL: end: #Fleury(G,u): Inputs a directed graph [V,E] #and a vertex u #and outputs a Eulerian cycle Fleury:=proc(G,u) local i,V,E,OutN,InN,E1,V1,cv,Path1,f,G1: V:=G[1]: E:=G[2]: for i from 1 to nops(V) do InN[V[i]]:={}: OutN[V[i]]:={}: od: for i from 1 to nops(E) do OutN[E[i][1]]:= OutN[E[i][1]] union {E[i][2]}: InN[E[i][2]]:= InN[E[i][2]] union {E[i][1]}: od: for i from 1 to nops(V) do if nops(InN[V[i]])<>nops(OutN[V[i]]) then RETURN(FAIL): fi: od: V1:=V: E1:=E: G1:=G: cv:=u: Path1:=[u]: while V1<>{u} do f:=FindFollower(G1,cv): Path1:=[op(Path1),f]: E1:=E1 minus {[cv,f]}: OutN[cv]:=OutN[cv] minus {f}: if nops(OutN[cv])=0 and cv<>u then V1:=V1 minus {cv}: fi: G1:=[V1,E1]: cv:=f: od: Path1: end: