#7640: shortest_path should not use NetworkX if the underlying graph is a
c_graph
----------------------------+-----------------------------------------------
Reporter: rlm | Owner: rlm
Type: defect | Status: needs_work
Priority: major | Milestone: sage-4.3
Component: graph theory | Keywords:
Work_issues: | Author:
Upstream: N/A | Reviewer:
Merged: |
----------------------------+-----------------------------------------------
Comment(by rlm):
Replying to [comment:9 ncohen]:
> Several answers, then :-)
>
> 1. That's why I wanted to use at first but Martin Albrecht told me in
#7637 that this version should be more efficient
Great!
> 2. The version ``bidirectional = False`` is indeed very easy to write (
one only needs to remove variables ), but I wondered if this was useful...
``bidirectional=True`` is the default option, used in all the others call
to it, and this second version is meant to be faster... :-)
This is indeed a good point. I wonder if anyone ever in the history of
Sage has used bidirectional=False.
> 3. I started by trying to write the Dijkstra algorithm, and ended up
wondering whether there was a Heap structure already written in Cython. I
needed to maintain a sorted list, and found no reference about it ... If
you know how to do it, I'll begin immediately ! :-)
I'm not sure...
> This version of shortest_path seems to be the most used (
bidirectional=True, weights=False ), so I thought the most urgent was to
make your c_graphs the default ones.. I just created two tickets in the
graph section about functions that should be moved from networkx to
c_graphs, we could just add these two ! Anyway I intend to take care of
them :-)
I don't think `bidirectional=False` is a showstopper at all (in fact we
should ping sage-devel about removing this option, since it seems silly).
However, `by_weights=True` is going to be necessary to make the switch. I
also just noticed that the function `shortest_paths` needs to be
implemented for `c_graph`s too.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7640#comment:11>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
