Opened 4 years ago

Closed 4 years ago

#18317 closed enhancement (fixed)

General documentation about graph data structures

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.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) 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 4 years ago by ncohen

  • Branch set to public/18317
  • Commit set to 8d61e569bfd222ee604bf433bf557ac88469518c
  • Status changed from new to needs_review

New commits:

8d61e56trac #18317: General documentation about graph data structures

comment:2 follow-up: Changed 4 years ago by darij

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 4 years ago by git

  • Commit changed from 8d61e569bfd222ee604bf433bf557ac88469518c to b7d90367738afb7bfcf2d97701451fccbeebf31f

Branch pushed to git repo; I updated commit sha1. New commits:

b7d9036trac #18317: Reviewer's comments

comment:4 in reply to: ↑ 2 Changed 4 years ago by ncohen

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

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 follow-up: Changed 4 years ago by darij

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 ; follow-up: Changed 4 years ago by ncohen

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

Last edited 4 years ago by ncohen (previous) (diff)

comment:7 in reply to: ↑ 6 ; follow-up: Changed 4 years ago by darij

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 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 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 ; follow-up: Changed 4 years ago by ncohen

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

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 4 years ago by darij

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 4 years ago by chapoton

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 4 years ago by git

  • Commit changed from b7d90367738afb7bfcf2d97701451fccbeebf31f to c6678ce267bef7b5f805e78adae57c0b1d8a8b5d

Branch pushed to git repo; I updated commit sha1. New commits:

2c02e23trac #18317: Merged with 6.7.beta3
c6678cetrac #18317: Review

comment:12 Changed 4 years ago by ncohen

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

Thanks !!!

Nathann

comment:13 Changed 4 years ago by git

  • 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:

4378790trac #18317: Delete(s)

comment:14 Changed 4 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:15 Changed 4 years ago by vbraun

  • Branch changed from public/18317 to 4378790c6996a3e4949737a1bf2b9bb8c4cc217d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.