\hypertarget{classSpt}{
\section{Spt$<$ A $>$ Class Template Reference}
\label{classSpt}\index{Spt@{Spt}}
}


Shortest Path Tree.  




{\ttfamily \#include $<$spt.hh$>$}

\subsection*{Public Types}
\begin{DoxyCompactItemize}
\item 
\hypertarget{classSpt_ae42d0d5321a7616aaaaf7a0d5f2c3c8d}{
typedef map$<$ A, typename \hyperlink{classNode}{Node}$<$ A $>$::NodeRef $>$ {\bfseries Nodes}}
\label{classSpt_ae42d0d5321a7616aaaaf7a0d5f2c3c8d}

\end{DoxyCompactItemize}
\subsection*{Public Member Functions}
\begin{DoxyCompactItemize}
\item 
\hypertarget{classSpt_a912a845c79c113462c91e71a8a221db7}{
{\bfseries Spt} (bool trace=true)}
\label{classSpt_a912a845c79c113462c91e71a8a221db7}

\item 
\hypertarget{classSpt_a3518b66a09f0b6a59ef91bdde51b1ade}{
void \hyperlink{classSpt_a3518b66a09f0b6a59ef91bdde51b1ade}{clear} ()}
\label{classSpt_a3518b66a09f0b6a59ef91bdde51b1ade}

\begin{DoxyCompactList}\small\item\em Clear all state from this \hyperlink{classSpt}{Spt} instance. \item\end{DoxyCompactList}\item 
bool \hyperlink{classSpt_a6c28bb8c848fba56433a6c48663da6ee}{set\_\-origin} (const A \&node)
\begin{DoxyCompactList}\small\item\em Set \hyperlink{protocolthe-p}{the} origin node. \item\end{DoxyCompactList}\item 
bool \hyperlink{classSpt_aa21a97940021ca56ec3db607377add28}{add\_\-node} (const A \&node)
\begin{DoxyCompactList}\small\item\em Add node. \item\end{DoxyCompactList}\item 
bool \hyperlink{classSpt_a97746270155c0dc5409c2a6c080099c1}{update\_\-node} (const A \&node)
\begin{DoxyCompactList}\small\item\em Update node. \item\end{DoxyCompactList}\item 
bool \hyperlink{classSpt_a7736199686e608720ca6c19cb2823cdd}{remove\_\-node} (const A \&node)
\begin{DoxyCompactList}\small\item\em Remove node. \item\end{DoxyCompactList}\item 
bool \hyperlink{classSpt_a3acc460a6e910668d6ccd439c50e87c7}{exists\_\-node} (const A \&node)
\begin{DoxyCompactList}\small\item\em Does this node exist? \item\end{DoxyCompactList}\item 
bool \hyperlink{classSpt_a35c550a80fcd88cf5fbdd9ab7df0066d}{add\_\-edge} (const A \&src, int weight, const A \&dst)
\begin{DoxyCompactList}\small\item\em Add a new edge. \item\end{DoxyCompactList}\item 
bool \hyperlink{classSpt_ab22bf4496423fdedf57bd54760b8c641}{update\_\-edge\_\-weight} (const A \&src, int weight, const A \&dst)
\begin{DoxyCompactList}\small\item\em Update existing edge weight. \item\end{DoxyCompactList}\item 
bool \hyperlink{classSpt_a13dab2721dd8d412c339844844c6e11c}{get\_\-edge\_\-weight} (const A \&src, int \&weight, const A \&dst)
\begin{DoxyCompactList}\small\item\em Get edge weight. \item\end{DoxyCompactList}\item 
bool \hyperlink{classSpt_a13b98f6c4feb27c3f1a508af54f42e76}{remove\_\-edge} (const A \&src, const A \&dst)
\begin{DoxyCompactList}\small\item\em Remove an edge. \item\end{DoxyCompactList}\item 
bool \hyperlink{classSpt_a7b8b32cc63be7166c7031da628dde40e}{compute} (list$<$ \hyperlink{classRouteCmd}{RouteCmd}$<$ A $>$ $>$ \&routes)
\begin{DoxyCompactList}\small\item\em Compute \hyperlink{protocolthe-p}{the} tree. \item\end{DoxyCompactList}\item 
string \hyperlink{classSpt_a3686eb183a96cd08379cffb4c28e728e}{str} () const 
\begin{DoxyCompactList}\small\item\em Convert this graph to presentation format. \item\end{DoxyCompactList}\item 
\hypertarget{classSpt_a249f9e7c539ea5acdb77c3bad68c94c4}{
\hyperlink{classNode}{Node}$<$ A $>$::NodeRef \hyperlink{classSpt_a249f9e7c539ea5acdb77c3bad68c94c4}{find\_\-node} (const A \&node)}
\label{classSpt_a249f9e7c539ea5acdb77c3bad68c94c4}

\begin{DoxyCompactList}\small\item\em Find this node. \item\end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Private Member Functions}
\begin{DoxyCompactItemize}
\item 
bool \hyperlink{classSpt_ab36b19483eb96ffa108cb22b7829a511}{dijkstra} ()
\begin{DoxyCompactList}\small\item\em Dijkstra. \item\end{DoxyCompactList}\item 
bool \hyperlink{classSpt_a610b39c383d3a85d183d9b87e751b8d8}{incremental\_\-spt} ()
\begin{DoxyCompactList}\small\item\em Incremental SPT. \item\end{DoxyCompactList}\item 
\hypertarget{classSpt_a69ff07677fb56aa09b9d3ced1404c646}{
void \hyperlink{classSpt_a69ff07677fb56aa09b9d3ced1404c646}{garbage\_\-collect} ()}
\label{classSpt_a69ff07677fb56aa09b9d3ced1404c646}

\begin{DoxyCompactList}\small\item\em Remove all \hyperlink{protocolthe-p}{the} nodes that have been marked for deletion. \item\end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Private Attributes}
\begin{DoxyCompactItemize}
\item 
\hypertarget{classSpt_a2f516d3883d4b7019afb9aebb280dc2b}{
bool {\bfseries \_\-trace}}
\label{classSpt_a2f516d3883d4b7019afb9aebb280dc2b}

\item 
\hypertarget{classSpt_acbadf821ebcd88d42473731f16dd9cf6}{
\hyperlink{classNode}{Node}$<$ A $>$::NodeRef {\bfseries \_\-origin}}
\label{classSpt_acbadf821ebcd88d42473731f16dd9cf6}

\item 
\hypertarget{classSpt_a64ca2545f16f18d19c62cef4d7625c04}{
Nodes {\bfseries \_\-nodes}}
\label{classSpt_a64ca2545f16f18d19c62cef4d7625c04}

\end{DoxyCompactItemize}


\subsection{Detailed Description}
\subsubsection*{template$<$typename A$>$ class Spt$<$ A $>$}

Shortest Path Tree. Compute shortest path tree's 

\subsection{Member Function Documentation}
\hypertarget{classSpt_a35c550a80fcd88cf5fbdd9ab7df0066d}{
\index{Spt@{Spt}!add\_\-edge@{add\_\-edge}}
\index{add\_\-edge@{add\_\-edge}!Spt@{Spt}}
\subsubsection[{add\_\-edge}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename A$>$ bool {\bf Spt}$<$ A $>$::add\_\-edge (
\begin{DoxyParamCaption}
\item[{const A \&}]{src, }
\item[{int}]{weight, }
\item[{const A \&}]{dst}
\end{DoxyParamCaption}
)}}
\label{classSpt_a35c550a80fcd88cf5fbdd9ab7df0066d}


Add a new edge. 


\begin{DoxyParams}{Parameters}
{\em src} & source node must exist. \\
\hline
{\em weight} & edge weight. \\
\hline
{\em dst} & destination node, created if necessary. \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
true on success. 
\end{DoxyReturn}
\hypertarget{classSpt_aa21a97940021ca56ec3db607377add28}{
\index{Spt@{Spt}!add\_\-node@{add\_\-node}}
\index{add\_\-node@{add\_\-node}!Spt@{Spt}}
\subsubsection[{add\_\-node}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename A$>$ bool {\bf Spt}$<$ A $>$::add\_\-node (
\begin{DoxyParamCaption}
\item[{const A \&}]{node}
\end{DoxyParamCaption}
)}}
\label{classSpt_aa21a97940021ca56ec3db607377add28}


Add node. 

\begin{DoxyReturn}{Returns}
false if \hyperlink{protocolthe-p}{the} node already exists, otherwise true. 
\end{DoxyReturn}
\hypertarget{classSpt_a7b8b32cc63be7166c7031da628dde40e}{
\index{Spt@{Spt}!compute@{compute}}
\index{compute@{compute}!Spt@{Spt}}
\subsubsection[{compute}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename A$>$ bool {\bf Spt}$<$ A $>$::compute (
\begin{DoxyParamCaption}
\item[{list$<$ {\bf RouteCmd}$<$ A $>$ $>$ \&}]{routes}
\end{DoxyParamCaption}
)}}
\label{classSpt_a7b8b32cc63be7166c7031da628dde40e}


Compute \hyperlink{protocolthe-p}{the} tree. 


\begin{DoxyParams}{Parameters}
{\em routes} & a list of route adds, deletes and replaces that must be performed. \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
true on success 
\end{DoxyReturn}
\hypertarget{classSpt_ab36b19483eb96ffa108cb22b7829a511}{
\index{Spt@{Spt}!dijkstra@{dijkstra}}
\index{dijkstra@{dijkstra}!Spt@{Spt}}
\subsubsection[{dijkstra}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename A $>$ bool {\bf Spt}$<$ A $>$::dijkstra (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily  \mbox{[}private\mbox{]}}}}
\label{classSpt_ab36b19483eb96ffa108cb22b7829a511}


Dijkstra. 

\begin{DoxyReturn}{Returns}
true on success. 
\end{DoxyReturn}
\hypertarget{classSpt_a3acc460a6e910668d6ccd439c50e87c7}{
\index{Spt@{Spt}!exists\_\-node@{exists\_\-node}}
\index{exists\_\-node@{exists\_\-node}!Spt@{Spt}}
\subsubsection[{exists\_\-node}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename A$>$ bool {\bf Spt}$<$ A $>$::exists\_\-node (
\begin{DoxyParamCaption}
\item[{const A \&}]{node}
\end{DoxyParamCaption}
)}}
\label{classSpt_a3acc460a6e910668d6ccd439c50e87c7}


Does this node exist? 

\begin{DoxyReturn}{Returns}
true if \hyperlink{protocolthe-p}{the} node exists. 
\end{DoxyReturn}
\hypertarget{classSpt_a13dab2721dd8d412c339844844c6e11c}{
\index{Spt@{Spt}!get\_\-edge\_\-weight@{get\_\-edge\_\-weight}}
\index{get\_\-edge\_\-weight@{get\_\-edge\_\-weight}!Spt@{Spt}}
\subsubsection[{get\_\-edge\_\-weight}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename A$>$ bool {\bf Spt}$<$ A $>$::get\_\-edge\_\-weight (
\begin{DoxyParamCaption}
\item[{const A \&}]{src, }
\item[{int \&}]{weight, }
\item[{const A \&}]{dst}
\end{DoxyParamCaption}
)}}
\label{classSpt_a13dab2721dd8d412c339844844c6e11c}


Get edge weight. 


\begin{DoxyParams}{Parameters}
{\em src} & source node must exist. \\
\hline
{\em weight} & of this edge returned. \\
\hline
{\em dst} & destination node must exist \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
true on success. 
\end{DoxyReturn}
\hypertarget{classSpt_a610b39c383d3a85d183d9b87e751b8d8}{
\index{Spt@{Spt}!incremental\_\-spt@{incremental\_\-spt}}
\index{incremental\_\-spt@{incremental\_\-spt}!Spt@{Spt}}
\subsubsection[{incremental\_\-spt}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename A $>$ bool {\bf Spt}$<$ A $>$::incremental\_\-spt (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily  \mbox{[}private\mbox{]}}}}
\label{classSpt_a610b39c383d3a85d183d9b87e751b8d8}


Incremental SPT. 

\begin{DoxyReturn}{Returns}
true on success. 
\end{DoxyReturn}
\hypertarget{classSpt_a13b98f6c4feb27c3f1a508af54f42e76}{
\index{Spt@{Spt}!remove\_\-edge@{remove\_\-edge}}
\index{remove\_\-edge@{remove\_\-edge}!Spt@{Spt}}
\subsubsection[{remove\_\-edge}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename A$>$ bool {\bf Spt}$<$ A $>$::remove\_\-edge (
\begin{DoxyParamCaption}
\item[{const A \&}]{src, }
\item[{const A \&}]{dst}
\end{DoxyParamCaption}
)}}
\label{classSpt_a13b98f6c4feb27c3f1a508af54f42e76}


Remove an edge. 


\begin{DoxyParams}{Parameters}
{\em src} & source node must exist. \\
\hline
{\em dst} & destination node must exist \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
true on success. 
\end{DoxyReturn}
\hypertarget{classSpt_a7736199686e608720ca6c19cb2823cdd}{
\index{Spt@{Spt}!remove\_\-node@{remove\_\-node}}
\index{remove\_\-node@{remove\_\-node}!Spt@{Spt}}
\subsubsection[{remove\_\-node}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename A$>$ bool {\bf Spt}$<$ A $>$::remove\_\-node (
\begin{DoxyParamCaption}
\item[{const A \&}]{node}
\end{DoxyParamCaption}
)}}
\label{classSpt_a7736199686e608720ca6c19cb2823cdd}


Remove node. 

\begin{DoxyReturn}{Returns}
false if \hyperlink{protocolthe-p}{the} node doesn't exist or has already been removed, otherwise true. 
\end{DoxyReturn}
\hypertarget{classSpt_a6c28bb8c848fba56433a6c48663da6ee}{
\index{Spt@{Spt}!set\_\-origin@{set\_\-origin}}
\index{set\_\-origin@{set\_\-origin}!Spt@{Spt}}
\subsubsection[{set\_\-origin}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename A$>$ bool {\bf Spt}$<$ A $>$::set\_\-origin (
\begin{DoxyParamCaption}
\item[{const A \&}]{node}
\end{DoxyParamCaption}
)}}
\label{classSpt_a6c28bb8c848fba56433a6c48663da6ee}


Set \hyperlink{protocolthe-p}{the} origin node. 

\begin{DoxyReturn}{Returns}
false if \hyperlink{protocolthe-p}{the} node doesn't exist, otherwise true. 
\end{DoxyReturn}
\hypertarget{classSpt_a3686eb183a96cd08379cffb4c28e728e}{
\index{Spt@{Spt}!str@{str}}
\index{str@{str}!Spt@{Spt}}
\subsubsection[{str}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename A $>$ string {\bf Spt}$<$ A $>$::str (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
) const}}
\label{classSpt_a3686eb183a96cd08379cffb4c28e728e}


Convert this graph to presentation format. 

\begin{DoxyReturn}{Returns}
C++ string with \hyperlink{protocolthe-p}{the} human-\/readable ASCII representation of \hyperlink{protocolthe-p}{the} graph. 
\end{DoxyReturn}
\hypertarget{classSpt_ab22bf4496423fdedf57bd54760b8c641}{
\index{Spt@{Spt}!update\_\-edge\_\-weight@{update\_\-edge\_\-weight}}
\index{update\_\-edge\_\-weight@{update\_\-edge\_\-weight}!Spt@{Spt}}
\subsubsection[{update\_\-edge\_\-weight}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename A$>$ bool {\bf Spt}$<$ A $>$::update\_\-edge\_\-weight (
\begin{DoxyParamCaption}
\item[{const A \&}]{src, }
\item[{int}]{weight, }
\item[{const A \&}]{dst}
\end{DoxyParamCaption}
)}}
\label{classSpt_ab22bf4496423fdedf57bd54760b8c641}


Update existing edge weight. 


\begin{DoxyParams}{Parameters}
{\em src} & source node must exist. \\
\hline
{\em weight} & new edge weight. \\
\hline
{\em dst} & destination node must exist \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
true on success. 
\end{DoxyReturn}
\hypertarget{classSpt_a97746270155c0dc5409c2a6c080099c1}{
\index{Spt@{Spt}!update\_\-node@{update\_\-node}}
\index{update\_\-node@{update\_\-node}!Spt@{Spt}}
\subsubsection[{update\_\-node}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename A$>$ bool {\bf Spt}$<$ A $>$::update\_\-node (
\begin{DoxyParamCaption}
\item[{const A \&}]{node}
\end{DoxyParamCaption}
)}}
\label{classSpt_a97746270155c0dc5409c2a6c080099c1}


Update node. 

\begin{DoxyReturn}{Returns}
false if \hyperlink{protocolthe-p}{the} node doesn't exist, otherwise true. 
\end{DoxyReturn}


The documentation for this class was generated from the following file:\begin{DoxyCompactItemize}
\item 
/home/greearb/git/xorp.ct.github/xorp/libproto/spt.hh\end{DoxyCompactItemize}
