> 2) Graph theory. Creating graphs (weighted, unweighted, directed,
> undirected), drawing graphs (this may require another plotting
> package to gnuplot), modifying graphs, testing for planarity, euler
> and hamiltonian paths and circuits. Minimal spanning trees, shortest
> paths, coloring and matching, flow algorithms.
I have a graph theory package for maxima which I wrote when I needed
it for my work. I think it has most of what you list here implemented.
If anyone would find it useful I can send a copy.
Andrej