Opened 11 years ago
Last modified 7 years ago
#7720 needs_work enhancement
Digraph.reverse() should be rewritten more efficiently ( not hard )
Reported by: | ncohen | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | graph theory | Keywords: | |
Cc: | rlm | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
This function should be rewritten much more efficiently :
First, there should be a way to reverse the arcs "in place" ( without building a copy, by modifying the current graph -- I do not know if the expression used in frech translates in this case ). Such a function, for c_graphs, should be written in Cython and consist in the case of sparse graph in reverting the two copies kept of the graph. In the end, this function should consist in an (optional) copy of the graph (=fast) and a call to the functionr reverting the arcs ( O(1) )
If possible and if deemed useful, the same should be made for NetworkX graphs.
Change History (7)
comment:1 Changed 11 years ago by
comment:2 Changed 11 years ago by
- Type changed from defect to enhancement
comment:3 Changed 11 years ago by
- Status changed from new to needs_work
comment:4 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:5 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:6 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:7 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
In case of a
SparseGraph
, theSparseGraphBackend
hasself._cg
andself._cg_rev
. They can merely be swapped. In the case of aNetworkX
graph, I believe their digraphs havesucc
andpred
dictionaries storing the adjacency information. These could also be swapped. ForDenseGraphs
, this is equivalent to switching between row ordering and column ordering in bitsets, which is inevitably costly.