i think you are looking for a "feedback arc set", which describes exactly the problem that applying "post_update" to a mapping solves:
http://en.wikipedia.org/wiki/Feedback_arc_set and we actually generate a set like this in the _find_cycles() method, except it doesnt find just one edge of the cycle, it contains all of the edges comprising the cycle. the "mincut" term is definitely wrong: "A cut is minimal if the size of the cut is not larger than the size of any other cut." nothing to do with cycles, and a topological sort is definitely not a flow network (no "source" or "sink" to start with). On Feb 2, 2007, at 12:07 PM, Michael Bayer wrote: > > > On Feb 2, 2007, at 10:33 AM, svilen wrote: >> A mincut algorithm finds the minimal number of edges to cut in a >> cycled graph so it becomes without cycles. >> >> http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem >> >> i.e. applying such algorithm over the graph of table dependencies >> (foregnkey), one gets some minimal number of foreign keys to make >> use_alter=True. >> there might be many solutions. >> >> or in the mapper/relation graph, find which relations to make >> post_update=True so although obj-relaltions are cycling, the >> mapper/relations have no cycles. >> >> is it more clear now? >> > > no, not at all. thats the article I read, and it applies to a "flow > graph", which as far as I can tell has to apply numerical values to > each edge in the graph and applies a "capacity" to the nodes. I dont > see what "numerical" or "capacity" values would be applied to a > topological sort. > > class User > class Address > > User -> one to many -> Address > > whats the "capacity" for that graph ? whats the "x/y" to stick > between those two nodes ? > > also, this whole topic is not very important to me, as its easy > enough for someone to just add a "post_update" into their mapping > configuration when an obvious inter-row dependency is detected. > > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "sqlalchemy" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sqlalchemy?hl=en -~----------~----~----~----~------~----~------~--~---
