Opened 11 years ago

Closed 11 years ago

#7651 closed enhancement (fixed)

c_graph backends should include a "reversed" copy for digraphs in the sparse case

Reported by: rlm Owned by: rlm
Priority: major Milestone: sage-4.3
Component: graph theory Keywords:
Cc: ncohen, jason Merged in: sage-4.3.rc1
Authors: Robert Miller Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

This is because the data structure for sparse graphs is itself directed, and in_neighbors is a slow function, as it needs to check each node.

Attachments (1)

trac_7651.patch (19.7 KB) - added by rlm 11 years ago.
apply to sage-4.3.rc0 + #7640 + #7674 + #7673

Download all attachments as: .zip

Change History (15)

comment:1 Changed 11 years ago by ncohen

  • Cc ncohen added

comment:2 Changed 11 years ago by jason

  • Cc jason added

comment:3 Changed 11 years ago by rlm

  • Status changed from new to needs_review

comment:4 Changed 11 years ago by ylchapuy

line 945 in c_graphs.pyx, shouldn't it be in_neighbors ?

comment:5 Changed 11 years ago by rlm

  • Status changed from needs_review to needs_work

Yes! Good catch!

Changed 11 years ago by rlm

apply to sage-4.3.rc0 + #7640 + #7674 + #7673

comment:6 Changed 11 years ago by rlm

  • Status changed from needs_work to needs_review

comment:7 follow-up: Changed 11 years ago by ncohen

I saw you replaced

for w in (self._cg.out_neighbors(v) if side == 1 else self._cg.in_neighbors(v)): 

with

if side == 1: 
   neighbors = self._cg.out_neighbors(v) 
elif self._cg_rev is not None: # Sparse 
   neighbors = self._cg_rev.out_neighbors(v) 
else: # Dense 
   neighbors = self._cg.in_neighbors(v) 

I understand what you mean, but wouldn't it easier for developpers to define a function "in_neighbors" or "out_neighbors" doing this stuff to avoid dealing with the implementation of graphs when in the c_graph.pyx file ( where the algorithm are more graph-theoretic and a bit further from the implementation ) ?

This kind of thing is bound to reappear very often as we write algorithms in Cython... :-)

Nathann

comment:8 Changed 11 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:9 in reply to: ↑ 7 Changed 11 years ago by rlm

  • Status changed from needs_info to needs_review

Replying to ncohen:

I saw you replaced ... with ... I understand what you mean, but wouldn't it easier for developpers to define a function "in_neighbors" or "out_neighbors" doing this stuff to avoid dealing with the implementation of graphs when in the c_graph.pyx file ( where the algorithm are more graph-theoretic and a bit further from the implementation ) ?

On the level of c_graphs, there is no way to avoid the implementation of graphs. You're using ints as vertices which may not line up with the actual labels, and since you're calling methods of self._cg, there's no way around it. If you want to write on a more friendly level, you need to sacrifice some speed, since on the level of (mostly Python) backends, the vertex labels are honest, and 'in_neighbors' is the appropriate function there.

This kind of thing is bound to reappear very often as we write algorithms in Cython... :-)

This is only relevant to very low-level functions. In which case you *are* implementing graphs :)

comment:10 Changed 11 years ago by rlm

I should have pointed out that self._cg.in_neighbors(v) would still work in the case you point out. It's just that using self._cg_rev.out_neighbors(v) is faster when it's available. The point is that you only have to worry about these things when you're writing a function in the GraphBackends?.

I'm more and more becoming convinced that #7634 is the appropriate place to break up graph.py. It will already be an invasive change to sage/graphs, and this will encourage people to get their pet patches merged before the switch. When I break up the file, part of the result will be a Cython layer, which sits "above" the graph backends. That way, when people are writing more advanced graph theory functions in Cython, they can do it there, safely away from the implementation-level stuff you're talking about.

comment:11 follow-up: Changed 11 years ago by ncohen

Got it :-)

D you think there could be a *nice* way, though, to prevent people from using in_neighbors on sparse graphs having a reversed version of themselves ?

comment:12 Changed 11 years ago by ncohen

  • Status changed from needs_review to positive_review

Positive review for this patch ! Applies fine, pass tests, and as far as I could I found nothing wrong inside... :-)

comment:13 in reply to: ↑ 11 Changed 11 years ago by rlm

Replying to ncohen:

Got it :-)

D you think there could be a *nice* way, though, to prevent people from using in_neighbors on sparse graphs having a reversed version of themselves ?

SparseGraphs? will never have a reversed version. CGraphBackends may have a reversed version (i.e. two SparseGraphs?), in which case in_neighbors will call it. I don't think we need to worry too much about lots of people implementing functions for the backends.

comment:14 Changed 11 years ago by mhansen

  • Authors set to Robert Miller
  • Merged in set to sage-4.3.rc1
  • Milestone changed from sage-4.3.1 to sage-4.3
  • Resolution set to fixed
  • Reviewers set to Nathann Cohen
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.