20210422.query_graph.sql

CREATE INDEX edges_from_node_id_to_node_id_idx ON playground.edges(from_node_id,to_node_id);

INSERT INTO playground.nodes (node_name) VALUES(chr(generate_series(65,75))); -- A..K
INSERT INTO playground.edges (from_node_id, to_node_id, type)
  VALUES
    (1,2,'parent'),(2,3,'parent'),(3,1,'parent'),(3,10,'parent'),(10,3,'child'),
    (7,8,'parent'),(8,7,'child');
  
  
CREATE OR REPLACE FUNCTION get_graph(node_id INTEGER)
  RETURNS TABLE (node_id INTEGER)
  LANGUAGE SQL
AS $$
  WITH RECURSIVE traverse(id, path, cycle) AS (
    SELECT
      playground.edges.from_node_id,
      ARRAY[playground.edges.from_node_id],
      false
    FROM playground.edges
    WHERE playground.edges.from_node_id = node_id
    UNION ALL
    SELECT
      playground.edges.to_node_id, 
      traverse.path || playground.edges.to_node_id,
      playground.edges.to_node_id = ANY(traverse.path)
    FROM traverse
    INNER JOIN playground.edges
    ON playground.edges.from_node_id = traverse.id 
    WHERE NOT cycle 
  )
  SELECT id FROM traverse GROUP BY id ORDER BY MIN(CARDINALITY(path))
$$;