接続探索


素朴に接続探索してみる。
距離ベースだと至った認定のルートの最小値書き直しとか必要。
まあでも自ルート覚えて再度出たノードが閉路の端か、探索方向距離積み重ねで自ルート逆送なしと考えると割合すんなりできるか。

ft-search

適当に作った接続データを使う。
LINK-Node

取り敢えずPKEY足しとく

ALTER TABLE
 tmpEdge
ADD eid INT IDENTITY

ALTER TABLE
 tmpEdge
ADD CONSTRAINT PK_tmpEdge
  PRIMARY KEY(eid)

検索

IF OBJECT_ID('tempdb..#node') IS NOT NULL
  DROP TABLE #node;

DECLARE @maxCnt INT = 3;
DECLARE @counter INT = 0;

CREATE TABLE #node (pid INT, cnt INT, eid INT);
CREATE INDEX inx_pid ON #node(pid);
CREATE INDEX inx_eid ON #node(eid);

INSERT INTO
  #node
SELECT
  PID AS pid
 ,@counter AS CNT
 ,null AS eid
FROM
  tmpNode
WHERE
  PID = 18; -- 起点


WHILE (@counter < @maxCnt)
BEGIN
 INSERT INTO 
  #node
 SELECT
  TID AS pid,
  @counter + 1 AS cnt,
  eid AS eid
 FROM
  tmpEdge 
 WHERE
  FID IN (SELECT PID FROM #node WHERE CNT = @counter)
   AND
  NOT EXISTS (SELECT * FROM #node n WHERE tmpEdge.eid = n.eid)
  --NOT eid IN ( SELECT eid FROM #node)と同様
 ;

 INSERT INTO 
  #node
 SELECT
  FID AS pid,
  @counter + 1 AS cnt,
  eid AS eid
 FROM
  tmpEdge
 WHERE
  TID IN (SELECT PID FROM #node WHERE CNT = @counter)
   AND
  NOT EXISTS (SELECT * FROM #node n WHERE tmpEdge.eid = n.eid)
 ;

 SET @counter = @counter + 1;
END

SELECT
 n.cnt,n.pid
 ,t.name
FROM
 #node n
LEFT OUTER JOIN
 tmpNode t
ON
 n.pid = t.PID
GROUP BY
 n.cnt,n.pid, t.name
;

SELECT
 SHP,
 eid
FROM
 tmpEdge
WHERE
 eid IN (SELECT eid FROM #node)
;
カテゴリー: 開発 タグ: パーマリンク