2.2.1 属性リストの利用

Next: 2.3 パスの長さ Up: 2.2 コストの表現 Previous: 2.2 コストの表現

2.2.1 属性リストの利用

頂点をシンボルで表現し属性リストに隣接点リストを表現するという例の場合には，隣接点リストの属性リストを変更するのではなく，他の属性を利用するという手が考えられます．ある頂点への辺への距離をデータとして頂点の属性リストに蓄えるには，各隣接点ごとに距離を求めておく必要があります．最初からその距離を登録しておき，使いたいときにそのデータをとり出して来て使うという方法が考えられます．たとえば，


(setq *graph1-with-cost*
          '((a s 5.0) (b a 3.0) (c b 4.0)
            (d a 6.0827627) (d s 4.2426405)
            (e d 3.0) (e b 6.0827627)
            (f e 5.8309517)))

(defun init-graph-cost (ee)
  (mapc
   #'(lambda (e)
       (put (elt e 0) (elt e 1) (elt e 2))
       (put (elt e 1) (elt e 0) (elt e 2)))
   ee))

(defun node-distance (n1 n2)
  (get n1 n2))

というぐあいに，辺間の距離をリストにしたデータから頂点の属性として，属性を隣接する頂点の名前とし，値を距離にするという具合に定義しています．


> (init-graph-cost *graph1-with-cost*)
((a s 5.0) (b a 3.0) (c b 4.0)
 (d a 6.0827627) (d s 4.2426405)
 (e d 3.0) (e b 6.0827627) (f e 5.8309517))

> (get 'a 's)
5.0

> (get 's 'a)
5.0

> (get 's 'b)
nil

> (node-distance 'd 's)
4.2426405

> (node-distance 's 'd)
4.2426405

node-distanceは２つの頂点を与えるとその頂点間の距離を返します．

generated through LaTeX2HTML. M.Inaba 平成18年5月6日