Basic.hpp File Reference

Plans on the basic graph functionality. More...

Go to the source code of this file.

Detailed Description

Plans on the basic graph functionality.

DONE Naming conventions
  • DONE "g" for graphs, "gl" for graphs with loops, "dg" for directed graph, "dgl" for directed graphs with loops, "gg" for general graph, and "gdg" for "general directed graph".
  • DONE "og" for ordered graphs, similarly "ogl", "odg", "odgl", "ogg" and "ogdg".
  • DONE For Maxima-graphs we use "mg" and "mdg".
  • So for multigraphs we need to use the abbreviation "mug", for multigraphs with loops mugl, for directed multigraphs mudg, for directed multigraphs with loops mudgl, and finally omug, omugl, omudg, omudgl denote the ordered versions.
  • DONE There is a clash for "directed graphs":
    1. Either we speak of "directed graphs", "directed multigraphs", "directed general graphs", or of "digraphs", "multi-digraphs", "general digraphs".
    2. The "digraph" has the advantage that there is no confusion about the order of adjectives.
Graph concepts
  • DONE A "graph" is just a 2-element list, consisting of the set of vertices, and a set of 2-element vertex sets.
  • DONE A "graph with loops" also allows 1-element vertex sets.
  • DONE A "general graph" is a triple [V,E,f], where V, E are sets and f is a map from E to 1-2-element subsets of V.
  • DONE The same with directed graphs, only that this time we have vertex-lists (always of size 2) instead of vertex-sets.
  • There is also the (cryptomorphic) notion of a "precategory", which is a 4-tuple [V,E,source,target]; abbreviation "precat".
  • Multigraphs:
    1. A "multigraph" is a triple [V,E,f], where [V,E] is a graph, and f is a map which maps every element of E to a natural number (that is, >0).
    2. While a "multigraph with loops" is similarly a triple [V,E,f] such that [V,E] is a graph with loops.
    3. And a "directed multigraph" is a triple [V,E,f], where now the elements of E or pairs, while a "directed multigraph with loops" allows the elements of the pairs to be identical.
    4. One could actually make the domain of f the set of all possible edges (directed or undirected, with or without loops), allowing then (of course) the value 0. Then possibly the edge set could be dropped.
    5. We needed then to change all functions concerned with multi(di)graphs.
    6. To compute the set of edges, one had to go through all possible edges (given the vertex set) and select those with a weight at least 1.
    7. The basic possibilities are (i) with/without explicit edge set, (ii) allowing/disallowing zero multiplicities. Without explicit edge set, we need to allow zero multiplicities, while with it one could disallow (as now) or allow them (having then two possibilities for checking whether some edge is present).
    8. At this time it seems best to avoid the further proliferation of graph types, and just stick to the current form of "multigraph", since yet there is no concrete motivation to consider further types.
  • Since also for general graphs the edge set needs to be given, we don't have the possibility of "lazy graph representations". Seems unavoidable --- except that by changing the concept of a multigraph as above we can at least avoid to mention the edge-set.
  • "Oriented" versions:
    1. An "oriented general digraph" has additionally a function o, defined on edge-labels and returning -1 or +1.
    2. We use "or", so " orgdg, ordgl, ordg, and oorgdg,oordgl, and oordg.
    3. From an oriented digraph one gets a digraph by oriented the edges accordingly.
    4. Morphisms of oriented digraphs can additionally flip the orientations (and the result must be an ordinary morphism).
    5. Shall we also use "oriented graphs", as graphs with such orientation functions, to be interpreted according to the natural order on vertices?
  • Standardisation of vertex-names:
    1. From the point of view of the OKlibrary, the best choice for standard vertex sets would be {1,..,n}.
    2. This coincides with mathematical conventions, and also 0 is not possible as a clause-set-variable.
    3. However Maxima graphs by themselves are labelled starting with 0, and array-indices start with 0 as well.
    4. So well, when translating Maxima graphs to graphs we translate vertex names, if needed, to start with 1.
    5. That is, when these or "original" Maxima graphs, which one can apparently recognise by the vertex list in reverse order, finishing with a zero.
    6. Standardised graphs can be denoted by "stdg", "stdog" etc.
  • Given a vertex, we need the set of edges incident to the vertex; this can be handled via the dual hypergraph, but we should provide some more convenient methods.
  • Likely, our graph-etc-concepts are conceptually appropriate, but when using or implementing algorithms then we should, if possible, use the maxima-graphs.
  • How to handle "properties" ? DONE (these shall just be maps)
  • Can we tag such objects as being "graphs" ? DONE (we are living type-free)
Subgraph concepts
  • Perhaps we should create "Subgraphs.mac".
  • Likely the subgraphs of ordered graphs-types should inherit the order(s).

Definition in file Basic.hpp.