Opened 3 years ago

Closed 3 years ago

#19381 closed defect (fixed)

Refactor Graph.__init__

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.9
Component: graph theory Keywords:
Cc: borassi, dcoudert, dimpase, vdelecroix Merged in:
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 9bdf527 (Commits) Commit: 9bdf527fd59509647ccefd86cbd87bb2e92071b4
Dependencies: Stopgaps:

Description

This (very unpleasant) ticket attempts to clean a bit more the content of Graph.__init__.

To this end, it creates a graph_input modules that gathers into individual functions the different pieces of code that build a graph from <any other data>.

Admittedly, this is just one step toward a cleaner graph constructor, but we are not there yet.

Nothing smart is done in this branch: the pieces of code from Graph.__init__ are moved to new individual functions (some variables/parameters are renamed). One from DiGraph.__init__ is moved too.

In particular, some pieces of code from DiGraph.__init__ may eventually be merged with the functions that this branch creates, but this will be done later.

This branch is already sufficiently long and sufficiently unpleasant to write/review :-/

Nathann

Change History (12)

comment:1 Changed 3 years ago by ncohen

  • Branch set to u/ncohen/19381
  • Commit set to a74b0ff454c22237989edef3078ae55552ccf02e
  • Status changed from new to needs_review

Last 10 new commits:

daff6d5trac #19382: graph6
69cf259trac #19382: sparse6
cb6af84trac #19382: disclaimer
d230783trac #19382: seidel adjacency matrix
eebc428trac #19382: adjacency matrix
102e977trac #19382: Fix seidel adjacency
8d50d1ftrac #19382: Incidence matrix
28ecfcetrac #19382: dict_of_dicts
fa5d01ctrac #19382: dict of lists
a74b0fftrac #19382: dig6

comment:2 follow-up: Changed 3 years ago by tscrim

Would it be possible in this ticket to add support for constructing a graph by [V, E] like this:

sage: V = [1,2,3,4]
sage: E = [[1,2]]
sage: Graph([V, E])

I know I can do it like this

sage: G = Graph({1:[2], 2:[], 3:[], 4:[]})
sage: G.vertices()
[1, 2, 3, 4]

but this is somewhat cumbersome (and doesn't work for graphs with labeled (multiple) edges). The other way I know how to do this is I have to pass the edge set, then add the vertices.

The reason I ask is because I have wanted to create immutable graphs with larger vertex sets than the connectivity of the edges and I don't want to have to waste time copying a mutable graph backend into the static backend. (As an additional reason, it also follows the basic intro to combinatorics definition of a graph.)

I should also be able to review this ticket too (and I definitely will if you make the above change).

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

Would it be possible in this ticket to add support for constructing a graph by [V, E] like this:

Certainly not in this ticket. It refactors code, and it is already (as you can see) a lot to review. I guess it can be done in another ticket, though, I don't thing that there is any problem. With 5-6 lines any ambiguity with the other kind of inputs can be cleared ([V,f], list_of_edges, ...)

I know I can do it like this

sage: G = Graph({1:[2], 2:[], 3:[], 4:[]})
sage: G.vertices()
[1, 2, 3, 4]

but this is somewhat cumbersome (and doesn't work for graphs with labeled (multiple) edges).

sage: Graph({1:{2:['l1','l2']}},multiedges=True).edges()
[(1, 2, 'l1'), (1, 2, 'l2')]

See also Graph.to_dictionary which generates this kind of output.

Nathann

comment:4 Changed 3 years ago by dcoudert

  • Note: This is a internal... -> 'an internal`?

Preliminary tests are ok and the doc build and display properly. I'm currently running tests on sage/graphs/. I'll let you know soon.

comment:5 Changed 3 years ago by git

  • Commit changed from a74b0ff454c22237989edef3078ae55552ccf02e to dc36f023927a79dea403e9112ae2935327bfe205

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

dc36f02trac #19381: Typo

comment:6 Changed 3 years ago by dimpase

hey, your commit messages have the ticket number wrong...

comment:7 follow-up: Changed 3 years ago by dcoudert

For me the patch is good to go, but I don't know if Nathann has something to do about the commit ticket numbers...

Note: the (possible) segfault in the test src/sage/graphs is independent from this patch and is resolved in #19337.

comment:8 Changed 3 years ago by git

  • Commit changed from dc36f023927a79dea403e9112ae2935327bfe205 to 9bdf527fd59509647ccefd86cbd87bb2e92071b4

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

7a33fadtrac #19381: sparse6
efb842btrac #19381: disclaimer
d9522bbtrac #19381: seidel adjacency matrix
f0f8ee4trac #19381: adjacency matrix
7a51fdetrac #19381: Fix seidel adjacency
5abbd4btrac #19381: Incidence matrix
cf7f515trac #19381: dict_of_dicts
f9fc7a8trac #19381: dict of lists
dd28d93trac #19381: dig6
9bdf527trac #19381: Typo

comment:9 in reply to: ↑ 7 Changed 3 years ago by dimpase

Replying to dcoudert:

For me the patch is good to go, but I don't know if Nathann has something to do about the commit ticket numbers...

well, he adds these numbers by hand. If you think it's OK, then it's OK with me, too.

Note: the (possible) segfault in the test src/sage/graphs is independent from this patch and is resolved in #19337.

comment:10 Changed 3 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

Then let's go!

comment:11 Changed 3 years ago by ncohen

Thaaaaaaaaanks for this quick review O_O

Nathann

comment:12 Changed 3 years ago by vbraun

  • Branch changed from u/ncohen/19381 to 9bdf527fd59509647ccefd86cbd87bb2e92071b4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.