그래프 표현하기

그래프 표현하기¶

그래프를 그릴 때는 일반적으로 노드를 동그라미나 사각형으로, 연결선을 선으로 그린다.

위 그래프에서 연결선들의 가중치는 미국 동북부 도시들 간의 대략적인 이동시간을 나타낸다. 이 경우, 노드의 배치는 도시들의 대략적인 지리적 위치를 반영하고 있지만, 일반적으로 그래프의 레이아웃은 임의로 배치된다.

그래프 알고리즘을 구현하기 위해서, 여러분은 그래프를 데이터 구조의 형식으로 나타내는 법을 알아야 한다. 그러나 가장 좋은 데이터 구조를 선택하기 위해서는 그래프가 어떤 작업들을 지원해야 하는지를 먼저 알아야 한다.

이 같은 닭이 먼저냐 달걀이 먼저냐 하는 문제에서, 여러 가지 그래프 알고리즘에 쓰기 좋은 그래프 구조를 먼저 보여주고자 한다. 이후에 이 구조로 다시 돌아와 장단점을 평가해 보겠다.

다음은 다수의 딕셔너리로 이루어진 딕셔너리 구조로 그래프를 구현한 것이다.

In [13]:

class Graph(dict):
    def __init__(self, vs=[], es=[]):
        '''새로운 그래프를 만든다. (vs)는 노드의 리스트다
        (es)는 연결선 리스트다'''
        for v in vs:
            self.add_vertex(v)
        for e in es:
            self.add_edge(e)
    def add_vertex(self,v):
        ''' (v)를 그래프에 추가한다.'''
        self[v] = {}
    def add_edge(self,e):
        """양방향으로 (e)를 그래프에 추가한다.
        
        이미 두 노드를 잇는 연결선이 존재한다면,
        새로운 노드가 그것을 대체한다.
        """
        
        v, w = e
        self[v][w] = e
        self[w][v] = e

class Graph(dict):<br>

첫번째 줄은 Graph가 내장된 자료형 dict를 상속한다고 선언하고, 따라서 Graph 객체는 사전의 모든 연산자와 메소드를 갖게 된다.

더 자세히 말하면, Graph클래스에서는 외부 딕셔너리 안에 내부 딕셔너리가 들어있고, 외부 딕셔너리의 키인 Vertex v의 값은 내부 딕셔너리이며, 내부 딕셔너리의 키인 Vertex w의 값으로는 w와 v를 연결하는 Edge가 들어있는 것이다. 그래서 만약 g가 그래프 객체라면, g[v][w]는 연결선이 존재하는 경우 매핑이 된다. 그렇지 않으면 KeyError를 일으키게 된다.

def __init__(self, vs=[], es=[]):<br>

__init__은 노드 리스트와 연결선 리스트를 선택적 인자로 받는다. 인자를 넣어주는 경우, add_vertex와 add_edge를 호출해서 그래프에 노드와 연결선이 추가된다.    

노드를 그래프에 추가한다는 것은 외부 딕셔너리에 그 노드에 대한 항목을 만든다는 뜻이다. 연결선을 하나 추가한다는 의미는 동일한 연결선을 가리키는 두 개의 항목을 추가하게 되는 것이므로, 구현되는 그래프는 무방향 그래프가 된다.

다음은 노드에 대한 정의이다.

In [14]:

class Vertex(object):
    def __init__(self, label=''):
        self.label = label
    def __repr__(self):
        return 'Vertex(%s)' % repr(self.label)
    
    __str__ = __repr__

class Vertex(object):

Vertex는 라벨 속성을 가지는 객체이다. 필요하게 되면 추후에 속성들을 추가할 수 있다.

def __repr__(self):
    return 'Vertex(%s)' % repr(self.label)

__repr__은 객체를 문자열로 표현해 반환하는 특수한 함수다. __str__과 유사하지만, __str__이 사람이 읽을 목적으로 값을 반환한다면 __repr__은 파이썬의 공식 표현값을 반환한다는 차이가 있다. 

내장 함수인 str은 객체를 대상으로 __str__를 불러와 작동시킨다. 이와 유사하게 내장 함수 repr는 __repr__를 호출한다.

이 경우, Vertex.__str과 Vertex.__repr__은 동일한 함수를 지칭하므로 어떤 것을 사용하든 같은 문자열을 얻게 된다.

다음은 Edge의 정의이다.

In [18]:

class Edge(tuple):
    def __new__(cls, e1, e2):
        return tuple.__new__(cls,(e1,e2))
    
    def __repr__(self):
        return 'Edge(%s, %s)' % (repr(self[0]), repr(self[1]))
    
    __str__ = __repr__

class Edge(tuple):
    def __new__(cls, e1, e2):
        return tuple.__new__(cls,(e1,e2))

Edge는 내장 자료형인 tuple(튜플)을 상속하고, __new__메소드를 재정의한다. 일반적으로 여러분이 객체 생성자를 호출할 때, 파이썬은 __new__를 불러와서 객체를 생성한 뒤 __init__를 통해 속성들을 초기화한다.

변경 가능한 객체들에서 __init__를 재정의하고 __new__의 기본 구현값을 사용하는 것은 매우 흔한 일이지만, EDge는 튜플에서 상속을 받기 때문에 변경이 불가능한 객체다. 다시 말해 __init__에서 튜플의 원소들을 변경할 수 없다는 뜻이다. 그래서 __new__를 덮어씀으로써 우리는 인자들을 사용해 튜플의 원소들을 초기화할 수 있는 것이다.

다음은 두 개의 노드와 연결선 하나를 생성하는 예제다.

In [27]:

v = Vertex('v')
w = Vertex('w')
e = Edge(v, w)
print(e)

Edge(Vertex('v'), Vertex('w'))

Edge.__str__내부에서 self[0]이라는 용어는 v를 지칭하며 self[1]는 w를 지칭한다.

이제 우리는 연결선과 노드를 모아서 그래프로 만들 수 있다.

In [28]:

g = Graph([v, w], [e])
print(g)

{Vertex('v'): {Vertex('w'): Edge(Vertex('v'), Vertex('w'))}, Vertex('w'): {Vertex('v'): Edge(Vertex('v'), Vertex('w'))}}

결과는 약간의 포매팅을 거친 것이다.

참고로 우리가 Graph.__str__를 굳이 쓸 필요는 없었다. dict에서 자동으로 상속되기 때문이다.

출처: 복잡계와 데이터 과학