9.1 グラフを連結なグラフに分割する手続き

Next: 10 探索木 Up: 9 グラフの比較 Previous: 9 グラフの比較

9.1 グラフを連結なグラフに分割する手続き

任意のグラフを与えて，辺の集合により表現したグラフに分割する手続きgraph-equivalent-graphsを定義してみます．


(defun graph-equivalent-graphs (graph)
  (mapcar
   #'(lambda (x)
       (list 'elist x))
   (equivalent-graphs (graph-edge-list graph))))

(defun equivalent-graphs
           (edges &optional (result nil))
  (cond
   ((null edges) (merge-equivalent-graphs result))
   (t (equivalent-graphs
       (cdr edges)
       (merge-edge-to-edges (car edges) result)))))

(defun merge-edge-to-edges (edge elists)
  (cond
   ((null elists) (list (list edge)))
   ((intersection edge
                 (apply #'append (car elists)))
    (cons (cons edge (car elists)) (cdr elists)))
   (t (cons
        (car elists)
        (merge-edge-to-edges edge (cdr elists))))))

(defun merge-equivalent-graphs (egraphs)
  (cond
   ((null egraphs) nil)
   (t (merge-equivalent-graphs-aux
       (car egraphs)
       (merge-equivalent-graphs (cdr egraphs))))))

(defun merge-equivalent-graphs-aux
             (egraph egraphs-list)
  (cond
   ((null egraphs-list) (list egraph))
   ((egraph-intersection-p egraph (car egraphs-list))
    (merge-equivalent-graphs-aux
       (egraph-union egraph (car egraphs-list))
          (cdr egraphs-list)))
   (t (cons (car egraphs-list)
            (merge-equivalent-graphs-aux
                  egraph (cdr egraphs-list))))))

(defun edge-equal (e1 e2)
  (set-equal e1 e2))
(defun edge-connected-p (e1 e2)
  (intersection e1 e2))
(defun egraph-intersection-p (eg1 eg2)
  (cond
   ((null eg2) nil)
   ((find (car eg2) eg1 :test #'edge-connected-p) t)
   (t (egraph-intersection-p eg1 (cdr eg2)))))
(defun egraph-union (eg1 eg2)
  (cond
   ((null eg2) eg1)
   ((member (car eg2) eg1 :test #'edge-equal)
    (egraph-union eg1 (cdr eg2)))
   (t (cons (car eg2) (egraph-union eg1 (cdr eg2))))))

実行例は，

<cl> (equivalent-graphs '((a b) (b c) (d e) (f e)))
(((F E) (D E)) ((B C) (A B))) 
<cl> (equivalent-graphs '((a b) (c d) (a c)))
(((C D) (A C) (A B))) 

<cl> (setq g '(ELIST ((A B) (D E) (B C) (F E))))
(ELIST ((A B) (D E) (B C) (F E))) 
<cl> (graph-equivalent-graphs g)
((ELIST ((B C) (A B))) (ELIST ((F E) (D E))))

という具合になり，前節のように頂点のリストを返すようにするには，

<cl> (mapcar #'graph-vertex-list
            (graph-equivalent-graphs g))
((C A B) (F D E))

という具合に各グラフにgraph-vertex-listを適用すると得られます．これまで扱ってきたグラフに適用してみると，


<cl> (graph-equivalent-graphs *graph1*)
((ELIST ((E F) (D E) (B E) (B C)
         (A D) (A B) (S D) (S A)))) 
<cl> (graph-equivalent-graphs *graph2*)
((ELIST ((F E) (E B) (E D) (D S)
         (D A) (C B) (B A) (A S)))) 
<cl> (graph-equivalent-graphs *graph3*)
((ELIST ((F E) (E B) (E D) (D S)
         (D A) (C B) (B A) (A S))))

というようにすべて同じグラフの集合に変換されます．

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