Daniel@0: .TH DIJKSTRA 1 "21 March 2001"
Daniel@0: .SH NAME
Daniel@0: dijkstra \- single-source distance filter
Daniel@0: .SH SYNOPSIS
Daniel@0: .B dijkstra
Daniel@0: [
Daniel@0: .B \-ap?
Daniel@0: ]
Daniel@0: [ 
Daniel@0: .I sourcenode file
Daniel@0: ]
Daniel@0: .SH DESCRIPTION
Daniel@0: .B dijkstra
Daniel@0: reads a stream of graphs and for each computes the distance of every
Daniel@0: node from
Daniel@0: .I sourcenode.
Daniel@0: Edge length is given in the 
Daniel@0: .I len
Daniel@0: attribute, and the default is 1.  The 
Daniel@0: .I dist
Daniel@0: attribute of every node is set to its distance from
Daniel@0: .I sourcenode.
Daniel@0: If the \fB-p\fP flag is used, the
Daniel@0: .I prev
Daniel@0: attribute of each node reachable from
Daniel@0: .I sourcenode
Daniel@0: is set to the name of the previous node on a shortest path.
Daniel@0: The graph attribute
Daniel@0: .I maxdist
Daniel@0: is set to the maximum 
Daniel@0: .I dist
Daniel@0: of all nodes in the graph.
Daniel@0: .P
Daniel@0: By default, if the graph is disconnected, the
Daniel@0: .I dist
Daniel@0: attribute of nodes unreachable from
Daniel@0: .I sourcenode
Daniel@0: are left untouched, and
Daniel@0: .I maxdist
Daniel@0: is set to the maximum of any previous value and the largest
Daniel@0: distance recorded in this run. On the other hand, if
Daniel@0: the \fB-a\fP flag is used, the
Daniel@0: .I dist
Daniel@0: attribute of an unreachable node is assigned a very large value,
Daniel@0: and
Daniel@0: .I maxdist
Daniel@0: records the maximum distance found in the component containing
Daniel@0: .I sourcenode.
Daniel@0: .P
Daniel@0: Any number of
Daniel@0: .I sourcenode file
Daniel@0: pairs may be given.
Daniel@0: If the last 
Daniel@0: .I file 
Daniel@0: is missing, \fBstdin\fP is used.
Daniel@0: All output is written to \fBstdout\fP.
Daniel@0: .P
Daniel@0: In a typical application,
Daniel@0: .I dist
Daniel@0: and 
Daniel@0: .I maxdist
Daniel@0: can drive a downstream calculation of color or some other attribute.
Daniel@0: .SH "SEE ALSO"
Daniel@0: gvpr(1), gvcolor(1), libgraph(3)