Opened 11 years ago

Last modified 6 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 rlm

In case of a SparseGraph, the SparseGraphBackend has self._cg and self._cg_rev. They can merely be swapped. In the case of a NetworkX graph, I believe their digraphs have succ and pred dictionaries storing the adjacency information. These could also be swapped. For DenseGraphs, this is equivalent to switching between row ordering and column ordering in bitsets, which is inevitably costly.

comment:2 Changed 11 years ago by jason

  • Type changed from defect to enhancement

comment:3 Changed 11 years ago by ncohen

  • Status changed from new to needs_work

comment:4 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.