Read 155 times | Created 2013-07-16 03:32:02 | Updated 2013-07-16 09:56:29 | | |

 

-- Struktur tabel-nya adalah sebagai berikut:

DROP TABLE IF EXISTS dijnodes,dijpaths; 
CREATE TABLE dijnodes ( 
  nodeID int PRIMARY KEY AUTO_INCREMENT NOT NULL, 
  nodename varchar (20) NOT NULL, 
  cost int NULL, 
  pathID int NULL, 
  calculated tinyint NOT NULL  
); 

CREATE TABLE dijpaths ( 
  pathID int PRIMARY KEY AUTO_INCREMENT, 
  fromNodeID int NOT NULL , 
  toNodeID int NOT NULL , 
  cost int NOT NULL 
); 

-- Berikut ini adalah 'store procedure' untuk menghasilkan node dan path yang valid:

DROP PROCEDURE IF EXISTS dijAddPath; 
DELIMITER | 
CREATE PROCEDURE dijAddPath(  
  pFromNodeName VARCHAR(20), pToNodeName VARCHAR(20), pCost INT  
) 
BEGIN 
  DECLARE vFromNodeID, vToNodeID, vPathID INT; 
  SET vFromNodeID = ( SELECT NodeID FROM dijnodes WHERE NodeName = pFromNodeName ); 
  IF vFromNodeID IS NULL THEN 
    BEGIN 
      INSERT INTO dijnodes (NodeName,Calculated) VALUES (pFromNodeName,0); 
      SET vFromNodeID = LAST_INSERT_ID(); 
    END; 
  END IF; 
  SET vToNodeID = ( SELECT NodeID FROM dijnodes WHERE NodeName = pToNodeName ); 
  IF vToNodeID IS NULL THEN 
    BEGIN 
      INSERT INTO dijnodes(NodeName, Calculated)  
      VALUES(pToNodeName,0); 
      SET vToNodeID = LAST_INSERT_ID(); 
    END; 
  END IF; 
  SET vPathID = ( SELECT PathID FROM dijpaths  
                  WHERE FromNodeID = vFromNodeID AND ToNodeID = vToNodeID  
                ); 
  IF vPathID IS NULL THEN 
    INSERT INTO dijpaths(FromNodeID,ToNodeID,Cost)  
    VALUES(vFromNodeID,vToNodeID,pCost); 
  ELSE 
    UPDATE dijpaths SET Cost = pCost   
    WHERE FromNodeID = vFromNodeID AND ToNodeID = vToNodeID; 
  END IF; 
END;  
| 
DELIMITER ; 

-- Dengan menggunakan 'store procedure' dijAddpath() dibuatlah daftar path-nya:

call dijaddpath( 'a', 'b',  4 ); 
call dijaddpath( 'a', 'd',  1 ); 
call dijaddpath( 'b', 'a', 74 ); 
call dijaddpath( 'b', 'c',  2 ); 
call dijaddpath( 'b', 'e', 12 ); 
call dijaddpath( 'c', 'b', 12 ); 
call dijaddpath( 'c', 'f', 74 ); 
call dijaddpath( 'c', 'j', 12 ); 
call dijaddpath( 'd', 'e', 32 ); 
call dijaddpath( 'd', 'g', 22 ); 
call dijaddpath( 'e', 'd', 66 ); 
call dijaddpath( 'e', 'f', 76 ); 
call dijaddpath( 'e', 'h', 33 ); 
call dijaddpath( 'f', 'i', 11 ); 
call dijaddpath( 'f', 'j', 21 ); 
call dijaddpath( 'g', 'd', 12 ); 
call dijaddpath( 'g', 'h', 10 ); 
call dijaddpath( 'h', 'g',  2 ); 
call dijaddpath( 'h', 'i', 72 ); 
call dijaddpath( 'i', 'f', 31 ); 
call dijaddpath( 'i', 'j',  7 ); 
call dijaddpath( 'i', 'h', 18 ); 
call dijaddpath( 'j', 'f',  8 ); 

SELECT * FROM dijnodes; 
+--------+----------+------+--------+------------+ 
| nodeID | nodename | cost | pathID | calculated | 
+--------+----------+------+--------+------------+ 
|      1 | a        | NULL |   NULL |          0 | 
|      2 | b        | NULL |   NULL |          0 | 
|      3 | d        | NULL |   NULL |          0 | 
|      4 | c        | NULL |   NULL |          0 | 
|      5 | e        | NULL |   NULL |          0 | 
|      6 | f        | NULL |   NULL |          0 | 
|      7 | j        | NULL |   NULL |          0 | 
|      8 | g        | NULL |   NULL |          0 | 
|      9 | h        | NULL |   NULL |          0 | 
|     10 | i        | NULL |   NULL |          0 | 
+--------+----------+------+--------+------------+ 
SELECT * FROM dijpaths; 
+--------+------------+----------+------+ 
| pathID | fromNodeID | toNodeID | cost | 
+--------+------------+----------+------+ 
|      1 |          1 |        2 |    4 | 
|      2 |          1 |        3 |    1 | 
|      3 |          2 |        1 |   74 | 
|      4 |          2 |        4 |    2 | 
|      5 |          2 |        5 |   12 | 
|      6 |          4 |        2 |   12 | 
|      7 |          4 |        6 |   74 | 
|      8 |          4 |        7 |   12 | 
|      9 |          3 |        5 |   32 | 
|     10 |          3 |        8 |   22 | 
|     11 |          5 |        3 |   66 | 
|     12 |          5 |        6 |   76 | 
|     13 |          5 |        9 |   33 | 
|     14 |          6 |       10 |   11 | 
|     15 |          6 |        7 |   21 | 
|     16 |          8 |        3 |   12 | 
|     17 |          8 |        9 |   10 | 
|     18 |          9 |        8 |    2 | 
|     19 |          9 |       10 |   72 | 
|     20 |         10 |        6 |   31 | 
|     21 |         10 |        7 |    7 | 
|     22 |         10 |        9 |   18 | 
|     23 |          7 |        6 |    8 | 
+--------+------------+----------+------+ 

-- Berikut adalah 'store procedure' untuk menghitung 'shortest path' dalam 6 langkah:
-- * inisialisasi path dengan memberikan nilai NULL pada kolom path pada tabel dijnodes
-- * temukan nodeID yang sesuai dengan parameter masukan
-- * lakukan looping pada semua 'one-step' path yang belum dihitung, dan hitung 'cost' dari masing-masing path tersebut
-- * jika sebuah node tidak pernah dihitung, maka graph tidak valid, sehingga diabaikan saja
-- * tulis 'path' yang diperoleh ke dalam tabel temporary 'map'
-- * query dari tabel temporary 'map' untuk melihat hasilnya

DROP PROCEDURE IF EXISTS dijResolve; 
DELIMITER | 
CREATE PROCEDURE dijResolve( pFromNodeName VARCHAR(20), pToNodeName VARCHAR(20) ) 
BEGIN 
  DECLARE vFromNodeID, vToNodeID, vNodeID, vCost, vPathID INT; 
  DECLARE vFromNodeName, vToNodeName VARCHAR(20); 
  -- null out path info in the nodes table 
  UPDATE dijnodes SET PathID = NULL,Cost = NULL,Calculated = 0; 
  -- find nodeIDs referenced by input params 
  SET vFromNodeID = ( SELECT NodeID FROM dijnodes WHERE NodeName = pFromNodeName ); 
  IF vFromNodeID IS NULL THEN 
    SELECT CONCAT('From node name ', pFromNodeName, ' not found.' );  
  ELSE 
    BEGIN 
      -- start at src node 
      SET vNodeID = vFromNodeID; 
      SET vToNodeID = ( SELECT NodeID FROM dijnodes WHERE NodeName = pToNodeName ); 
      IF vToNodeID IS NULL THEN 
        SELECT CONCAT('From node name ', pToNodeName, ' not found.' ); 
      ELSE 
        BEGIN 
          -- calculate path costs till all are done 
          UPDATE dijnodes SET Cost=0 WHERE NodeID = vFromNodeID; 
          WHILE vNodeID IS NOT NULL DO 
            BEGIN 
              UPDATE  
                dijnodes AS src 
                JOIN dijpaths AS paths ON paths.FromNodeID = src.NodeID 
                JOIN dijnodes AS dest ON dest.NodeID = Paths.ToNodeID 
              SET dest.Cost = CASE 
                                WHEN dest.Cost IS NULL THEN src.Cost + Paths.Cost 
                                WHEN src.Cost + Paths.Cost < dest.Cost THEN src.Cost + Paths.Cost
                                ELSE dest.Cost 
                              END, 
                  dest.PathID = Paths.PathID 
              WHERE  
                src.NodeID = vNodeID 
                AND (dest.Cost IS NULL OR src.Cost + Paths.Cost < dest.Cost) 
                AND dest.Calculated = 0; 
              UPDATE dijnodes SET Calculated = 1 WHERE NodeID = vNodeID; 
              SET vNodeID = ( SELECT nodeID FROM dijnodes 
                              WHERE Calculated = 0 AND Cost IS NOT NULL 
                              ORDER BY Cost LIMIT 1 
                            ); 
            END; 
          END WHILE; 
        END; 
      END IF; 
    END; 
  END IF; 
  IF EXISTS( SELECT 1 FROM dijnodes WHERE NodeID = vToNodeID AND Cost IS NULL ) THEN 
    -- problem,  cannot proceed 
    SELECT CONCAT( 'Node ',vNodeID, ' missed.' ); 
  ELSE 
    BEGIN 
      -- write itinerary to map table 
      DROP TEMPORARY TABLE IF EXISTS map; 
      CREATE TEMPORARY TABLE map ( 
        RowID INT PRIMARY KEY AUTO_INCREMENT, 
        FromNodeName VARCHAR(20), 
        ToNodeName VARCHAR(20), 
        Cost INT 
      ) ENGINE=MEMORY; 
      WHILE vFromNodeID <> vToNodeID DO 
        BEGIN 
          SELECT  
            src.NodeName,dest.NodeName,dest.Cost,dest.PathID 
            INTO vFromNodeName, vToNodeName, vCost, vPathID 
          FROM  
            dijnodes AS dest 
            JOIN dijpaths AS Paths ON Paths.PathID = dest.PathID 
            JOIN dijnodes AS src ON src.NodeID = Paths.FromNodeID 
          WHERE dest.NodeID = vToNodeID; 
          INSERT INTO Map(FromNodeName,ToNodeName,Cost) VALUES(vFromNodeName,vToNodeName,vCost); 
          SET vToNodeID = (SELECT FromNodeID FROM dijPaths WHERE PathID = vPathID); 
        END; 
      END WHILE; 
      SELECT FromNodeName,ToNodeName,Cost FROM Map ORDER BY RowID DESC; 
      DROP TEMPORARY TABLE Map; 
    END; 
  END IF; 
END; 
| 
DELIMITER ; 
CALL dijResolve( 'a','i'); 
+--------------+------------+------+ 
| FromNodeName | ToNodeName | Cost | 
+--------------+------------+------+ 
| a            | b          |    4 | 
| b            | c          |    6 | 
| c            | j          |   18 | 
| j            | f          |   26 | 
| f            | i          |   37 | 
+--------------+------------+------+