Nils, First of all, I hope my distaste for the muggy weather hasn't made me unbearable. 0:-)
When I was referring to things being much more difficult, I was thinking of implementing a cmp() function that took arbitrary hashables and defined a total ordering on all of them, consistent regardless of order of definition or memory location. Not necessary-- see below. On Wed, Aug 4, 2010 at 7:20 PM, Nils Bruin <nbr...@sfu.ca> wrote: > On Aug 4, 3:14 pm, Robert Miller <r...@rlmiller.org> wrote: >> If Python jumped off a cliff... > Then Sage might as well :-). Or be reimplemented in CL. Yes! This is the obvious solution! Let's continue this subthread on sage-flame so we can really express our excitement! ;-) > Which was my suggestion: Order the vertices by the order in which they > are added. That is a well-defined, consistent choice that does not > require a non-existing total ordering. This is not that objectionable of an approach, given some elbow grease (see my comments below). The only problem is that if you make a copy of the graph, for example, and somehow in the process the vertices get jumbled around (which is the case currently-- somewhere things get converted to a set or something, and then iterated over), the adjacency matrix might differ even though the graphs themselves would be equal. > Forcing people to be explicit about their choices often seems > pedantic, until one encounters a situation where the choice > unexpectedly makes a difference. I can definitely agree with this sentiment. I think it is what Sage's graphs should do, *eventually*. > "order of introduction" and hashing. Order of introduction makes sense as long as you're careful about it (see my comment about copying above), but I have a small problem with hashing -- when you get to collisions, you are back to the same problem. It is a practical way to make things sort quickly, but the theoretical/hypothetical problem of how to define the ordering remains. >> ordering, I'm just suggesting that since there is an inconsistent >> definition of < for Sage sets, and since they get used frequently as >> vertices, that we define a total ordering. You yourself admitted that >> you can't think of a natural mathematical meaning for < for arbitrary >> sets... > > I think you are patching things the wrong way around: We find that > graphs assume the existence of a total ordering on their vertex set, > but that such an ordering need not be implemented. The more natural > way to solve the problem is by looking why graphs make that assumption > and if they have to. Not by trying to endow everything with a total > ordering. I'm definitely not trying to endow everything with a total ordering. (I think by saying this we might be converging towards agreement... I hope) Again, see my comments below. > In terms of cost, I think your solution will be more expensive as > well. I'm not actually advocating using a binary search for anything specific. I was just bringing it up as an example of why one might want things sorted. You're right, hashing is much faster. > I think this example makes me even more convinced that vertices should > be looked up via hashing and not via sorted lists and hence > strengthens my opinion that "universal total ordering" is a bad thing, > inviting bad programming style. > > But then again, I'm not volunteering to implement the required > changes. I think we've had a very healthy discussion and seen some > good arguments on either sides. Now it's up to the painter to choose > the colour of the shed. I appreciate that sentiment greatly. And I want to reiterate the fact that I am in no way advocating universal total ordering. Let me summarize what I'd like to do, short term and long term: For now, I'd like to fix the problem in the short term as in the patch at http://trac.sagemath.org/sage_trac/ticket/9677 This allows researchers to get on with their research, and me to get on with my life. It gives the ability to use sets of integers as vertices in Sage, the way things are now, thus making for much rejoicing. Perhaps I should also add some caveat to the graph documentation that a total ordering on the vertices is expected, or subtle bugs may rear their ugly heads. I agree with you that it is a bit silly for this assumption to be there in the first place. However, it is kind of all over the place. Fixing it should be done incrementally, and over time. There are a couple facts working in our favor. 1. All vertices need to be hashable. That almost completely defines a quickly computable arbitrary sort right there, for when it is needed. 2. At least when we are using c_graphs, part of the underlying implementation includes a bijection from the set of vertices to a certain set of nonnegative integers, which is defined exactly by order of insertion. So in that case, we are finished. 3. There are probably several places where we are using sorted() when we don't really need to be. If you ever decided to grep through the graphs module and offer any suggestions for improvements, you probably wouldn't wait too long to see a patch. Hopefully this all agrees with you, and if not, I guess I can start learning Lisp... -- Robert L. Miller http://www.rlmiller.org/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
