Fully Dynamic Algorithms for Maintaining Shortest Paths Trees 리뷰 #2 - 중간 점검 output information 구현해보기

안녕하세요. 이번에는 Fully Dynamic Algorithms for Maintaining Shortest Paths Trees 논문 공부의 중간 점검을 위해서 output information 구하는 코드를 직접 작성해봤습니다.

 

bellman ford 알고리즘과 floyd warshall 알고리즘을 기반으로 output information을 만들어 봤습니다.

• bellman ford 알고리즘 - dijkstra 알고리즘 다음은 bellman ford죠!
• floyd warshall 알고리즘 - 이 정도는 되야 지도를 외웠다고 할 수 있죠!

 

bellman ford, floyd warshall 알고리즘을 공부할 때도 최단 경로값과 최단 경로 트리 비슷하게 값을 반환하기는 했었습니다만

이번에는 조금 더 정돈된 결과값을 반환해보겠습니다.

 

예제 지도

 

1. bellman ford 알고리즘 + output information

import pprint
from dataclasses import dataclass
from typing import List, Dict, Set


@dataclass
class Node:
    id: int
    is_visited: bool = False


@dataclass
class Edge:
    id: int
    start_node: Node
    end_node: Node
    weight: float

    def get_weight(self) -> float:
        return self.weight

    def set_weight(self, weight: float):
        self.weight = weight

    def get_other_node(self, node_id: int) -> Node:
        if self.start_node.id == node_id:
            return self.end_node
        else:
            return self.start_node


@dataclass
class Graph:
    nodes: dict
    adjacent_edges: dict

    def get_node(self, node_id: int) -> Node:
        return self.nodes[node_id]

    def set_node_visited(self, node_id: int):
        self.nodes[node_id].is_visited = True

    def get_connected_nodes(self, node_id: int) -> List[Node]:
        adjacent_edges = self.adjacent_edges.get(node_id, [])
        return [edge.get_other_node(node_id) for edge in adjacent_edges]

    def get_adjacent_edges(self, node_id: int) -> List[Edge]:
        return self.adjacent_edges.get(node_id, [])


class Tree:
    def __init__(self, value: Node):
        self.value: Node = value
        self.parent: "Tree" | None = None
        self.children: Set["Tree"] = set()

    def set_parent(self, parent: "Tree"):
        if self.parent is not None:
            self.parent.remove_child(self)

        self.parent = parent

        self.parent.add_child(self)

    def add_child(self, child: "Tree"):
        self.children.add(child)

    def remove_child(self, child: "Tree"):
        self.children.remove(child)


def make_output_information(graph, source_node):
    shortest_distance_dict = {}
    tree_dict = {}
    for node in graph.nodes.values():
        shortest_distance_dict[node.id] = float("inf")
        tree_dict[node.id] = Tree(node)
    shortest_distance_dict[source_node.id] = 0

    for node in graph.nodes.values():
        for edge in graph.get_adjacent_edges(node.id):
            new_distance = shortest_distance_dict[edge.start_node.id] + edge.get_weight()
            if new_distance >= shortest_distance_dict[edge.end_node.id]:
                continue

            shortest_distance_dict[edge.end_node.id] = new_distance

            start_tree = tree_dict[edge.start_node.id]
            end_tree = tree_dict[edge.end_node.id]
            end_tree.set_parent(start_tree)

    return shortest_distance_dict, tree_dict[source_node.id]


if __name__ == "__main__":
    nodes = {}
    for i in range(6):
        nodes[i + 1] = Node(id=i + 1)

    adjacent_edges = {}
    adjacent_edges[1] = [Edge(1, start_node=nodes[1], end_node=nodes[2], weight=3)]
    adjacent_edges[1] += [Edge(2, start_node=nodes[1], end_node=nodes[3], weight=1)]
    adjacent_edges[2] = [Edge(3, start_node=nodes[2], end_node=nodes[4], weight=1)]
    adjacent_edges[2] += [Edge(4, start_node=nodes[2], end_node=nodes[5], weight=1)]
    adjacent_edges[2] += [Edge(5, start_node=nodes[2], end_node=nodes[6], weight=10)]
    adjacent_edges[3] = [Edge(6, start_node=nodes[3], end_node=nodes[4], weight=1)]
    adjacent_edges[5] = [Edge(7, start_node=nodes[5], end_node=nodes[6], weight=1)]

    graph = Graph(nodes=nodes, adjacent_edges=adjacent_edges)
    shortest_path_dict, shortest_path_tree = make_output_information(graph, nodes[1])
    pprint.pprint(shortest_path_dict)

    queue = [shortest_path_tree]
    while len(queue) > 0:
        node = queue.pop(0)
        msg = ""
        if node.parent is not None:
            msg += f"{node.parent.value.id}"
        else:
            msg += "root"
        msg += f" -> {node.value.id}"
        print(msg)
        for child in node.children:
            queue.append(child)

스크립트 실행 결과

 

2. floyd warshall 알고리즘 + output information

import pprint
from dataclasses import dataclass
from typing import List, Dict, Set


@dataclass
class Node:
    id: int
    is_visited: bool = False


@dataclass
class Edge:
    id: int
    start_node: Node
    end_node: Node
    weight: float

    def get_weight(self) -> float:
        return self.weight

    def set_weight(self, weight: float):
        self.weight = weight

    def get_other_node(self, node_id: int) -> Node:
        if self.start_node.id == node_id:
            return self.end_node
        else:
            return self.start_node


@dataclass
class Graph:
    nodes: dict
    adjacent_edges: dict

    def get_node(self, node_id: int) -> Node:
        return self.nodes[node_id]

    def set_node_visited(self, node_id: int):
        self.nodes[node_id].is_visited = True

    def get_connected_nodes(self, node_id: int) -> List[Node]:
        adjacent_edges = self.adjacent_edges.get(node_id, [])
        return [edge.get_other_node(node_id) for edge in adjacent_edges]

    def get_adjacent_edges(self, node_id: int) -> List[Edge]:
        return self.adjacent_edges.get(node_id, [])


class Tree:
    def __init__(self, value: Node):
        self.value: Node = value
        self.parent: "Tree" | None = None
        self.children: Set["Tree"] = set()

    def set_parent(self, parent: "Tree"):
        if self.parent is not None:
            self.parent.remove_child(self)

        self.parent = parent

        self.parent.add_child(self)

    def add_child(self, child: "Tree"):
        self.children.add(child)

    def remove_child(self, child: "Tree"):
        self.children.remove(child)


def make_output_information(graph):
    shortest_distance_dict = {}
    tree_dict = {}
    for node in graph.nodes.values():
        shortest_distance_dict[node.id] = {}
        tree_dict[node.id] = {}
        for other_node in graph.nodes.values():
            if node.id != other_node.id:
                shortest_distance_dict[node.id][other_node.id] = float("inf")
            else:
                shortest_distance_dict[node.id][other_node.id] = 0
            tree_dict[node.id][other_node.id] = Tree(other_node)
        
        for adjacent_edge in graph.get_adjacent_edges(node.id):
            other_node = adjacent_edge.get_other_node(node.id)
            shortest_distance_dict[node.id][other_node.id] = adjacent_edge.get_weight()

            start_tree = tree_dict[node.id][node.id]
            end_tree = tree_dict[node.id][other_node.id]
            end_tree.set_parent(start_tree)

    for pivot_node in graph.nodes.values():
        for start_node in graph.nodes.values():
            for end_node in graph.nodes.values():
                new_distance = shortest_distance_dict[start_node.id][pivot_node.id] + shortest_distance_dict[pivot_node.id][end_node.id]
                if new_distance >= shortest_distance_dict[start_node.id][end_node.id]:
                    continue

                shortest_distance_dict[start_node.id][end_node.id] = new_distance
                start_tree = tree_dict[start_node.id][start_node.id]
                pivot_tree = tree_dict[start_node.id][pivot_node.id]
                end_tree = tree_dict[start_node.id][end_node.id]
                end_tree.set_parent(pivot_tree)

    return shortest_distance_dict, tree_dict


if __name__ == "__main__":
    nodes = {}
    for i in range(6):
        nodes[i + 1] = Node(id=i + 1)

    adjacent_edges = {}
    adjacent_edges[1] = [Edge(1, start_node=nodes[1], end_node=nodes[2], weight=3)]
    adjacent_edges[1] += [Edge(2, start_node=nodes[1], end_node=nodes[3], weight=1)]
    adjacent_edges[2] = [Edge(3, start_node=nodes[2], end_node=nodes[4], weight=1)]
    adjacent_edges[2] += [Edge(4, start_node=nodes[2], end_node=nodes[5], weight=1)]
    adjacent_edges[2] += [Edge(5, start_node=nodes[2], end_node=nodes[6], weight=10)]
    adjacent_edges[3] = [Edge(6, start_node=nodes[3], end_node=nodes[4], weight=1)]
    adjacent_edges[5] = [Edge(7, start_node=nodes[5], end_node=nodes[6], weight=1)]

    graph = Graph(nodes=nodes, adjacent_edges=adjacent_edges)
    shortest_path_dict, shortest_path_tree = make_output_information(graph)
    pprint.pprint(shortest_path_dict)

    for source_node in graph.nodes.values():
        queue = [shortest_path_tree[source_node.id][source_node.id]]
        while len(queue) > 0:
            tree = queue.pop(0)
            msg = ""
            if tree.parent is not None:
                msg += f"{tree.parent.value.id}"
            else:
                msg += "root"
            msg += f" -> {tree.value.id}"
            print(msg)
            for child in tree.children:
                queue.append(child)
        print("=========================")

 

스크립트 실행 결과

 

🎁 Fully Dynamic Algorithms for Maintaining Shortest Paths Trees 이전 리뷰들 🎁

• Fully Dynamic Algorithms for Maintaining Shortest Paths Trees 리뷰 #1 - 논문을 읽게 된 이유 및 용어 정리

---

나중에 논문의 edge update에 따른 최단 경로 값, 최단 경로 트리 수정 알고리즘을 구현하면 위에서 만든 스크립트를 기반으로 개선된 속도를 측정해보려고 합니다.

 

열심히 공부해봐야겠네요!