Graphs in maxima

graphs.mac

anyp(pred, seq) := lreduce(lambda([P, x], P or pred(x)), seq, false);
allp(pred, seq) := lreduce(lambda([P, x], P and pred(x)), seq, true);

walklength(seq) := (length(seq)-1)/2;
walkverts(seq) := makelist(seq[2*i-1], i, 1, walklength(seq)+1);
walkedges(seq) := makelist(seq[2*i], i, 1, walklength(seq));
closedp(seq) := is(first(seq) = last(seq));

vertexset(G) := first(G);
edgeset(G) := second(G);
incidentset(G) := third(G);
incidents(G, e) := assoc(e, incidentset(G), []);

vertexp(G, v) := member(v, vertexset(G));
edgep(G, e) := member(e, edgeset(G));
incidentp(G, e, v) := member(v, incidents(G, e));
edgejoinsp(G, e, u, v) :=
	if is(u = v) then
		(is(incidents(G, e) = [u, u]) or is(incidents(G, e) = {u}))
	else
		(incidentp(G, e, u) and incidentp(G, e, v));

walkp(G, seq) :=
	if (is(length(seq) = 0) or not(vertexp(G, first(seq)))) then
		false
	else if is(length(seq) = 1) then
		true
	else
		(length(seq) > 2
		and edgejoinsp(G, second(seq), first(seq), third(seq))
		and walkp(G, rest(seq, 2)));

pathp(G, seq) :=
	(walkp(G, seq)) and
	block([vs], vs: walkverts(seq),
		is(length(vs) = length(setify(vs))));

cyclep(G, seq) :=
	closedp(seq) and
	walkp(G, seq) and
	(is(length(seq) = 1) or pathp(G, rest(seq, 2))) and
	block([vs], es: walkedges(seq),
		is(length(es) = length(setify(es))));

forestp(G, edges) :=
	if is(length(edges) = 0) then
		true
	else if anyp(lambda([e], not(edgep(G, e))), edges) then
		false
	else block([verts, isforest],
		verts: [],
		isforest: true,
		for e in edges do
			if allp(lambda([v], member(v, verts)), listify(incidents(G, e))) then
				(isforest: false) or return
			else
				verts: append(verts, listify(incidents(G, e))),
		return(isforest)
	);

spanningtreep(G, edges) :=
	is(length(edges) = length(vertexset(G)) - 1) and forestp(G, edges);

cyclelengthp(G, n, seq) := cyclep(G, seq) and is(walklength(seq) = n);

VV: {u,v,w,x};
EE: [a,b,c,d,e,f,g];
AA: [a={u,v}, b={v,w}, c={w,x}, d={w,x}, e={u,w}, f={u,x}, g={x,x}];
GG: [VV, EE, AA];

walkp(GG, [u, a, v, b, w, d, x, g, x, c, w]);
pathp(GG, [u, f, x, d, w]);
cyclep(GG, [u, f, x, d, w, e, u]);
walklength([u, f, x, d, w, e, u]);
walkp(GG, [u, a, x]);

spanningtreep(GG, [a, b, f]);

cyclelengthp(GG, 4, [u, f, x, d, w, e, u]);

cyclep(GG, [x,d,w,d,x]);