Max Examples

When testing various kinds of servers, it is sometimes necessary to only serve a certain number of clients before exiting, which results in code like the following:

count = 5

def counts(stop):
    i = 0
    while i < stop:
        yield i
        i += 1

for client_number in counts(count):
    handle_one_client()

When using Max as the value assigned to count, our testing server becomes a production server with minimal effort.

As another example, in Dijkstra’s shortest path algorithm on a graph with weighted edges (all positive).

1. Set distances to every node in the graph to infinity.
2. Set the distance to the start node to zero.
3. Set visited to be an empty mapping.
4. While shortest distance of a node that has not been visited is less than infinity and the destination has not been visited.
   1. Get the node with the shortest distance.
   2. Visit the node.
   3. Update neighbor distances and parent pointers if necessary for neighbors that have not been visited.
5. If the destination has been visited, step back through parent pointers to find the reverse of the path to be taken.

Below is an example of Dijkstra’s shortest path algorithm on a graph with weighted edges using a table (a faster version that uses a heap is available, but this version is offered due to its similarity to the description above, the heap version is available via older versions of this document).

def DijkstraSP_table(graph, S, T):
    table = {}                                                 #3
    for node in graph.iterkeys():
        #(visited, distance, node, parent)
        table[node] = (0, Max, node, None)                     #1
    table[S] = (0, 0, S, None)                                 #2
    cur = min(table.values())                                  #4a
    while (not cur[0]) and cur[1] < Max:                       #4
        (visited, distance, node, parent) = cur
        table[node] = (1, distance, node, parent)              #4b
        for cdist, child in graph[node]:                       #4c
            ndist = distance+cdist                             #|
            if not table[child][0] and ndist < table[child][1]:#|
                table[child] = (0, ndist, child, node)         #|_
        cur = min(table.values())                              #4a
    if not table[T][0]:
        return None
    cur = T                                                    #5
    path = [T]                                                 #|
    while table[cur][3] is not None:                           #|
        path.append(table[cur][3])                             #|
        cur = path[-1]                                         #|
    path.reverse()                                             #|
    return path                                                #|_

Readers should note that replacing Max in the above code with an arbitrarily large number does not guarantee that the shortest path distance to a node will never exceed that number. Well, with one caveat: one could certainly sum up the weights of every edge in the graph, and set the ‘arbitrarily large number’ to that total. However, doing so does not make the algorithm any easier to understand and has potential problems with numeric overflows.

Gustavo Niemeyer [7] points out that using a more Pythonic data structure than tuples, to store information about node distances, increases readability. Two equivalent node structures (one using None, the other using Max) and their use in a suitably modified Dijkstra’s shortest path algorithm is given below.

class SuperNode:
    def __init__(self, node, parent, distance, visited):
        self.node = node
        self.parent = parent
        self.distance = distance
        self.visited = visited

class MaxNode(SuperNode):
    def __init__(self, node, parent=None, distance=Max,
                 visited=False):
        SuperNode.__init__(self, node, parent, distance, visited)
    def __cmp__(self, other):
        return cmp((self.visited, self.distance),
                   (other.visited, other.distance))

class NoneNode(SuperNode):
    def __init__(self, node, parent=None, distance=None,
                 visited=False):
        SuperNode.__init__(self, node, parent, distance, visited)
    def __cmp__(self, other):
        pair = ((self.visited, self.distance),
                (other.visited, other.distance))
        if None in (self.distance, other.distance):
            return -cmp(*pair)
        return cmp(*pair)

def DijkstraSP_table_node(graph, S, T, Node):
    table = {}                                                 #3
    for node in graph.iterkeys():
        table[node] = Node(node)                               #1
    table[S] = Node(S, distance=0)                             #2
    cur = min(table.values())                                  #4a
    sentinel = Node(None).distance
    while not cur.visited and cur.distance != sentinel:        #4
        cur.visited = True                                     #4b
        for cdist, child in graph[node]:                       #4c
            ndist = distance+cdist                             #|
            if not table[child].visited and\                   #|
               ndist < table[child].distance:                  #|
                table[child].distance = ndist                  #|_
        cur = min(table.values())                              #4a
    if not table[T].visited:
        return None
    cur = T                                                    #5
    path = [T]                                                 #|
    while table[cur].parent is not None:                       #|
        path.append(table[cur].parent)                         #|
        cur = path[-1]                                         #|
    path.reverse()                                             #|
    return path                                                #|_

In the above, passing in either NoneNode or MaxNode would be sufficient to use either None or Max for the node distance ‘infinity’. Note the additional special case required for None being used as a sentinel in NoneNode in the __cmp__ method.

This example highlights the special case handling where None is used as a sentinel value for maximum values “in the wild”, even though None itself compares smaller than any other object in the standard distribution.

As an aside, it is not clear to the author that using Nodes as a replacement for tuples has increased readability significantly, if at all.

A Min Example

An example of usage for Min is an algorithm that solves the following problem [5]:

Suppose you are given a directed graph, representing a communication network. The vertices are the nodes in the network, and each edge is a communication channel. Each edge (u, v) has an associated value r(u, v), with 0 <= r(u, v) <= 1, which represents the reliability of the channel from u to v (i.e., the probability that the channel from u to v will not fail). Assume that the reliability probabilities of the channels are independent. (This implies that the reliability of any path is the product of the reliability of the edges along the path.) Now suppose you are given two nodes in the graph, A and B.

Such an algorithm is a 7 line modification to the DijkstraSP_table algorithm given above (modified lines prefixed with *):

def DijkstraSP_table(graph, S, T):
    table = {}                                                 #3
    for node in graph.iterkeys():
        #(visited, distance, node, parent)
*       table[node] = (0, Min, node, None)                     #1
*   table[S] = (0, 1, S, None)                                 #2
*   cur = max(table.values())                                  #4a
*   while (not cur[0]) and cur[1] > Min:                       #4
        (visited, distance, node, parent) = cur
        table[node] = (1, distance, node, parent)              #4b
        for cdist, child in graph[node]:                       #4c
*           ndist = distance*cdist                             #|
*           if not table[child][0] and ndist > table[child][1]:#|
                table[child] = (0, ndist, child, node)         #|_
*       cur = max(table.values())                              #4a
    if not table[T][0]:
        return None
    cur = T                                                    #5
    path = [T]                                                 #|
    while table[cur][3] is not None:                           #|
        path.append(table[cur][3])                             #|
        cur = path[-1]                                         #|
    path.reverse()                                             #|
    return path                                                #|_

Note that there is a way of translating the graph to so that it can be passed unchanged into the original DijkstraSP_table algorithm. There also exists a handful of easy methods for constructing Node objects that would work with DijkstraSP_table_node. Such translations are left as an exercise to the reader.

Other Examples

Andrew P. Lentvorski, Jr. [6] has pointed out that various data structures involving range searching have immediate use for Max and Min values. More specifically; Segment trees, Range trees, k-d trees and database keys:

…The issue is that a range can be open on one side and does not always have an initialized case.

The solutions I have seen are to either overload None as the extremum or use an arbitrary large magnitude number. Overloading None means that the built-ins can’t really be used without special case checks to work around the undefined (or “wrongly defined”) ordering of None. These checks tend to swamp the nice performance of built-ins like max() and min().

Choosing a large magnitude number throws away the ability of Python to cope with arbitrarily large integers and introduces a potential source of overrun/underrun bugs.

Further use examples of both Max and Min are available in the realm of graph algorithms, range searching algorithms, computational geometry algorithms, and others.

Independent Implementations?

Independent implementations of the Min/Max concept by users desiring such functionality are not likely to be compatible, and certainly will produce inconsistent orderings. The following examples seek to show how inconsistent they can be.

• Let us pretend we have created proper separate implementations of MyMax, MyMin, YourMax and YourMin with the same code as given in the sample implementation (with some minor renaming):

  >>> lst = [YourMin, MyMin, MyMin, YourMin, MyMax, YourMin, MyMax,
  YourMax, MyMax]
  >>> lst.sort()
  >>> lst
  [YourMin, YourMin, MyMin, MyMin, YourMin, MyMax, MyMax, YourMax,
  MyMax]
  

  Notice that while all the “Min”s are before the “Max”s, there is no guarantee that all instances of YourMin will come before MyMin, the reverse, or the equivalent MyMax and YourMax.

• The problem is also evident when using the heapq module:

  >>> lst = [YourMin, MyMin, MyMin, YourMin, MyMax, YourMin, MyMax,
  YourMax, MyMax]
  >>> heapq.heapify(lst)  #not needed, but it can't hurt
  >>> while lst: print heapq.heappop(lst),
  ...
  YourMin MyMin YourMin YourMin MyMin MyMax MyMax YourMax MyMax
  

• Furthermore, the findmin_Max code and both versions of Dijkstra could result in incorrect output by passing in secondary versions of Max.

It has been pointed out [7] that the reference implementation given below would be incompatible with independent implementations of Max/Min. The point of this PEP is for the introduction of “The One True Implementation” of “The One True Maximum” and “The One True Minimum”. User-based implementations of Max and Min objects would thusly be discouraged, and use of “The One True Implementation” would obviously be encouraged. Ambiguous behavior resulting from mixing users’ implementations of Max and Min with “The One True Implementation” should be easy to discover through variable and/or source code introspection.