Categories of connected graphs and connected simplicial complexes

[mkoeppe]

There is the category of Graphs and there is an axiom 'Connected' (used in Manifolds), but so far there is no category of connected graphs. They would be metric spaces... if edge weights are positive.

CC: @tscrim @dcoudert

Component: graph theory

Author: Travis Scrimshaw

Branch/Commit: 47836ad

Reviewer: Matthias Koeppe

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

[dcoudert]

comment:1

I have zero knowledge on manifolds, so I don't understand what's the idea/objective.

[mkoeppe]

comment:2

Connected graphs with positive edge weights define discrete metric spaces whose elements are the vertices and whose distance function is the length of the shortest path between the vertices.

[tscrim]

comment:3

The mentioning of manifolds is just an indication of where the axiom is used. So what I believe is being proposing is to allow the axiom to be added to the category of graphs with a default metric function being the usual distance between vertices.

[mkoeppe]

comment:4

That's right.

[dcoudert]

comment:5

I'm not used to the terminology of category, but I understand some relationships between graphs and metric spaces (I did some work on Gromov hyperbolicity).

If I understand well, you want a new class ConnectedGraphs, that inherits from Graphs and overwrites delete_edge and delete_vertex to raise an error if the removal of a vertex or an edge disconnects the graph. The class should also get a check_weight method to check that edge weights are positive.

More work would certainly be needed to ensure that a subgraph of a connected graph is of the same type, etc. right?

[mkoeppe]

comment:6

Great point, of course, regarding delete_edge etc.

Is there currently a way to make graphs immutable?

[mkoeppe]

comment:7

Replying to @dcoudert:

More work would certainly be needed to ensure that a subgraph of a connected graph is of the same type, etc. right?

Right. This can be done by calling self.__class__ or self.parent() rather than Graph().

[dcoudert]

comment:8

1. Immutable: a graph can be immutable, but we cannot flip from one state to another. This is done via a copy like Graph(G, immutable=True)

2. using self.__class__ or self.parent() is a good idea, but may be not so easy to do. We have to correct/modify many parts of the code...

[tscrim]

comment:9

I think we can at least solve the immediate issue of adding the axiom Connected to the graph category. So I did this in the highest place it makes sense: simplicial complexes. With this, we have the natural category for those that want to use it. The later steps of adding the refinement to the graph class can come on a later ticket.

---

New commits:

6b99a12	Added connected to simplicial complexes.
47836ad	Added that a connected graph is a metric space.

[tscrim]

Author: Travis Scrimshaw

[tscrim]

Commit: 47836ad

[tscrim]

Branch: public/categories/connected_simplicial_complexes-30126

[mkoeppe]

comment:10

Replying to @dcoudert:

1. Immutable: a graph can be immutable, but we cannot flip from one state to another. This is done via a copy like Graph(G, immutable=True)

Thanks.

[mkoeppe]

comment:11

Replying to @tscrim:

I think we can at least solve the immediate issue of adding the axiom Connected to the graph category. So I did this in the highest place it makes sense: simplicial complexes. With this, we have the natural category for those that want to use it.

This looks great. In sage.categories.simplicial_complexes I see you have already planned for categories to express more general cell complexes.

I'll play with this a little bit and wait for the patchbot

[mkoeppe]

comment:12

sage: CSC = SimplicialComplexes().Connected()
sage: L = SimplicialComplex([[1,2], [1,4]], category=CSC & SimplicialComplexes().Finite())
sage: L in CSC
True
sage: II = SimplicialComplex([[1,4], [2,3]], category=CSC & SimplicialComplexes().Finite())
sage: II in CSC
True

Should something be added to make sure that the second example raises an error?

[tscrim]

comment:14

No category does explicit tests checking whether or not an object belongs to it. Something we could add is a _test_connected method, so that it gets picked up by a run of the TestSuite. Perhaps we could add it to the __contains__ method, but the fact that the category is set would basically override any reasonable test.

[mkoeppe]

Reviewer: Matthias Koeppe

[mkoeppe]

comment:15

Thanks for the explanation! Let's continue on follow-up tickets.

[vbraun]

Changed branch from public/categories/connected_simplicial_complexes-30126 to 47836ad