Plans for graphs in Maxima/Lisp.
More...
Go to the source code of this file.
Detailed Description
Plans for graphs in Maxima/Lisp.
 Todo:
 Organisation

See module "GraphTraversal" below.

See module "Treewidth" below.

See module "Matchings" below.

See module "Drawings" below.

Likely we should have modules "Homomorphisms" and "Isomorphisms".

It seems yet we have nothing on graph homo/isomorphisms.

Though isomorphisms are special homomorphisms, it seems their treatment is so specialised that we should have two independent modules.

There are also categories of graphs: Likely the organisation here should be the same as for hypergraphs and for clausesets.

In ComputerAlgebra/Satisfiability we have "Symmetries" instead of "Isomorphisms", and we have "Categories" which includes "Homomorphisms".

So perhaps also here we should have modules "Symmetries" and "Categories".

We need a submodule "Colourings".

A submodule "IndependentSets".

A submodule "Cliques".

Likely also a submodule "RandomGraphs".

And a submodule "RamseyTheory" (but this perhaps better belongs to Hypergraphs ?).

DONE See module "Trees" below.
 Todo:
 Complete tests

ComputerAlgebra/Graphs/Lisp/Basic.mac

Checking the defining properties : DONE

Checking equality : DONE

Promotions : DONE

Downcasts : DONE

Conversions : DONE

Basic graph operations : DONE

Basic graph constructions : DONE

Tests : DONE

Connections to Maximagraphs

Once all these tests are completed, new functions are only to be entered with tests.
 Todo:
 Redesign
 Todo:
 Representing edge and vertex labellings
 Todo:
 Lists instead of sets

Additionally to "graphs" and "general graphs" we introduce "ordered graphs" and "ordered general graphs":

Computationally these notions are considered to be more fundamental.

An ordered graphs is a pair [V,E], where V and E are lists without repetition, such that [setify(V),setify(E)] is a graph.

An ordered general graph is a triple [V,E,f], where V, E are lists without repetition, such that [setify(V),setify(E)] is a general graph.

An ordered multigraph is a triple [V,E,f], where [V,E] is an ordered graph, such that for the underlying graph [V',E'] it is [V',E,',f] a multigraph.
 Todo:
 Graphs as hypergraphs

The topic is discussed in "Polar hypergraphs" in ComputerAlgebra/Hypergraphs/Lisp/plans/Basics.hpp.

We need a good overview on the different representations of graphs via hypergraphs, incidence structures and combinatorial matrices:

On the one hand, these representations show different points of view.

And on the other hand they provide different data structures!
 Todo:
 Memoisation for general graphs and multigraphs

The function f in a general graph [V,E,f] could show three different types of computational strategies for computing f(e):

(i) f(e) could always be computed from scratch.

(ii) The other extreme is to store f as an array (and thus only compute the values once, when creating the general graph).

(iii) The intermediate strategy is the "lazy" one, where f(e) is computed only when needed, and then stored; see "Memoisation" in ComputerAlgebra/CombinatorialMatrices/Lisp/plans/general.hpp for how to do this.

It seems that in many cases the first strategy is alright, since different from combinatorial matrices, the edges in general graphs typically are just simple namingissues.

Also for multigraphs, in the typical applications the multiplicity of an edge is typically "given", not computed.

However for example for conflictgraphs of clausesets it seems best to compute f upfront (using (ii)).

Using a hashmap inside f is made easy by lambda_hm; though, since E is fixed, an array would be more efficient but this works only for edgelabels which are consecutive integers.
 Todo:
 Maxima package "graphs"

DONE (solved with version 5.18.1) Problems with the graph without vertices:

is_bipartite(empty_graph(0));
Evaluation took 0.0040 seconds (0.0001 elapsed) using 1.148 KB.
(%o294) false
though it should be true.

We also have
complete_graph(0);
Argument 1 to complete_graph is not a positive integer
 an error. To debug this try debugmode(true);

What is petersen_graph(n,d)?

We always have the outer and the inner cirle (each of length n), with the direct connections, and d is then the "step" to the next vertex on the inner circle.

Thus for d=0 there is no edge, for d=1 we have the two parallel edges, for n=2 we skip one (as for the Petersen graph), and for d=n/2 we get parallel edges.

The parallel edges shouldn't be possible?

And for d=0 actually print_graph shows loops??

Tell the mailinglist, that this needs documentation, and that the nongraph cases needs investigation.

In general we need to write docus for all the undocumented notions w.r.t. the Maxima graphsmodule.

We need conversions between graphs and maximagraphs.

We can use the vertexlabels (assuming they are present).

Currently, mg2g doesn't use the vertex labels (since they might not be there).

So we need a second version, which also translates the vertex labels.

How to call it? Which version is standard? Perhaps mg2g should translate the vertex labels, and "mg2g_nl" doesn't translate them.

DONE (no loops possible; so we have only "graphs" and "directed graphs") What about loops? Are they possible with Maxima graphs?

We need conversions between directed graphs and maximadigraphs.

"dg2mdg" needs to be complemented by two inverses, mdg2dg and mdg2dg_nvl.

DONE (not possible) What about loops?

DONE (the vertex names become vertex labels) Given a graph, we can either just forget the vertex names, or use them as vertex labels.

DONE And given a maximagraph, we can use the standardvertexnames 0, ...

DONE (only "graphs" and "digraphs", nothing else) Do Maxima graphs allow parallel edges? Apparently not.

DONE (exact values are computed) We need to find out whether for example the colouring function computes an exact value or an approximation! See my email to the maximamailinglist.

DONE (solved with installed gnuplotversion) Bug (with 5.14.0 and 5.15.0):
draw_graph(complete_graph(3))$
gnuplot> plot '/home/kullmann/data.gnuplot' index 0 t '' w lp ps 1 pt 0 lw 1 lt 1 lc rgb 'black', '/home/kullmann/data.gnuplot' index 1 t '' w lp ps 1 pt 0 lw 1 lt 1 lc rgb 'black', '/home/kullmann/data.gnuplot' index 2 t '' w lp ps 1 pt 0 lw 1 lt 1 lc rgb 'black', '/home/kullmann/data.gnuplot' index 3 t '' w p ps 2 pt 7 lc rgb 'red'
"/home/kullmann/maxout.gnuplot", line 22: ';' expected
Notify maxima mailinglist.
 Todo:
 Graph traversal

This likely deserves its own module "GraphTraversal".

Implement the generic graph traversal from module CS232.

This is likely best done with the maximagraphs.

Compute connected components and strong connected components.
 Todo:
 Treewidth
 Todo:
 Primitive directed graphs etc.

Compute the index of imprimitivity of a directed graph (with loops).

And for primitive directed graphs (with loops) compute the index of primitivity.

Again, perhaps best done with the maximagraphpackage. But then loops need to be handled specially (is this reasonable?).
 Todo:
 Generalised matching problems

Implement [David G. Kirkpatrick and Pavol Hell, On the completeness of a generalized matching problem, STOC'78].

That is, the NPcompleteness results (as reductions), and the polytime algorithms.

Perhaps this has been extended, and perhaps also simplified?

A variant is considered in [Dorit Dor and Michael Tarsi, Graph Decomposition is NPComplete: A Complete Proof of Holyer's Conjecture, SIAM Journal on Computing, 1997].
 Todo:
 Graph drawing

This should become module "Drawings".

We need our own graphdrawing functions:

Maxima cannot handle loops nor parallel edges.

The drawing algorithms are rather weak (but we should also try the possible plugins).

We need referencealgorithms.

And we need the possibility to fix our own drawings (for an example see "Visualising automorphisms" in ComputerAlgebra/Graphs/Lisp/Isomorphisms/plans/Homomorphisms.hpp).

We need to find out to what extend the Gnuplot functions can be used (this is likely our own possibility anyway).

But we must establish an abstract level, where the algorithms only produce abstract treedrawings (just usual Maximallists, with coordinates and other information), and as a separate layer then these abstractions are drawn.

Does there exist some basic "vocabulary" ?

Likely other graphdrawing packages can read such drawings (in a suitable output, of course). See "Concepts" in GraphDrawing/plans/general.hpp.
Definition in file general.hpp.