Return to navmapsdocs.tex CVS log

Up to [LON-CAPA] / doc / lonnavdocs

Annotation of doc/lonnavdocs/navmapsdocs.tex, revision 1.1

1.1     ! bowersj2    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}