diff options
author | Brecht Van Lommel <brechtvanlommel@pandora.be> | 2013-02-26 22:15:51 +0400 |
---|---|---|
committer | Brecht Van Lommel <brechtvanlommel@pandora.be> | 2013-02-26 22:15:51 +0400 |
commit | e8642ecc0041a7f70d103c44da5738f6460414f2 (patch) | |
tree | 6e623c9e191a71a860045fcd37210a5af6cd2d06 | |
parent | 1d20f2496ab489c98224375ba63f4a726e931edb (diff) |
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.
-rw-r--r-- | source/blender/blenkernel/BKE_depsgraph.h | 177 | ||||
-rw-r--r-- | source/blender/blenkernel/depsgraph_private.h | 32 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/depsgraph.c | 548 |
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; |