# Experimental Math Rocks
# Math-640 Project: Explore Solitaire games using Depth First Search (DFS)
# Phil Benjamin

# DFS Application: Find Path in Graph from Source to Sink
# Prefix for this application: GR

# Note: directed graph defined by edge lists, not edge sets!

# Global variables
GR := [[],[8,7],[8,7,2,5],[],[8,2,7,1],[10,9,2,3],[8,2,3],[7,6,3]]:
GRstart := 8:
GRend := 1:
GRpath := []:

# Packages
with(ListTools):

# Control program
GRpathControl := proc()
	local success;
	success := DFScontrol(GRinit,GRisTerm,
	GRnextProg,GRnextAlt,GRnextBack);
	if success then print(GRpath);
	else print(`No path`);
	end if;
end proc:

GRinit := proc()
	global GRpath,GRstart;
	GRpath := [GRstart];
end proc:

GRisTerm := proc()
	global GRpath,GRend;
	return GRpath[nops(GRpath)] = GRend;
end proc:

GRnextProg := proc()
	global GR,GRpath;
	local n; # length of path
	local i; # current end node
	local j; # next node (maybe)
	local k; # index of next node
	n := nops(GRpath);
	if n = 0 then return false; end if;
	i := GRpath[n];
	for k from 1 to nops(GR[i]) do
		j := GR[i][k];
		if Search(j,GRpath) = 0 then
			GRpath := [op(GRpath),j];
			return true;
		end if;
	end do;
	return false;
end proc:

GRnextAlt := proc()
	global GR,GRpath;
	local n; # length of path
	local iPrev; # next-to-last in path
	local iCurr; # last in path
	local j; # next node (maybe)
	local k; # index of next node
	n := nops(GRpath);
	if n < 2 then return false; end if;
	iPrev := GRpath[n-1]; iCurr := GRpath[n];
	k := Search(iCurr,GR[iPrev]);
	if k = 0 or k = nops(GR[iPrev]) then
		return false;
	end if;
	for k from k+1 to nops(GR[iPrev]) do
		j := GR[iPrev][k];
		if Search(j,GRpath) = 0 then
			GRpath := [op(1..n-1,GRpath),j];
			return true;
		end if;
	end do;
	return false;
end proc:

GRnextBack := proc()
	global GRpath;
	local n;
	n := nops(GRpath);
	if n < 2 then return false; end if;
	GRpath := [op(1..n-1,GRpath)];
	return true;
end proc: