10-334 経路探索で別の木で訪問済ノードを避けて探索

SQLパズル

TestGraph
ID  NextID
--  ------
 1       2
 1       3
 2       3
 2       4
 2       8
 3       6
 4       5
 4       6
 5       7
 6       7
 7       9
 8      10

ID=1の行から探索を開始して、木の葉となるノードを表示する。

ただし、distinctを使った下記のSQLではなく、
別の木で訪問済ノードを避けて(枝切りして)探索を行う。

select distinct ID
  from TestGraph
 where connect_by_IsLeaf = 1
start with ID = 1
connect by prior NextID = ID

出力結果
ID
--
 7
 8

こちらを参考にさせていただきました(英語)

データ作成スクリプト

create table TestGraph(ID,NextID) as
select 1,   2 from dual union all
select 1,   3 from dual union all
select 2,   3 from dual union all
select 2,   4 from dual union all
select 2,   8 from dual union all
select 3,   6 from dual union all
select 4,   5 from dual union all
select 4,   6 from dual union all
select 5,   7 from dual union all
select 6,   7 from dual union all
select 7,null from dual union all
select 8,null from dual;

SQL

--■■■再帰with句を使う方法(11gR2以降)■■■
with rec(rootID,ID,NextID,Lv) as(
select ID,ID,NextID,1
  from TestGraph
 where ID = 1
union all
select a.rootID,b.ID,b.NextID,a.Lv+1
  from rec a Join TestGraph b
    on a.NextID = b.ID
 where (b.ID,b.NextID)
 not in(select c.ID,c.NextID
          from TestGraph c
        start with c.ID = 1
        connect by prior c.NextID = c.ID
               and Level <= a.Lv))
select rootID,ID,NextID,LV
  from rec a
 where not exists(select 1 from rec b
                   where a.NextID = b.ID);

--■■■表関数を使う方法■■■
create or replace Package Pack10_334 Is
    type PrintRType is record(
    ID TestGraph.ID%type,
    Path varchar2(30));

    type PrintRTypeSet is table of PrintRType;
end;
/

create or replace function Print10_334 return Pack10_334.PrintRTypeSet PipeLined IS
    outR Pack10_334.PrintRType;
    cursor cur is select ID,NextID,to_char(RowNum,'fm0009') as Row_ID,0 as IsAppear from TestGraph;
    type saveDataDef is table of cur%rowType index by binary_integer;
    saveData saveDataDef;

    type InfoDef is record(
        RowData  cur%rowType,
        RowIDList varchar2(1000),
        Path      varchar2(1000)
    );

    stackP binary_integer := 0;
    type StackClass is table of InfoDef index by binary_integer;
    st StackClass;
    priInfo  InfoDef;
    willPush InfoDef;
    LoopChk pls_Integer :=0;
    IsLeaf boolean;

    procedure push(pInfoDef InfoDef) is
    begin
        st(stackP) := pInfoDef;
        stackP := stackP+1;
    end;

    function pop return InfoDef is
    begin
        stackP := stackP-1;
        return st(stackP);
    end;

    function isEmpty return boolean is
    begin
        return stackP = 0;
    end;

begin
    open cur;
    fetch cur bulk collect into saveData;
    close cur;

    --Start With句
    for I in 1..saveData.Count Loop
        if saveData(I).ID = 1 then
            willPush.RowData.ID := saveData(I).ID;
            willPush.RowData.NextID   := saveData(I).NextID;
            saveData(I).IsAppear := 1;
            willPush.RowIDList := saveData(I).Row_ID;
            willPush.Path := to_char(saveData(I).NextID);

            push(willPush);
        end if;
    end Loop;

    while (isEmpty = false) loop
        priInfo := pop();
        IsLeaf := true;

        -- connect by句
        for I in 1..saveData.Count Loop
            if priInfo.RowData.NextID = saveData(I).ID then
                IsLeaf := false;

                if saveData(I).IsAppear = 0 then
                    saveData(I).IsAppear := 1;

                    -- 未訪問ノードならpush
                    if instr(priInfo.RowIDList,saveData(I).Row_ID) = 0 then
                        willPush.RowData.ID := saveData(I).ID;
                        willPush.RowData.NextID := saveData(I).NextID;
                        willPush.RowIDList := priInfo.RowIDList || '/' || saveData(I).Row_ID;
                        willPush.Path := priInfo.Path || '/' || to_char(saveData(I).NextID);

                        push(willPush);
                    end if;
                end if;
            end if;
        end Loop;

        --葉なら表示
        if IsLeaf then
            outR.ID   := priInfo.RowData.ID;
            outR.Path   := priInfo.Path;
            pipe row(outR);
        end if;

        LoopChk := LoopChk+1;
        if (LoopChk=999) then
            DBMS_Output.Put_Line('CountStop!!!');
            exit;
        end if;
    end Loop;
end;
/

sho err

select ID,Path from table(Print10_334)
order by ID;

解説

再帰With句の再帰項では、recを使ったnot in述語もnot exists述語も使えなかったので、
階層問い合わせで代用しました :-)

---