In order to prevent the movement algorithm from returning to already visited edges, you can really save the visited edges. As you already found out, you will not get much success with string concatenation. However, there are other applicable methods of "concatenation of value" ...
You should have one convenient collection of scalar levels at the circuit level:
create or replace type arr_strings is table of varchar2(64);
And then you can collect visited edges in this collection at each iteration:
with nondirected$ as ( select from_id, to_id, from_id||'-'||to_id as edge_desc from edge where from_id != to_id union all select to_id, from_id, from_id||'-'||to_id as edge_desc from edge where (to_id, from_id) not in ( select from_id, to_id from edge ) ), graph$(lvl, from_id, to_id, edge_desc, visited_edges) as ( select 1, from_id, to_id, edge_desc, arr_strings(edge_desc) from nondirected$ R where from_id in (&nodes) -- union all -- select lvl+1, Y.from_id, Y.to_id, Y.edge_desc, X.visited_edges multiset union arr_strings(Y.edge_desc) from graph$ X join nondirected$ Y on Y.from_id = X.to_id where not exists ( select 1 from table(X.visited_edges) Z where Y.edge_desc = Z.column_value ) ) search breadth first by edge_desc set order_id cycle edge_desc set is_cycle to 1 default 0, ranked_graph$ as ( select C.*, row_number() over (partition by edge_desc order by lvl, order_id) as rank$ from graph$ C -- where is_cycle = 0 ) select * from ranked_graph$ --where rank$ <= 1 order by lvl, order_id ;
Notes
- I pre-processed the directed graph with the undirected
union symbol by pointing the set of back edges to the input. This should facilitate reading recursive predicates. Exclusively for my purposes, it’s easier to read + write SQL. Of course, you should not do this. - I remember several years ago I tried something similar in Oracle 11.2. And I remember that it was unsuccessful, although I do not remember why. At 12.2 he went fine. Just try 11g too; I do not have one available.
- Since each iteration, in addition to the internal internal bypass, is also an anti-join, I sincerely doubt that this will be more effective. However, it certainly solves the problem of reducing the number of recursive investments.
- You will need to decide the desired order yourself, as you probably understood from my comments. :-)
Limit revised edges to zero
In SQL, you cannot. The PostgreSQL solution you mentioned does this. However, in Oracle you cannot. You must, for each crawl join, test strings for all other crawls. And that would mean some kind of aggregation or analytics ... which Oracle prohibits and excludes ORA exception.
PLSQL for salvation?
However, you can do this in PL / SQL. How it should function depends on how much memory you want to spend pre-fetching the edges from the database, and how many SQL queries you are willing to take to cross the graph from the “current” nodes or if you are ready to use even more memory to maintain visited nodes in a fancy collection with an index at the edges against if you prefer anti-join with the regular arr_output l_visited_nodes collection. You have several choices, reasonable.
In any case, for the simplest scenario with heavier use of the SQL engine, this may be the code you are looking for ...
create or replace package pkg_so_recursive_traversal is type rec_output is record ( from_id edge.from_id%type, to_id edge.to_id%type, lvl integer ); type arr_output is table of rec_output; function traverse_a_graph ( i_from in arr_strings , i_is_directed in varchar2 default 'NO' ) return arr_output pipelined; end pkg_so_recursive_traversal; / create or replace package body pkg_so_recursive_traversal is function traverse_a_graph ( i_from in arr_strings , i_is_directed in varchar2 ) return arr_output pipelined is l_next_edges arr_output; l_current_edges arr_output; l_visited_edges arr_output := arr_output(); l_out rec_output; i pls_integer; l_is_directed varchar2(32) := case when i_is_directed = 'YES' then 'YES' else 'NO' end; begin select E.from_id, E.to_id, 0 bulk collect into l_next_edges from table(i_from) F join edge E on F.column_value in (E.from_id, case when l_is_directed = 'YES' then null else E.to_id end) where E.from_id != E.to_id; l_out.lvl := 0; loop dbms_output.put_line(l_next_edges.count()); exit when l_next_edges.count() <= 0; l_out.lvl := l_out.lvl + 1; -- spool the edges to output i := l_next_edges.first(); while i is not null loop l_out.from_id := l_next_edges(i).from_id; l_out.to_id := l_next_edges(i).to_id; pipe row(l_out); i := l_next_edges.next(i); end loop; l_current_edges := l_next_edges; l_visited_edges := l_visited_edges multiset union l_current_edges; -- find next edges select unique E.from_id, E.to_id, 0 bulk collect into l_next_edges from table(l_current_edges) CE join edge E on CE.to_id in (E.from_id, case when l_is_directed = 'YES' then null else E.to_id end) or l_is_directed = 'NO' and CE.from_id in (E.from_id, E.to_id) where E.from_id != E.to_id and not exists ( select 1 from table(l_visited_edges) VE where VE.from_id = E.from_id and VE.to_id = E.to_id ); end loop; return; end; end pkg_so_recursive_traversal; /
When called to start node from A and assuming that the graph is not oriented ...
select * from table(pkg_so_recursive_traversal.traverse_a_graph( i_from => arr_strings('A'), i_is_directed => 'NO' ));
... this gives...
FROM_ID TO_ID LVL ---------- ---------- ---------- AB 1 CA 1 CE 2 BD 2 CF 2 EB 2 GD 3 HF 3 GI 4
Notes
- Again, I made no effort to keep the order that you requested, because you said that it was not so important.
- This makes several (exactly 5 for your example inputs) SQL calls to the
edge table. This may or may not be more efficient than comparing to a pure-SQL solution with excessive edge visiting. Check the correctness of the solutions, see which one is best for you. - This particular piece of code will work with 12c and above. For 11g and below, you will have to declare the
rec_output and arr_output at the circuit level.