algorithm_ch06_graph.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graph\n",
    "\n",
    "## 기초 함수/클래스\n",
    "\n",
    "### listSetEqual\n",
    "\n",
    ": 두 리스트 (A, B)를 비교하여, 두 리스트를 구성하는 리스트가 동일하면 True를  반환한다.\n",
    "\n",
    "파이썬에서 리스트 비교 연산 == 또는 메소트 __eq__()는 리스트를 구성하는 원소들의 순서까지 모두 같아야 동일한 리스트로 간주한다.\n",
    "\n",
    "listSetEqual은 리스트를 하나의 집합으로 간주하여 비교하기 때문에 리스트를 구성하는 원소의 순서는 고려하지 않는다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def listSetEqual(A, B):\n",
    "    if len(A) != len(B):\n",
    "        return False\n",
    "    else:\n",
    "        C = B.copy()\n",
    "        for x in A:\n",
    "            if x not in C:\n",
    "                return False\n",
    "            else:\n",
    "                C.remove(x)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Queue\n",
    "\n",
    "리스트를 큐로 이용하여 데이터를 관리한다.\n",
    "\n",
    "* enQueue: 데이터 저장\n",
    "* deQueue: 데이터 추출"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.queue=[]\n",
    "        \n",
    "    def enQueue(self, data):        \n",
    "        self.queue.append(data)\n",
    "\n",
    "    def deQueue(self):\n",
    "        data = self.queue[0]\n",
    "        del self.queue[0]    \n",
    "        return data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 정점(Vertex)\n",
    "\n",
    "정점을 구성하는 클래스 변수는 다음과 같다\n",
    "\n",
    "* daga\n",
    "* adjacenyList: 해당 정점을 진출 정점으로 하는 간선(Edge)들의 집합. 무향 그래프의 경우, 간선의 source를 기준으로 정점의 인접리스트에 등록한다. 즉, 간선의 destination의 인접리스트에는 등록하지 않는다 (향후 수정 예정)\n",
    "\n",
    "알고리즘 구현 시 사용되는 선택적 정보(option field)는 다음과 같다\n",
    "* index\n",
    "* visited: 탐색 시, 해당 정점을 탐색했는지 여부를 기록한다. 해당 필드의 값이  True이면, 알고리즘에 의해서 해당 정점이 이미 탐색되었음을 의미한다.\n",
    "* value: 알고리즘 구현 시, 해당 정점을 사용하기 위한 소요/필요 비용을 의미한다. \n",
    "* tree: 트리 구성 시, 해당 정점을 진입 정점으로 하는 간선의 진출 정점을 의미한다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Vertex:\n",
    "    def __init__(self, data=0):\n",
    "        \n",
    "        self.data = data\n",
    "        self.adjacencyList =[]\n",
    "        \n",
    "        self.index = -1\n",
    "        self.visited = False\n",
    "        self.value = 0\n",
    "        self.tree  = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 간선(Edge)\n",
    "\n",
    "* source: 간선을 구성하는 진출 정점\n",
    "* destination: 간선을 구성하는 진입 정점\n",
    "* weight: 간선의 가중치"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Edge:\n",
    "    def __init__(self, source: Vertex, destination: Vertex, weight=0):\n",
    "        self.source         = source\n",
    "        self.destination    = destination\n",
    "        self.weight         = weight   \n",
    "        \n",
    "    def changeWeight(self, weight):\n",
    "        self.weight = weight"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 그래프 클래스\n",
    "\n",
    "### 클래스 변수\n",
    "* vertexList\n",
    "* numOfVertex\n",
    "* dir: 유향 그래프 (True)와 무향 그래프 (False)를 구분한다.\n",
    "\n",
    "### 클래스 함수\n",
    "\n",
    "* addVertex\n",
    "* removeVertex: 그래프에서 정점을 제거한다. 주의: 제거되는 정점이 간선의 진입정점인 경우가 있을 수 있으므로, 그래프믜 모든 간선들을 확인하여 제거되는 정점을 포함하는 간선도 함께 삭제해야 한다. 또한 파이썬 리스트에서 반복문을 사용하여 순차적으로 원소를 검색하고 remove()를 사용하여 리스트의 원소를 제거할 때 i번째 원소가 제거되면 i+1 번째 원소가 i번째 원소가 된다. 이 경우, 반복문에서 기존 i+1번째 원소가 반복 수행에서 빠질 수 있으므로 주의해야 하낟.\n",
    "* addEdge\n",
    "* removeEdge\n",
    "* breadthFirstSearch: 너비우선탐색 (BFS). 현재 교재를 기반으로 구현된 알고리즘은 유향 그래프에서 탐색의 결과 트리에 진입노드로 연결된 정점과 연결되지 않은 정점은 탐색되지 않는다 (향후 수정 예정)\n",
    "* depthFirstSearch: 깊이우선탐색 (DFS)\n",
    "* mst_prim: 최소신장트리를 생성하기 위한 프림 알고리즘"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graph:\n",
    "    def __init__(self, dir=True):\n",
    "        self.vertexList=[]\n",
    "        self.numOfVertex=0\n",
    "        self.dir = dir\n",
    "        \n",
    "    def addVertex(self, vertex: Vertex):\n",
    "        if vertex == None:\n",
    "            return\n",
    "        if type(vertex) != Vertex:\n",
    "            return\n",
    "        self.vertexList.append(vertex)\n",
    "        self.numOfVertex += 1\n",
    "        \n",
    "    def removeVertex(self, vertex: Vertex):\n",
    "        \n",
    "        if vertex == None:\n",
    "            return \n",
    "        \n",
    "        if type(vertex) != Vertex:\n",
    "            return\n",
    "        \n",
    "        if vertex not in self.vertexList :\n",
    "            return\n",
    "        \n",
    "        #양방향 그래프를 고려해서 vertex가 destination인 edge가 있는지 확인 필요\n",
    "        for v in self.vertexList:\n",
    "            if v == vertex:\n",
    "                continue\n",
    "            \n",
    "            index = 0\n",
    "            length = len(v.adjacencyList)\n",
    "            while index < length:\n",
    "                edge = v.adjacencyList[index]\n",
    "                if edge.destination == vertex:\n",
    "                    v.adjacencyList.remove(edge)\n",
    "                    length -=1\n",
    "                else:\n",
    "                    index += 1\n",
    "            \n",
    "        self.vertexList.remove(vertex)\n",
    "        self.numOfVertex -= 1\n",
    "        \n",
    "           \n",
    "    def addEdge(self, edge: Edge):\n",
    "        if edge == None:\n",
    "            return \n",
    "        if type(edge) != Edge:\n",
    "            return\n",
    "        \n",
    "        try:\n",
    "            index = self.vertexList.index(edge.source)\n",
    "        except:\n",
    "            return \n",
    "        \n",
    "        vertex = self.vertexList[index]\n",
    "        vertex.adjacencyList.append(edge)\n",
    "        \n",
    "    def removeEdge(self, edge: Edge):\n",
    "        \n",
    "        if edge == None:\n",
    "            return\n",
    "        \n",
    "        if type(edge) != Edge:\n",
    "            return\n",
    "        \n",
    "        if edge.source not in self.vertexList :\n",
    "            return \n",
    "        \n",
    "        if edge.destination not in self.vertexList :\n",
    "            return \n",
    "        \n",
    "        if edge not in edge.source.adjacencyList :       \n",
    "            return\n",
    "        \n",
    "        edge.source.adjacencyList.remove(edge)\n",
    "        \n",
    "    #유향 그래프에서의 탐색만 가능\n",
    "    #start로부터 연결된 path가 없는 vertex는 탐색할 수 없\n",
    "    def breadthFirstSearch(self, start: Vertex):  \n",
    "        if type(start) != Vertex:\n",
    "            return \n",
    "        if start not in self.vertexList:\n",
    "            return \n",
    "        \n",
    "        for v in self.vertexList:\n",
    "            if v == start:\n",
    "                v.visited = True\n",
    "            else:\n",
    "                v.visited = False\n",
    "        \n",
    "        queue=Queue()\n",
    "        queue.enQueue(start)\n",
    "        \n",
    "        while len(queue.queue) > 0:\n",
    "            u = queue.deQueue()\n",
    "            for edge in u.adjacencyList:\n",
    "                v = edge.destination\n",
    "                if v.visited == False:\n",
    "                    v.visited = True\n",
    "                    queue.enQueue(v)\n",
    "        \n",
    "    \n",
    "    def _dfs(self, vertex: Vertex):\n",
    "        vertex.visited = True\n",
    "        for edge in vertex.adjacencyList:\n",
    "            if edge.destination.visited == False:\n",
    "                self._dfs(edge.destination)\n",
    "    \n",
    "    def depthFirstSearch(self):\n",
    "        for v in self.vertexList:\n",
    "            v.visited = False\n",
    "            \n",
    "        for v in self.vertexList:\n",
    "            if v.visited == False:\n",
    "                self._dfs(v)\n",
    "    \n",
    "    \n",
    "    def _extractMinValue(self, vertexSet):\n",
    "        \n",
    "        minVertex = vertexSet[0]\n",
    "        for v in vertexSet:\n",
    "            if minVertex.value > v.value:\n",
    "                minVertex = v\n",
    "        return minVertex\n",
    "    \n",
    "    def mst_prim(self, root: Vertex, maxValue=100000000):\n",
    "        \n",
    "        if root not in self.vertexList:\n",
    "            return \n",
    "        \n",
    "        vertexSet=[]\n",
    "        \n",
    "        for v in self.vertexList:\n",
    "            v.value = maxValue\n",
    "        root.value = 0\n",
    "        \n",
    "        \n",
    "        difference = self.vertexList.copy()\n",
    "        # vertextSet.__eq__(self.vertexList)는 원소의 순서까지 맞아야 True이다.\n",
    "        # 리스트에서 == 연산도 마찬가지로 순서까지 확인한다.\n",
    "        while listSetEqual(vertexSet, self.vertexList) == False :            \n",
    "            u = self._extractMinValue(difference)\n",
    "            vertexSet.append(u)    # S = S + {u}\n",
    "            difference.remove(u)    # D = V-S\n",
    "            for edge in u.adjacencyList:\n",
    "                if edge.destination in difference:\n",
    "                    if edge.destination.value > edge.weight: \n",
    "                        edge.destination.value = edge.weight\n",
    "                        edge.destination.tree  = u \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}