classes for graphs and lattices

[mantepse]

We have

sage: P = Posets(5); P
Posets containing 5 elements
sage: P.cardinality()
63
sage: next(iter(P))
Finite poset containing 5 elements

It would be nice to have the same for graphs and finite lattices. For lattices, we have

sage: FiniteLatticePosets()
Category of finite lattice posets
sage: from sage.databases.findstat import _finite_lattices
sage: next(_finite_lattices(4))
Finite lattice containing 4 elements

Besides, a fast iterator for finite lattices was proposed in #20516.

For graphs, we have an iterator. Besides, it would be even nicer if we could generate the graphs so that they are immutable. A subclass for connected graphs would be extra cool.

CC: @jm58660 @fchapoton

Component: combinatorics

Branch/Commit: u/mantepse/classes_for_graphs_and_lattices @ c84d0a1

Issue created by migration from https://trac.sagemath.org/ticket/34943

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:2

Actually graphs() has parameter copy. Could it be removed and have immutable instead?

Otherwise someone should just add the code from #20516, maybe as an internal function first.

[mantepse]

comment:3

I agree that this might be a good solution. Like so:

diff --git a/src/sage/graphs/graph_generators.py b/src/sage/graphs/graph_generators.py
index df88bbe2713..7195a1a4866 100644
--- a/src/sage/graphs/graph_generators.py
+++ b/src/sage/graphs/graph_generators.py
@@ -780,6 +780,7 @@ class GraphGenerators():
                 degree_sequence is None and not loops and augment == 'edges' and
                 sparse and copy):
             for g in graphs.nauty_geng(vertices):
+                g._immutable = True
                 yield g
             return

I ran the tests in graphs and combinat without any failures. I guess that nobody will actually try to modify a graph generated using graphs(5), and if this is desired, making a mutable copy should not be a problem.

However, the current documentation suggests a different philosophy.

    - ``copy`` (boolean) -- If set to ``True`` (default)
      this method makes copies of the graphs before returning
      them. If set to ``False`` the method returns the graph it
      is working on. The second alternative is faster, but modifying
      any of the graph instances returned by the method may break
      the function's behaviour, as it is using these graphs to
      compute the next ones: only use ``copy = False`` when
      you stick to *reading* the graphs returned.

Unfortunately, the copy keyword is not used at all in the entire sage library (with one trivial exception in findstat.py - it is not even doctested. So I have no idea what the intended use is.

[mantepse]

Branch: u/mantepse/classes_for_graphs_and_lattices

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Commit: c84d0a1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

c84d0a1

infrastructure for lattice posets

[mantepse]

comment:6

I set up the infrastructure. It remains to decide the immutability issue, and incorporate #20516.

In principle, #20516 could also be done later.

[mantepse]

Ping?

[mantepse]

@dcoudert, could you have a look at the question in https://github.com/sagemath/sage/issues/34943#issuecomment-1418193212 ?

[dcoudert]

Parameter copy is not used when calling nauty_geng (which always returns a copy). It is used for methods canaug_traverse_vert and canaug_traverse_edge. These generators work by modifying a graph that is returned. Here, it is faster to avoid returning a copy of the graph when you only want to count the graphs or check a property. However, this is not a good design. We should always return a copy of the graph to avoid errors if a returned graph is modified. And the extra cost of making copies is rather small. So I agree that we should deprecate it and always return a copy.

We can also add parameter immutable but one should not modify g._immutable manually. The good way is to add parameter immutable to method nauty_geng so that it can return immutable graphs, and to set parameter immutable to the right value when making a copy of the graph returned by methods canaug_traverse_*. It is also possible to modify methods canaug_traverse_* to return copies of the graph instead of the internal working graph...

The same should be done for graphs and digraphs.

Last, designing a subclass of connected graphs is certainly possible but it would require a lot of work. Unless such graphs are always immutable, it would require to constantly check that the graph remains connected after the addition/deletion of vertices/edges (a nightmare) and to clarify how the property should be preserved when taking a subgraph or performing certain operations like the join of a connected and a non connected graph (another nightmare). Honestly, I don't know how to do that. This is certainly too much work and long term effort for a very limited usage.

[mantepse]

Indeed, I was only thinking of a class of immutable objects