Dependency graph patch, provided by Jean-Luc Peuriere.

Works like a charm... well it now replaces the old base-sorting hack. :)
Next stage will be to define how to further integrate it. Plus some
minor code cleanups... static/internal functions versus external, etc.

13 files changed, 1973 insertions, 7 deletions

diff --git a/source/blender/blenkernel/BKE_depsgraph.h b/source/blender/blenkernel/BKE_depsgraph.h
new file mode 100644
index 00000000000..007b38b984c
--- /dev/null
+++ b/source/blender/blenkernel/BKE_depsgraph.h
@@ -0,0 +1,103 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2004 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+
+#ifndef DEPSGRAPH_API
+#define DEPSGRAPH_API
+
+/*
+#define DEPS_DEBUG
+*/
+
+struct Scene;
+struct DagNodeQueue;
+struct DagForest;
+struct DagNode;
+
+typedef enum { 
+	DAG_RL_SCENE				= 1,
+	DAG_RL_DATA					= 2,
+	DAG_RL_PARENT				= 4,
+	DAG_RL_TRACK				= 8,
+	DAG_RL_PATH					= 16,
+	DAG_RL_CONSTRAINT			= 32,
+	DAG_RL_HOOK					= 64,
+	DAG_RL_DATA_CONSTRAINT		= 128,
+	DAG_NO_RELATION				= 256
+} dag_rel_type;
+
+
+typedef enum {
+	DAG_RL_SCENE_MASK			= 1,
+	DAG_RL_DATA_MASK			= 2,
+	DAG_RL_PARENT_MASK			= 4,
+	DAG_RL_TRACK_MASK			= 8,
+	DAG_RL_PATH_MASK			= 16,
+	DAG_RL_CONSTRAINT_MASK		= 32,
+	DAG_RL_HOOK_MASK			= 64,
+	DAG_RL_DATA_CONSTRAINT_MASK	= 128,
+	DAG_RL_ALL_BUT_DATA_MASK	= 253,
+	DAG_RL_ALL_MASK				= 255
+} dag_rel_type_mask;
+
+typedef void (*graph_action_func)(void * ob, void **data);
+
+// queues are returned by all BFS & DFS queries
+// opaque type
+void	*pop_ob_queue(struct DagNodeQueue *queue);
+int		queue_count(struct DagNodeQueue *queue);
+void	queue_delete(struct DagNodeQueue *queue);
+
+// queries
+struct DagForest	*build_dag(struct Scene *sce, short mask);
+void				free_forest(struct DagForest *Dag);
+
+// note :
+// the meanings of the 2 returning values is a bit different :
+// BFS return 1 for cross-edges and back-edges. the latter are considered harmfull, not the former
+// DFS return 1 only for back-edges
+int pre_and_post_BFS(struct DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data);
+int pre_and_post_DFS(struct DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data);
+
+int pre_and_post_source_BFS(struct DagForest *dag, short mask, struct DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data);
+int pre_and_post_source_DFS(struct DagForest *dag, short mask, struct DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data);
+
+struct DagNodeQueue *get_obparents(struct DagForest	*dag, void *ob); 
+struct DagNodeQueue *get_first_ancestors(struct DagForest	*dag, void *ob); 
+struct DagNodeQueue *get_all_childs(struct DagForest	*dag, void *ob); //
+dag_rel_type		are_obs_related(struct DagForest	*dag, void *ob1, void *ob2);
+int					is_acyclic(struct DagForest	*dag); //
+//int					get_cycles(struct DagForest	*dag, struct DagNodeQueue **queues, int *count); //
+void				topo_sort_baselist(struct Scene *sce);
+
+void	boundbox_deps(void);
+void	draw_all_deps(void);
+
+
+#endif
\ No newline at end of file
diff --git a/source/blender/blenkernel/SConscript b/source/blender/blenkernel/SConscript
index 3ab7dc385c7..0b6bf520bc4 100644
--- a/source/blender/blenkernel/SConscript
+++ b/source/blender/blenkernel/SConscript
@@ -5,6 +5,7 @@ Import ('library_env')
 blenkernel_env = library_env.Copy ()
 
 source_files = ['intern/constraint.c',
+		'intern/depsgraph.c',
                 'intern/DerivedMesh.c',
                 'intern/group.c',
                 'intern/material.c',
diff --git a/source/blender/blenkernel/depsgraph_private.h b/source/blender/blenkernel/depsgraph_private.h
new file mode 100644
index 00000000000..7b3da76c652
--- /dev/null
+++ b/source/blender/blenkernel/depsgraph_private.h
@@ -0,0 +1,129 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2004 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+#ifndef DEPSGRAPH_PRIVATE
+#define DEPSGRAPH_PRIVATE
+
+#include "BKE_depsgraph.h"
+#include "DNA_constraint_types.h"
+#include "BKE_constraint.h"
+
+
+#define DEPSX	5.0
+#define DEPSY	1.8
+
+#define DAGQUEUEALLOC 50
+
+enum {
+	DAG_WHITE = 0,
+	DAG_GRAY = 1,
+	DAG_BLACK = 2
+};
+
+
+
+typedef struct DagAdjList
+{
+	struct DagNode *node;
+	dag_rel_type type;
+	int count; // number of identical arcs
+	struct DagAdjList *next;
+} DagAdjList;
+
+
+typedef struct DagNode 
+{
+	int color;
+	short type;
+	float x, y, k;	
+	void * ob;
+	void * first_ancestor;
+	int		ancestor_count;
+	int BFS_dist;		// BFS distance
+	int DFS_dist;		// DFS distance
+	int DFS_dvtm;		// DFS discovery time
+	int DFS_fntm;		// DFS Finishing time
+	struct DagAdjList *child;
+	struct DagNode *next;
+} DagNode;
+
+typedef struct DagNodeQueueElem {
+	struct DagNode *node;
+	struct DagNodeQueueElem *next;
+} DagNodeQueueElem;
+
+typedef struct DagNodeQueue
+{
+	DagNodeQueueElem *first;
+	DagNodeQueueElem *last;
+	int count;
+	int maxlevel;
+	struct DagNodeQueue *freenodes;
+} DagNodeQueue;
+
+// forest as we may have more than one DAG unnconected
+typedef struct DagForest 
+{
+	ListBase DagNode;
+	int numNodes;
+	int is_acyclic;
+} DagForest;
+
+
+// queue operations
+DagNodeQueue * queue_create (int slots);
+void queue_raz(DagNodeQueue *queue);
+void push_queue(DagNodeQueue *queue, DagNode *node);
+void push_stack(DagNodeQueue *queue, DagNode *node);
+DagNode * pop_queue(DagNodeQueue *queue);
+DagNode * get_top_node_queue(DagNodeQueue *queue);
+
+// Dag management
+DagForest *getMainDag(void);
+void setMainDag(DagForest *dag);
+DagForest * dag_init(void);
+DagNode * dag_find_node (DagForest *forest,void * fob);
+DagNode * dag_add_node (DagForest *forest,void * fob);
+DagNode * dag_get_node (DagForest *forest,void * fob);
+DagNode * dag_get_sub_node (DagForest *forest,void * fob);
+void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, dag_rel_type rel);
+
+void graph_bfs(void);
+
+DagNodeQueue * graph_dfs(void);
+
+void set_node_xy(DagNode *node, float x, float y);
+void graph_print_queue(DagNodeQueue *nqueue);
+void graph_print_queue_dist(DagNodeQueue *nqueue);
+void graph_print_adj_list(void);
+
+int build_deps(short mask);
+
+#endif
+ 
\ No newline at end of file
diff --git a/source/blender/blenkernel/intern/depsgraph.c b/source/blender/blenkernel/intern/depsgraph.c
new file mode 100644
index 00000000000..7ae3f39e197
--- /dev/null
+++ b/source/blender/blenkernel/intern/depsgraph.c
@@ -0,0 +1,1206 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2004 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+ 
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+
+#ifdef _WIN32
+#include "BLI_winstuff.h"
+#endif
+
+//#include "BMF_Api.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_arithb.h"
+
+#include "DNA_ID.h"
+#include "DNA_object_types.h"
+#include "DNA_oops_types.h"
+#include "DNA_scene_types.h"
+#include "DNA_action_types.h"
+#include "DNA_screen_types.h"
+#include "DNA_space_types.h"
+#include "DNA_view2d_types.h"
+
+#include "BKE_utildefines.h"
+#include "BKE_global.h"
+
+#include "MEM_guardedalloc.h"
+#include "blendef.h"
+
+ 
+ #include "depsgraph_private.h"
+ 
+/* Queue and stack operations for dag traversal 
+ *
+ * the queue store a list of freenodes to avoid successives alloc/dealloc
+ */
+
+DagNodeQueue * queue_create (int slots) 
+{
+	DagNodeQueue * queue;
+	DagNodeQueueElem * elem;
+	int i;
+	
+	queue = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
+	queue->freenodes = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
+	queue->count = 0;
+	queue->maxlevel = 0;
+	queue->first = queue->last = NULL;
+	elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem3");
+	elem->node = NULL;
+	elem->next = NULL;
+	queue->freenodes->first = queue->freenodes->last = elem;
+	
+	for (i = 1; i <slots;i++) {
+		elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem4");
+		elem->node = NULL;
+		elem->next = NULL;
+		queue->freenodes->last->next = elem;
+		queue->freenodes->last = elem;
+	}
+	queue->freenodes->count = slots;
+	return queue;
+}
+
+void queue_raz(DagNodeQueue *queue)
+{
+	DagNodeQueueElem * elem;
+	
+	elem = queue->first;
+	if (queue->freenodes->last)
+		queue->freenodes->last->next = elem;
+	else
+		queue->freenodes->first = queue->freenodes->last = elem;
+	
+	elem->node = NULL;
+	queue->freenodes->count++;
+	while (elem->next) {
+		elem = elem->next;
+		elem->node = NULL;
+		queue->freenodes->count++;
+	}
+	queue->freenodes->last = elem;
+	queue->count = 0;
+}
+
+void queue_delete(DagNodeQueue *queue)
+{
+	DagNodeQueueElem * elem;
+	DagNodeQueueElem * temp;
+	
+	elem = queue->first;
+	while (elem) {
+		temp = elem;
+		elem = elem->next;
+		MEM_freeN(temp);
+	}
+	
+	elem = queue->freenodes->first;
+	while (elem) {
+		temp = elem;
+		elem = elem->next;
+		MEM_freeN(temp);
+	}
+	
+	MEM_freeN(queue->freenodes);			
+	MEM_freeN(queue);			
+}
+
+/* insert in queue, remove in front */
+void push_queue(DagNodeQueue *queue, DagNode *node)
+{
+	DagNodeQueueElem * elem;
+	int i;
+
+	if (node == NULL) {
+		fprintf(stderr,"pushing null node \n");
+		return;
+	}
+	/*fprintf(stderr,"BFS push : %s %d\n",((ID *) node->ob)->name, queue->count);*/
+
+	elem = queue->freenodes->first;
+	if (elem != NULL) {
+		queue->freenodes->first = elem->next;
+		if ( queue->freenodes->last == elem) {
+			queue->freenodes->last = NULL;
+			queue->freenodes->first = NULL;
+		}
+		queue->freenodes->count--;
+	} else { /* alllocating more */		
+		elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
+		elem->node = NULL;
+		elem->next = NULL;
+		queue->freenodes->first = queue->freenodes->last = elem;
+
+		for (i = 1; i <DAGQUEUEALLOC;i++) {
+			elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
+			elem->node = NULL;
+			elem->next = NULL;
+			queue->freenodes->last->next = elem;
+			queue->freenodes->last = elem;
+		}
+		queue->freenodes->count = DAGQUEUEALLOC;
+			
+		elem = queue->freenodes->first;	
+		queue->freenodes->first = elem->next;	
+	}
+	elem->next = NULL;
+	elem->node = node;
+	if (queue->last != NULL)
+		queue->last->next = elem;
+	queue->last = elem;
+	if (queue->first == NULL) {
+		queue->first = elem;
+	}
+	queue->count++;
+}
+
+
+/* insert in front, remove in front */
+void push_stack(DagNodeQueue *queue, DagNode *node)
+{
+	DagNodeQueueElem * elem;
+	int i;
+
+	elem = queue->freenodes->first;	
+	if (elem != NULL) {
+		queue->freenodes->first = elem->next;
+		if ( queue->freenodes->last == elem) {
+			queue->freenodes->last = NULL;
+			queue->freenodes->first = NULL;
+		}
+		queue->freenodes->count--;
+	} else { /* alllocating more */
+		elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
+		elem->node = NULL;
+		elem->next = NULL;
+		queue->freenodes->first = queue->freenodes->last = elem;
+
+		for (i = 1; i <DAGQUEUEALLOC;i++) {
+			elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
+			elem->node = NULL;
+			elem->next = NULL;
+			queue->freenodes->last->next = elem;
+			queue->freenodes->last = elem;
+		}
+		queue->freenodes->count = DAGQUEUEALLOC;
+			
+		elem = queue->freenodes->first;	
+		queue->freenodes->first = elem->next;	
+	}
+	elem->next = queue->first;
+	elem->node = node;
+	queue->first = elem;
+	if (queue->last == NULL)
+		queue->last = elem;
+	queue->count++;
+}
+
+
+DagNode * pop_queue(DagNodeQueue *queue)
+{
+	DagNodeQueueElem * elem;
+	DagNode *node;
+
+	elem = queue->first;
+	if (elem) {
+		queue->first = elem->next;
+		if (queue->last == elem) {
+			queue->last=NULL;
+			queue->first=NULL;
+		}
+		queue->count--;
+		if (queue->freenodes->last)
+			queue->freenodes->last->next=elem;
+		queue->freenodes->last=elem;
+		if (queue->freenodes->first == NULL)
+			queue->freenodes->first=elem;
+		node = elem->node;
+		elem->node = NULL;
+		elem->next = NULL;
+		queue->freenodes->count++;
+		return node;
+	} else {
+		fprintf(stderr,"return null \n");
+		return NULL;
+	}
+}
+
+void	*pop_ob_queue(struct DagNodeQueue *queue) {
+	return(pop_queue(queue)->ob);
+}
+
+DagNode * get_top_node_queue(DagNodeQueue *queue) 
+{
+	return queue->first->node;
+}
+
+int		queue_count(struct DagNodeQueue *queue){
+	return queue->count;
+}
+
+
+DagForest * dag_init()
+{
+	DagForest *forest;
+	
+	forest = MEM_mallocN(sizeof(DagForest),"DAG root");
+	forest->DagNode.first = NULL;
+	forest->DagNode.last = NULL;
+	forest->numNodes = 0;
+	return forest;
+}
+
+struct DagForest	*build_dag(struct Scene *sce, short mask) 
+{
+	Base *base;
+	Object *ob;
+	DagNode * node;
+	DagNode * node2;
+	DagNode * node3;
+	DagNode * scenenode;
+	DagForest *dag;
+
+	dag = sce->theDag;
+	sce->dagisvalid=1;
+	if ( dag)
+		free_forest( dag ); 
+	else {
+		dag = dag_init();
+		sce->theDag = dag;
+	}
+	
+	// add base node for scene. scene is always the first node in DAG
+	scenenode = dag_add_node(dag, sce);	
+	
+	/* targets in object struct yet to be added. should even they ?
+		struct Ipo *ipo;
+	ListBase nlastrips;
+	ListBase hooks;
+	*/
+	
+	
+	base = sce->base.first;
+	while(base) { // add all objects in any case
+		int addtoroot = 1;
+		ob= (Object *) base->object;
+		
+		node = dag_get_node(dag,ob);
+		
+		if ((ob->data) && (mask&DAG_RL_DATA_MASK)) {
+			node2 = dag_get_node(dag,ob->data);
+			dag_add_relation(dag,node,node2,DAG_RL_DATA);
+			node2->first_ancestor = ob;
+			node2->ancestor_count += 1;
+			
+			if ((ob->type == OB_ARMATURE) && (mask&DAG_RL_DATA_CONSTRAINT_MASK)) { // add armature constraints to datas
+				if (ob->pose){
+					bPoseChannel *pchan;
+					bConstraint *con;
+					Object * target;
+					
+					for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){
+						for (con = pchan->constraints.first; con; con=con->next){
+							if (constraint_has_target(con)) {
+								target = get_constraint_target(con);
+								if (strcmp(target->id.name, ob->id.name) != 0) {
+									//fprintf(stderr,"armature target :%s \n", target->id.name);
+									node3 = dag_get_node(dag,target);
+									dag_add_relation(dag,node3,node2,DAG_RL_CONSTRAINT);
+								}
+							}
+						}
+					}
+				}
+			}
+			
+			if ((ob->hooks.first) && (mask&DAG_RL_HOOK)) {
+				ObHook *hook;
+				
+				for(hook= ob->hooks.first; hook; hook= hook->next) {
+					if(hook->parent) {
+						node3 = dag_get_node(dag,hook->parent);
+						dag_add_relation(dag,node3,node2,DAG_RL_HOOK);
+					}
+				}
+			}
+		} else { // add armature constraints to object itself
+			if ((ob->type == OB_ARMATURE) && (mask&DAG_RL_DATA_CONSTRAINT_MASK)) {
+				if (ob->pose){
+					bPoseChannel *pchan;
+					bConstraint *con;
+					Object * target;
+					
+					for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){
+						for (con = pchan->constraints.first; con; con=con->next){
+							if (constraint_has_target(con)) {
+								target = get_constraint_target(con);
+								if (strcmp(target->id.name, ob->id.name) != 0) {
+									//fprintf(stderr,"armature target :%s \n", target->id.name);
+									node3 = dag_get_node(dag,target);
+									dag_add_relation(dag,node3,node,DAG_RL_CONSTRAINT);
+								}
+							}
+						}
+					}
+				}
+			}
+			if ((ob->hooks.first)  && (mask&DAG_RL_HOOK)) {
+				ObHook *hook;
+				
+				for(hook= ob->hooks.first; hook; hook= hook->next) {
+					if(hook->parent) {
+						node3 = dag_get_node(dag,hook->parent);
+						dag_add_relation(dag,node3,node,DAG_RL_HOOK);
+					}
+				}
+			}			
+		}
+		
+		if ((ob->parent) && (mask&DAG_RL_PARENT_MASK)){
+			node2 = dag_get_node(dag,ob->parent);
+			dag_add_relation(dag,node2,node,DAG_RL_PARENT);
+			addtoroot = 0;
+		}
+		if ((ob->track) && (mask&DAG_RL_TRACK_MASK)){
+			node2 = dag_get_node(dag,ob->track);
+			dag_add_relation(dag,node2,node,DAG_RL_TRACK);
+			addtoroot = 0;
+			
+		}
+		if ((ob->path) && (mask&DAG_RL_PATH_MASK)){
+			node2 = dag_get_node(dag,ob->track);
+			dag_add_relation(dag,node2,node,DAG_RL_PATH);
+			addtoroot = 0;
+			
+		}
+		
+		/* Count constraints */
+		if (mask & DAG_RL_CONSTRAINT_MASK) {
+			bConstraint *con;
+			for (con = ob->constraints.first; con; con=con->next){
+				if (constraint_has_target(con)) {
+					node2 = dag_get_node(dag,get_constraint_target(con));
+					dag_add_relation(dag,node2,node,DAG_RL_CONSTRAINT);
+					addtoroot = 0;
+					
+				}
+			}
+		}	
+		
+		
+		if (addtoroot == 1 )
+			dag_add_relation(dag,scenenode,node,DAG_RL_SCENE);
+		
+		addtoroot = 1;
+		base= base->next;
+	}
+	
+	// cycle detection and solving
+	// solve_cycles(dag);	
+	
+	return dag;
+}
+
+
+void free_forest(DagForest *Dag) 
+{  /* remove all nodes and deps */
+	DagNode *tempN;
+	DagAdjList *tempA;	
+	DagAdjList *itA;
+	DagNode *itN = Dag->DagNode.first;
+	
+	while (itN) {
+		itA = itN->child;	
+		while (itA) {
+			tempA = itA;
+			itA = itA->next;
+			MEM_freeN(tempA);			
+		}
+		tempN = itN;
+		itN = itN->next;
+		MEM_freeN(tempN);
+	}
+	Dag->DagNode.first = NULL;
+	Dag->DagNode.last = NULL;
+	Dag->numNodes = 0;
+
+}
+
+DagNode * dag_find_node (DagForest *forest,void * fob)
+{
+		DagNode *node = forest->DagNode.first;
+		
+		while (node) {
+			if (node->ob == fob)
+				return node;
+			node = node->next;
+		}
+		return NULL;
+}
+
+/* no checking of existance, use dag_find_node first or dag_get_node */
+DagNode * dag_add_node (DagForest *forest,void * fob)
+{
+	DagNode *node;
+		
+	node = MEM_mallocN(sizeof(DagNode),"DAG node");
+	if (node) {
+		node->ob = fob;
+		node->color = DAG_WHITE;
+		node->BFS_dist = 0;		
+		node->DFS_dist = 0;		
+		node->DFS_dvtm = 0;		
+		node->DFS_fntm = 0;
+		node->child = NULL;
+		node->next = NULL;
+		node->first_ancestor = NULL;
+		node->ancestor_count = 0;
+
+		node->type = GS(((ID *) fob)->name);
+		if (forest->numNodes) {
+			((DagNode *) forest->DagNode.last)->next = node;
+			forest->DagNode.last = node;
+			forest->numNodes++;
+		} else {
+			forest->DagNode.last = node;
+			forest->DagNode.first = node;
+			forest->numNodes = 1;
+		}
+	}
+	return node;
+}
+
+DagNode * dag_get_node (DagForest *forest,void * fob)
+{
+	DagNode *node;
+	
+	node = dag_find_node (forest, fob);	
+	if (!node) 
+		node = dag_add_node(forest, fob);
+	return node;
+}
+
+
+
+DagNode * dag_get_sub_node (DagForest *forest,void * fob)
+{
+	DagNode *node;
+	DagAdjList *mainchild, *prev=NULL;
+	
+	mainchild = ((DagNode *) forest->DagNode.first)->child;
+	/* remove from first node (scene) adj list if present */
+	while (mainchild) {
+		if (mainchild->node == fob) {
+			if (prev) {
+				prev->next = mainchild->next;
+				MEM_freeN(mainchild);
+				break;
+			} else {
+				((DagNode *) forest->DagNode.first)->child = mainchild->next;
+				MEM_freeN(mainchild);
+				break;
+			}
+		}
+		prev = mainchild;
+		mainchild = mainchild->next;
+	}
+	node = dag_find_node (forest, fob);	
+	if (!node) 
+		node = dag_add_node(forest, fob);
+	return node;
+}
+
+void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, dag_rel_type rel) 
+{
+	DagAdjList *itA = fob1->child;
+	
+	while (itA) { /* search if relation exist already */
+		if (itA->node == fob2) {
+			if (itA->type == rel) { 
+				itA->count += 1;
+				return;
+			}
+		}
+		itA = itA->next;
+	}
+	/* create new relation and insert at head */
+	itA = MEM_mallocN(sizeof(DagAdjList),"DAG adj list");
+	itA->node = fob2;
+	itA->type = rel;
+	itA->count = 1;
+	itA->next = fob1->child;
+	fob1->child = itA;
+}
+
+
+/*
+ * MainDAG is the DAG of all objects in current scene
+ * used only for drawing there is one also in each scene
+ */
+static DagForest * MainDag = NULL;
+
+DagForest *getMainDag(void)
+{
+	return MainDag;
+}
+
+
+void setMainDag(DagForest *dag)
+{
+	MainDag = dag;
+}
+
+
+/*
+ * note for BFS/DFS
+ * in theory we should sweep the whole array
+ * but in our case the first node is the scene
+ * and is linked to every other object
+ *
+ * for general case we will need to add outer loop
+ */
+
+/*
+ * ToDo : change pos kludge
+ */
+
+/* adjust levels for drawing in oops space */
+void graph_bfs(void)
+{
+	DagNode *node;
+	DagNodeQueue *nqueue;
+	int pos[50];
+	int i;
+	DagAdjList *itA;
+	int minheight;
+	
+	/* fprintf(stderr,"starting BFS \n ------------\n"); */	
+	nqueue = queue_create(DAGQUEUEALLOC);
+	for ( i=0; i<50; i++)
+		pos[i] = 0;
+	
+	/* Init
+	 * dagnode.first is alway the root (scene) 
+	 */
+	node = MainDag->DagNode.first;
+	while(node) {
+		node->color = DAG_WHITE;
+		node->BFS_dist = 9999;
+		node->k = 0;
+		node = node->next;
+	}
+	
+	node = MainDag->DagNode.first;
+	if (node->color == DAG_WHITE) {
+		node->color = DAG_GRAY;
+		node->BFS_dist = 1;
+		push_queue(nqueue,node);  
+		while(nqueue->count) {
+			node = pop_queue(nqueue);
+			
+			minheight = pos[node->BFS_dist];
+			itA = node->child;
+			while(itA != NULL) {
+				if((itA->node->color == DAG_WHITE) ) {
+					itA->node->color = DAG_GRAY;
+					itA->node->BFS_dist = node->BFS_dist + 1;
+					itA->node->k = minheight;
+					push_queue(nqueue,itA->node);
+				}
+				
+				 else {
+					fprintf(stderr,"bfs not dag tree edge color :%i \n",itA->node->color);
+				}
+				 
+				
+				itA = itA->next;
+			}
+			if (pos[node->BFS_dist] > node->k ) {
+				pos[node->BFS_dist] += 1;				
+				node->k = pos[node->BFS_dist];
+			} else {
+				pos[node->BFS_dist] = node->k +1;
+			}
+			set_node_xy(node, DEPSX*2*node->BFS_dist, pos[node->BFS_dist]*DEPSY*2);
+			node->color = DAG_BLACK;
+			/*
+			 fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);	
+			 */
+		}
+	}
+	queue_delete(nqueue);
+}
+
+int pre_and_post_BFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
+	DagNode *node;
+	
+	node = dag->DagNode.first;
+	return pre_and_post_source_BFS(dag, mask,  node,  pre_func,  post_func, data);
+}
+
+
+int pre_and_post_source_BFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
+{
+	DagNode *node;
+	DagNodeQueue *nqueue;
+	DagAdjList *itA;
+	int	retval = 0;
+	/* fprintf(stderr,"starting BFS \n ------------\n"); */	
+	
+	/* Init
+		* dagnode.first is alway the root (scene) 
+		*/
+	node = dag->DagNode.first;
+	nqueue = queue_create(DAGQUEUEALLOC);
+	while(node) {
+		node->color = DAG_WHITE;
+		node->BFS_dist = 9999;
+		node = node->next;
+	}
+	
+	node = source;
+	if (node->color == DAG_WHITE) {
+		node->color = DAG_GRAY;
+		node->BFS_dist = 1;
+		pre_func(node->ob,data);
+		
+		while(nqueue->count) {
+			node = pop_queue(nqueue);
+			
+			itA = node->child;
+			while(itA != NULL) {
+				if((itA->node->color == DAG_WHITE) && (itA->type & mask)) {
+					itA->node->color = DAG_GRAY;
+					itA->node->BFS_dist = node->BFS_dist + 1;
+					push_queue(nqueue,itA->node);
+					pre_func(node->ob,data);
+				}
+				
+				else { // back or cross edge
+					retval = 1;
+				}
+				itA = itA->next;
+			}
+			post_func(node->ob,data);
+			node->color = DAG_BLACK;
+			/*
+			 fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);	
+			 */
+		}
+	}
+	queue_delete(nqueue);
+	return retval;
+}
+
+/* non recursive version of DFS, return queue -- outer loop present to catch odd cases (first level cycles)*/
+DagNodeQueue * graph_dfs(void)
+{
+	DagNode *node;
+	DagNodeQueue *nqueue;
+	DagNodeQueue *retqueue;
+	int pos[50];
+	int i;
+	DagAdjList *itA;
+	int time;
+	int skip = 0;
+	int minheight;
+	int maxpos=0;
+	int	is_cycle = 0;
+	/*
+	 *fprintf(stderr,"starting DFS \n ------------\n");
+	 */	
+	nqueue = queue_create(DAGQUEUEALLOC);
+	retqueue = queue_create(MainDag->numNodes);
+	for ( i=0; i<50; i++)
+		pos[i] = 0;
+	
+	/* Init
+	 * dagnode.first is alway the root (scene) 
+	 */
+	node = MainDag->DagNode.first;
+	while(node) {
+		node->color = DAG_WHITE;
+		node->DFS_dist = 9999;
+		node->DFS_dvtm = node->DFS_fntm = 9999;
+		node->k = 0;
+		node =  node->next;
+	}
+	
+	time = 1;
+	
+	node = MainDag->DagNode.first;
+
+	do {
+	if (node->color == DAG_WHITE) {
+		node->color = DAG_GRAY;
+		node->DFS_dist = 1;
+		node->DFS_dvtm = time;
+		time++;
+		push_stack(nqueue,node);  
+			
+		while(nqueue->count) {
+			//graph_print_queue(nqueue);
+
+			 skip = 0;
+			node = get_top_node_queue(nqueue);
+			
+			minheight = pos[node->DFS_dist];
+
+			itA = node->child;
+			while(itA != NULL) {
+				if((itA->node->color == DAG_WHITE) ) {
+					itA->node->DFS_dvtm = time;
+					itA->node->color = DAG_GRAY;
+
+					time++;
+					itA->node->DFS_dist = node->DFS_dist + 1;
+					itA->node->k = minheight;
+					push_stack(nqueue,itA->node);
+					skip = 1;
+					break;
+				} else { 
+					if (itA->node->color == DAG_GRAY) { // back edge
+						fprintf(stderr,"dfs back edge :%15s %15s \n",((ID *) node->ob)->name, ((ID *) itA->node->ob)->name);
+						is_cycle = 1;
+					} else if (itA->node->color == DAG_BLACK) {
+						;
+						/* already processed node but we may want later to change distance either to shorter to longer.
+						 * DFS_dist is the first encounter  
+						*/
+						/*if (node->DFS_dist >= itA->node->DFS_dist)
+							itA->node->DFS_dist = node->DFS_dist + 1;
+						 	
+							fprintf(stderr,"dfs forward or cross edge :%15s %i-%i %15s %i-%i \n",
+								((ID *) node->ob)->name,
+								node->DFS_dvtm, 
+								node->DFS_fntm, 
+								((ID *) itA->node->ob)->name, 
+								itA->node->DFS_dvtm,
+								itA->node->DFS_fntm);
+					*/
+					} else 
+						fprintf(stderr,"dfs unknown edge \n");
+				}
+				itA = itA->next;
+			}			
+
+			if (!skip) {
+				node = pop_queue(nqueue);
+				node->color = DAG_BLACK;
+
+				node->DFS_fntm = time;
+				time++;
+				if (node->DFS_dist > maxpos)
+					maxpos = node->DFS_dist;
+				if (pos[node->DFS_dist] > node->k ) {
+					pos[node->DFS_dist] += 1;				
+					node->k = pos[node->DFS_dist];
+				} else {
+					pos[node->DFS_dist] = node->k +1;
+				}
+				set_node_xy(node, DEPSX*2*node->DFS_dist, pos[node->DFS_dist]*DEPSY*2);
+				
+				/*
+				 fprintf(stderr,"DFS node : %20s %i %i %i %i\n",((ID *) node->ob)->name,node->BFS_dist, node->DFS_dist, node->DFS_dvtm, node->DFS_fntm ); 	
+				*/
+				 push_stack(retqueue,node);
+				
+			}
+		}
+	}
+		node = node->next;
+	} while (node);
+//	  fprintf(stderr,"i size : %i \n", maxpos);
+	  
+	queue_delete(nqueue);
+	  return(retqueue);
+}
+
+int pre_and_post_DFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
+	DagNode *node;
+
+	node = dag->DagNode.first;
+	return pre_and_post_source_DFS(dag, mask,  node,  pre_func,  post_func, data);
+}
+
+int pre_and_post_source_DFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
+{
+	DagNode *node;
+	DagNodeQueue *nqueue;
+	DagAdjList *itA;
+	int time;
+	int skip = 0;
+	int retval = 0;
+	/*
+	 *fprintf(stderr,"starting DFS \n ------------\n");
+	 */	
+	nqueue = queue_create(DAGQUEUEALLOC);
+	
+	/* Init
+		* dagnode.first is alway the root (scene) 
+		*/
+	node = dag->DagNode.first;
+	while(node) {
+		node->color = DAG_WHITE;
+		node->DFS_dist = 9999;
+		node->DFS_dvtm = node->DFS_fntm = 9999;
+		node->k = 0;
+		node =  node->next;
+	}
+	
+	time = 1;
+	
+	node = source;
+	do {
+		if (node->color == DAG_WHITE) {
+			node->color = DAG_GRAY;
+			node->DFS_dist = 1;
+			node->DFS_dvtm = time;
+			time++;
+			push_stack(nqueue,node);  
+			pre_func(node->ob,data);
+
+			while(nqueue->count) {
+				skip = 0;
+				node = get_top_node_queue(nqueue);
+								
+				itA = node->child;
+				while(itA != NULL) {
+					if((itA->node->color == DAG_WHITE) && (itA->type & mask) ) {
+						itA->node->DFS_dvtm = time;
+						itA->node->color = DAG_GRAY;
+						
+						time++;
+						itA->node->DFS_dist = node->DFS_dist + 1;
+						push_stack(nqueue,itA->node);
+						pre_func(node->ob,data);
+
+						skip = 1;
+						break;
+					} else {
+						if (itA->node->color == DAG_GRAY) {// back edge
+							retval = 1;
+						}
+//						else if (itA->node->color == DAG_BLACK) { // cross or forward
+//							;
+					}
+					itA = itA->next;
+				}			
+				
+				if (!skip) {
+					node = pop_queue(nqueue);
+					node->color = DAG_BLACK;
+					
+					node->DFS_fntm = time;
+					time++;
+					post_func(node->ob,data);
+				}
+			}
+		}
+		node = node->next;
+	} while (node);
+	queue_delete(nqueue);
+	return(retval);
+}
+
+// sort the base list on place
+void topo_sort_baselist(struct Scene *sce){
+	DagNode *node;
+	DagNodeQueue *nqueue;
+	DagAdjList *itA;
+	int time;
+	int skip = 0;
+	ListBase tempbase;
+	Base *base;
+	
+	tempbase.first= tempbase.last= 0;
+	
+	build_dag(sce,DAG_RL_ALL_BUT_DATA_MASK);
+	
+	nqueue = queue_create(DAGQUEUEALLOC);
+	
+	node = sce->theDag->DagNode.first;
+	while(node) {
+		node->color = DAG_WHITE;
+		node =  node->next;
+	}
+	
+	time = 1;
+	
+	node = sce->theDag->DagNode.first;
+	
+	node->color = DAG_GRAY;
+	time++;
+	push_stack(nqueue,node);  
+	
+	while(nqueue->count) {
+		
+		skip = 0;
+		node = get_top_node_queue(nqueue);
+		
+		itA = node->child;
+		while(itA != NULL) {
+			if((itA->node->color == DAG_WHITE) ) {
+				itA->node->DFS_dvtm = time;
+				itA->node->color = DAG_GRAY;
+				
+				time++;
+				push_stack(nqueue,itA->node);
+				skip = 1;
+				break;
+			} 
+			itA = itA->next;
+		}			
+		
+		if (!skip) {
+			if (node) {
+				node = pop_queue(nqueue);
+				if (node->ob == sce)	// we are done
+					break ;
+				node->color = DAG_BLACK;
+				
+				time++;
+				base = sce->base.first;
+				while (base->object != node->ob)
+					base = base->next;
+				BLI_remlink(&sce->base,base);
+				BLI_addhead(&tempbase,base);
+			}	
+		}
+	}
+	
+	sce->base = tempbase;
+	queue_delete(nqueue);
+}
+
+
+// used to get the obs owning a datablock
+struct DagNodeQueue *get_obparents(struct DagForest	*dag, void *ob) 
+{
+	DagNode * node, *node1;
+	DagNodeQueue *nqueue;
+	DagAdjList *itA;
+
+	node = dag_find_node(dag,ob);
+	if (node->ancestor_count == 1) { // simple case
+		nqueue = queue_create(1);
+		push_queue(nqueue,node);
+	} else {	// need to go over the whole dag for adj list
+		nqueue = queue_create(node->ancestor_count);
+		
+		node1 = dag->DagNode.first;
+		do {
+			if (node1->DFS_fntm > node->DFS_fntm) { // a parent is finished after child. must check adj list
+				itA = node->child;
+				while(itA != NULL) {
+					if ((itA->node == node) && (itA->type == DAG_RL_DATA)) {
+						push_queue(nqueue,node);
+					}
+					itA = itA->next;
+				}
+			}
+			node1 = node1->next;
+		} while (node1);
+	}
+	return nqueue;
+}
+
+struct DagNodeQueue *get_first_ancestors(struct DagForest	*dag, void *ob)
+{
+	DagNode * node, *node1;
+	DagNodeQueue *nqueue;
+	DagAdjList *itA;
+	
+	node = dag_find_node(dag,ob);
+	
+	// need to go over the whole dag for adj list
+	nqueue = queue_create(node->ancestor_count);
+	
+	node1 = dag->DagNode.first;
+	do {
+		if (node1->DFS_fntm > node->DFS_fntm) { 
+			itA = node->child;
+			while(itA != NULL) {
+				if (itA->node == node) {
+					push_queue(nqueue,node);
+				}
+				itA = itA->next;
+			}
+		}
+		node1 = node1->next;
+	} while (node1);
+	
+	return nqueue;	
+}
+
+// standard DFS list
+struct DagNodeQueue *get_all_childs(struct DagForest	*dag, void *ob)
+{
+	DagNode *node;
+	DagNodeQueue *nqueue;
+	DagNodeQueue *retqueue;
+	DagAdjList *itA;
+	int time;
+	int skip = 0;
+
+	nqueue = queue_create(DAGQUEUEALLOC);
+	retqueue = queue_create(MainDag->numNodes);
+	
+	node = dag->DagNode.first;
+	while(node) {
+		node->color = DAG_WHITE;
+		node =  node->next;
+	}
+	
+	time = 1;
+	
+	node = dag_find_node(dag,ob);
+	
+	node->color = DAG_GRAY;
+	time++;
+	push_stack(nqueue,node);  
+	
+	while(nqueue->count) {
+		
+		skip = 0;
+		node = get_top_node_queue(nqueue);
+				
+		itA = node->child;
+		while(itA != NULL) {
+			if((itA->node->color == DAG_WHITE) ) {
+				itA->node->DFS_dvtm = time;
+				itA->node->color = DAG_GRAY;
+				
+				time++;
+				push_stack(nqueue,itA->node);
+				skip = 1;
+				break;
+			} 
+			itA = itA->next;
+		}			
+		
+		if (!skip) {
+			node = pop_queue(nqueue);
+			node->color = DAG_BLACK;
+			
+			time++;
+			push_stack(retqueue,node);			
+		}
+	}
+		
+	queue_delete(nqueue);
+	return(retqueue);
+}
+
+dag_rel_type	are_obs_related(struct DagForest	*dag, void *ob1, void *ob2) {
+	DagNode * node;
+	DagAdjList *itA;
+	
+	node = dag_find_node(dag,ob1);
+	
+	itA = node->child;
+	while(itA != NULL) {
+		if((itA->node->ob == ob2) ) {
+			return itA->node->type;
+		} 
+		itA = itA->next;
+	}
+	return DAG_NO_RELATION;
+}
+
+int	is_acyclic( DagForest	*dag) {
+	return dag->is_acyclic;
+}
+
+void set_node_xy(DagNode *node, float x, float y)
+{
+ 	node->x = x;
+	node->y = y;
+}
+
+
+/* debug test functions */
+
+void graph_print_queue(DagNodeQueue *nqueue)
+{	
+	DagNodeQueueElem *queueElem;
+	
+	queueElem = nqueue->first;
+	while(queueElem) {
+		fprintf(stderr,"** %s %i %i-%i ",((ID *) queueElem->node->ob)->name,queueElem->node->color,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
+		queueElem = queueElem->next;		
+	}
+	fprintf(stderr,"\n");
+}
+
+void graph_print_queue_dist(DagNodeQueue *nqueue)
+{	
+	DagNodeQueueElem *queueElem;
+	int max, count;
+	
+	queueElem = nqueue->first;
+	max = queueElem->node->DFS_fntm;
+	count = 0;
+	while(queueElem) {
+		fprintf(stderr,"** %25s %2.2i-%2.2i ",((ID *) queueElem->node->ob)->name,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
+		while (count < queueElem->node->DFS_dvtm-1) { fputc(' ',stderr); count++;}
+		fputc('|',stderr); 
+		while (count < queueElem->node->DFS_fntm-2) { fputc('-',stderr); count++;}
+		fputc('|',stderr);
+		fputc('\n',stderr);
+		count = 0;
+		queueElem = queueElem->next;		
+	}
+	fprintf(stderr,"\n");
+}
+
+void graph_print_adj_list(void)
+{
+	DagNode *node;
+	DagAdjList *itA;
+	
+	node = (getMainDag())->DagNode.first;
+	while(node) {
+		fprintf(stderr,"node : %s col: %i",((ID *) node->ob)->name, node->color);		
+		itA = node->child;
+		while (itA) {
+			fprintf(stderr,"-- %s ",((ID *) itA->node->ob)->name);
+			
+			itA = itA->next;
+		}
+		fprintf(stderr,"\n");
+		node = node->next;
+	}
+}
+
+
diff --git a/source/blender/blenkernel/intern/scene.c b/source/blender/blenkernel/intern/scene.c
index aebfa54fe1e..1d7bb7e5f47 100644
--- a/source/blender/blenkernel/intern/scene.c
+++ b/source/blender/blenkernel/intern/scene.c
@@ -85,6 +85,11 @@
 
 #include "BPY_extern.h"
 
+#include "BKE_depsgraph.h"
+
+#include <sys/time.h>
+
+
 void free_avicodecdata(AviCodecData *acd)
 {
 	if (acd) {
@@ -140,6 +145,10 @@ void free_scene(Scene *sce)
 		MEM_freeN(sce->r.qtcodecdata);
 		sce->r.qtcodecdata = NULL;
 	}
+	if (sce->theDag) {
+		free_forest(sce->theDag);
+		MEM_freeN(sce->theDag);
+	}
 }
 
 Scene *add_scene(char *name)
@@ -209,13 +218,18 @@ int object_in_scene(Object *ob, Scene *sce)
 
 void sort_baselist(Scene *sce)
 {
+	 	topo_sort_baselist(sce);
+}
+
+#if 0
+void old_sort_baselist(Scene *sce)
+{
 	/* in order of parent and track */
 	ListBase tempbase, noparentbase, notyetbase;
 	Base *base, *test=NULL;
 	Object *par;
 	int doit, domore= 0, lastdomore=1;
 	
-	
 	/* keep same order when nothing has changed! */
 	
 	while(domore!=lastdomore) {
@@ -287,8 +301,9 @@ void sort_baselist(Scene *sce)
 		addlisttolist(&sce->base, &notyetbase);
 
 	}
-}
 
+}
+#endif
 
 void set_scene_bg(Scene *sce)
 {
diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index ff3953296df..a3d9e0e1202 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -2694,7 +2694,6 @@ static void lib_link_screen(FileData *fd, Main *main)
 								tselem->id= newlibadr(fd, NULL, tselem->id);
 							}
 						}
-						
 					}
 					else if(sl->spacetype==SPACE_SOUND) {
 						SpaceSound *ssound= (SpaceSound *)sl;
@@ -4640,7 +4639,11 @@ static void do_versions(Main *main)
 		bScreen *sc;
 		
 		while(sce) {
+			sce->theDag = NULL;
+			sce->dagisvalid = 0;
+
 			if(sce->r.postsat==0.0) sce->r.postsat= 1.0;
+
 			if(sce->r.zgamma==0.0) {
 				sce->r.focus= 0.9;
 				sce->r.zgamma= 1.0;
@@ -4648,6 +4651,7 @@ static void do_versions(Main *main)
 				sce->r.zblur= 10.0;
 				sce->r.zmin= 0.8;
 			}
+
 			sce= sce->id.next;
 		}
 		while(cam) {
@@ -4658,6 +4662,7 @@ static void do_versions(Main *main)
 			cam= cam->id.next;
 		}
 		/* set manipulator type */
+		/* force oops draw if depgraph was set*/
 		for (sc= main->screen.first; sc; sc= sc->id.next) {
 			ScrArea *sa;
 			for (sa= sc->areabase.first; sa; sa= sa->next) {
@@ -4667,6 +4672,12 @@ static void do_versions(Main *main)
 						View3D *v3d= (View3D *)sl;
 						if(v3d->twtype==0) v3d->twtype= V3D_MANIP_TRANSLATE;
 					}
+#ifndef SHOWDEPGRAPH
+					if(sl->spacetype==SPACE_OOPS) {
+						if ( ((SpaceOops *)sl)->type==SO_DEPSGRAPH)
+							 ((SpaceOops *)sl)->type=SO_OOPS;
+					}
+#endif						
 				}
 			}
 		}
diff --git a/source/blender/makesdna/DNA_scene_types.h b/source/blender/makesdna/DNA_scene_types.h
index d285a46c3ae..2297c1b50aa 100644
--- a/source/blender/makesdna/DNA_scene_types.h
+++ b/source/blender/makesdna/DNA_scene_types.h
@@ -273,6 +273,11 @@ typedef struct Scene {
 	struct AudioData audio;	
 	
 	ScriptLink scriptlink;
+	
+	/* none of the dependancy graph  vars is mean to be saved */
+	struct  DagForest *theDag;
+	short dagisvalid, dagflags;
+	int pad1;
 } Scene;
 
 
diff --git a/source/blender/makesdna/DNA_space_types.h b/source/blender/makesdna/DNA_space_types.h
index 13047c6a793..ee45cf67074 100644
--- a/source/blender/makesdna/DNA_space_types.h
+++ b/source/blender/makesdna/DNA_space_types.h
@@ -199,7 +199,7 @@ typedef struct SpaceOops {
 	ListBase tree;
 	struct TreeStore *treestore;
 	short type, outlinevis, storeflag;
-	short pad1;
+	short deps_flags;
 	
 } SpaceOops;
 
@@ -451,6 +451,7 @@ typedef struct SpaceImaSel {
 /* SpaceOops->type */
 #define SO_OOPS			0
 #define SO_OUTLINER		1
+#define SO_DEPSGRAPH    2
 
 /* SpaceOops->flag */
 #define SO_TESTBLOCKS	1
diff --git a/source/blender/src/SConscript b/source/blender/src/SConscript
index 166c2a9b133..28889f674fb 100644
--- a/source/blender/src/SConscript
+++ b/source/blender/src/SConscript
@@ -23,6 +23,7 @@ source_files = ['B.blend.c',
                 'cmovie.tga.c',
                 'cursors.c',
                 'drawaction.c',
+                'drawdeps.c',
                 'drawimage.c',
                 'drawimasel.c',
                 'drawipo.c',
diff --git a/source/blender/src/drawdeps.c b/source/blender/src/drawdeps.c
new file mode 100644
index 00000000000..56445b71099
--- /dev/null
+++ b/source/blender/src/drawdeps.c
@@ -0,0 +1,413 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2004 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+
+#ifdef _WIN32
+#include "BLI_winstuff.h"
+#endif
+
+#include "BMF_Api.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_arithb.h"
+
+#include "DNA_ID.h"
+#include "DNA_object_types.h"
+#include "DNA_oops_types.h"
+#include "DNA_scene_types.h"
+#include "DNA_screen_types.h"
+#include "DNA_space_types.h"
+#include "DNA_view2d_types.h"
+#include "DNA_action_types.h"
+
+#include "BKE_utildefines.h"
+#include "BKE_global.h"
+
+#include "BIF_interface.h"
+#include "BIF_gl.h"
+#include "BIF_glutil.h"
+#include "BIF_mywindow.h"
+#include "BIF_resources.h"
+#include "BIF_screen.h"
+
+#include "BIF_oops.h"
+
+#include "BSE_drawipo.h"
+#include "BSE_drawoops.h"
+#include "MEM_guardedalloc.h"
+#include "blendef.h"
+
+
+#include "depsgraph_private.h"
+
+#include <sys/time.h>
+
+
+
+void boundbox_deps()
+{
+	DagNode *node;
+	float min[2], max[2];
+	
+	if(G.soops==0) return;
+	
+	min[0]= 1000.0;
+	max[0]= -10000.0;
+	min[1]= 1000.0;
+	max[1]= -1000.0;
+	
+	node = getMainDag()->DagNode.first;
+	while(node) {
+		min[0]= MIN2(min[0], node->x);
+		max[0]= MAX2(max[0], node->x+OOPSX);
+		min[1]= MIN2(min[1], node->y);
+		max[1]= MAX2(max[1], node->y+OOPSY);
+		
+		node= node->next;
+	}
+		
+	G.v2d->tot.xmin= min[0];
+	G.v2d->tot.xmax= max[0];
+	G.v2d->tot.ymin= min[1];
+	G.v2d->tot.ymax= max[1];
+}
+
+static unsigned int get_line_color(DagAdjList *child)
+{
+	switch  (child->type) {
+		case DAG_RL_SCENE :
+			return 0x00000;
+		case DAG_RL_DATA :
+			return 0xFF0000;
+		case DAG_RL_PARENT :
+			return 0x00FF00;
+		case DAG_RL_TRACK :
+			return 0xFFFF00;
+		case DAG_RL_PATH :
+			return 0x000000;
+		case DAG_RL_CONSTRAINT :
+			return 0x0000FF;
+		case DAG_RL_HOOK :
+			return 0x00FFFF;
+		case DAG_RL_DATA_CONSTRAINT :
+			return 0x0000FF;
+		default :
+			return 0x0000FF;
+	}
+	//return 0x00000;
+}
+
+
+static void draw_deps(DagNode *node)
+{
+	float v1[2], x1, y1, x2, y2;
+	unsigned int body, border;
+	short line= 0;
+	char str[32];
+	DagAdjList *itA = node->child;
+
+	x1= node->x; 
+	x2= node->x+DEPSX;
+	y1= node->y; 
+	y2= node->y+DEPSY;
+
+	if(x2 < G.v2d->cur.xmin || x1 > G.v2d->cur.xmax) return;
+	if(y2 < G.v2d->cur.ymin || y1 > G.v2d->cur.ymax) return;
+
+	body =  give_oops_color(node->type, 0, &border);
+
+	line= 0;
+//	border= 00;
+	cpack(body);
+
+	glRectf(x1,  y1,  x2,  y2);
+	
+	v1[0]= x1; 
+	v1[1]= (y1+y2)/2 -0.3;
+	sprintf(str, "     %s", ((ID *) node->ob)->name+2);
+	
+	calc_oopstext(str, v1);
+	
+		/* ICON */
+//	if(str[1] && oopscalex>1.1) {
+	draw_icon_oops(v1, node->type);
+//	}
+
+	
+	cpack(0x0);
+	glRasterPos3f(v1[0],  v1[1], 0.0);
+	BMF_DrawString(G.fonts, str);
+
+	
+	if(line) setlinestyle(2);
+	cpack(border);
+
+	glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
+	glRectf(x1,  y1,  x2,  y2);
+	glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
+	if(line) setlinestyle(0);
+
+	while (itA) { /* draw connection lines */
+		cpack(get_line_color(itA));
+		glBegin(GL_LINE_STRIP);
+			glVertex2f(node->x+DEPSX, node->y+ 0.5*DEPSY);
+			glVertex2f(itA->node->x, itA->node->y+ 0.5*DEPSY);			
+		glEnd();
+		itA = itA->next;
+	}
+			/* Draw the little rounded connection point */
+		glColor3ub(0, 0, 0);
+		glPushMatrix();
+
+		glTranslatef(node->x , node->y+ 0.5*DEPSY, 0.0);
+		glutil_draw_filled_arc(-M_PI/2, M_PI, 0.07*DEPSX, 7);
+
+		glPopMatrix();
+
+}
+
+void	draw_all_deps(void)
+{
+	DagNode *node;
+	DagForest *dag;
+	
+	dag = getMainDag();
+	 node = dag->DagNode.first;
+	//node = node->next;
+	while(node) {
+		draw_deps(node);
+		node = node->next;
+	}
+	free_forest(dag);
+	MEM_freeN(dag);
+	setMainDag(NULL);
+}
+
+
+
+
+int build_deps(short mask)
+{
+	Base *base;
+	Object *ob = NULL;
+	DagNode * node = NULL; 
+	DagNode * node2 = NULL ;
+	DagNode * node3 = NULL;
+DagNode * scenenode;
+	DagForest *dag;
+
+#ifdef DEPS_DEBUG
+	//timers
+	struct timeval tp1, tp2, tp3, tp4;
+	
+	gettimeofday(&tp1,NULL);
+#endif
+	
+	DagNodeQueue *retqueue;
+	
+//	float y = 0;
+//	int maxlev = 0;
+
+	if(G.soops==0) return -1;
+	
+	
+	// rebuilt each time for now
+	dag = getMainDag();
+	if ( dag)
+		free_forest( dag ); 
+	else {
+		dag = dag_init();
+		setMainDag(dag);
+		}
+		
+	// add base node for scene. scene is always the first node in DAG
+	scenenode = dag_add_node(dag, G.scene);
+	set_node_xy(scenenode,0.0, 0.0); 	
+		/* blocks from this scene */
+		
+		
+		/* targets in object struct yet to be added. should even they ?
+				struct Ipo *ipo;
+			ListBase nlastrips;
+			ListBase hooks;
+		*/
+		
+		
+	base= FIRSTBASE;
+	while(base) { // add all objects in any case
+		int addtoroot = 1;
+		
+//				 graph_print_adj_list();
+ob= (Object *) base->object;
+
+		node = dag_get_node(dag,ob);
+	
+		if ((ob->data) && (mask&DAG_RL_DATA_MASK)) {
+			node2 = dag_get_node(dag,ob->data);
+			dag_add_relation(dag,node,node2,DAG_RL_DATA);
+			node2->first_ancestor = ob;
+			node2->ancestor_count += 1;
+			
+			if ((ob->type == OB_ARMATURE) && (mask&DAG_RL_DATA_CONSTRAINT_MASK)) { // add armature constraints to datas
+				if (ob->pose){
+					bPoseChannel *pchan;
+					bConstraint *con;
+					Object * target;
+					
+					for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){
+						for (con = pchan->constraints.first; con; con=con->next){
+							if (constraint_has_target(con)) {
+								target = get_constraint_target(con);
+								if (strcmp(target->id.name, ob->id.name) != 0) {
+									//fprintf(stderr,"armature target :%s \n", target->id.name);
+									node3 = dag_get_node(dag,target);
+									dag_add_relation(dag,node3,node2,DAG_RL_CONSTRAINT);
+								}
+							}
+						}
+					}
+				}
+			}
+			
+			if (ob->hooks.first) {
+				ObHook *hook;
+				
+				for(hook= ob->hooks.first; hook; hook= hook->next) {
+					if(hook->parent) {
+						node3 = dag_get_node(dag,hook->parent);
+						dag_add_relation(dag,node3,node2,DAG_RL_HOOK);
+					}
+				}
+			}
+		} else { // add armature constraints to object itself
+			if ((ob->type == OB_ARMATURE) && (mask&DAG_RL_DATA_CONSTRAINT_MASK)) {
+				if (ob->pose){
+					bPoseChannel *pchan;
+					bConstraint *con;
+					Object * target;
+					
+					for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){
+						for (con = pchan->constraints.first; con; con=con->next){
+							if (constraint_has_target(con)) {
+								target = get_constraint_target(con);
+								if (strcmp(target->id.name, ob->id.name) != 0) {
+									//fprintf(stderr,"armature target :%s \n", target->id.name);
+									node3 = dag_get_node(dag,target);
+									dag_add_relation(dag,node3,node,DAG_RL_CONSTRAINT);
+								}
+							}
+						}
+					}
+				}
+			}
+			if (ob->hooks.first) {
+				ObHook *hook;
+				
+				for(hook= ob->hooks.first; hook; hook= hook->next) {
+					if(hook->parent) {
+						node3 = dag_get_node(dag,hook->parent);
+						dag_add_relation(dag,node3,node,DAG_RL_HOOK);
+					}
+				}
+			}			
+		}
+
+		if ((ob->parent) && (mask&DAG_RL_PARENT_MASK)){
+			node2 = dag_get_node(dag,ob->parent);
+			dag_add_relation(dag,node2,node,DAG_RL_PARENT);
+			addtoroot = 0;
+		}
+		if ((ob->track) && (mask&DAG_RL_TRACK_MASK)){
+			node2 = dag_get_node(dag,ob->track);
+			dag_add_relation(dag,node2,node,DAG_RL_TRACK);
+			addtoroot = 0;
+
+		}
+		if ((ob->path) && (mask&DAG_RL_PATH_MASK)){
+			node2 = dag_get_node(dag,ob->track);
+			dag_add_relation(dag,node2,node,DAG_RL_PATH);
+			addtoroot = 0;
+
+		}
+
+		/* Count constraints */
+		if (mask & DAG_RL_CONSTRAINT_MASK) {
+			bConstraint *con;
+			for (con = ob->constraints.first; con; con=con->next){
+				if (constraint_has_target(con)) {
+					node2 = dag_get_node(dag,get_constraint_target(con));
+					dag_add_relation(dag,node2,node,DAG_RL_CONSTRAINT);
+					addtoroot = 0;
+					
+				}
+			}
+		}	
+		
+		
+		if (addtoroot == 1 )
+			dag_add_relation(dag,scenenode,node,DAG_RL_SCENE);
+
+		addtoroot = 1;
+		base= base->next;
+	}
+
+//graph_print_adj_list();
+//fprintf(stderr,"building deps\n");
+#ifdef DEPS_DEBUG
+	gettimeofday(&tp2,NULL);
+#endif
+
+//graph_bfs(); //set levels
+
+#ifdef DEPS_DEBUG
+gettimeofday(&tp3,NULL);
+#endif
+
+
+retqueue = graph_dfs(); //set levels
+#ifdef DEPS_DEBUG
+gettimeofday(&tp4,NULL);
+fprintf(stderr,"************************************\n");
+graph_print_queue_dist(retqueue);
+//graph_print_queue(retqueue);
+
+fprintf(stderr,"TIME BUILD %d %d BFS %d %d DFS  %d %d\n",tp2.tv_sec-tp1.tv_sec ,tp2.tv_usec-tp1.tv_usec
+														, tp3.tv_sec-tp2.tv_sec ,tp3.tv_usec-tp2.tv_usec
+														, tp4.tv_sec-tp3.tv_sec ,tp4.tv_usec-tp3.tv_usec);
+#endif
+
+queue_delete(retqueue);
+
+//graph_print_adj_list();
+return 0;
+}
diff --git a/source/blender/src/drawoops.c b/source/blender/src/drawoops.c
index ea90a4c35f1..8d18466dff9 100644
--- a/source/blender/src/drawoops.c
+++ b/source/blender/src/drawoops.c
@@ -68,6 +68,12 @@
 #include "BSE_drawipo.h"
 #include "BSE_drawoops.h"
 
+#include "BKE_depsgraph.h"
+
+extern void build_deps(short mask);
+//extern void draw_deps(DagNode *node);
+
+
 float oopscalex;
 
 void boundbox_oops()
@@ -399,7 +405,17 @@ void drawoopsspace(ScrArea *sa, void *spacedata)
 	if(soops==0) return;	
 	
 	if(soops->type==SO_OUTLINER) draw_outliner(sa, soops);
-	else {
+	else if (soops->type==SO_DEPSGRAPH) {
+		build_deps(soops->deps_flags);
+		boundbox_deps();
+		calc_scrollrcts(sa,G.v2d, curarea->winx, curarea->winy);
+
+		myortho2(G.v2d->cur.xmin, G.v2d->cur.xmax, G.v2d->cur.ymin, G.v2d->cur.ymax);
+
+		oopscalex= .14*((float)curarea->winx)/(G.v2d->cur.xmax-G.v2d->cur.xmin);
+		calc_ipogrid();	/* for scrollvariables */
+		draw_all_deps();
+	} else {
 		boundbox_oops();
 		calc_scrollrcts(sa, G.v2d, curarea->winx, curarea->winy);
 
diff --git a/source/blender/src/header_oops.c b/source/blender/src/header_oops.c
index 0ed3c440ae8..fa2386aaabd 100644
--- a/source/blender/src/header_oops.c
+++ b/source/blender/src/header_oops.c
@@ -69,6 +69,8 @@
 
 #include "blendef.h"
 
+#include "BKE_depsgraph.h"
+
 static int viewmovetemp = 0;
 
 void do_oops_buttons(short event)
@@ -119,7 +121,7 @@ static void do_oops_viewmenu(void *arg, int event)
 	case 4: /* show outliner */
 		{
 			SpaceOops *soops= curarea->spacedata.first;
-			if(soops->type==SO_OOPS) soops->type= SO_OUTLINER;
+			if(soops->type==SO_OOPS || soops->type==SO_DEPSGRAPH) soops->type= SO_OUTLINER;
 			else soops->type= SO_OOPS;
 			init_v2d_oops(curarea, soops);
 			test_view2d(G.v2d, curarea->winx, curarea->winy);
@@ -141,6 +143,22 @@ static void do_oops_viewmenu(void *arg, int event)
 	case 9:
 		outliner_one_level(curarea, -1);
 		break;
+#ifdef SHOWDEPGRAPH
+	case 10:
+		// show deps
+		{
+			SpaceOops *soops= curarea->spacedata.first;
+			if(soops->type==SO_OOPS) {
+				soops->type= SO_DEPSGRAPH;
+				soops->deps_flags = DAG_RL_ALL_BUT_DATA_MASK;
+			} else 
+				soops->type= SO_OOPS;
+			init_v2d_oops(curarea, soops);
+			test_view2d(G.v2d, curarea->winx, curarea->winy);
+			scrarea_queue_winredraw(curarea);
+		}
+		break;
+#endif
 	}
 }			
 
@@ -155,7 +173,9 @@ static uiBlock *oops_viewmenu(void *arg_unused)
 	
 	if(soops->type==SO_OOPS) {
 		uiDefIconTextBut(block, BUTM, 1, ICON_BLANK1, "Show Outliner", 0, yco-=20, menuwidth, 19, NULL, 0.0, 0.0, 1, 4, "");
-
+#ifdef SHOWDEPGRAPH
+		uiDefIconTextBut(block, BUTM, 1, ICON_BLANK1, "Show Dependancies", 0, yco-=20, menuwidth, 19, NULL, 0.0, 0.0, 1, 10, "");
+#endif
 		uiDefBut(block, SEPR, 0, "",        0, yco-=6, menuwidth, 6, NULL, 0.0, 0.0, 0, 0, "");  
 
 		uiDefIconTextBut(block, BUTM, 1, ICON_BLANK1, "Shuffle Selected Blocks|Shift S", 0, yco-=20, menuwidth, 19, NULL, 0.0, 0.0, 1, 0, "");
@@ -165,6 +185,12 @@ static uiBlock *oops_viewmenu(void *arg_unused)
 
 		uiDefIconTextBut(block, BUTM, 1, ICON_BLANK1, "View All|Home", 0, yco-=20, menuwidth, 19, NULL, 0.0, 0.0, 1, 2, "");
 	}
+#ifdef SHOWDEPGRAPH
+	else if(soops->type==SO_DEPSGRAPH) {
+		uiDefIconTextBut(block, BUTM, 1, ICON_BLANK1, "Show Outliner", 0, yco-=20, menuwidth, 19, NULL, 0.0, 0.0, 1, 4, "");
+		uiDefIconTextBut(block, BUTM, 1, ICON_BLANK1, "Show Oops Schematic", 0, yco-=20, menuwidth, 19, NULL, 0.0, 0.0, 1, 10, "");
+	}
+#endif
 	else {
 		uiDefIconTextBut(block, BUTM, 1, ICON_BLANK1, "Show Oops Schematic", 0, yco-=20, menuwidth, 19, NULL, 0.0, 0.0, 1, 4, "");
 		
@@ -386,6 +412,33 @@ void oops_buttons(void)
 
 		}
 	}
+#ifdef SHOWDEPGRAPH
+	else if(soops->type==SO_DEPSGRAPH) {
+		// cpack colors : 0x00FF00 0xFF0000 0xFFFF00 0x000000 0x0000FF 0x00FFFF
+		static unsigned char colr[21] ={0x00, 0xFF, 0x00, 
+										0x00, 0x00, 0xFF,
+										0x00, 0xFF, 0xFF,
+										0x00, 0x00, 0x00,
+										0xFF, 0x00, 0x00,
+										0xFF, 0xFF, 0x00,
+										0xFF, 0x00, 0x00};
+		
+		uiDefButC(	block, COL, 0, "", (short)(xco+=10),0, 5,YIC, colr, 0, 1, 0, 0,  "");
+		uiDefButS(	block, TOG|BIT|2, B_REDR, "parent", (short)(xco+=7),0, 50,YIC, &soops->deps_flags, 0, 1, 0, 0,  "parent");
+		uiDefButC(	block, COL, 0, "", (short)(xco+=60),0, 5,YIC, colr+3, 0, 1, 0, 0,  "");
+		uiDefButS(	block, TOG|BIT|1, B_REDR, "data", (short)(xco+=7),0, 50,YIC, &soops->deps_flags, 0, 1, 0, 0,  "data");
+		uiDefButC(	block, COL, 0, "", (short)(xco+=60),0, 5,YIC, colr+6, 0, 1, 0, 0,  "");
+		uiDefButS(	block, TOG|BIT|3, B_REDR, "track", (short)(xco+=7),0, 50,YIC, &soops->deps_flags, 0, 1, 0, 0,  "track");
+		uiDefButC(	block, COL, 0, "", (short)(xco+=60),0, 5,YIC, colr+9, 0, 1, 0, 0,  "");
+		uiDefButS(	block, TOG|BIT|4, B_REDR, "path", (short)(xco+=7),0, 50,YIC, &soops->deps_flags, 0, 1, 0, 0,  "path");
+		uiDefButC(	block, COL, 0, "", (short)(xco+=60),0, 5,YIC, colr+12, 0, 1, 0, 0,  "");
+		uiDefButS(	block, TOG|BIT|5, B_REDR, "cons.", (short)(xco+=7),0, 50,YIC, &soops->deps_flags, 0, 1, 0, 0,  "constraint");
+		uiDefButC(	block, COL, 0, "", (short)(xco+=60),0, 5,YIC, colr+15, 0, 1, 0, 0,  "");
+		uiDefButS(	block, TOG|BIT|6, B_REDR, "hook.", (short)(xco+=7),0, 50,YIC, &soops->deps_flags, 0, 1, 0, 0,  "hook");
+		uiDefButC(	block, COL, 0, "", (short)(xco+=60),0, 5,YIC, colr+18, 0, 1, 0, 0,  "");
+		uiDefButS(	block, TOG|BIT|7, B_REDR, "d cons.", (short)(xco+=7),0, 50,YIC, &soops->deps_flags, 0, 1, 0, 0,  "d cons");
+	} 
+#endif
 	else {
 		uiDefButS(block, MENU, B_REDR, "Outliner Display%t|All Scenes %x0|Current Scene %x1|Visible Layers %x2|Same Types %x5|Selected %x3|Active %x4",	 xco, 0, 100, 20,  &soops->outlinevis, 0, 0, 0, 0, "");
 	}
diff --git a/source/blender/src/space.c b/source/blender/src/space.c
index f2bf392f956..813ec2d749e 100644
--- a/source/blender/src/space.c
+++ b/source/blender/src/space.c
@@ -143,6 +143,8 @@
 
 #include "BIF_transform.h"
 
+#include "BKE_depsgraph.h"
+
 #include "TPT_DependKludge.h"
 #ifdef NAN_TPT
 #include "BSE_trans_types.h"
@@ -4481,6 +4483,16 @@ void allqueue(unsigned short event, short val)
 
 	sa= G.curscreen->areabase.first;
 	while(sa) {
+//#ifdef NAN_DEP_GRAPH
+		/* dependency check.maybe not final pos */
+		if (sa->spacetype==SPACE_VIEW3D) {
+			if (G.scene->dagisvalid == 0) {
+				fprintf(stderr,"building dag \n");
+				G.scene->theDag = build_dag(G.scene, DAG_RL_ALL_BUT_DATA_MASK);
+				G.scene->dagisvalid = 1;
+			}
+		}
+//#endif
 		if(event==REDRAWALL) {
 			scrarea_queue_winredraw(sa);
 			scrarea_queue_headredraw(sa);