CODEWITHSUNDEEP
sqloracle-database
Jane Liu
Jane Liu

Reputation: 61

How do you find the end nodes of a graph?

My code currently outputs all the nodes traversed in a graph.

CREATE TABLE DAG(
  pid NUMBER,
  cid NUMBER,
  PRIMARY KEY(pid, cid)
);

WITH Ancestor(ancestor, descendant) AS 
(   SELECT d.pid, d.cid
    FROM DAG d
    UNION ALL
    SELECT d.pid, a.descendant
    FROM Ancestor a  
    JOIN DAG d
    ON d.cid = a.ancestor
)   
SELECT * FROM Ancestor;

How do I get it to show all end nodes of a graph?

Upvotes: 0

Views: 318

Answers (2)

Joachim Isaksson
Joachim Isaksson

Reputation: 180917

How about;

SELECT * FROM dag WHERE cid NOT IN (SELECT pid FROM dag)

Basically it just finds all nodes and removes all the nodes that are parents of another node.

EDIT: After your edit of the question, you seem to want to recursively find all parents and grandparents that don't have a child;

WITH Ancestor(grandparent, parent, child) AS 
(   SELECT 0, d.pid, d.cid FROM DAG d WHERE pid=1
    UNION ALL
    SELECT a.parent, a.child, d.cid
    FROM Ancestor a  
    LEFT JOIN DAG d
      ON d.pid = a.child
    WHERE a.child IS NOT NULL
)   
SELECT grandparent ancestor, parent descendant
FROM Ancestor
WHERE ancestor.child IS NULL;

Your base case here being the root node (pid=1), use a left join to recursively find all grandparents/parents that don't have a child, and display them as ancestor/descendant.

An SQLfiddle to test with.

Upvotes: 1

Lennart - Slava Ukraini
Lennart - Slava Ukraini

Reputation: 7171

Expanded answer from comment:

WITH Ancestor(ancestor, leaf) AS 
(   SELECT d.pid, d.cid
    FROM DAG d
    UNION ALL
    SELECT  d.pid, a.leaf
    FROM    Ancestor a
    JOIN    DAG d
        ON d.cid = a.ancestor
)   
SELECT leaf, ancestor 
FROM Ancestor a1
WHERE NOT EXISTS (
   select 1 from ancestor a2 
   where a2.ancestor = a1.leaf
)

Upvotes: 1

Related Questions