Return to navmapsdocs.tex CVS log

Up to [LON-CAPA] / doc / lonnavdocs

Documentation on the algorithm used in lonnavmaps.

    1: %% LyX 1.2 created this file.  For more info, see http://www.lyx.org/.
    2: %% Do not edit unless you really know what you are doing.
    3: \documentclass[english]{article}
    4: \usepackage[T1]{fontenc}
    5: \usepackage[latin1]{inputenc}
    6: \usepackage{graphicx}
    7: 
    8: \makeatletter
    9: 
   10: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
   11: \providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}
   12: 
   13: \usepackage{babel}
   14: \makeatother
   15: \begin{document}
   16: 
   17: \title{Navigation Maps Iterator Algorithm}
   18: 
   19: 
   20: \title{Jeremy Bowers}
   21: 
   22: \maketitle
   23: As part of re-doing the Navigation Maps screen for LON-CAPA, I created an
   24: iterator for traversing the maps. Since I'm not going to be around forever,
   25: I wanted to document the most subtle part of the the algorithm I developed,
   26: so later people don't need to read my mind. Since I wanted to use pictures,
   27: that rules out trying to do it all in comments.
   28: 
   29: %
   30: \begin{figure}
   31: \begin{center}\includegraphics[  height=2in,
   32:   keepaspectratio]{simple.branch.eps}\end{center}
   33: 
   34: 
   35: \caption{\label{simple branches}Simple Branching Nav Map}
   36: \end{figure}
   37: In particular, the handling of branches is a challenge. So, suppose we have
   38: the simple navigation map shown in figure \ref{simple branches}. As human
   39: beings, we can look at that resource map and mentally represent that as the
   40: following: \emph{Everybody sees resource A, then you have a choice of resources
   41: B and C, or resources E and F, and everybody will do resource D}. We want
   42: to represent that like this:
   43: 
   44: \begin{itemize}
   45: \item A
   46: 
   47: \begin{itemize}
   48: \item B or C
   49: \item E or F
   50: \end{itemize}
   51: \item D
   52: \end{itemize}
   53: Or something like that. Actually, \LaTeX{} fails me here. At the very least,
   54: I don't want a bullet in front of D, since that follows A, and in the real
   55: nav maps, {}``B or C'' is represented in two rows, but you get the idea.
   56: 
   57: The problem is that the computer doesn't have the global, overall view we
   58: get, and getting the computer to match our intuition is surprisingly difficult. 
   59: 
   60: If we consider the \emph{desired indentation depth} (or just \emph{depth}
   61: for short) as what we are looking for, so we can display the navmaps correctly,
   62: then we are looking for two things:
   63: 
   64: \begin{enumerate}
   65: \item A mapping of the nodes to some depth.
   66: \item A way of traversing the graph once the depth has been assigned.
   67: \end{enumerate}
   68: 
   69: \section{Mapping The Nodes to Some Depth}
   70: 
   71: As I talk about the algorithm, markers like \textbf{{*}{*}1{*}{*}} will be
   72: used to track the places in the source code that are being discussed.
   73: 
   74: Mapping the nodes to a depth is done via a two-pass algorithm (\textbf{{*}{*}1{*}{*}}).
   75: The passes are virtually identical, but one starts from the top and one starts
   76: from the bottom. 
   77: 
   78: The order the nodes are traversed in is not terribly importent, as long as
   79: no node is encountered before one of its parent nodes have been encountered,
   80: which is known to be true with this traversal (and most others, as well). 
   81: 
   82: For the top-down pass, we start with the first resource, and give it a {}``top-down-value''
   83: (TDV for short) value of 0 (\textbf{{*}{*}2{*}{*}}). We then progress along
   84: the links in some order, visiting resources and assigning them a value as
   85: follows:
   86: 
   87: \begin{enumerate}
   88: \item If the node we came from has only one link leaving it (i.e., this is the
   89: only next node for that node), then this node is given the same TDV value
   90: as the parent. (\textbf{{*}{*}3{*}{*}})
   91: \item If the node we came from has more then one link leaving it, this node is
   92: given the TDV value of the parent, plus one. (\textbf{{*}{*}4{*}{*}})
   93: \item If we get to any given node through multiple paths, the minimal value is
   94: taken. (See all uses of the {}``min'' function.)
   95: \end{enumerate}
   96: %
   97: \begin{figure}
   98: \begin{center}\includegraphics[  height=2in,
   99:   keepaspectratio]{tdv.vals.eps}\end{center}
  100: 
  101: 
  102: \caption{\label{TDV values figure}TDV Values}
  103: \end{figure}
  104: Using that algorithm on the given example navmap, we get the result shown
  105: in figure \ref{TDV values figure}. \textbf{A} was given the value 0 to start
  106: with. Each of \textbf{B} and \textbf{E} was given 1, because there are two
  107: ways out of \textbf{A}. The rest of the resources were given the value 1
  108: as well, because there is only one way out of the resources from that point
  109: on.
  110: 
  111: %
  112: \begin{figure}
  113: \begin{center}\includegraphics[  height=2in,
  114:   keepaspectratio]{depth.eps}\end{center}
  115: 
  116: 
  117: \caption{\label{cap:Final-Depth-labels}Final Depth labels}
  118: \end{figure}
  119: Using the same algorithm on the link-reversed graph, starting at the finish
  120: resource, we can do the same thing to get the {}``Bottom-Up-Values'' (BUV).
  121: We can then take each node, and take the minimum of each value to get the
  122: final Depth (D) value.. This is shown in figure \ref{cap:Final-Depth-labels}. 
  123: 
  124: 
  125: \section{Traversing the graph}
  126: 
  127: Now that we've assigned desired depths, we need to figure out an order for
  128: traversing the graph. I create a list of arrays, of the size of the maximum
  129: depth, which I use to keep track of the links we need to keep track of. This
  130: is stored in the variable \{STACK\}, which holds an array reference of array
  131: references of that size. 
  132: 
  133: In the shown example, the maximum depth is two, so \$self->\{STACK\} will
  134: be {[}{[}{]}, {[}{]}{]}. \textbf{A} and \textbf{D} will eventually end up
  135: in the first array, \textbf{B}, \textbf{C}, \textbf{E}, and \textbf{F} will
  136: be in the second. 
  137: 
  138: Basically, the procedure is this:
  139: 
  140: \begin{itemize}
  141: \item Select the next resource to display.
  142: \item Explore where that resource can get us, and store it in the stack.
  143: \item Repeat until there are no more resources.
  144: \end{itemize}
  145: We start by priming the stack with the first resource to be examined, the
  146: firstResource (\textbf{{*}{*}5{*}{*}}).
  147: 
  148: In order to select the next resource to display, we walk backwards along
  149: the stack until we find the first non-empty list (\textbf{{*}{*}6{*}{*}}).
  150: We pop the resource off that list, and that is the next resource (\textbf{{*}{*}7{*}{*}}).
  151: This has the effect of following branches as quickly as possible, so that
  152: we can guarentee that \textbf{B}, \textbf{C}, and \textbf{E}, \textbf{F}
  153: will both be explored before \textbf{D}. \textbf{D} will not be selected
  154: until the higher levels have been exhausted. 
  155: 
  156: Of course this works recursively, so it will work no matter how high the
  157: level goes.
  158: 
  159: The only thing that needs a special case is when there are two branches,
  160: as in the sample figure, and we get to the end of the first branch (\textbf{{*}{*}8{*}{*}}).
  161: We can't detect the fact that the branch has ended just by looking at the
  162: stack afterwards. So to remember that a branch has ended, detected when all
  163: the potential next resources are of a lower level then the current resource,
  164: even if there are no possible next resources, we push a marker onto the corresponding
  165: stack that the branch has ended (\textbf{{*}{*}9{*}{*}}). We have to push
  166: a marker onto the stack, because we may still need to recursively explore
  167: the last resource if it's a map.
  168: 
  169: And that's pretty much it; there's a lot of bookkeeping and stuff, but that's
  170: the core.
  171: \end{document}