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.

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);
 int pgm_get_nr_threshold(edge_t edge);
 
 /*
+   Query to see if 'query' is an ancestor of 'node'.
+     [in] node:  possible decendent of 'query'
+     [in] query: possible ancestor of 'node'
+   Return:
+     1 if 'query' is an ancestor of 'node'.
+     0 if 'query' is NOT an ancestor of 'node'.
+        -1 if 'query' or 'node' is an invalid node, or
+       if 'query' and 'node' are from different graphs, or
+       if 'query' == 'node'
+
+   Note: pgm_is_ancestor(n, q) === pgm_is_descendant(q, n)
+ */
+int pgm_is_ancestor(node_t node, node_t query);
+
+/*
+   Query to see if 'query' is a decendant of 'node'.
+     [in] node:  possible ancestor of 'query'
+     [in] query: possible decendent of 'node'
+   Return:
+     1 if 'query' is an decendent of 'node'.
+     0 if 'query' is NOT an decendent of 'node'.
+        -1 if 'query' or 'node' is an invalid node, or
+       if 'query' and 'node' are from different graphs, or
+       if 'query' == 'node'
+
+   Note: pgm_is_ancestor(n, q) === pgm_is_descendant(q, n)
+ */
+int pgm_is_descendant(node_t node, node_t query);
+
+/*
    Check if a graph is a acyclic.
      [in] graph: Graph descriptor
          [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:
         return ret;
 }
 
+static int is_ancestor(const struct pgm_graph* g,
+        const struct pgm_node* n, const struct pgm_node* q,
+        std::set<int>& visited)
+{
+        if(n == q)
+                return 1;
+
+        const int degree = n->nr_in;
+        if(degree == 0)
+                return 0;
+
+        int is_pred = 0;
+
+        // depth-first search to see if q is a predecessor of n.
+        for(int i = 0; i < degree && !is_pred; ++i)
+        {
+                if(g->edges[n->in[i]].is_backedge)
+                        continue; // skip backeges
+
+                int parent_idx = g->edges[n->in[i]].producer;
+                if(visited.find(parent_idx) == visited.end())
+                {
+                        visited.insert(parent_idx);
+
+                        const struct pgm_node* parent = &g->nodes[parent_idx];
+                        is_pred = is_ancestor(g, parent, q, visited);
+                }
+        }
+
+        return is_pred;
+}
+
+int pgm_is_ancestor(node_t node, node_t query)
+{
+        int ret = -1;
+        struct pgm_graph* g;
+        struct pgm_node* n;
+        struct pgm_node* q;
+
+        if(node.graph != query.graph)
+                goto out;
+        if(node.node == query.node)
+                goto out;
+        if(!is_valid_graph(node.graph))
+                goto out;
+
+        g = &gGraphs[node.graph];
+        n = &g->nodes[node.node];
+        q = &g->nodes[query.node];
+
+        {
+                std::set<int> visited;
+
+                pthread_mutex_lock(&g->lock);
+                ret = is_ancestor(g, n, q, visited);
+                pthread_mutex_unlock(&g->lock);
+        }
+
+out:
+        return ret;
+
+}
+
+int pgm_is_descendant(node_t n, node_t query)
+{
+        return pgm_is_ancestor(query, n);
+}
 
 ///////////////////////////////////////////////////
 //           Graph Validation Routines           //