> 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).
of course, topological sort is a sort, but in order of it to work, the graph should not have cycles. Which are cut by use_alter's and post_updates, on foreign keys and relations. well, in our case all edges have cost of 1, except inheritance-related primary-key-joins which have cost of infinity, so they become uncuttable. Duplicate edges do matter as they increase the total cost. Thus min cut is a cut with mininal cost, which is the number of edges cut. i am trying to automaticaly add the relations' post_update, given a set of classes and their relations. i've already done the use_alter's on foreign keys in same automatical way. Anyway. My conclusion from the source code, is that current object/mappers-based flush() does not handle the concrete-inheritance in a different way than table-inheritance, while IMO they should differ as they touch different set of tables. which in a way confirms your saying about flush() would be better based on tables/foreign keys than obj/mappers. > 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 sqlalchemy@googlegroups.com 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 -~----------~----~----~----~------~----~------~--~---
