Opened 22 months ago
Closed 22 months ago
#30126 closed enhancement (fixed)
Categories of connected graphs and connected simplicial complexes
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage9.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: 
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
comment:2 Changed 22 months ago by
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
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
That's right.
comment:5 followup: ↓ 7 Changed 22 months ago by
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
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
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 followup: ↓ 10 Changed 22 months ago by
 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)
 using
self.__class__
orself.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 followup: ↓ 11 Changed 22 months ago by
 Branch set to public/categories/connected_simplicial_complexes30126
 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:
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
Replying to dcoudert:
 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
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
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
 Summary changed from Category of connected graphs to Categories of connected graphs and connected simplicial complexes
comment:14 Changed 22 months ago by
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
 Reviewers set to Matthias Koeppe
 Status changed from needs_review to positive_review
Thanks for the explanation! Let's continue on followup tickets.
comment:16 Changed 22 months ago by
 Branch changed from public/categories/connected_simplicial_complexes30126 to 47836adba7b3379d3c31df0925716d4a962243ba
 Resolution set to fixed
 Status changed from positive_review to closed
I have zero knowledge on manifolds, so I don't understand what's the idea/objective.