📄 page582.html
字号:
<HTML><HEAD><TITLE>Implementation</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html7838" HREF="page583.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7836" HREF="page581.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7832" HREF="page581.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7840" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0016601000000000000000">Implementation</A></H3><P>Given an activity-node graph,the objective of critical path analysis is to determinethe slack time for each activity andthereby to identify the critical activities and the critical path.We shall assume that the activity node graphhas already been transformed to an edge-node graph.The implementation of this transformationis left as a project for the reader (Project <A HREF="page584.html#projectgraphsxform"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).Therefore, the first step is to compute the earliest and latest event times.<P>According to Equation <A HREF="page581.html#eqngraphsetime"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the earliest event time of vertex <I>w</I>is obtained from the earliest event times of all its predecessors.Therefore, must compute the earliest event times<em>in topological order</em>.To do this, we define the <tt>EarliestTimeVisitor</tt>shown in Program <A HREF="page582.html#progalgorithmsi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="55526"> </A><A NAME="progalgorithmsi"> </A> <IMG WIDTH=575 HEIGHT=277 ALIGN=BOTTOM ALT="program55523" SRC="img2470.gif" ><BR><STRONG>Program:</STRONG> Critical path analysis--computing earliest event times.<BR><P><P>The <tt>EarliestTimeVisitor</tt> has one instance attribute,<tt>_earliestTime</tt>,which is an array used to record the <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline72369" SRC="img2461.gif" > values.The <tt>visit</tt> method of the <tt>EarliestTimeVisitor</tt> class implements directly Equation <A HREF="page581.html#eqngraphsetime"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.It uses the <tt>incidentEdges</tt> property to obtain an iterator that enumeratesall the predecessors of a given nodeand computes <IMG WIDTH=186 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72427" SRC="img2471.gif" >.<P>In order to compute the latest event times,it is necessary to define also a <tt>LatestTimeVisitor</tt>.This visitor must visit the vertices of the event-node graphin <em>reverse topological order</em>.Its implementation follows directly from Equation <A HREF="page581.html#eqngraphsltime"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>and Program <A HREF="page582.html#progalgorithmsi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P>Program <A HREF="page582.html#progalgorithmsh"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the methodcalled <tt>criticalPathAnalysis</tt> that does what its name implies.This method takes as its argument a <tt>Digraph</tt>that represents an event-node graph.This implementation assumes that the edge weights are <tt>int</tt>s.<P><P><A NAME="55555"> </A><A NAME="progalgorithmsh"> </A> <IMG WIDTH=575 HEIGHT=489 ALIGN=BOTTOM ALT="program55552" SRC="img2472.gif" ><BR><STRONG>Program:</STRONG> Critical path analysis--finding the critical paths.<BR><P><P>The method first uses the <tt>EarliestTimeVisitor</tt> in atopological order traversal to compute the earliest event timeswhich are recored in the <tt>earliestTime</tt> array (lines 6-9).Next, the latest event times are computed and recorded inthe <tt>latestTime</tt> array.Notice that this is done using a <tt>LatestTimeVisitor</tt>in a <em>postorder</em> depth-first traversal (lines 11-14).This is because a postorder depth-first traversalis equivalent to a topological order traversal in reverse!<P>Once the earliest and latest event times have been found,we can compute the slack time for each edge.In the implementation shown,an edge-weighted graph is constructed that is isomorphic with thethe original event-node graph,but in which the edge weights are the slack timesas given by Equation <A HREF="page581.html#eqngraphsslack"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (lines 16-23).By constructing such a graph we can make use of Dijkstra's algorithmfind the shortest path from start to finishsince the shortest path must be the critical path (line 24).<P>The <tt>DijkstrasAlgorithm</tt> method given in Section <A HREF="page565.html#secgraphsdijkstra"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>returns its result in the form of a shortest-path graph.The shortest-path graph for the activity-node graph of Figure <A HREF="page581.html#figcritical2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>is shown in Figure <A HREF="page582.html#figcritical3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.By following the path in this graph from vertex 9 back to vertex 0,we find that the critical path is <IMG WIDTH=105 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72429" SRC="img2473.gif" >.<P><P><A NAME="55912"> </A><A NAME="figcritical3"> </A> <IMG WIDTH=575 HEIGHT=150 ALIGN=BOTTOM ALT="figure55570" SRC="img2474.gif" ><BR><STRONG>Figure:</STRONG> The critical path graph corresponding to Figure <A HREF="page581.html#figcritical2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<BR><P><HR><A NAME="tex2html7838" HREF="page583.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7836" HREF="page581.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7832" HREF="page581.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7840" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -