[Bf-blender-cvs] [b9fea12] depsgraph_refactor: Transitive reduction optimization for operation relations.

[Lukas Tönne]

Commit: b9fea128e07bb9eccecc09159fb6894317f724ff
Author: Lukas Tönne
Date:   Mon May 19 19:41:25 2014 +0200
https://developer.blender.org/rBb9fea128e07bb9eccecc09159fb6894317f724ff

Transitive reduction optimization for operation relations.

This removed redundant relations between operations, implementing the
transitive reduction algorithm:
http://en.wikipedia.org/wiki/Transitive_reduction

The current implementation is a bit naive, but can be improved later.

Using this optimization gives more flexibility in the build procedure,
since we don't need to have fully defined relations in a component
before adding external relations.

Performance would only be improved in some extreme cases probably
(huge amount of redundant relations), it should be much more dependent
on a good scheduling heuristic.

===================================================================

M	source/blender/depsgraph/intern/depsgraph_build.cpp
M	source/blender/depsgraph/intern/depsnode_operation.h

===================================================================

diff --git a/source/blender/depsgraph/intern/depsgraph_build.cpp b/source/blender/depsgraph/intern/depsgraph_build.cpp
index 2fda0ed..bf4895e 100644
--- a/source/blender/depsgraph/intern/depsgraph_build.cpp
+++ b/source/blender/depsgraph/intern/depsgraph_build.cpp
@@ -389,6 +389,73 @@ void DepsgraphRelationBuilder::add_operation_relation(OperationDepsNode *node_fr
 
 /* -------------------------------------------------- */
 
+/* performs a transitive reduction to remove redundant relations
+ * http://en.wikipedia.org/wiki/Transitive_reduction
+ * 
+ * XXX The current implementation is somewhat naive and has O(V*E) worst case runtime.
+ * A more optimized algorithm can be implemented later, e.g.
+ * 
+ * http://www.sciencedirect.com/science/article/pii/0304397588900321/pdf?md5=3391e309b708b6f9cdedcd08f84f4afc&pid=1-s2.0-0304397588900321-main.pdf
+ * 
+ * Care has to be taken to make sure the algorithm can handle the cyclic case too!
+ * (unless we can to prevent this case early on)
+ */
+
+enum {
+	OP_VISITED = 1,
+	OP_REACHABLE = 2,
+};
+
+static void deg_graph_tag_paths_recursive(OperationDepsNode *node)
+{
+	if (node->done & OP_VISITED)
+		return;
+	node->done |= OP_VISITED;
+	
+	for (OperationDepsNode::Relations::const_iterator it = node->inlinks.begin(); it != node->inlinks.end(); ++it) {
+		DepsRelation *rel = *it;
+		
+		deg_graph_tag_paths_recursive(rel->from);
+		/* do this only in inlinks loop, so the target node does not get flagged! */
+		rel->from->done |= OP_REACHABLE;
+	}
+}
+
+static void deg_graph_transitive_reduction(Depsgraph *graph)
+{
+	for (Depsgraph::OperationNodes::const_iterator it_target = graph->operations.begin(); it_target != graph->operations.end(); ++it_target) {
+		OperationDepsNode *target = *it_target;
+		
+		/* clear tags */
+		for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin(); it != graph->operations.end(); ++it) {
+			OperationDepsNode *node = *it;
+			node->done = 0;
+		}
+		
+		/* mark nodes from which we can reach the target
+		 * start with children, so the target node and direct children are not flagged
+		 */
+		target->done |= OP_VISITED;
+		for (OperationDepsNode::Relations::const_iterator it = target->inlinks.begin(); it != target->inlinks.end(); ++it) {
+			DepsRelation *rel = *it;
+			
+			deg_graph_tag_paths_recursive(rel->from);
+		}
+		
+		/* remove redundant paths to the target */
+		for (OperationDepsNode::Relations::const_iterator it_rel = target->inlinks.begin(); it_rel != target->inlinks.end();) {
+			DepsRelation *rel = *it_rel;
+			++it_rel; /* increment in advance, so we can safely remove the relation */
+			
+			if (rel->from->done & OP_REACHABLE) {
+				delete rel;
+			}
+		}
+	}
+}
+
+/* -------------------------------------------------- */
+
 /* Build depsgraph for the given scene, and dump results in given graph container */
 // XXX: assume that this is called from outside, given the current scene as the "main" scene 
 void DEG_graph_build_from_scene(Depsgraph *graph, Main *bmain, Scene *scene)
@@ -420,6 +487,8 @@ void DEG_graph_build_from_scene(Depsgraph *graph, Main *bmain, Scene *scene)
 	/* sort nodes to determine evaluation order (in most cases) */
 	DEG_graph_sort(graph);
 #endif
+	
+	deg_graph_transitive_reduction(graph);
 }
 
 /* ************************************************* */
diff --git a/source/blender/depsgraph/intern/depsnode_operation.h b/source/blender/depsgraph/intern/depsnode_operation.h
index c085e01..6d27599 100644
--- a/source/blender/depsgraph/intern/depsnode_operation.h
+++ b/source/blender/depsgraph/intern/depsnode_operation.h
@@ -60,9 +60,6 @@ typedef enum eDepsOperation_Flag {
 
 	/* Operation is evaluated using CPython; has GIL and security implications... */
 	DEPSOP_FLAG_USES_PYTHON   = (1 << 2),
-	
-	/* node was visited/handled already in traversal... */
-	DEPSOP_FLAG_TEMP_TAG           = (1 << 3),
 } eDepsOperation_Flag;
 
 /* Atomic Operation - Base type for all operations */
@@ -90,6 +87,7 @@ struct OperationDepsNode : public DepsNode {
 	
 	short optype;                 /* (eDepsOperation_Type) stage of evaluation */
 	short flag;                   /* (eDepsOperation_Flag) extra settings affecting evaluation */
+	short done;                   /* generic tag for traversal algorithms */
 };
 
 /* Macros for common static typeinfo */