diff options
author | Glenn Elliott <gelliott@cs.unc.edu> | 2014-07-28 18:27:33 -0400 |
---|---|---|
committer | Glenn Elliott <gelliott@cs.unc.edu> | 2014-07-28 18:27:33 -0400 |
commit | b51031e88ba20dea0126de91e35026ed8ecf98b0 (patch) | |
tree | 27cff05464e433f761b0a1b1c7f718d17f3607cd | |
parent | efc4f3158dadb1bb1b61d97aec64b07f8f7b42d8 (diff) |
API: Add pgm_is_ancestor() and pgm_is_descendant()
This patch adds routines to check if one node
is an ancestor/decendant of the other.
-rw-r--r-- | include/pgm.h | 30 | ||||
-rw-r--r-- | src/pgm.cpp | 67 |
2 files changed, 97 insertions, 0 deletions
diff --git a/include/pgm.h b/include/pgm.h index 676bd85..4f6182f 100644 --- a/include/pgm.h +++ b/include/pgm.h | |||
@@ -403,6 +403,36 @@ int pgm_get_nr_consume(edge_t edge); | |||
403 | int pgm_get_nr_threshold(edge_t edge); | 403 | int pgm_get_nr_threshold(edge_t edge); |
404 | 404 | ||
405 | /* | 405 | /* |
406 | Query to see if 'query' is an ancestor of 'node'. | ||
407 | [in] node: possible decendent of 'query' | ||
408 | [in] query: possible ancestor of 'node' | ||
409 | Return: | ||
410 | 1 if 'query' is an ancestor of 'node'. | ||
411 | 0 if 'query' is NOT an ancestor of 'node'. | ||
412 | -1 if 'query' or 'node' is an invalid node, or | ||
413 | if 'query' and 'node' are from different graphs, or | ||
414 | if 'query' == 'node' | ||
415 | |||
416 | Note: pgm_is_ancestor(n, q) === pgm_is_descendant(q, n) | ||
417 | */ | ||
418 | int pgm_is_ancestor(node_t node, node_t query); | ||
419 | |||
420 | /* | ||
421 | Query to see if 'query' is a decendant of 'node'. | ||
422 | [in] node: possible ancestor of 'query' | ||
423 | [in] query: possible decendent of 'node' | ||
424 | Return: | ||
425 | 1 if 'query' is an decendent of 'node'. | ||
426 | 0 if 'query' is NOT an decendent of 'node'. | ||
427 | -1 if 'query' or 'node' is an invalid node, or | ||
428 | if 'query' and 'node' are from different graphs, or | ||
429 | if 'query' == 'node' | ||
430 | |||
431 | Note: pgm_is_ancestor(n, q) === pgm_is_descendant(q, n) | ||
432 | */ | ||
433 | int pgm_is_descendant(node_t node, node_t query); | ||
434 | |||
435 | /* | ||
406 | Check if a graph is a acyclic. | 436 | Check if a graph is a acyclic. |
407 | [in] graph: Graph descriptor | 437 | [in] graph: Graph descriptor |
408 | [in] ignore_explicit_backedges: Ignore edges that were added | 438 | [in] ignore_explicit_backedges: Ignore edges that were added |
diff --git a/src/pgm.cpp b/src/pgm.cpp index cdf3ff4..6e7a888 100644 --- a/src/pgm.cpp +++ b/src/pgm.cpp | |||
@@ -2720,6 +2720,73 @@ out: | |||
2720 | return ret; | 2720 | return ret; |
2721 | } | 2721 | } |
2722 | 2722 | ||
2723 | static int is_ancestor(const struct pgm_graph* g, | ||
2724 | const struct pgm_node* n, const struct pgm_node* q, | ||
2725 | std::set<int>& visited) | ||
2726 | { | ||
2727 | if(n == q) | ||
2728 | return 1; | ||
2729 | |||
2730 | const int degree = n->nr_in; | ||
2731 | if(degree == 0) | ||
2732 | return 0; | ||
2733 | |||
2734 | int is_pred = 0; | ||
2735 | |||
2736 | // depth-first search to see if q is a predecessor of n. | ||
2737 | for(int i = 0; i < degree && !is_pred; ++i) | ||
2738 | { | ||
2739 | if(g->edges[n->in[i]].is_backedge) | ||
2740 | continue; // skip backeges | ||
2741 | |||
2742 | int parent_idx = g->edges[n->in[i]].producer; | ||
2743 | if(visited.find(parent_idx) == visited.end()) | ||
2744 | { | ||
2745 | visited.insert(parent_idx); | ||
2746 | |||
2747 | const struct pgm_node* parent = &g->nodes[parent_idx]; | ||
2748 | is_pred = is_ancestor(g, parent, q, visited); | ||
2749 | } | ||
2750 | } | ||
2751 | |||
2752 | return is_pred; | ||
2753 | } | ||
2754 | |||
2755 | int pgm_is_ancestor(node_t node, node_t query) | ||
2756 | { | ||
2757 | int ret = -1; | ||
2758 | struct pgm_graph* g; | ||
2759 | struct pgm_node* n; | ||
2760 | struct pgm_node* q; | ||
2761 | |||
2762 | if(node.graph != query.graph) | ||
2763 | goto out; | ||
2764 | if(node.node == query.node) | ||
2765 | goto out; | ||
2766 | if(!is_valid_graph(node.graph)) | ||
2767 | goto out; | ||
2768 | |||
2769 | g = &gGraphs[node.graph]; | ||
2770 | n = &g->nodes[node.node]; | ||
2771 | q = &g->nodes[query.node]; | ||
2772 | |||
2773 | { | ||
2774 | std::set<int> visited; | ||
2775 | |||
2776 | pthread_mutex_lock(&g->lock); | ||
2777 | ret = is_ancestor(g, n, q, visited); | ||
2778 | pthread_mutex_unlock(&g->lock); | ||
2779 | } | ||
2780 | |||
2781 | out: | ||
2782 | return ret; | ||
2783 | |||
2784 | } | ||
2785 | |||
2786 | int pgm_is_descendant(node_t n, node_t query) | ||
2787 | { | ||
2788 | return pgm_is_ancestor(query, n); | ||
2789 | } | ||
2723 | 2790 | ||
2724 | /////////////////////////////////////////////////// | 2791 | /////////////////////////////////////////////////// |
2725 | // Graph Validation Routines // | 2792 | // Graph Validation Routines // |