Opened 13 years ago

Closed 13 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:

GitHub link to the corresponding issue

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 13 years ago.
apply to sage-4.3.rc0 + #7640 + #7674 + #7673

Download all attachments as: .zip

Change History (15)

comment:1 Changed 13 years ago by ncohen

Cc: ncohen added

comment:2 Changed 13 years ago by jason

Cc: jason added

comment:3 Changed 13 years ago by rlm

Status: newneeds_review

comment:4 Changed 13 years ago by ylchapuy

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

comment:5 Changed 13 years ago by rlm

Status: needs_reviewneeds_work

Yes! Good catch!

Changed 13 years ago by rlm

Attachment: trac_7651.patch added

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

comment:6 Changed 13 years ago by rlm

Status: needs_workneeds_review

comment:7 Changed 13 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 13 years ago by ncohen

Status: needs_reviewneeds_info

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

Status: needs_infoneeds_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 13 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 Changed 13 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 13 years ago by ncohen

Status: needs_reviewpositive_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 13 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 13 years ago by mhansen

Authors: Robert Miller
Merged in: sage-4.3.rc1
Milestone: sage-4.3.1sage-4.3
Resolution: fixed
Reviewers: Nathann Cohen
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.