Logo Search packages:      
Sourcecode: python-networkx version File versions  Download package

paths.py

00001 """
Shortest paths, diameter, radius, eccentricity, and related methods.
"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nDan Schult(dschult@colgate.edu)"""
__date__ = ""
__credits__ = """"""
__revision__ = ""
#    Copyright (C) 2004-2006 by 
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html
import networkx
#use deque only if networkx requires python 2.4
#from collections import deque 
import heapq

00019 def eccentricity(G, v=None, sp=None, with_labels=False):
    """Return the eccentricity of node v in G (or all nodes if v is None).

    The eccentricity is the maximum of shortest paths to all other nodes. 

    The optional keyword sp must be a dict of dicts of
    shortest_path_length keyed by source and target.
    That is, sp[v][t] is the length from v to t.
       
    If with_labels=True 
    return dict of eccentricities keyed by vertex.
    """
    nodes=[]
    if v is None:                # none, use entire graph 
        nodes=G.nodes() 
    elif isinstance(v, list):  # check for a list
        nodes=v
    else:                      # assume it is a single value
        nodes=[v]

    e={}
    for v in nodes:
        if sp is None:
            length=single_source_shortest_path_length(G,v)
        else:
            length=sp[v]
        try:
            assert len(length)==G.number_of_nodes()
        except:
            raise networkx.NetworkXError,\
                  "Graph not connected: infinite path length"
            
        e[v]=max(length.values())

    if with_labels:
        return e
    else:
        if len(e)==1: return e.values()[0] # return single value
        return e.values()

00059 def diameter(G, e=None):
    """Return the diameter of the graph G.

    The diameter is the maximum of all pairs shortest path.
    """
    if e is None:
        e=eccentricity(G,with_labels=True)
    return max(e.values())

00068 def periphery(G, e=None):
    """Return the periphery of the graph G. 

    The periphery is the set of nodes with eccentricity equal to the diameter. 
    """
    if e is None:
        e=eccentricity(G,with_labels=True)
    diameter=max(e.values())
    p=[v for v in e if e[v]==diameter]
    return p


00080 def radius(G, e=None):
    """Return the radius of the  graph G.

    The radius is the minimum of all pairs shortest path.
       """
    if e is None:
        e=eccentricity(G,with_labels=True)
    return min(e.values())

00089 def center(G, e=None):
    """Return the center of graph G.

    The center is the set of nodes with eccentricity equal to radius. 
    """
    if e is None:
        e=eccentricity(G,with_labels=True)
    # order the nodes by path length
    radius=min(e.values())
    p=[v for v in e if e[v]==radius]
    return p


00102 def shortest_path_length(G,source,target):
    """Return the shortest path length in the graph G between
    the source and target.

    G is treated as an unweighted graph.  For weighted graphs
    see dijkstra_path_length.
    """
            
    try:
        return len(bidirectional_shortest_path(G,source,target))-1
    except TypeError:
        raise networkx.NetworkXError,\
              "no path from %s to %s"%(source,target)


00117 def single_source_shortest_path_length(G,source,cutoff=None):
    """
    Shortest path length from source to all reachable nodes.

    Returns a dictionary of shortest path lengths keyed by target.

    >>> G=path_graph(5)
    >>> length=single_source_shortest_path_length(G,1)
    >>> length[4]
    3
    >>> print length
    {0: 1, 1: 0, 2: 1, 3: 2, 4: 3}

    cutoff is optional integer depth to stop the search - only
    paths of length <= cutoff are returned.

    """
    seen={}                  # level (number of hops) when seen in BFS
    level=0                  # the current level
    nextlevel={source:1}  # dict of nodes to check at next level
    while nextlevel:
        thislevel=nextlevel  # advance to next level
        nextlevel={}         # and start a new list (fringe)
        for v in thislevel:
            if not seen.has_key(v): 
                seen[v]=level # set the level of vertex v
                nbrs=dict.fromkeys(G.neighbors_iter(v),1)
                nextlevel.update(nbrs) # add neighbors of v
        if (cutoff is not None and cutoff <= level):  break
        level=level+1
    return seen  # return all path lengths as dictionary


00150 def all_pairs_shortest_path_length(G,cutoff=None):
    """ Return dictionary of shortest path lengths between all nodes in G.

    The dictionary only has keys for reachable node pairs.
    >>> G=path_graph(5)
    >>> length=all_pairs_shortest_path_length(G)
    >>> print length[1][4]
    3
    >>> length[1]
    {0: 1, 1: 0, 2: 1, 3: 2, 4: 3}


    cutoff is optional integer depth to stop the search - only
    paths of length <= cutoff are returned.

    """
    paths={}
    for n in G:
        paths[n]=single_source_shortest_path_length(G,n,cutoff=cutoff)
    return paths        
        
00171 def shortest_path(G,source,target):
    """Return a list of nodes in G for a shortest path between source
    and target.

    There may be more than one shortest path.  This returns only one.
    
    """
    return bidirectional_shortest_path(G,source,target)


00181 def bidirectional_shortest_path(G,source,target):
    """
       Return list of nodes in a shortest path between source and target.

       Also known as shortest_path.

    """
    try:
        # call helper to do the real work
        pred,succ,w=_bidirectional_pred_succ(G,source,target)
    except:
        return False  # no path from source to target

    # build path from pred+w+succ
    path=[]
    # from w to target
    while w is not None:
        path.append(w)
        w=succ[w]
    # from source to w        
    w=pred[path[0]]
    while w is not None:
        path.insert(0,w)
        w=pred[w]

    return path        

00208 def _bidirectional_pred_succ(G, source, target):
    """
       Bidirectional shortest path helper.

       Returns (pred,succ,w) where
       pred is a dictionary of predecessors from w to the source, and
       succ is a dictionary of successors from w to the target.
    """
    # does BFS from both source and target and meets in the middle
    if source is None or target is None:
        raise NetworkXException(\
            "Bidirectional shortest path called without source or target")
    if target == source:  return ({1:None},{1:None},1)

    # handle either directed or undirected
    if G.is_directed():
        Gpred=G.predecessors_iter
        Gsucc=G.successors_iter
    else:
        Gpred=G.neighbors_iter
        Gsucc=G.neighbors_iter

    # predecesssor and successors in search
    pred={source:None}
    succ={target:None}

    # initialize fringes, start with forward
    forward_fringe=[source] 
    reverse_fringe=[target]  

    while forward_fringe and reverse_fringe:
        this_level=forward_fringe
        forward_fringe=[]
        for v in this_level:
            for w in Gsucc(v):
                if w not in pred:
                    forward_fringe.append(w)
                    pred[w]=v
                if w in succ:  return pred,succ,w # found path
        this_level=reverse_fringe
        reverse_fringe=[]
        for v in this_level:
            for w in Gpred(v):
                if w not in succ:
                    succ[w]=v
                    reverse_fringe.append(w)
                if w in pred:  return pred,succ,w # found path

    return False  # no path found


00259 def single_source_shortest_path(G,source,cutoff=None):
    """
    Return list of nodes in a shortest path between source
    and all other nodes in G reachable from source.

    There may be more than one shortest path between the
    source and target nodes - this routine returns only one.

    cutoff is optional integer depth to stop the search - only
    paths of length <= cutoff are returned.

    See also shortest_path and bidirectional_shortest_path.
    """
    level=0                  # the current level
    nextlevel={source:1}       # list of nodes to check at next level
    paths={source:[source]}  # paths dictionary  (paths to key from source)
    if cutoff==0:
        return paths
    while nextlevel:
        thislevel=nextlevel
        nextlevel={}
        for v in thislevel:
            for w in G.neighbors(v):
                if not paths.has_key(w): 
                    paths[w]=paths[v]+[w]
                    nextlevel[w]=1
        level=level+1
        if (cutoff is not None and cutoff <= level):  break
    return paths   


00290 def all_pairs_shortest_path(G,cutoff=None):
    """ Return dictionary of shortest paths between all nodes in G.

    The dictionary only has keys for reachable node pairs.

    cutoff is optional integer depth to stop the search - only
    paths of length <= cutoff are returned.

    See also floyd_warshall.

    """
    paths={}
    for n in G:
        paths[n]=single_source_shortest_path(G,n,cutoff=cutoff)
    return paths        


00307 def dijkstra_path(G,source,target):
    """
    Returns the shortest path from source to target in a weighted
    graph G.  Uses a bidirectional version of Dijkstra's algorithm.

    Edge data must be numerical values for XGraph and XDiGraphs.
    The weights are assigned to be 1 for Graphs and DiGraphs.

    See also bidirectional_dijkstra for more information about the algorithm.
    """
#    (length,path)=bidirectional_dijkstra(G,source,target) # faster, needs test
#     return path
    (length,path)=single_source_dijkstra(G,source)
    try:
        return path[target]
    except KeyError:
        raise networkx.NetworkXError, \
              "node %s not reachable from %s"%(source,target)


00327 def dijkstra_path_length(G,source,target):
    """
    Returns the shortest path length from source to target in a weighted
    graph G.  Uses a bidirectional version of Dijkstra's algorithm.

    Edge data must be numerical values for XGraph and XDiGraphs.
    The weights are assigned to be 1 for Graphs and DiGraphs.

    See also bidirectional_dijkstra for more information about the algorithm.

    """

#    (length,path)=bidirectional_dijkstra(G,source,target) # faster, needs test
#    return length
    (length,path)=single_source_dijkstra(G,source)
    try:
        return length[target]
    except KeyError:
        raise networkx.NetworkXError, \
              "node %s not reachable from %s"%(source,target)



00350 def bidirectional_dijkstra(G, source, target):
    """
    Dijkstra's algorithm for shortest paths using bidirectional search. 

    Returns a two-tuple (d,p) where d is the distance and p
    is the path from the source to the target.

    Distances are calculated as sums of weighted edges traversed.

    Edges must hold numerical values for XGraph and XDiGraphs.
    The weights are set to 1 for Graphs and DiGraphs.
    
    In practice  bidirectional Dijkstra is much more than twice as fast as 
    ordinary Dijkstra.

    Ordinary Dijkstra expands nodes in a sphere-like manner from the
    source. The radius of this sphere will eventually be the length 
    of the shortest path. Bidirectional Dijkstra will expand nodes 
    from both the source and the target, making two spheres of half 
    this radius. Volume of the first sphere is pi*r*r while the  
    others are 2*pi*r/2*r/2, making up half the volume. 
    
    This algorithm is not guaranteed to work if edge weights
    are negative or are floating point numbers
    (overflows and roundoff errors can cause problems). 

    """
    if source is None or target is None:
        raise NetworkXException(
            "Bidirectional Dijkstra called with no source or target")
    if source == target: return (0, [source])
    #Init:   Forward             Backward
    dists =  [{},                {}]# dictionary of final distances
    paths =  [{source:[source]}, {target:[target]}] # dictionary of paths 
    fringe = [[],                []] #heap of (distance, node) tuples for extracting next node to expand
    seen =   [{source:0},        {target:0} ]#dictionary of distances to nodes seen 
    #initialize fringe heap
    heapq.heappush(fringe[0], (0, source)) 
    heapq.heappush(fringe[1], (0, target))
    #neighs for extracting correct neighbor information
    if G.is_directed():
        neighs = [G.successors_iter, G.predecessors_iter]
    else:
        neighs = [G.neighbors_iter, G.neighbors_iter]
    #variables to hold shortest discovered path
    #finaldist = 1e30000
    finalpath = []
    # if unweighted graph, set the weights to 1 on edges by
    # introducing a get_edge method
    if not hasattr(G,"get_edge"): G.get_edge=lambda x,y:1
    dir = 1
    while fringe[0] and fringe[1]:
        # choose direction 
        # dir == 0 is forward direction and dir == 1 is back
        dir = 1-dir
        # extract closest to expand
        (dist, v )= heapq.heappop(fringe[dir]) 
        if v in dists[dir]:
            # Shortest path to v has already been found 
            continue
        # update distance
        dists[dir][v] = dist #equal to seen[dir][v]
        if v in dists[1-dir]:
            # if we have scanned v in both directions we are done 
            # we have now discovered the shortest path
            return (finaldist,finalpath)
        for w in neighs[dir](v):
            if(dir==0): #forward
                vwLength = dists[dir][v] + G.get_edge(v,w)
            else: #back, must remember to change v,w->w,v
                vwLength = dists[dir][v] + G.get_edge(w,v)
            
            if w in dists[dir]:
                if vwLength < dists[dir][w]:
                    raise ValueError,\
                        "Contradictory paths found: negative weights?"
            elif w not in seen[dir] or vwLength < seen[dir][w]:
                # relaxing        
                seen[dir][w] = vwLength
                heapq.heappush(fringe[dir], (vwLength,w)) 
                paths[dir][w] = paths[dir][v]+[w]
                if w in seen[0] and w in seen[1]:
                    #see if this path is better than than the already
                    #discovered shortest path
                    totaldist = seen[0][w] + seen[1][w] 
                    if finalpath == [] or finaldist > totaldist:
                        finaldist = totaldist
                        revpath = paths[1][w][:]
                        revpath.reverse()
                        finalpath = paths[0][w] + revpath[1:]
    return False


#def dijkstra(G,source,target):
#    return bidirectional_dijkstra(G,source,target)


00447 def single_source_dijkstra_path(G,source):
    """
    Returns the shortest paths from source to all other reachable
    nodes in a weighted graph G.  Uses Dijkstra's algorithm.

    Returns a dictionary of shortest path lengths keyed by source.
    
    Edge data must be numerical values for XGraph and XDiGraphs.
    The weights are assigned to be 1 for Graphs and DiGraphs.

    See also single_source_dijkstra for more information about the algorithm.

    """
    (length,path)=single_source_dijkstra(G,source)
    return path


00464 def single_source_dijkstra_path_length(G,source):
    """
    Returns the shortest path lengths from source to all other
    reachable nodes in a weighted graph G.  Uses Dijkstra's algorithm.

    Returns a dictionary of shortest path lengths keyed by source.
    
    Edge data must be numerical values for XGraph and XDiGraphs.
    The weights are assigned to be 1 for Graphs and DiGraphs.

    See also single_source_dijkstra for more information about the algorithm.

    """
    (length,path)=single_source_dijkstra(G,source)
    return length


00481 def single_source_dijkstra(G,source,target=None):
    """
    Dijkstra's algorithm for shortest paths in a weighted graph G.

    Use:

    single_source_dijkstra_path() - shortest path list of nodes 

    single_source_dijkstra_path_length() - shortest path length

    Returns a tuple of two dictionaries keyed by node.
    The first stores distance from the source.
    The second stores the path from the source to that node.

    Distances are calculated as sums of weighted edges traversed.
    Edges must hold numerical values for XGraph and XDiGraphs.
    The weights are 1 for Graphs and DiGraphs.

    Optional target argument stops the search when target is found.

    Based on the Python cookbook recipe (119466) at 
    http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466

    This algorithm is not guaranteed to work if edge weights
    are negative or are floating point numbers
    (overflows and roundoff errors can cause problems). 
    
    See also 'bidirectional_dijkstra_path'
    """
    if source==target: return (0, [source])
    dist = {}  # dictionary of final distances
    paths = {source:[source]}  # dictionary of paths
    seen = {source:0} 
    fringe=[] # use heapq with (distance,label) tuples 
    heapq.heappush(fringe,(0,source))
    if not G.is_directed():  G.successors=G.neighbors
    # if unweighted graph, set the weights to 1 on edges by
    # introducing a get_edge method
    # NB: for the weighted graphs (XGraph,XDiGraph), the data
    # on the edge (returned by get_edge) must be numerical
    if not hasattr(G,"get_edge"): G.get_edge=lambda x,y:1

    while fringe:
        (d,v)=heapq.heappop(fringe)
        if v in dist: continue # already searched this node.
        dist[v] = seen[v]
        if v == target: break
            
        for w in G.successors(v):
            vw_dist = dist[v] + G.get_edge(v,w)
            if w in dist:
                if vw_dist < dist[w]:
                    raise ValueError,\
                          "Contradictory paths found: negative weights?"
            elif w not in seen or vw_dist < seen[w]:
                seen[w] = vw_dist
                heapq.heappush(fringe,(vw_dist,w))
                paths[w] = paths[v]+[w]
    return (dist,paths)


00542 def floyd_warshall(graph):
    """
    The Floyd-Warshall algorithm for all pairs shortest paths.
    
    Returns a tuple (distance,path) containing two matrixes of
    shortest distance and paths as dicts-in-dicts. 
        
    Not intended for large graphs. Time and space grows as O(N^3).
    This algorithm handles negative weights.
    """
    
    dist = {}
    path = {}
    for i in graph:
        dist[i] = {}
        path[i] = {}
        for j in graph:
            if i == j :continue
            if not graph.has_edge(i,j): continue
            if hasattr(graph,"get_edge"): 
                val = graph.get_edge(i,j)
            else:
                val= 1
            path[i][j] = [i, j]
            dist[i][j] = val
    for k in graph:
        for i in graph:
            if i==k : continue
            for j in graph:
                if j == i or j == k: continue
                if j in dist[k] and k in dist[i]: 
                    if j in dist[i]:
                        if dist[i][j] > dist[i][k] + dist[k][j]:
                            dist[i][j] = dist[i][k] + dist[k][j]
                            path[i][j] = path[i][k] + path[k][j][1:]
                    else:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        path[i][j] = path[i][k] + path[k][j][1:]
    return dist, path


00583 def is_directed_acyclic_graph(G):
    """Return True if the graph G is a directed acyclic graph (DAG).

    Otherwise return False.
    
    """
    if topological_sort(G) is None:
        return False
    else:
        return True

00594 def topological_sort(G):
    """
    Return a list of nodes of the digraph G in topological sort order.

    A topological sort is a nonunique permutation of the nodes
    such that an edge from u to v implies that u appears before v in the
    topological sort order.

    If G is not a directed acyclic graph no topological sort exists
    and the Python keyword None is returned.

    This algorithm is based on a description and proof at
    http://www2.toki.or.id/book/AlgDesignManual/book/book2/node70.htm

    See also is_directed_acyclic_graph()
    
    """
    # nonrecursive version

    seen={}
    order_explored=[] # provide order and 
    explored={}       # fast search without more general priorityDictionary
                     
    if not G.is_directed():  G.successors_iter=G.neighbors_iter

    for v in G.nodes_iter():     # process all vertices in G
        if v in explored: continue

        fringe=[v]   # nodes yet to look at
        while fringe:
            w=fringe[-1]  # depth first search
            if w in explored: # already looked down this branch
                fringe.pop()
                continue
            seen[w]=1     # mark as seen
            # Check successors for cycles and for new nodes
            new_nodes=[]
            for n in G.successors_iter(w):  
                if n not in explored:
                    if n in seen: return #CYCLE !!
                    new_nodes.append(n)
            if new_nodes:   # Add new_nodes to fringe
                fringe.extend(new_nodes)
            else:           # No new nodes so w is fully explored
                explored[w]=1
                order_explored.insert(0,w) # reverse order explored
                fringe.pop()    # done considering this node
    return order_explored

00643 def topological_sort_recursive(G):
    """
    Return a list of nodes of the digraph G in topological sort order.

    This is a recursive version of topological sort.
    
    """
    # function for recursive dfs
    def _dfs(G,seen,explored,v):
        seen[v]=1
        for w in G.successors(v):
            if w not in seen: 
                if not _dfs(G,seen,explored,w):
                    return
            elif w in seen and w not in explored:
                # cycle Found--- no topological sort
                return False
        explored.insert(0,v) # inverse order of when explored 
        return v

    seen={}
    explored=[]

    if not G.is_directed():  G.successors=G.neighbors
    
    for v in G.nodes_iter():  # process all nodes
        if v not in explored:
            if not _dfs(G,seen,explored,v): 
                return 
    return explored

00674 def predecessor(G,source,target=False,cutoff=False):
    """ Returns dictionary of predecessors for the path from source to all
    nodes in G.  

    Optional target returns only predecessors between source and target.
    Cutoff is a limit on the number of hops traversed.

    Example for the path graph 0-1-2-3
    
    >>> G=path_graph(4)
    >>> print G.nodes()
    [0, 1, 2, 3]
    >>> predecessor(G,0)
    {0: [], 1: [0], 2: [1], 3: [2]}

    """
    level=0                  # the current level
    nextlevel=[source]       # list of nodes to check at next level
    seen={source:level}      # level (number of hops) when seen in BFS
    pred={source:[]}         # predecessor dictionary
    while nextlevel:
        level=level+1
        thislevel=nextlevel
        nextlevel=[]
        for v in thislevel:
            for w in G.neighbors(v):
                if (not seen.has_key(w)): 
                    pred[w]=[v]
                    seen[w]=level
                    nextlevel.append(w)
                elif (seen[w]==level):# add v to predecessor list if it 
                    pred[w].append(v) # is at the correct level
        if (cutoff and cutoff <= level):
            break

    if target:
        if not pred.has_key(target): return ([],-1)  # No predecessor
        return pred[target]
    else:
        return pred

00715 def connected_components(G):
    """
    Return a list of lists of nodes in each connected component of G.

    The list is ordered from largest connected component to smallest.
    For undirected graphs only. 
    """
    if G.is_directed():
        raise networkx.NetworkXError,\
              """Not allowed for directed graph G.
              Use UG=G.to_undirected() to create an undirected graph."""
    seen={}
    components=[]
    for v in G:      
        if v not in seen:
            c=single_source_shortest_path_length(G,v)
            components.append(c.keys())
            seen.update(c)
    components.sort(lambda x, y: cmp(len(y),len(x)))
    return components            


00737 def number_connected_components(G):
    """Return the number of connected components in G.
    For undirected graphs only. 
    """
    return len(connected_components(G))


00744 def is_connected(G):
    """Return True if G is connected.
    For undirected graphs only. 
    """
    if G.is_directed():
        raise networkx.NetworkXError,\
              """Not allowed for directed graph G.
              Use UG=G.to_undirected() to create an undirected graph."""
    return len(single_source_shortest_path(G, G.nodes_iter().next()))==len(G)


00755 def connected_component_subgraphs(G):
    """
    Return a list of graphs of each connected component of G.
    The list is ordered from largest connected component to smallest.
    For undirected graphs only. 

    For example, to get the largest connected component:
    >>> H=connected_component_subgraphs(G)[0]

    """
    cc=connected_components(G)
    graph_list=[]
    for c in cc:
        graph_list.append(G.subgraph(c,inplace=False))
    return graph_list


00772 def node_connected_component(G,n):
    """
    Return a list of nodes of the connected component containing node n.

    For undirected graphs only. 

    """
    if G.is_directed():
        raise networkx.NetworkXError,\
              """Not allowed for directed graph G.
              Use UG=G.to_undirected() to create an undirected graph."""
    return single_source_shortest_path_length(G,n).keys()

00785 def bfs(G,source):
    """
    Traverse the graph G with breadth-first-search from source.
    Return list of nodes connected to source in BFS order.
    
    Primarily intended as an example.
    See also shortest_path and bidirectional_shortest_path.
    """

    nlist=[source] # list of nodes in a BFS order
    seen={} # nodes seen
    queue=[source] # FIFO queue
    seen[source]=True 
    while queue:
        v=queue.pop(0)  # this is expensive, should use a faster FIFO queue
        for w in G.neighbors(v):
            if w not in seen:
                seen[w]=True
                queue.append(w)
                nlist.append(w)
    return nlist


00808 def dfs(G,source):
    """
    Traverse the graph G with depth-first-search from source.
    Return list of nodes connected to source in DFS order.
    
    Primarily intended as an example.

    """
    nlist=[] # list of nodes in a DFS order
    seen={} # nodes seen
    queue=[source]  # use as LIFO queue
    seen[source]=True 
    while queue:
        v=queue.pop()
        nlist.append(v)
        for w in G.neighbors(v):
            if w not in seen:
                seen[w]=True
                queue.append(w)
    return nlist


def _test_suite():
    import doctest
    suite = doctest.DocFileSuite('tests/paths.txt',package='networkx')
    return suite


if __name__ == "__main__":
    import os
    import sys
    import unittest
    if sys.version_info[:2] < (2, 4):
        print "Python version 2.4 or later required for tests (%d.%d detected)." %  sys.version_info[:2]
        sys.exit(-1)
    # directory of networkx package (relative to this)
    nxbase=sys.path[0]+os.sep+os.pardir
    sys.path.insert(0,nxbase) # prepend to search path
    unittest.TextTestRunner().run(_test_suite())
    

Generated by  Doxygen 1.6.0   Back to index