general.hpp File Reference

Plans for graphs in Maxima/Lisp. More...

Go to the source code of this file.

Detailed Description

Plans for graphs in Maxima/Lisp.

  • See module "GraphTraversal" below.
  • See module "Treewidth" below.
  • See module "Matchings" below.
  • See module "Drawings" below.
  • Likely we should have modules "Homomorphisms" and "Isomorphisms".
    1. It seems yet we have nothing on graph homo/isomorphisms.
    2. Though isomorphisms are special homomorphisms, it seems their treatment is so specialised that we should have two independent modules.
    3. There are also categories of graphs: Likely the organisation here should be the same as for hypergraphs and for clause-sets.
    4. In ComputerAlgebra/Satisfiability we have "Symmetries" instead of "Isomorphisms", and we have "Categories" which includes "Homomorphisms".
    5. 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.
Complete tests
  • ComputerAlgebra/Graphs/Lisp/Basic.mac
    1. Checking the defining properties : DONE
    2. Checking equality : DONE
    3. Promotions : DONE
    4. Downcasts : DONE
    5. Conversions : DONE
    6. Basic graph operations : DONE
    7. Basic graph constructions : DONE
    8. Tests : DONE
    9. Connections to Maxima-graphs
  • Once all these tests are completed, new functions are only to be entered with tests.
Representing edge and vertex labellings
Lists instead of sets
  • Additionally to "graphs" and "general graphs" we introduce "ordered graphs" and "ordered general graphs":
    1. Computationally these notions are considered to be more fundamental.
    2. 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.
    3. 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.
    4. 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.
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:
    1. On the one hand, these representations show different points of view.
    2. And on the other hand they provide different data structures!
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):
    1. (i) f(e) could always be computed from scratch.
    2. (ii) The other extreme is to store f as an array (and thus only compute the values once, when creating the general graph).
    3. (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.
    4. 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 naming-issues.
    5. Also for multigraphs, in the typical applications the multiplicity of an edge is typically "given", not computed.
    6. However for example for conflict-graphs of clause-sets it seems best to compute f up-front (using (ii)).
    7. Using a hash-map inside f is made easy by lambda_hm; though, since E is fixed, an array would be more efficient but this works only for edge-labels which are consecutive integers.
Maxima package "graphs"
  • DONE (solved with version 5.18.1) Problems with the graph without vertices:
    1. is_bipartite(empty_graph(0));
      Evaluation took 0.0040 seconds (0.0001 elapsed) using 1.148 KB.
      (%o294) false
      though it should be true.
    2. We also have
      Argument 1 to complete_graph is not a positive integer
       -- an error.  To debug this try debugmode(true);
  • What is petersen_graph(n,d)?
    1. 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.
    2. 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.
    3. The parallel edges shouldn't be possible?
    4. And for d=0 actually print_graph shows loops??
    5. Tell the mailing-list, that this needs documentation, and that the non-graph cases needs investigation.
  • In general we need to write docus for all the undocumented notions w.r.t. the Maxima graphs-module.
  • We need conversions between graphs and maxima-graphs.
    1. We can use the vertex-labels (assuming they are present).
    2. Currently, mg2g doesn't use the vertex labels (since they might not be there).
    3. So we need a second version, which also translates the vertex labels.
    4. How to call it? Which version is standard? Perhaps mg2g should translate the vertex labels, and "mg2g_nl" doesn't translate them.
    5. 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 maxima-digraphs.
    1. "dg2mdg" needs to be complemented by two inverses, mdg2dg and mdg2dg_nvl.
    2. 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 maxima-graph, we can use the standard-vertex-names 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 e-mail to the maxima-mailing-list.
  • DONE (solved with installed gnuplot-version) Bug (with 5.14.0 and 5.15.0):
    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 mailing-list.
Graph traversal
  • This likely deserves its own module "GraphTraversal".
  • Implement the generic graph traversal from module CS-232.
  • This is likely best done with the maxima-graphs.
  • Compute connected components and strong connected components.
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 maxima-graph-package. But then loops need to be handled specially (is this reasonable?).
Generalised matching problems
  • Implement [David G. Kirkpatrick and Pavol Hell, On the completeness of a generalized matching problem, STOC'78].
  • That is, the NP-completeness 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 NP-Complete: A Complete Proof of Holyer's Conjecture, SIAM Journal on Computing, 1997].
Graph drawing
  • This should become module "Drawings".
  • We need our own graph-drawing functions:
    1. Maxima cannot handle loops nor parallel edges.
    2. The drawing algorithms are rather weak (but we should also try the possible plug-ins).
    3. We need reference-algorithms.
    4. 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 tree-drawings (just usual Maximal-lists, with coordinates and other information), and as a separate layer then these abstractions are drawn.
  • Does there exist some basic "vocabulary" ?
  • Likely other graph-drawing packages can read such drawings (in a suitable output, of course). See "Concepts" in GraphDrawing/plans/general.hpp.

Definition in file general.hpp.