Opened 6 years ago
Closed 6 years ago
#18317 closed enhancement (fixed)
General documentation about graph data structures
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.7 
Component:  graph theory  Keywords:  
Cc:  tmonteil, vdelecroix, dcoudert, darij  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  4378790 (Commits, GitHub, GitLab)  Commit:  4378790c6996a3e4949737a1bf2b9bb8c4cc217d 
Dependencies:  Stopgaps: 
Description
This branch adds some more general documentation about graph data structures.
Let it be said that I am not setting in stone what we currently do, but rather trying to make it clear so that we can change whatever needs to be :P
Change History (15)
comment:1 Changed 6 years ago by
 Branch set to public/18317
 Commit set to 8d61e569bfd222ee604bf433bf557ac88469518c
 Status changed from new to needs_review
comment:2 followup: ↓ 4 Changed 6 years ago by
Just commenting...
In src/sage/graphs/base/overview.py
, you mention digraphs, but you seem to say nothing about them.
"Supports: addition/removal of edges/vertices available": remove the "available"?
"ligther" should be "lighter".
There is yet another distinction that is often left implicit but needs to be clarified here: In a graph, the edges can be either just predicates saying that "vertex a
is connected to vertex b
, (possibly) with edge label l
", or they can be mathematical objects on their own rights. The difference is most obvious when you have two edges with the same label both from a vertex a
to a vertex b
. Are these two edges equal or not? In the first case, they are (i.e., we've got one edge appearing twice in the edge multiset), while in the second case, they're not (i.e., we have two edges which just happen to have the same a
, the same b
, and the same label). The second viewpoint is important in homology, category and quiver theory (e.g., to make sense of a cycle basis of a multigraph, edges would have to have their own identities), whereas the first one seems to be a thing among graph theorists. A doc should make clear which of them is supported by which class.
comment:3 Changed 6 years ago by
 Commit changed from 8d61e569bfd222ee604bf433bf557ac88469518c to b7d90367738afb7bfcf2d97701451fccbeebf31f
Branch pushed to git repo; I updated commit sha1. New commits:
b7d9036  trac #18317: Reviewer's comments

comment:4 in reply to: ↑ 2 Changed 6 years ago by
Hello,
In
src/sage/graphs/base/overview.py
, you mention digraphs, but you seem to say nothing about them.
I always talk about both. From time to time I said "graph and digraph", but if I need to be politically correct and do not make one side feel like (s)he is neglected I added "(di)graph" everywhere.
"Supports: addition/removal of edges/vertices available": remove the "available"?
Right, done. I hesitated between different versions of this text, and this was a leftover.
"ligther" should be "lighter".
Done.
There is yet another distinction that is often left implicit but needs to be clarified here
Well, it's not really related to the data structure
In a graph, the edges can be either just predicates saying that "vertex
a
is connected to vertexb
, (possibly) with edge labell
", or they can be mathematical objects on their own rights. The difference is most obvious when you have two edges with the same label both from a vertexa
to a vertexb
. Are these two edges equal or not?
There is no "edge" object in Sage. So asking whether they are equal is almost philosophy :)
The label of an edge, however, can be any data that you like. So if you need edges to be more complicated objects, you can store it there.
A doc should make clear which of them is supported by which class.
Edge labels are "not very compatible" with a dense data structure, and for those it is claimed that edge labels are not supported. For sparse graphs arbitrary edge labels are supported.
Nathann
comment:5 followup: ↓ 6 Changed 6 years ago by
Thanks for the edits!
I think you should write "(di)graph", because for many people (such as myself), digraphs are not graphs.
As for the lack of edge identity, this is a perfectly fine choice, but should be documented. I don't know where, though  I am a stranger to Sage's decision decisions concerning where to document things...
comment:6 in reply to: ↑ 5 ; followup: ↓ 7 Changed 6 years ago by
Yooooooo !
I think you should write "(di)graph", because for many people (such as myself), digraphs are not graphs.
Yesyes. Did you find one that I missed in my last commit?
As for the lack of edge identity, this is a perfectly fine choice, but should be documented. I don't know where, though
Hmmm.. Well, I'm used to document a feature or a cornercase, but it's my first time trying to document something which is not there. And if there was some place to do that, it is very unlikely that it would also be found by whoever is interested. In GenericGraph.edges
perhaps?
But (please) in another ticket. In this one I hoped to present a clear view of the graph classes/backends and the data structures behind, so that we can start working on them seriously.
Nathann
comment:7 in reply to: ↑ 6 ; followup: ↓ 8 Changed 6 years ago by
Replying to ncohen:
Yesyes. Did you find one that I missed in my last commit?
No, sorry, I meant the "you" as a generic. The actual you has fixed this in your last commit.
Hmmm.. Well, I'm used to document a feature or a cornercase, but it's my first time trying to document something which is not there. And if there was some place to do that, it is very unlikely that it would also be found by whoever is interested. In
GenericGraph.edges
perhaps?
Sorry, I mean document, not doctest. Just say that edges in a multigraph are stored as elements of multisets, so if there are two edges from a
to b
in an unlabelled (di)multigraph, then they will be implemented not as two separate objects but as one object appearing twice in a multiset of edges. Say that this is not the convention used in quiver theory, and that the latter can be simulated using labelled (di)graphs.
comment:8 in reply to: ↑ 7 ; followup: ↓ 9 Changed 6 years ago by
No, sorry, I meant the "you" as a generic. The actual you has fixed this in your last commit.
Oh.
Sorry, I mean document, not doctest. Just say that edges in a multigraph are stored as elements of multisets, so if there are two edges from
a
tob
in an unlabelled (di)multigraph, then they will be implemented not as two separate objects but as one object appearing twice in a multiset of edges. Say that this is not the convention used in quiver theory, and that the latter can be simulated using labelled (di)graphs.
In this file, despite being about data structures, you will notice that I do not explain how exactly the data is stored, as this documentation belong to each individual module implementing a data structure. Moreover, to me your explanation of what is an edge in Sage belongs to some documentation explaining the *usage* or graphs, while this one is about their implementation. This precision does not belong here.
To convince you, notice that there is a class of Quivers in Sage, which I suspect is based on Sage's graphs: you can do whatever you like with respect to Edge
objects, by storing them as labels.
If you want to discuss this issue further let us please do it on another ticket or by email. This branch is about describing the class diagram and the performances of Sage's graph backends.
Nathann
comment:9 in reply to: ↑ 8 Changed 6 years ago by
Replying to ncohen:
Moreover, to me your explanation of what is an edge in Sage belongs to some documentation explaining the *usage* or graphs, while this one is about their implementation.
It is part of the definition of a graph. I have no idea where it belongs, really... I would normally say "into the docstring of the Graph
constructor", but hell knows where people will actually look.
comment:10 Changed 6 years ago by
in graph.py, and digraph.py, the backlink is indented too much (remove one space) as follows:
:mod:`~sage.graphs.base.overview`):
in graph_backends.py, in the line
:meth:`~GenericGraphBackend.degree`  Returns the total number of vertices incident to v.
replace Returns
by Return
and v by `v`
Same with Deletes and another Returns a few line below.
Once done, you can set to positive review.
comment:11 Changed 6 years ago by
 Commit changed from b7d90367738afb7bfcf2d97701451fccbeebf31f to c6678ce267bef7b5f805e78adae57c0b1d8a8b5d
comment:12 Changed 6 years ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
Thanks !!!
Nathann
comment:13 Changed 6 years ago by
 Commit changed from c6678ce267bef7b5f805e78adae57c0b1d8a8b5d to 4378790c6996a3e4949737a1bf2b9bb8c4cc217d
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
4378790  trac #18317: Delete(s)

comment:14 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:15 Changed 6 years ago by
 Branch changed from public/18317 to 4378790c6996a3e4949737a1bf2b9bb8c4cc217d
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #18317: General documentation about graph data structures