#18564: Boost Edge Connectivity
-------------------------------------+-------------------------------------
Reporter: borassi | Owner: borassi
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.8
Component: graph theory | Resolution:
Keywords: Boost, | Merged in:
connectivity | Reviewers:
Authors: Michele Borassi | Work issues:
Report Upstream: N/A | Commit:
Branch: | b513cf9f6a52e1dae5805cb622da9481069defc3
u/borassi/boost_edge_connectivity | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Helloooooooo Michele,
Thanks for this update, the code looks much better. Further remarks:
- About `clang: c++`: this was useful for you to run `sage -cython -a
boost_graph.pyx` since this command does not read `module_list.py` (in
which
you specified that it was a c++ file). However, there is no need to add
this
line for everything to work 'in sage'. That's only useful to create the
html
file, though you found a better way to do it with the `--cplus` file.
- About `sig_on/off`:
http://www.sagemath.org/documentation/html/en/developer/coding_in_cython.html
#interrupt-and-signal-handling
- About `cdef int i`: well, you are right this is not a bottleneck at all.
I
just said that as a reflex, sorry ^^;
- About:
{{{
Because, in my opinion, it could be better to keep the Boost
implementation
separated from the Boost algorithms (since soon there will be many of
them),
and to put the algorithms in the files where they will be used.
}}}
Hmmmm... Well, as a result we would end up with data-structure specific
code
in `generic_graph_pyx.pyx`, and that is not very pretty either. It is
better
to have such low-level functions close together in a data-structure
specific
file. If you think that the boost file will grow too large after a
while,
however, we can split it in two files: one for the data structure, one
for the
exposed algorithms. Several files from base/ already contain some
algorithm.
- About:
{{{
Because I do not really like functions that are "too long", and I
thought
that some code used with Boost could be re-used by the LP algorithm,
simplifying the function.
}}}
First, note that moving code around has a very very bad effect on the
final
'diff'. The reviewer sees a big removal and a big addition, and his job
is to
check that no new bug was introduced, so that's quite some work only to
move
code around. When you only want to *move* code around, it is much easier
for
the reviewer if you do it in two steps:
- Move the code *without any other modification* (easy to check with a
couple
of bash commands)
- Make the small changed needed in the code to 'adapt' it to its new
location.
This way the review is easier.
- You added 'boost_graph' first in its block in the graph documentation.
That
list is not sorted alphabetically, for the first item is 'overview of
graph
classes'. Could you move it below it? It is the most 'general' document.
- Style issue, do whatever you want: instead of `if not (G is None)`
followed by
a big indented block, you can write `if G is None: return`
By the way, `G is not None` does what you want:
{{{
sage: not False
True
sage: None is True
False
sage: None is not False
True
}}}
- Your functions are "def" functions, i.e. Python functions. If you turn
them
into 'cpdef' functions they will be both Python+C functions, and C code
will
call the C function directly
- Could you write somewhere in the doc of your boost classes that edge
labels
are not supported (in particular when you build a Boost graph from a
Sage
graph)
- If multiple edges and loops are supported, can you add a doctest that
checks
it?
- `m = max(u, v)`: looks useless
- `self.vertices.at(u)`: this sems to check that `u` is actually within
the
bounds of the vector. Why not `self.vertices[u]` since the function is
`unsafe`?
- `def edge_connectivity`: we try to keep the first line of a docstring to
be a
short sentence describing what the function does. The next paragraph can
be as
think as you want.
- `for i from 0 <= i < ec`: that's old-style. Nowadays, it is equivalent
to `for
i in range(ec)` (Cython translates it 'properly').
- Awkward question: I have to admit that I am no big fan of the huge
copy/paste... Since Cython extension classes do not support templating
but
functions do, what about not having a `BoostGraph` struct instead of a
class?
We could have two of these struct and many functions that apply to it,
each of
which handles fused types. Thus, only one function instead of two, no
more
copy/paste?... Please tell me how you feel about that.
- About:
{{{
Now the diff should be cleaner. Is there any way to see the diff before
pushing my changes (e.g. git diffall or something like that)?
}}}
You can see all the changes made by your current branch compared with
the
latest release with 'git diff HEAD ^develop'. Beware: does not take
uncommited
changed into account.
- Another "git cleanness" issue: having commits undo what a previous
commit did
is not entirely 'free'. For example, if you run 'git blame' on
`generic_graph.py` you will notice that your name on all lines of
`edge_connectivity` since you are the last one who touched them (you
moved
them twice). While this is not a very very very bad problem, we somehow
lose
information with things like that.
I also believe (and nobody but me is forced to follow those rules) that
the
git history of a branch should be made to be read rather than be the
try-and-fail history of attempts to write a code.
A way to solve both problems is to *merge* commits together (a specific
case
of history rewriting). You can do this with 'git rebase -i develop' [1]
(look
for the 'squash' keyword).
If you do that, you will have to add -f (force) to your 'push' command
since
you will not be adding commit but overwriting existing ones.
- `from sage.graphs.digraph import DiGraph`: looks useless
- `if H.is_directed(): val.append(H.strongly_connected_components())`
shouldn't
you be using a `breadth_first_search` instead of a `SCC`?
- There is a `delete_edges` function.
Nathann
[1] https://www.atlassian.com/git/tutorials/rewriting-history/git-
rebase-i/
--
Ticket URL: <http://trac.sagemath.org/ticket/18564#comment:31>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
