DiGraph methods predecessors and successors
Nathann Cohen
I thought odd, a few days ago when writing some script dealing with DiGraphs, that Sage had no methods to list out_neighbors and in_neighbors of a graph. I used the functions outgoing_edges and incoming_edges to find them, but still...
When trying to write a patch for that, I noticed there were functions for this already !
DiGraph.successors()
DiGraph.predecessors()
Well. I think those two functions should be renamed..... I think DiGraph.out_neighbors() and DiGraph.in_neighbors() would be much easier to find and more natural...
( At the same time, I think it's be good to rename outgoing_edges to out_edges and incoming_edges to in_edges )
What do you think about it ?
Nathann
Tom Boothby
to find. I rather like successors and predecessors -- though I'd name
them "parents" and "children", myself.
Rob Beezer
> DiGraph.out_neighbors() and DiGraph.in_neighbors() would be much easier to
> find and more natural...
neighbors_in()
neighbors_out()
neighbors()
to make tab completion easier and to group them next to each other
when browsing commands with DiGraph.<tab>, plus the last one is
identical to what is available for "plain" graphs.
Rob
Tom Boothby
>
> On Oct 3, 2:47 am, Nathann Cohen <nathann.co...@gmail.com> wrote:
>> DiGraph.out_neighbors() and DiGraph.in_neighbors() would be much easier to
>> find and more natural...
>
> I'd suggest
>
> neighbors_in()
> neighbors_out()
> neighbors()
nightmare right now, thanks the the gobs of features that have been
implemented. I wonder -- could we somehow consolidate things? My
first idea is to break methods off into subobjects somehow;
G.neighbors()
G.neighbors.iterator()
G.neighbors.in()
G.neighbors.in.iterator()
...
This would clean up tab completion, and maybe even make it possible to
break the 12k line graph.py into more files. Thoughts?
Robert Bradshaw
> On Sat, Oct 3, 2009 at 12:52 PM, Rob Beezer
> <goo...@beezer.cotse.net> wrote:
>>
>> On Oct 3, 2:47 am, Nathann Cohen <nathann.co...@gmail.com> wrote:
>>> DiGraph.out_neighbors() and DiGraph.in_neighbors() would be much
>>> easier to
>>> find and more natural...
>>
>> I'd suggest
>>
>> neighbors_in()
>> neighbors_out()
>> neighbors()
>
> Now that *is* more natural. Introspection on graphs is a bit of a
> nightmare right now, thanks the the gobs of features that have been
> implemented. I wonder -- could we somehow consolidate things? My
> first idea is to break methods off into subobjects somehow;
>
> G.neighbors()
> G.neighbors.iterator()
> G.neighbors.in()
> G.neighbors.in.iterator()
> ...
>
> This would clean up tab completion, and maybe even make it possible to
> break the 12k line graph.py into more files. Thoughts?
Sounds good, but perhaps even more natural to have G.neighbors be
iterable and use the __iter__ method on it, rather than .iterator().
Then you can do list(G.neighbors()).
- Robert
Rob Beezer
> This would clean up tab completion, and maybe even make it possible
to
> break the 12k line graph.py into more files. Thoughts?
There is a noticeable lag every time I load the file in my editor -
just to do the syntax highlighting. ;-)
Not sure how subobjects would work - I guess if it was natural, it
would be an improvement, but if it were just to split files or to
improve introspection it might feel awkward in practice (ie when used
in code).
Rob
Tom Boothby
mind -- I didn't think it was that great an idea to begin with, just
wanted to get the discussion going. Perhaps the simplest thing would
be for introspection to "hide" methods that begin the same substring
(matching up to a _):
G.d<tab>
would include
G.db
G.degree...
G.delete...
G.density
(note the ... -- those would literally be included) and
G.degree<tab>
would show
G.degree
G.degree_histogram
G.degree_iterator
G.degree_to_cell
This would require only changes to introspection, not graphs.
>
> Rob
> >
>
Nicolas M. Thiery
+1
Besides, and as far as possible, keeping the names as consistent as
possible with networkx (and other python graph libraries) should be a
priority (just my 2cents).
Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/
Nathann Cohen
to neighbors_out or neighbors_in ( if all of us are ok about it ), but
I have no clue how to write what you are describing. Graph.neighbors
would be a subobject, does that mean an independent class ? Wouldn't
this slow down the whole Graph class, as these functions are among the
most used ? Here I feel that I do not know Python enough to help.. :-)
Nathann
Tom Boothby
>
> I would be glad to write a patch changing the names of these functions
> to neighbors_out or neighbors_in ( if all of us are ok about it ), but
That's fine by me.
> I have no clue how to write what you are describing. Graph.neighbors
> would be a subobject, does that mean an independent class ? Wouldn't
> this slow down the whole Graph class, as these functions are among the
> most used ? Here I feel that I do not know Python enough to help.. :-)
That's probably for the best -- it was a pretty bad idea, and any
implementation that one comes up with is probably going to be terrible
in one way or another. Don't do it.
Nick Alexander
>> would be a subobject, does that mean an independent class ? Wouldn't
>> this slow down the whole Graph class, as these functions are among
>> the
>> most used ? Here I feel that I do not know Python enough to
>> help.. :-)
>
> That's probably for the best -- it was a pretty bad idea, and any
> implementation that one comes up with is probably going to be terrible
> in one way or another. Don't do it.
I (and you?) did something similar for torsion subgroups of elliptic
curves. One can always break out the neighbours object, and then
provide the original functions in terms of that new object. That
factors the code while preserving the rich interface.
Nick
Jason Grout
We've had this discussion on whether method names should be
noun_adjective, or adjective_noun (e.g., left_kernel or kernel_left).
Adhering to the convention of English in Sage makes adjective_noun sound
better (e.g., left_kernel), but tab completion makes noun_adjective
easier to find and groups things together nicely.
One way around this difficulty would be to make tab completion smarter.
One proposed solution was to enhance tab completion, so that it worked
like:
sage: m.*kernel*?
m.integer_kernel
m.kernel
m.kernel_matrix
m.kernel_on
m.left_kernel
m.right_kernel
in other words, a tab would complete method names where the given text
was anywhere in the method name, not just at the start. Another
proposal was that a single tab would behave as we have now, but two tabs
in a row would do the above m.*kernel*? completion.
Note that these tab completions won't group things together on the
display, but they will help you find methods easier if we use the
adjective_noun convention.
On the issue of neighbors, I agree it would be nice to have neighbor
functions that were explicit for digraphs that contained the word
neighbor. I've needed this before,and remember spending some time to
figure out what I needed (i.e., the predecessors function).
Thanks,
Jason
--
Jason Grout
Tom Boothby
>> That's probably for the best -- it was a pretty bad idea, and any
>> implementation that one comes up with is probably going to be terrible
>> in one way or another. Don't do it.
>
> I (and you?) did something similar for torsion subgroups of elliptic
> curves. One can always break out the neighbours object, and then
> provide the original functions in terms of that new object. That
> factors the code while preserving the rich interface.
I don't think I was responsible for this. I maintain the opinion that
it's a bad idea, though I'm willing to capitulate if enough people
disagree. OTOH, if you've implemented it, I trust that it isn't too
ugly -- so maybe if somebody is interested in this sort of a project,
they could look at your code as an example.
However, Robert Miller has been notably silent on this topic. We
should try to get him to weigh in before making any sweeping
decisions, since he's (at the very least) the most familiar with the
code.
--tom
Robert Miller
> should try to get him to weigh in before making any sweeping
> decisions, since he's (at the very least) the most familiar with the
> code.
I have spent months trying to make function calls just like, e.g.
G.predecessors(3), as fast as possible. There is still a lot of work
left, but things like G.neighbors().in()... or whatever sounds
alarmingly to me like extra unnecessary Python layers around a
function which you want ABSOLUTELY no Python involved in at all, other
than the initial function call. Name changes and aliases I can live
with. Extra layers of Python function calls for no reason other than
tab completion prettiness, this is really bad. Especially when it's a
function as basic as neighbors, which gets used in almost every graph
theory algorithm out there. Imagine the future "embarrassing" thread
where a 10x speedup is discovered by avoiding this exact approach...
As far as it being *possible* to split up graph.py... It's a ten
minute job, but nobody's done it. You could split it in three right
away by having generic_graph.py, graph.py and digraph.py.
--
Robert L. Miller
http://www.rlmiller.org/
Nick Alexander
> minute job, but nobody's done it. You could split it in three right
> away by having generic_graph.py, graph.py and digraph.py.
+1
Nick
Jason Grout
>> However, Robert Miller has been notably silent on this topic. We
>> should try to get him to weigh in before making any sweeping
>> decisions, since he's (at the very least) the most familiar with the
>> code.
>
> I have spent months trying to make function calls just like, e.g.
> G.predecessors(3), as fast as possible. There is still a lot of work
> left, but things like G.neighbors().in()... or whatever sounds
> alarmingly to me like extra unnecessary Python layers around a
> function which you want ABSOLUTELY no Python involved in at all, other
> than the initial function call. Name changes and aliases I can live
> with. Extra layers of Python function calls for no reason other than
> tab completion prettiness, this is really bad. Especially when it's a
> function as basic as neighbors, which gets used in almost every graph
> theory algorithm out there. Imagine the future "embarrassing" thread
> where a 10x speedup is discovered by avoiding this exact approach...
>
+1
I'm with Robert.
> As far as it being *possible* to split up graph.py... It's a ten
> minute job, but nobody's done it. You could split it in three right
> away by having generic_graph.py, graph.py and digraph.py.
>
+1 too.
Jason
--
Jason Grout
Nathann Cohen
sending a patch for this file while another patch is removing this
file and creating three others... If that's how HG works ;-)
Nathann
Dan Drake
> The thing is that is it a pretty hard patch to send... If someone is
> sending a patch for this file while another patch is removing this
> file and creating three others... If that's how HG works ;-)
Mercurial should support this. If the big file is copied to the three
new files (using "hg copy") and then the correct bits removed from each
file, the resulting patch (if exported in the right format) will convey
this information.
Then if another patch comes along that refers to the original big file,
I think Mercurial can figure out where it should look.
Dan
--
--- Dan Drake
----- http://mathsci.kaist.ac.kr/~drake
-------
Nathann Cohen
To continue the discussion :-)
Nathann
> < 1KViewDownload
Robert Bradshaw
> On Thu, 08 Oct 2009 at 06:11AM -0700, Nathann Cohen wrote:
>> The thing is that is it a pretty hard patch to send... If someone is
>> sending a patch for this file while another patch is removing this
>> file and creating three others... If that's how HG works ;-)
>
> Mercurial should support this. If the big file is copied to the three
> new files (using "hg copy") and then the correct bits removed from
> each
> file, the resulting patch (if exported in the right format) will
> convey
> this information.
>
> Then if another patch comes along that refers to the original big
> file,
> I think Mercurial can figure out where it should look.
That is *if* git-style patches or bundles are used. Normal unified
diffs have no concept of a move, only a delete and add.
- Robert