#30126 closed enhancement (fixed)

Categories of connected graphs and connected simplicial complexes

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-9.2
Component: graph theory Keywords:
Cc: tscrim, dcoudert Merged in:
Authors: Travis Scrimshaw Reviewers: Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: 47836ad (Commits, GitHub, GitLab) Commit: 47836adba7b3379d3c31df0925716d4a962243ba
Dependencies: Stopgaps:

Status badges

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.

Change History (16)

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.

comment:4 Changed 22 months ago by mkoeppe

That's right.

comment:5 follow-up: 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

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

comment:8 follow-up: 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: Changed 22 months ago by tscrim

  • Authors set to Travis Scrimshaw
  • Branch set to public/categories/connected_simplicial_complexes-30126
  • Commit set to 47836adba7b3379d3c31df0925716d4a962243ba
  • 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:

6b99a12Added connected to simplicial complexes.
47836adAdded that a connected graph is a metric space.

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

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.

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

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

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.