Sage: Ticket #18317: General documentation about graph data structures
https://trac.sagemath.org/ticket/18317
<p>
This branch adds some more general documentation about graph data structures.
</p>
<p>
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 <code>:-P</code>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/18317
Trac 1.1.6ncohenMon, 27 Apr 2015 19:41:09 GMTstatus changed; commit, branch set
https://trac.sagemath.org/ticket/18317#comment:1
https://trac.sagemath.org/ticket/18317#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>8d61e569bfd222ee604bf433bf557ac88469518c</em>
</li>
<li><strong>branch</strong>
set to <em>public/18317</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8d61e569bfd222ee604bf433bf557ac88469518c"><span class="icon"></span>8d61e56</a></td><td><code>trac #18317: General documentation about graph data structures</code>
</td></tr></table>
TicketdarijMon, 27 Apr 2015 20:26:52 GMT
https://trac.sagemath.org/ticket/18317#comment:2
https://trac.sagemath.org/ticket/18317#comment:2
<p>
Just commenting...
</p>
<p>
In <code>src/sage/graphs/base/overview.py</code>, you mention digraphs, but you seem to say nothing about them.
</p>
<p>
"Supports: addition/removal of edges/vertices available": remove the "available"?
</p>
<p>
"ligther" should be "lighter".
</p>
<p>
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 <code>a</code> is connected to vertex <code>b</code>, (possibly) with edge label <code>l</code>", 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 <code>a</code> to a vertex <code>b</code>. 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 <code>a</code>, the same <code>b</code>, 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.
</p>
TicketgitMon, 27 Apr 2015 20:33:55 GMTcommit changed
https://trac.sagemath.org/ticket/18317#comment:3
https://trac.sagemath.org/ticket/18317#comment:3
<ul>
<li><strong>commit</strong>
changed from <em>8d61e569bfd222ee604bf433bf557ac88469518c</em> to <em>b7d90367738afb7bfcf2d97701451fccbeebf31f</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b7d90367738afb7bfcf2d97701451fccbeebf31f"><span class="icon"></span>b7d9036</a></td><td><code>trac #18317: Reviewer's comments</code>
</td></tr></table>
TicketncohenMon, 27 Apr 2015 20:39:00 GMT
https://trac.sagemath.org/ticket/18317#comment:4
https://trac.sagemath.org/ticket/18317#comment:4
<p>
Hello,
</p>
<blockquote class="citation">
<p>
In <code>src/sage/graphs/base/overview.py</code>, you mention digraphs, but you seem to say nothing about them.
</p>
</blockquote>
<p>
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.
</p>
<blockquote class="citation">
<p>
"Supports: addition/removal of edges/vertices available": remove the "available"?
</p>
</blockquote>
<p>
Right, done. I hesitated between different versions of this text, and this was a leftover.
</p>
<blockquote class="citation">
<p>
"ligther" should be "lighter".
</p>
</blockquote>
<p>
Done.
</p>
<blockquote class="citation">
<p>
There is yet another distinction that is often left implicit but needs to be clarified here
</p>
</blockquote>
<p>
Well, it's not really related to the data structure
</p>
<blockquote class="citation">
<p>
In a graph, the edges can be either just predicates saying that "vertex <code>a</code> is connected to vertex <code>b</code>, (possibly) with edge label <code>l</code>", 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 <code>a</code> to a vertex <code>b</code>. Are these two edges equal or not?
</p>
</blockquote>
<p>
There is no "edge" object in Sage. So asking whether they are equal is almost philosophy <code>:-)</code>
</p>
<p>
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.
</p>
<blockquote class="citation">
<p>
A doc should make clear which of them is supported by which class.
</p>
</blockquote>
<p>
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.
</p>
<p>
Nathann
</p>
TicketdarijMon, 27 Apr 2015 20:44:51 GMT
https://trac.sagemath.org/ticket/18317#comment:5
https://trac.sagemath.org/ticket/18317#comment:5
<p>
Thanks for the edits!
</p>
<p>
I think you should write "(di)graph", because for many people (such as myself), digraphs are not graphs.
</p>
<p>
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...
</p>
TicketncohenMon, 27 Apr 2015 20:54:02 GMT
https://trac.sagemath.org/ticket/18317#comment:6
https://trac.sagemath.org/ticket/18317#comment:6
<p>
Yooooooo !
</p>
<blockquote class="citation">
<p>
I think you should write "(di)graph", because for many people (such as myself), digraphs are not graphs.
</p>
</blockquote>
<p>
Yesyes. Did you find one that I missed in my last commit?
</p>
<blockquote class="citation">
<p>
As for the lack of edge identity, this is a perfectly fine choice, but should be documented. I don't know where, though
</p>
</blockquote>
<p>
Hmmm.. Well, I'm used to document a feature or a corner-case, 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 <code>GenericGraph.edges</code> perhaps?
</p>
<p>
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.
</p>
<p>
Nathann
</p>
TicketdarijMon, 27 Apr 2015 21:16:15 GMT
https://trac.sagemath.org/ticket/18317#comment:7
https://trac.sagemath.org/ticket/18317#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18317#comment:6" title="Comment 6">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Yesyes. Did you find one that I missed in my last commit?
</p>
</blockquote>
<p>
No, sorry, I meant the "you" as a generic. The actual you has fixed this in your last commit.
</p>
<blockquote class="citation">
<p>
Hmmm.. Well, I'm used to document a feature or a corner-case, 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 <code>GenericGraph.edges</code> perhaps?
</p>
</blockquote>
<p>
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 <code>a</code> to <code>b</code> 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.
</p>
TicketncohenTue, 28 Apr 2015 06:37:03 GMT
https://trac.sagemath.org/ticket/18317#comment:8
https://trac.sagemath.org/ticket/18317#comment:8
<blockquote class="citation">
<p>
No, sorry, I meant the "you" as a generic. The actual you has fixed this in your last commit.
</p>
</blockquote>
<p>
Oh.
</p>
<blockquote class="citation">
<p>
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 <code>a</code> to <code>b</code> 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.
</p>
</blockquote>
<p>
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.
</p>
<p>
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 <code>Edge</code> objects, by storing them as labels.
</p>
<p>
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.
</p>
<p>
Nathann
</p>
TicketdarijTue, 28 Apr 2015 07:16:47 GMT
https://trac.sagemath.org/ticket/18317#comment:9
https://trac.sagemath.org/ticket/18317#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18317#comment:8" title="Comment 8">ncohen</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
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 <code>Graph</code> constructor", but hell knows where people will actually look.
</p>
TicketchapotonFri, 01 May 2015 15:22:05 GMT
https://trac.sagemath.org/ticket/18317#comment:10
https://trac.sagemath.org/ticket/18317#comment:10
<p>
in graph.py, and digraph.py, the backlink is indented too much (remove one space) as follows:
</p>
<pre class="wiki"> :mod:`~sage.graphs.base.overview`):
</pre><p>
in graph_backends.py, in the line
</p>
<pre class="wiki">:meth:`~GenericGraphBackend.degree` | Returns the total number of vertices incident to v.
</pre><p>
replace <code>Returns</code> by <code>Return</code> and v by <code>`v`</code>
</p>
<p>
Same with Deletes and another Returns a few line below.
</p>
<p>
Once done, you can set to positive review.
</p>
TicketgitFri, 01 May 2015 15:27:45 GMTcommit changed
https://trac.sagemath.org/ticket/18317#comment:11
https://trac.sagemath.org/ticket/18317#comment:11
<ul>
<li><strong>commit</strong>
changed from <em>b7d90367738afb7bfcf2d97701451fccbeebf31f</em> to <em>c6678ce267bef7b5f805e78adae57c0b1d8a8b5d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2c02e2304db34a154303f7930dde40d356bce719"><span class="icon"></span>2c02e23</a></td><td><code>trac #18317: Merged with 6.7.beta3</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c6678ce267bef7b5f805e78adae57c0b1d8a8b5d"><span class="icon"></span>c6678ce</a></td><td><code>trac #18317: Review</code>
</td></tr></table>
TicketncohenFri, 01 May 2015 15:28:10 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/18317#comment:12
https://trac.sagemath.org/ticket/18317#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Frédéric Chapoton</em>
</li>
</ul>
<p>
Thanks !!!
</p>
<p>
Nathann
</p>
TicketgitFri, 01 May 2015 15:29:13 GMTstatus, commit changed
https://trac.sagemath.org/ticket/18317#comment:13
https://trac.sagemath.org/ticket/18317#comment:13
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>c6678ce267bef7b5f805e78adae57c0b1d8a8b5d</em> to <em>4378790c6996a3e4949737a1bf2b9bb8c4cc217d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4378790c6996a3e4949737a1bf2b9bb8c4cc217d"><span class="icon"></span>4378790</a></td><td><code>trac #18317: Delete(s)</code>
</td></tr></table>
TicketncohenFri, 01 May 2015 15:29:25 GMTstatus changed
https://trac.sagemath.org/ticket/18317#comment:14
https://trac.sagemath.org/ticket/18317#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketvbraunSat, 02 May 2015 14:22:33 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/18317#comment:15
https://trac.sagemath.org/ticket/18317#comment:15
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/18317</em> to <em>4378790c6996a3e4949737a1bf2b9bb8c4cc217d</em>
</li>
</ul>
Ticket