Dependency Graph: refactoring to move private functions to the private header,

and add more documentation about the public functions. Also removed unused graph
traversal code and other minor unused functions.

3 files changed, 105 insertions, 652 deletions

diff --git a/source/blender/blenkernel/BKE_depsgraph.h b/source/blender/blenkernel/BKE_depsgraph.h
index 4cdfc1cba95..71204c73063 100644
--- a/source/blender/blenkernel/BKE_depsgraph.h
+++ b/source/blender/blenkernel/BKE_depsgraph.h
@@ -30,114 +30,93 @@
  *  \ingroup bke
  */
 
+/* Dependency Graph
+ *
+ * The dependency graph tracks relations between datablocks, and is used to
+ * determine which datablocks need to be update based on dependencies and
+ * visibility.
+ *
+ * It does not itself execute changes in objects, but rather sorts the objects
+ * in the appropriate order and sets flags indicating they should be updated.
+ */
+
 #ifdef __cplusplus
 extern "C" {
 #endif
 
-// #define DEPS_DEBUG
-
-struct DagForest;
-struct DagNode;
-struct DagNodeQueue;
-struct GHash;
 struct ID;
 struct Main;
 struct Object;
 struct Scene;
 
-/* **** DAG relation types *** */
-
-/* scene link to object */
-#define DAG_RL_SCENE        (1 << 0)
-/* object link to data */
-#define DAG_RL_DATA         (1 << 1)
-
-/* object changes object (parent, track, constraints) */
-#define DAG_RL_OB_OB        (1 << 2)
-/* object changes obdata (hooks, constraints) */
-#define DAG_RL_OB_DATA      (1 << 3)
-/* data changes object (vertex parent) */
-#define DAG_RL_DATA_OB      (1 << 4)
-/* data changes data (deformers) */
-#define DAG_RL_DATA_DATA    (1 << 5)
-
-#define DAG_NO_RELATION     (1 << 6)
-
-#define DAG_RL_ALL_BUT_DATA (DAG_RL_SCENE | DAG_RL_OB_OB | DAG_RL_OB_DATA | DAG_RL_DATA_OB | DAG_RL_DATA_DATA)
-#define DAG_RL_ALL          (DAG_RL_ALL_BUT_DATA | DAG_RL_DATA)
-
-
-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 Main *bmain, 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);
-short  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); //
-
-/* ********** API *************** */
-/* Note that the DAG never executes changes in Objects, only sets flags in Objects */
-
-/* clear all dependency graphs, call this when changing relations between objects.
- * the dependency graphs will be rebuilt just before they are used to avoid them
- * getting rebuild many times during operators */
-void    DAG_relations_tag_update(struct Main *bmain);
-
-/* (re)-create the dependency graph before using it */
-void    DAG_scene_relations_update(struct Main *bmain, struct Scene *sce);
-
-/* force an immediate rebuild of the dependency graph, only needed in rare cases */
-void    DAG_scene_relations_rebuild(struct Main *bmain, struct Scene *scene);
-
-/* flag all objects that need recalc because they're animated */
-void    DAG_scene_update_flags(struct Main *bmain, struct Scene *sce, unsigned int lay, const short do_time);
-/* flushes all recalc flags in objects down the dependency tree */
-void    DAG_scene_flush_update(struct Main *bmain, struct Scene *sce, unsigned int lay, const short do_time);
-/* tag objects for update on file load */
-void    DAG_on_visible_update(struct Main *bmain, const short do_time);
-
-/* tag datablock to get updated for the next redraw */
-void    DAG_id_tag_update_ex(struct Main *bmain, struct ID *id, short flag);
-void    DAG_id_tag_update(struct ID *id, short flag);
-/* flush all tagged updates */
-void    DAG_ids_flush_tagged(struct Main *bmain);
-/* check and clear ID recalc flags */
-void    DAG_ids_check_recalc(struct Main *bmain, struct Scene *scene, int time);
-void    DAG_ids_clear_recalc(struct Main *bmain);
-/* test if any of this id type is tagged for update */
-void    DAG_id_type_tag(struct Main *bmain, short idtype);
-int     DAG_id_type_tagged(struct Main *bmain, short idtype);
-
-/* (re)-create dependency graph for armature pose */
-void    DAG_pose_sort(struct Object *ob);
-
-/* callback for editors module to do updates */
-void    DAG_editors_update_cb(void (*id_func)(struct Main *bmain, struct ID *id),
-                              void (*scene_func)(struct Main *bmain, struct Scene *scene, int updated));
-
-/* debugging */
-void    DAG_print_dependencies(struct Main *bmain, struct Scene *scene, struct Object *ob);
+/* Build and Update
+ *
+ * DAG_scene_relations_update will rebuild the dependency graph for a given
+ * scene if needed, and sort objects in the scene.
+ *
+ * DAG_relations_tag_update will clear all dependency graphs and mark them to
+ * be rebuilt later. The graph is not rebuilt immediately to avoid slowdowns
+ * when this function is call multiple times from different operators.
+ *
+ * DAG_scene_relations_rebuild forces an immediaterebuild of the dependency
+ * graph, this is only needed in rare cases
+ */
+
+void DAG_scene_relations_update(struct Main *bmain, struct Scene *sce);
+void DAG_relations_tag_update(struct Main *bmain);
+void DAG_scene_relations_rebuild(struct Main *bmain, struct Scene *scene);
+
+/* Update Tagging
+ *
+ * DAG_scene_update_flags will mark all objects that depend on time (animation,
+ * physics, ..) to be recalculated, used when changing the current frame.
+ * 
+ * DAG_on_visible_update will mark all objects that are visible for the first
+ * time to be updated, for example on file load or changing layer visibility.
+ *
+ * DAG_id_tag_update will mark a given datablock to be updated. The flag indicates
+ * a specific subset to be update (only object transform and data for now).
+ *
+ * DAG_id_type_tag marks a particular datablock type as having changing. This does
+ * not cause any updates but is used by external render engines to detect if for
+ * example a datablock was removed. */
+
+void DAG_scene_update_flags(struct Main *bmain, struct Scene *sce, unsigned int lay, const short do_time);
+void DAG_on_visible_update(struct Main *bmain, const short do_time);
+
+void DAG_id_tag_update(struct ID *id, short flag);
+void DAG_id_tag_update_ex(struct Main *bmain, struct ID *id, short flag);
+void DAG_id_type_tag(struct Main *bmain, short idtype);
+int  DAG_id_type_tagged(struct Main *bmain, short idtype);
+
+/* Flushing Tags
+ *
+ * DAG_scene_flush_update flushes object recalculation flags immediately to other
+ * dependencies. Do not use outside of depsgraph.c, this will be removed.
+ *
+ * DAG_ids_flush_tagged will flush datablock update flags flags to dependencies,
+ * use this right before updating to mark all the needed datablocks for update.
+ *
+ * DAG_ids_check_recalc and DAG_ids_clear_recalc are used for external render
+ * engines to detect changes. */
+
+void DAG_scene_flush_update(struct Main *bmain, struct Scene *sce, unsigned int lay, const short do_time);
+void DAG_ids_flush_tagged(struct Main *bmain);
+void DAG_ids_check_recalc(struct Main *bmain, struct Scene *scene, int time);
+void DAG_ids_clear_recalc(struct Main *bmain);
+
+/* Armature: sorts the bones according to dependencies between them */
+
+void DAG_pose_sort(struct Object *ob);
+
+/* Editors: callbacks to notify editors of datablock changes */
+
+void DAG_editors_update_cb(void (*id_func)(struct Main *bmain, struct ID *id),
+                           void (*scene_func)(struct Main *bmain, struct Scene *scene, int updated));
+
+/* Debugging: print dependency graph for scene or armature object to console */
+
+void DAG_print_dependencies(struct Main *bmain, struct Scene *scene, struct Object *ob);
 
 #ifdef __cplusplus
 }
diff --git a/source/blender/blenkernel/depsgraph_private.h b/source/blender/blenkernel/depsgraph_private.h
index 12c111f5f16..ad5369c0820 100644
--- a/source/blender/blenkernel/depsgraph_private.h
+++ b/source/blender/blenkernel/depsgraph_private.h
@@ -34,9 +34,27 @@
 #include "DNA_constraint_types.h"
 #include "BKE_constraint.h"
 
+/* **** DAG relation types *** */
+
+/* scene link to object */
+#define DAG_RL_SCENE        (1 << 0)
+/* object link to data */
+#define DAG_RL_DATA         (1 << 1)
+
+/* object changes object (parent, track, constraints) */
+#define DAG_RL_OB_OB        (1 << 2)
+/* object changes obdata (hooks, constraints) */
+#define DAG_RL_OB_DATA      (1 << 3)
+/* data changes object (vertex parent) */
+#define DAG_RL_DATA_OB      (1 << 4)
+/* data changes data (deformers) */
+#define DAG_RL_DATA_DATA    (1 << 5)
+
+#define DAG_NO_RELATION     (1 << 6)
+
+#define DAG_RL_ALL_BUT_DATA (DAG_RL_SCENE | DAG_RL_OB_OB | DAG_RL_OB_DATA | DAG_RL_DATA_OB | DAG_RL_DATA_DATA)
+#define DAG_RL_ALL          (DAG_RL_ALL_BUT_DATA | DAG_RL_DATA)
 
-#define DEPSX   5.0f
-#define DEPSY   1.8f
 
 #define DAGQUEUEALLOC 50
 
@@ -46,8 +64,6 @@ enum {
 	DAG_BLACK = 2
 };
 
-
-
 typedef struct DagAdjList {
 	struct DagNode *node;
 	short type;
@@ -108,11 +124,13 @@ 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);
+int queue_count(DagNodeQueue *queue);
+void queue_delete(DagNodeQueue *queue);
 
 // Dag management
-DagForest *getMainDag(void);
-void setMainDag(DagForest *dag);
 DagForest *dag_init(void);
+DagForest *build_dag(struct Main *bmain, struct Scene *sce, short mask);
+void free_forest(struct DagForest *Dag);
 DagNode *dag_find_node(DagForest *forest, void *fob);
 DagNode *dag_add_node(DagForest *forest, void *fob);
 DagNode *dag_get_node(DagForest *forest, void *fob);
@@ -126,6 +144,6 @@ 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);
+void graph_print_adj_list(DagForest *dag);
 
 #endif /* __DEPSGRAPH_PRIVATE_H__ */
diff --git a/source/blender/blenkernel/intern/depsgraph.c b/source/blender/blenkernel/intern/depsgraph.c
index 8c55ad02dc6..68bdf8a8100 100644
--- a/source/blender/blenkernel/intern/depsgraph.c
+++ b/source/blender/blenkernel/intern/depsgraph.c
@@ -278,22 +278,11 @@ DagNode *pop_queue(DagNodeQueue *queue)
 	}
 }
 
-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(void)
 {
 	DagForest *forest;
@@ -1190,539 +1179,6 @@ static void dag_check_cycle(DagForest *dag)
 	}
 }
 
-/*
- * 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 always 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 = (float) 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 = (float) pos[node->BFS_dist];
-			}
-			else {
-				pos[node->BFS_dist] = (int) node->k + 1;
-			}
-			set_node_xy(node, node->BFS_dist * DEPSX * 2, 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 always 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; */ /* UNUSED */
-	/*
-	 *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 always 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 = (float) 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; */ /* UNUSED */
-						}
-						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 0
-							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);
-#endif
-						}
-						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 = (float) pos[node->DFS_dist];
-					}
-					else {
-						pos[node->DFS_dist] = (int) node->k + 1;
-					}
-					set_node_xy(node, node->DFS_dist * DEPSX * 2, 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);
-}
-
-/* unused */
-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 always 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);
-}
-
-
-/* used to get the obs owning a datablock */
-DagNodeQueue *get_obparents(struct DagForest *dag, void *ob)
-{
-	DagNode *node, *node1;
-	DagNodeQueue *nqueue;
-	DagAdjList *itA;
-
-	node = dag_find_node(dag, ob);
-	if (node == NULL) {
-		return NULL;
-	}
-	else 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;
-}
-
-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 */
-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(dag->numNodes);  /* was MainDag... why? (ton) */
-	
-	node = dag->DagNode.first;
-	while (node) {
-		node->color = DAG_WHITE;
-		node =  node->next;
-	}
-	
-	time = 1;
-	
-	node = dag_find_node(dag, ob);  /* could be done in loop above (ton) */
-	if (node) {                     /* can be null for newly added objects */
-		
-		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);
-}
-
-/* unused */
-#if 0
-short   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;
-}
-#endif
-
-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)
@@ -1757,12 +1213,12 @@ void graph_print_queue_dist(DagNodeQueue *nqueue)
 	fprintf(stderr, "\n");
 }
 
-void graph_print_adj_list(void)
+void graph_print_adj_list(DagForest *dag)
 {
 	DagNode *node;
 	DagAdjList *itA;
 	
-	node = (getMainDag())->DagNode.first;
+	node = dag->DagNode.first;
 	while (node) {
 		fprintf(stderr, "node : %s col: %i", ((ID *) node->ob)->name, node->color);
 		itA = node->child;