Categories of connected graphs and connected simplicial complexes

Reported by: Owned by: mkoeppe major sage-9.2 graph theory tscrim, dcoudert Travis Scrimshaw Matthias Koeppe N/A 47836ad 47836adba7b3379d3c31df0925716d4a962243ba

Description

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.

comment:1 Changed 22 months ago by dcoudert

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

comment:2 Changed 22 months ago by mkoeppe

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.

comment:3 Changed 22 months ago by tscrim

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.

That's right.

comment:5 follow-up: ↓ 7 Changed 22 months ago by dcoudert

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?

comment:6 Changed 22 months ago by mkoeppe

Great point, of course, regarding `delete_edge` etc.

Is there currently a way to make graphs immutable?

comment:7 in reply to: ↑ 5 Changed 22 months ago by mkoeppe

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()`.

comment:8 follow-up: ↓ 10 Changed 22 months ago by 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)`
1. 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...

comment:9 follow-up: ↓ 11 Changed 22 months ago by tscrim

• Authors set to Travis Scrimshaw
• Branch set to public/categories/connected_simplicial_complexes-30126
• Status changed from new to needs_review

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.`

comment:10 in reply to: ↑ 8 Changed 22 months ago by mkoeppe

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.

comment:11 in reply to: ↑ 9 Changed 22 months ago by mkoeppe

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

comment:12 Changed 22 months ago by mkoeppe

```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?

comment:13 Changed 22 months ago by mkoeppe

• Summary changed from Category of connected graphs to Categories of connected graphs and connected simplicial complexes

comment:14 Changed 22 months ago by tscrim

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.

comment:15 Changed 22 months ago by mkoeppe

• Reviewers set to Matthias Koeppe
• Status changed from needs_review to positive_review

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

comment:16 Changed 22 months ago by vbraun

• Branch changed from public/categories/connected_simplicial_complexes-30126 to 47836adba7b3379d3c31df0925716d4a962243ba
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.