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)
Change History (15)
comment:1 Changed 11 years ago by
- Cc ncohen added
comment:2 Changed 11 years ago by
- Cc jason added
comment:3 Changed 11 years ago by
- Status changed from new to needs_review
comment:4 Changed 11 years ago by
comment:6 Changed 11 years ago by
- Status changed from needs_work to needs_review
comment:7 follow-up: ↓ 9 Changed 11 years ago by
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
- Status changed from needs_review to needs_info
comment:9 in reply to: ↑ 7 Changed 11 years ago by
- 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
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: ↓ 13 Changed 11 years ago by
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
- 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
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
- 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
line 945 in
c_graphs.pyx
, shouldn't it bein_neighbors
?