David C Ullrich asked: > Q: How do we ensure there are no loops in the dependencies? > > Do we actually run the whole graph through some algorithm > to verify there are no loops?
The question you are asking is the dependency graph a "directed acyclic graph" (commonly called a DAG)? One algorithm to determine if it is, is called "topological sort". That algorithm tells you where there are cyclces in your graph, if any, and also tells you the order of the dependencies, i.e. if x is updated, what you have to update downstream AND THE ORDER you have to perform the downstream computations in. We use this algorithm for solving just the kind of dataflow problems you are talking about in our circuit design tools. Circuit designs have one-way dependencies that we want to sort and resolve--similarly, we don't want cycles in our circuits except ones that pass through clocked flip-flops. We solve such problems on circuits with millions of gates, i.e. enough gates to represent the CPU of your computer or a disk controller chip or a router. I believe there are also algorithms that allow you to construct only acyclic (the technical term for non-looping) graphs and don't require you to enter the vertexes (verticies if you prefer) of the graph in any specific order, and in the worst case you can always run the topological sort on any graph and determine if the graph is cyclic. The area is well-studied and you can find a variety of algorithms that solve most interesting graph problems as they all occur over-and-over in numerous diverse fields. Hope this helps, -Chris ***************************************************************************** Chris Clark Internet : [EMAIL PROTECTED] Compiler Resources, Inc. Web Site : http://world.std.com/~compres 23 Bailey Rd voice : (508) 435-5016 Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours) ------------------------------------------------------------------------------ -- http://mail.python.org/mailman/listinfo/python-list
