Sorry this took a few days. It was a bit more complicated than I anticipated. The main complexity was that Graphs need to have unqiue labels for each vertex, but, of course, we may want to repeat labels in the tree.

I welcome any critiques of my module. Especially, I'd like to know if there are any modern aspects modules that I could have used.

(* Written by Carl Love, 16-Mar-2013.

A module to convert a function tree representation (such as is returned by ToInert

or various commands in XMLtools) into a tree represented in the GraphTheory package

*)

FunctionToTree:= module()

local

(*____________________________________________________________________________________

Phase 1: Build a representation of the tree in tables with each vertex represented by

by an integer and each edge by an ordered pair of integers.

``````````````````````````````````````````````````````````````````````````````````````*)

# Vertices is a table that maps the original functional representation of the

# node to an integer. VertexLabels is simply the inverse of that table.

Vertices::table, VertexLabels::table, Vertex_index::nonnegint,

# Edges is a set (stored as a table indexed by an integer for efficiency)

# of ordered pairs of vertices in their integer representation.

Edges::table, Edge_index::nonnegint,

AddEdge:= proc(e::list(function))

Edge_index:= Edge_index + 1;

Edges[Edge_index]:= [Vertices[e[1]], Vertices[e[2]]]

end proc,

AddVertex:= proc(x::function)

Vertex_index:= Vertex_index + 1;

Vertices[x]:= Vertex_index;

VertexLabels[Vertex_index]:= x

end proc,

# Recursive

AddSubTree:= proc(f::function(function))

local x::function;

for x in f do

#Make functions unique.

if assigned(Vertices[x]) then x:= convert(op(0,x), `local`)(op(x)) fi;

AddVertex(x);

#Leaves are type function but not function(function).

if x::function(function) then thisproc(x) end if;

AddEdge([f,x])

end do

end proc,

(*__________________________________________________________________________________

Phase 2: Shorten the function labels to something that can be shown on a plot of the

tree but which is still meaningful.

`````````````````````````````````````````````````````````````````````````````````````*)

# Prefix is the number of chars at the beginning of each function name that

# can be trimmed off. For example, if every function name begins _Inert_, then

# Prefix should be set to 7. This value is passed in by the user.

Prefix::nonnegint,

# Labels is a table mapping the string form of the shortened function names to

# alternative (usually abbreviated) representations. For example, "SUM" can be

# mapped to `+`. This is passed in by the user.

Labels::table,

#Shorten the function names

StripName:= proc(f::function)

local f0:= sprintf("%a", op(0,f))[Prefix+1 .. -1];

`if`(assigned(Labels[f0]), Labels[f0], nprintf("%s", f0))

end proc,

ShortenLabels:= proc()

local k::nonnegint, f::function, f0::symbol;

VertexMap:= table();

for k to Vertex_index do

f:= VertexLabels[k];

f0:= StripName(f);

if not f::function(function) then

#For leaves, display the function operands also.

f0:= nprintf("%Q", `if`(f0 = ``, op(f), f0(op(f))))

end if;

if assigned(VertexMap[f0]) then f0:= convert(f0, `local`) fi;

VertexMap[f0]:= f;

VertexLabels[k]:= f0

end do

end proc,

(*____________________________________________________________________________________

Main

``````````````````````````````````````````````````````````````````````````````````````*)

ModuleInits:= proc()

Edges:= table();

Edge_index:= 0;

Vertices:= table();

VertexLabels:= table();

Vertex_index:= 0

end proc,

ModuleApply:= proc(func::function(function), {Labels::table:= table(), Prefix::nonnegint:= 0})

ModuleInits();

thismodule:-Prefix:= Prefix;

thismodule:-Labels:= Labels;

AddVertex(func); #Root the tree

AddSubTree(func); #Phase 1

ShortenLabels(); #Phase 2

#Subs the short labels into the integer labels, then build and return the graph

GraphTheory:-Graph(subs(op(eval(VertexLabels)), convert(Edges, set)))

end proc

;

# VertexMap is a table mapping the short labels to their original functions

export VertexMap::table;

end module;

Download FunctionTree.mw