• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Label Correction Algorithm

Contents

  • Pseudocode
  • Python
  • Examples
  • See also

The label-correction algorithm is a generalization which includes very common graph search algorithms like breadth first search (BFS), depth first search (DFS), A*, Dijkstra's algorithm and Branch and bound as special cases.

Pseudocode

Pseudocode for the Label correction algorithm
Pseudocode for the Label correction algorithm


Explanation:

First if: The left hand side is a lower bound to get from start to v, to c and then to t. If this lower bound is not lower than either u or the distance to c directly, then it will not be part of the optimal solution.

Special cases:

  • Depth-first search: K is LIFO list / Stack
  • Breadth-first search: K is FIFO list
  • Dijkstra's algorithm: K is priority queue
  • A*: K ist priority queue, \(h_j\) is non-trivial
  • Branch and bound: K ist priority queue, \(h_j\) and \(m_j\) are non-trivial

Python

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#!/usr/bin/env python

"""Label Correction algorithm."""


import logging
import sys

logging.basicConfig(format='%(asctime)s %(levelname)s %(message)s',
                    level=logging.DEBUG,
                    stream=sys.stdout)


class LIFO(list):
    """A LIFO storage."""

    def insert(self, el):
        self.append(el)


class Graph(object):
    """An undirected graph."""

    def __init__(self):
        self.nodes = []
        self.edges = []
        self.name2index = {}
        self.index2name = {}
        self.neighbors = []

    def add_node(self, name=None):
        """Add a new node and return its index."""
        node_index = len(self.nodes)
        if name.startswith('index-'):
            logging.warning('Node names beginning with "index-" may cause '
                            'problems.')
        if name is None:
            name = "index-%i" % node_index
        self.nodes.append(node_index)
        self.name2index[name] = node_index
        self.index2name[node_index] = name

        # Add weight from new node to other nodes and vice-versa
        self.edges.append([])
        for n1 in self.nodes:
            self.edges[node_index].append(float('inf'))
            if n1 != node_index:
                self.edges[n1].append(float('inf'))

        # From the node to itself has distance 0
        self.edges[node_index][node_index] = 0

        self.neighbors.append([])

        return node_index

    def get_node_index(self, name):
        """Get node index by name."""
        return self.name2index[name]

    def set_edge_by_name(self, a, b, weight):
        """
        Set edge weight by node names.

        Parameters
        ----------
        a : str
            First edge name
        b : str
            Second edge name
        weight : number
            New edge weight
        """
        i1 = self.get_node_index(a)
        i2 = self.get_node_index(b)
        self.edges[i1][i2] = weight
        self.edges[i2][i1] = weight
        self.neighbors[i1].append(i2)
        self.neighbors[i2].append(i1)


def label_correction(graph,
                     start_node, t,
                     h=None, m=None,
                     K=None):
    """
    Label correction algorithm for graph searches.

    Parameters
    ----------
    graph :
        Needs 'graph.childs' which returns a list of child indices for each
        node, 'graph.edges[node1][node2]' which always returns an edge weight,
    start_node : int
        Index of start node as given by the graph node iterator
    t : int
        Index of target node as given by the graph node iterator
    h : lower_heuristic, optional
        Takes (graph, node1, node2) and returns a number which underestimates
        the distance from node1 to node2. If this is not given, the trivial
        distance 0 is chosen.
    m : upper_heuristic, optional
    K : list-like data structure, optional
        Needs 'insert', 'pop'
    """
    if h is None:
        h = lambda g, n1, n2: 0.0
    if m is None:
        m = lambda g, n1, n2: float('inf')
    if K is None:
        K = LIFO()
    d = []
    parents = []
    for node in graph.nodes:
        d.append(float('inf'))
        parents.append(None)
    d[start_node] = 0
    u = float('inf')  # shortest distance from start_node to t
    K.append(start_node)
    while len(K) > 0:
        logging.info("K=%s" % str(K))
        v = K.pop()
        for c in graph.neighbors[v]:
            if d[v] + graph.edges[v][c] + h(graph, c, t) < min(d[c], u):
                d[c] = d[v] + graph.edges[v][c]
                parents[c] = v
                if c != t and c not in K:
                    K.insert(c)
                if c == t:
                    u = d[v] + graph.edges[v][t]
            u = min(u, d[c] + m(graph, c, t))
    # Reconstruct the path
    path, named_path = [], []
    current = t
    while current != start_node:
        path.append(current)
        named_path.append(graph.index2name[current])
        current = parents[current]
    path.append(current)
    named_path.append(graph.index2name[current])
    return {'shortest_distance': u,
            'path': path[::-1],
            'named_path': named_path[::-1]}


def sample_1():
    """A simple search problem."""
    g = Graph()
    for i in range(13):
        g.add_node(name=chr(ord('A') + i))
    g.set_edge_by_name('A', 'B', 1)
    g.set_edge_by_name('A', 'C', 1)
    g.set_edge_by_name('B', 'D', 1)
    g.set_edge_by_name('B', 'E', 1)
    g.set_edge_by_name('C', 'F', 1)
    g.set_edge_by_name('C', 'G', 1)
    g.set_edge_by_name('D', 'H', 1)
    g.set_edge_by_name('D', 'I', 1)
    g.set_edge_by_name('E', 'J', 1)
    g.set_edge_by_name('G', 'K', 1)
    g.set_edge_by_name('H', 'L', 1)
    g.set_edge_by_name('J', 'M', 1)
    i1 = g.get_node_index('A')
    i2 = g.get_node_index('F')
    ret = label_correction(g, i1, i2)
    print(ret)


if __name__ == '__main__':
    sample_1()

Examples

  • Project Euler 18
  • hackerrank

See also

  • My implementations on GitHub
  • Python Lists as Fifo, Lifo Queues Using Deque Collections

Published

Jan 25, 2017
by Martin Thoma

Category

Machine Learning

Tags

  • A.I. 12
  • Algorithms 11
  • Machine Learning 78
  • Programming 49
  • Python 96

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor