  Soliton solutions of the KP equation have been studied since 1970, when
Kadomtsev and Petviashvili proposed a two-dimensional dispersive wave equation
now known as the KP equation. It is well-known that one can use the Wronskian
method to construct a soliton solution to the KP equation from each point of
the real Grassmannian Gr_kn. More recently several authors have studied the
regular solutions that one obtains in this way: these come from points of the
totally non-negative part of the Grassmannian (Gr_kn)_{>= 0}. In this paper we
exhibit a surprising connection between the theory of total positivity for the
Grassmannian, and the structure of regular soliton solutions to the KP
equation. By exploiting this connection, we obtain new insights into the
structure of KP solitons, as well as new interpretations of the combinatorial
objects indexing cells of (Gr_kn)_{>= 0}. In particular, we completely classify
the spatial patterns of the soliton solutions coming from (Gr_2n)_{>0}, as well
as those coming from (Gr_kn)_{>= 0} when the absolute value of the time
parameter is sufficiently large. We also demonstrate an intriguing connection
between soliton graphs for (Gr_kn)_{>0} and the cluster algebras of Fomin and
Zelevinsky, and we use this connection to solve the inverse problem for generic
KP solitons coming from (Gr_kn)_{>0}. Finally we construct all the soliton
graphs for (Gr_2n)_{>0} using the triangulations of n-gon.
