情報基礎「Pythonプログラミング」（ステップ９・クラス・グラフのマッチング）

Pythonプログラミング（ステップ９・クラスとオブジェクト・グラフのマッチング）

このページでは、オブジェクトを使った例として、テキストの「4.4 学生を配属する」の実装について考える。

１．学生配属問題

参考書の「4.4 学生を配属する」(p.134)では、人数制限のある複数の授業に、最大限に本人の希望を汲み入れながら、学生を振り分ける方法について述べられている。ここでは、その内容を繰り返すことはしないが、解くべき問題を要約すると、

$N$人の新入生の集合がある：$X=\{ x_1, x_2, \cdots, x_N\}$
$M$個の授業（クラス）があって（$C = \{ c_1, c_2, \cdots, c_M\}$）、各クラスには定員が設けられている。ここで、クラス$c$の定員を $m(c)$ とする。
学生毎に最大$L$まで、配属の希望を出すことができる。
これらの条件のもとで、希望先に配属される学生の数が最大となるように、学生の配属先をひとつずつ決める。

となる。

もちろん、学生の希望が100%叶うとは限らない。極端な場合、全員がひとつのクラスを希望し、クラス定員が学生数より少なければ、多くの者は、希望しないクラスに配属せざるを得ない。

２．データの表現

まず、新入生の集合をPythonのリストで表すことにしよう。汎用性を持たせ、氏名以外の属性（配属先希望など）も扱えるよう、Studentというクラスを定義してみる：

L=2
class Student:
	def __init__(self,name,choices):
		self.name=name
		self.choices=choices   # 配属先希望リスト
		if len(choices)>L:
			print("希望数が多すぎます")

次に、授業のほうは（Classというクラスを使いたいところではあるが、名前が衝突するので）Lessonというクラスを使って

class Lesson:
	def __init__(self,title,capacity):
		self.title=title
		self.capacity=capacity # 定員

としてみる。すると、参考書図4.8の状況は

c1 = Lesson("数学",1)
c2 = Lesson("天文学",2)
c3 = Lesson("心理学",2)
c4 = Lesson("医学",1)

C = [c1,c2,c3,c4]

x1 = Student("城島",[c1,c2])
x2 = Student("山口",[c2,c3])
x3 = Student("国分",[c1,c4])
x4 = Student("松岡",[c2,c4])
x5 = Student("長瀬",[c3,c4])

X = [x1,x2,x3,x4,x5]

のようなコードで表現できる。

３．配属数が１のダミーの授業に分解する

続いて、定員が $m$ のクラスを、定員1で $m$ 個の（ダミーの）クラスに「分解」する。以下のコードでは、ダミーのクラスがリスト CP に生成される：

リスト.extend(別のリスト)で、「リスト」に「別のリスト」が連結される

import copy

CP=[ ]
for c in C:
    newlist=[ ]
    for i in range(c.capacity):
        cp = copy.copy(c)
        cp.capacity=1
        newlist.append(cp)
    CP.extend(newlist)
    for x in X:
        for z in x.choices:
            if z is c:
                x.choices.remove(z)
                x.choices.extend(newlist)
                break

ここで、オブジェクトをコピーする際の重要な注意点がある。変数cにオブジェクトがセットされているとき、代入 cp = c を行っても、そのオブジェクトの複製が生成されるわけではない。変数にセットされているのは、オブジェクトの参照先（オブジェクトがどこにあるか）なので、「住所」だけコピーしても、オブジェクト（家）が複製されるわけではない。

ここでは「浅いコピー」を行っている

上のコードでは、オブジェクトそのものの複製を生成したいので、代わりにcp = copy.copy(c)と記述している。 copyモジュールを使うことで、オブジェクトの実体を複製し、その参照先を cp にセットできる。そうして、新たなリスト CP の各オブジェクトは、定員１名ずつの新しいLessonクラスのオブジェクトが格納されてる。

４．データから「変形配属希望グラフ」を生成する

「配属先希望グラフ」を表現するために、二部グラフを表現するクラスを定義する。ここで、uは「左側」、vは「右側」の頂点に対応づけることを想定している。

class BGraph:
    """a bipartile graph representation by Python """
    class Vertex:
        def __init__(self,name):
            self.name=name
            self.link=[ ]  # list of [Vertex]
            self.label=None

    def __init__(self):
        self.us=[ ]
        self.vs=[ ]

    def create_vertex_u(self,name):
        u = BGraph.Vertex(name)
        self.us.append(u)

    def create_vertex_v(self,name):
        v = BGraph.Vertex(name)
        self.vs.append(v)

    def append_link(self,v,a):
        if a in v.link:
            print("already connected")
        else:
            v.link.append(a)

    def connect_vertex(self,u,v):
        self.append_link(u,v)
        self.append_link(v,u)

このようにクラスBGraphを定義すると、学生の希望リスト$X$と授業のリスト$CP$（定員１名）を使って、以下のコードで二部グラフが生成できる。

dict={}
for c in CP:
    v = g.create_vertex_v(c.title)
    dict[c]=v

for x in X:
    u = g.create_vertex_u(x.name)
    for c in x.choices:
        v = dict[c]
        g.connect_vertex(u,v)

ここで、希望リスト中のLessonクラスのオブジェクトと、BGraph中のVertexクラスのオブジェクトとの対応関係を記憶しておくため、「辞書」dictを用いている。

５．グラフの最大マッチングを求める

ここでは、教科書で説明されている$M-$交互道のアイデアに沿って、最大マッチングを求めるコードをさらに追加した例を示す。これまでに登場したコードも中に含まれる。

# coding: utf-8

import copy

L=2
class Student:
    def __init__(self,name,choices):
        self.name=name
        self.choices=choices   # 配属先希望リスト
        if len(choices)>L:
            print("希望数が多すぎます")

class Lesson:
    def __init__(self,title,capacity):
        self.title=title
        self.capacity=capacity # 定員

class BGraph:
    """a bipartile graph representation by Python """
    class Vertex:
        def __init__(self,name):
            self.name=name
            self.link=[ ]  # list of [Vertex]
            self.label=None

    def __init__(self):
        self.us=[ ]  # list of U
        self.vs=[ ]  # list of V

    def create_vertex_u(self,name):
        u = BGraph.Vertex(name)
        self.us.append(u)
        return u

    def create_vertex_v(self,name):
        v = BGraph.Vertex(name)
        self.vs.append(v)
        return v

    def append_link(self,v,a):
        if a in v.link:
            print("already connected")
        else:
            v.link.append(a)

    def connect_vertex(self,u,v):
        self.append_link(u,v)
        self.append_link(v,u)

    def is_in_u(self,x):
        if x in self.us:
            return True
        else:
            return False

    def is_in_v(self,x):
        if x in self.vs:
            return True
        else:
            return False

    def remove_all_labels(self):
        for x in self.us:
            x.label=None
        for x in self.vs:
            x.label=None

# a Python version of the algorithm described in
# http://www.csl.mtu.edu/cs4321/www/Lectures/
# Lecture%2022%20-%20Maximum%20Matching%20in%20Bipartite%20Graph.htm
    def perform_matching(self):
        matching=[ ]
        queue=[x for x in self.vs]
        while len(queue)>0:
            w = queue.pop()
            if self.is_in_v(w):
                for u in w.link:
                    u_matched=set()
                    for x,y in matching:
                        u_matched.add(y)
                    if u not in u_matched:
                        matching.append([w,u])
                        v=w
                        while v.label is not None:
                            u = v.label
                            matching.remove([v,u])
                            v = u.label
                            matching.append([v,u])
                        self.remove_all_labels()
                        v_matched=set()
                        for x,y in matching:
                            v_matched.add(x)
                        v_free = set(self.vs) - v_matched
                        queue=list(v_free)
                        break
                    else:
                        if ([w,u] not in matching) and u.label is None:
                            u.label = w
                            queue.append(u)
            else:
                for v,u in matching:
                    if u is w:
                        v.label = w
                        queue.append(v)
                        break
        return matching
# end of BGraph

# メイン部

c1 = Lesson("数学",1)
c2 = Lesson("天文学",2)
c3 = Lesson("心理学",2)
c4 = Lesson("医学",1)

C = [c1,c2,c3,c4]

x1 = Student("城島",[c1,c2])
x2 = Student("山口",[c2,c3])
x3 = Student("国分",[c1,c4])
x4 = Student("松岡",[c2,c4])
x5 = Student("長瀬",[c3,c4])

X = [x1,x2,x3,x4,x5]

# 各クラスを定員１名に分解し、CPにセットする
CP=[ ]
for c in C:
    newlist=[ ]
    for i in range(c.capacity):
        cp = copy.copy(c)
        cp.capacity=1
        newlist.append(cp)
    CP.extend(newlist)
    for x in X:
        for z in x.choices:
            if z is c:
                x.choices.remove(z)
                x.choices.extend(newlist)
                break

# XとCPから二部グラフを生成する
g = BGraph()
dict={}
for c in CP:
    v = g.create_vertex_v(c.title)
    dict[c]=v

for x in X:
    u = g.create_vertex_u(x.name)
    for c in x.choices:
        v = dict[c]
        g.connect_vertex(u,v)

# 最大マッチングを求める
matching=g.perform_matching()

# 結果を出力する
for v,u in matching:
    print(u.name,"--",v.name)

　練習：コードの動作確認

仮の学生とクラスを想定し、上記のコードをそれに合わせて変更した上で、動作確認を行いなさい。