Oracle - グラフのルート値を計算する

Question

私はOracle 10で作業しています。

私はグラフのノードとパスを記述するデータを持っています。 私は、エンドポイントとその値またはトラバーサルコスト間のすべてのルートを記述するクエリを作成したいと考えています。

例データ：

Start  End Cost 
1170 4275  126 
1170 8405  40 
1170 8410  67 
8405 4275  88 
8405 8410  29 
4275 8410  61 

：出力のようになります

1170    8406    8405 
[]-----------------o----------------[] 
     (39)  |  (1) 
        | 
        |(27) 
        |    4275 
       8411 o----------------[] 
        |  (60) 
        | 
       (1)| 
        | 
        [] 
        8410 

：

NodeId1 NodeId2 Endpoint1 Endpoint2 Value 
    1170  8406  34210  (null)  39 
    8411  8410  (null)  34260  1 
    8411  4275  (null)  32231  60 
    8406  8405  (null)  34287  1 
    8406  8411  (null)  (null)  26 

これは、この（費用はエンドポイントが角括弧は、括弧内にある）ように見えるグラフを記述する

出力を両方向（1170〜8406と8406〜1170）にする必要はありませんが結果のさらなる使用に役立つ可能性があるので、含めることができればいいでしょう。

Answer 1

Oracleのセットアップ：

CREATE FUNCTION sum_Number_List(
    i_str IN VARCHAR2, 
    i_delim IN VARCHAR2 DEFAULT ',' 
) RETURN NUMBER DETERMINISTIC 
AS 
    p_result  NUMBER := 0; 
    p_start  NUMBER(5) := 1; 
    p_end   NUMBER(5); 
    c_len CONSTANT NUMBER(5) := LENGTH(i_str); 
    c_ld CONSTANT NUMBER(5) := LENGTH(i_delim); 
BEGIN 
    IF c_len > 0 THEN 
    p_end := INSTR(i_str, i_delim, p_start); 
    WHILE p_end > 0 LOOP 
     p_result := p_result + TO_NUMBER(SUBSTR(i_str, p_start, p_end - p_start)); 
     p_start := p_end + c_ld; 
     p_end := INSTR(i_str, i_delim, p_start); 
    END LOOP; 
    IF p_start <= c_len + 1 THEN 
     p_result := p_result + TO_NUMBER(SUBSTR(i_str, p_start, c_len - p_start + 1)); 
    END IF; 
    END IF; 
    RETURN p_result; 
END; 
/

CREATE TABLE table_name (NodeId1, NodeId2, Endpoint1, Endpoint2, Value) AS 
SELECT 1170, 8406, 34210, null, 39 FROM DUAL UNION ALL 
SELECT 8411, 8410, null, 34260, 1 FROM DUAL UNION ALL 
SELECT 8411, 4275, null, 32231, 60 FROM DUAL UNION ALL 
SELECT 8406, 8405, null, 34287, 1 FROM DUAL UNION ALL 
SELECT 8406, 8411, null, null, 26 FROM DUAL; 

クエリ：

WITH directedgraph AS (
    SELECT NodeID1 AS f, 
     NodeID2 AS t, 
     EndPoint1 AS isStart, 
     EndPoint2 AS isEnd, 
     Value 
    FROM table_Name 
    UNION ALL 
    SELECT NodeID2 AS f, 
     NodeID1 AS t, 
     EndPoint2 AS isStart, 
     EndPoint1 AS isEnd, 
     Value 
    FROM table_Name 
) 
SELECT CONNECT_BY_ROOT(f) AS "START", 
     t AS "END", 
     SUM_NUMBER_LIST(SUBSTR(SYS_CONNECT_BY_PATH(value, ','), 2)) AS cost 
FROM directedgraph 
WHERE CONNECT_BY_ISLEAF = 1 
AND isEnd IS NOT NULL 
START WITH isStart IS NOT NULL 
CONNECT BY NOCYCLE 
      PRIOR t = f 
AND  PRIOR f <> t; 

出力：

 START  END  COST 
---------- ---------- ---------- 
     1170  8405   40 
     1170  4275  125 
     1170  8410   66 
     4275  1170  125 
     4275  8405   87 
     4275  8410   61 
     8405  1170   40 
     8405  4275   87 
     8405  8410   28 
     8410  4275   61 
     8410  1170   66 
     8410  8405   28