[kplato] Some code for KPTProject::getDuration()

[John D Lamb]

This is a multi-part message in MIME format.
--------------D5025E5856975D2BFEDF476C
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

I've had a look at Thomas Zander's code. I don't actually follow all the
concepts; so I've had a first stab at writing the code to handle
PERT/CPM. I've used a substantially simplified and slightly modified
version of kptnode because it made it easier to test the code robustly.
At the moment, it will compile with
g++ kptnode.cc

I've used STL a lot because it is very efficient and gives reasonably
compact source and object code. I don't know how easy it is to
substitute the STL list with a QList. In any case I think there's a
couple of good arguments for writing a core library that doesn't use Qt
(even though I suggested durations as the Qt class). First, we'll need a
lot of algorithms that are already available efficiently in STL. Second,
the library could be used outside this project. Third, it may be easier
to test (debug) the code as a library seperate from the GUI. The obvious
argument against is that we'd have to write conversion functions for an
interface to the Qt part - I can't think of a good way to counter that.
:-)

The code itself raised some issues for me. First, a lot of the core
functions like getDuration need PERT/CPM to have been done before they
can return a sensible value. Second, I haven't yet understood how kplato
will deal with activities that have already finished in a project.
Third, functions like getDuration will have to call the basic PERT/CPM
routines many times if we want a Monte Carlo simulation for the likely
outcome of a project. 

I think subprojects are going to be very easy to handle.

Please let me know if you can do anything with this or see improvements.
Clearly, we need more data-hiding.

The two files attached are kptnode.h and kptnode.cc. Don't overwrite the
versions in the kplato archive. If this code can be used, it will need
careful merging.

JDL
--------------D5025E5856975D2BFEDF476C
Content-Type: text/plain; charset=us-ascii;
 name="kptnode.h"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="kptnode.h"

/*
 * $id$
 * Copyright (C) 2001 John D Lamb
 */

#include"kptnode.h"
/*
 * Simplified example of kptnode
 */

#include<list>
#include<algorithm>
#include<string>
#include<iostream>

using namespace std;

#ifndef kptnode_h
#define kptnode_h

class KPTNode
{
 public:
  KPTNode( const string &description );
  virtual ~KPTNode();
  virtual double getDuration();
  virtual void dump() const;
 public: //Really should be private
  double duration; //Really KPTDuration
  list<KPTNode*> uncompletedPredecessors;
  list<KPTNode*> uncompletedSuccessors;
  double earliestStart;
  double latestFinish;
  list<KPTNode*> predecessors;
  list<KPTNode*> successors;
  int nodeType; //Really should be an enumerated type
  string getDescription() const;
 private:
  string description;
};

class KPTProject : public KPTNode
{
 public:
  KPTProject( const string &description );
  virtual ~KPTProject();
  void addNode( KPTNode &node );
  void createDependency( KPTNode &start, KPTNode &finish );
  virtual void dump() const;
  virtual double getDuration();
 public: //Really should be private
  KPTNode startNode;
  KPTNode endNode;
 private: //maybe could be protected
  static bool emptyUncompletedSuccessor( KPTNode* );
  static bool emptyUncompletedPredecessor( KPTNode* );
};


#endif

--------------D5025E5856975D2BFEDF476C
Content-Type: text/plain; charset=us-ascii;
 name="kptnode.cc"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="kptnode.cc"

/*
 * $id$
 * Copyright (C) 2001 John D Lamb
 */

#include"kptnode.h"

KPTNode::KPTNode( const string &description )
{
  this->description.assign( description );
  duration = 0;
  nodeType = 0; // A task if not specified otherwise
}

KPTNode::~KPTNode()
{
}

double KPTNode::getDuration()
{
  return duration;
}

string KPTNode::getDescription() const
{
  return description;
}

void KPTNode::dump() const
{
  cout << "Node: " << description << " - type " << nodeType << endl;
  cout << "Duration: " << duration << endl;
  cout << "Earliest start: " << earliestStart << endl;
  cout << "Latest finish: " << latestFinish << endl;
  if( !uncompletedPredecessors.empty() )
    cout << uncompletedPredecessors.size() << " uncompleted predecesors.\n";
  else if( !uncompletedSuccessors.empty() )
    cout << uncompletedSuccessors.size() << " uncompleted successors.\n";
  else
    cout << "Most recent PERT/CPM iteration OK on this node.\n";
  cout << endl;
}

KPTProject::KPTProject( const string &description )
  : KPTNode( description ),
    startNode( "start" ),
    endNode( "finish" )
{
  nodeType = 1; // A project
  /* startNode and endNode should have duration zero because they are only
   * there to aid the PERT/CPM calculation.
   */
  startNode.duration = 0;
  endNode.duration = 0;
  createDependency( startNode, endNode );
}

KPTProject::~KPTProject()
{
}

void KPTProject::addNode( KPTNode &node )
{
  /* indicate that a node has been added
   */
  createDependency( startNode, node );
  createDependency( node, endNode );
}

void KPTProject::createDependency( KPTNode &start, KPTNode &finish )
{
  /* Tell project that start has finish as a successor (in time) and
   * finish has start as a predecessor.
   */
  start.successors.push_back( &finish );
  finish.predecessors.push_back( &start );
}

double KPTProject::getDuration()
{
  /* This is where PERT/CPM gets used in earnest.
   * First run through all the nodes of the project
   * and make sure the (should be) private variable
   * duration has a sensible value. This should be possible by running
   * getDuration on each node.
   * Note that it is important to set the value of duration rather than
   * use a function call if (say) getDuration returns a random value.
   * In general the following is not nonsensical - even if it is in this
   * example.
   */
  list<KPTNode*>::iterator p, q;
  list<KPTNode*> unfinishedNodes;
  for( p = startNode.successors.begin(); p != startNode.successors.end(); ++p )
    (*p)->duration = (*p)->getDuration(); /* in general getDuration() may
					   * return soomething other than
					   * duration. */
  /* Now that duration is fixed for all subnodes of the project,
   * we can get a value for the project itself using PERT/CPM.
   * Also copy successors and predecessors to uncompleted versions.
   */
  startNode.earliestStart = 0;
  for( p = startNode.successors.begin(); p != startNode.successors.end(); ++p )
    {
      (*p)->earliestStart = 0; // Maybe this should be current time?
      (*p)->uncompletedSuccessors.assign( (*p)->successors.begin(),
					  (*p)->successors.end() );
      (*p)->uncompletedPredecessors.assign( (*p)->predecessors.begin(),
					    (*p)->predecessors.end() );
    }
  startNode.uncompletedSuccessors.assign( startNode.successors.begin(),
					  startNode.successors.end() );
  /* Now do a forward pass to get earliest starts.
   * Mark all nodes initially as unfinished.
   */
  unfinishedNodes.assign( startNode.successors.begin(),
			  startNode.successors.end() );
  unfinishedNodes.push_back( &startNode );
  while( !unfinishedNodes.empty() )
    {
      /* Find the first node that has been completed. Initially it must be the
       * start node. ***Note that this could fail if the Project is allowed
       * to contain any directed cycle*** ...but a directed cycle would
       * violate time-dependency assumptions.
       */
      p = find_if( unfinishedNodes.begin(), unfinishedNodes.end(),
		   emptyUncompletedPredecessor );
      /* Propagate earliest start time + duration to each succesor of (*p)
       * and remove (*p) from uncompletedPredecessors of each succesor.
       */
      double nextStart = (*p)->earliestStart + (*p)->duration;
      for( q = (*p)->successors.begin(); q != (*p)->successors.end(); ++q )
	{
	  if( nextStart > (*q)->earliestStart )
	    (*q)->earliestStart = nextStart;
	  (*q)->uncompletedPredecessors
	    .erase( find( (*q)->uncompletedPredecessors.begin(),
			  (*q)->uncompletedPredecessors.end(), (*p) ) );
	}
      unfinishedNodes.erase( p );
    }
  /* copy earliest start at end node to latest finish
   * and note duration.
   */
  endNode.latestFinish = endNode.earliestStart;
  duration = endNode.latestFinish - startNode.earliestStart; 
  for( p = endNode.predecessors.begin(); p != endNode.predecessors.end(); ++p )
    {
      (*p)->latestFinish = endNode.latestFinish;
    }
  /* Now do a backward pass to get earliest starts.
   * Mark all nodes initially as unfinished.
   */
  unfinishedNodes.assign( endNode.predecessors.begin(),
			  endNode.predecessors.end() );
  unfinishedNodes.push_back( &endNode );
  while( !unfinishedNodes.empty() )
    {
      /* Find the first node that has been completed. Initially it must be the
       * end node. ***Note that this could fail if the Project is allowed
       * to contain any directed cycle*** ...but a directed cycle would
       * violate time-dependency assumptions.
       */
      p = find_if( unfinishedNodes.begin(), unfinishedNodes.end(),
		   emptyUncompletedSuccessor );
      /* Propagate latest finish time - duration to each predecessor of (*p)
       * and remove (*p) from uncompletedSuccessors of each predecessor.
       */
      double nextFinish = (*p)->latestFinish - (*p)->duration;
      for( q = (*p)->predecessors.begin(); q != (*p)->predecessors.end(); ++q )
	{
	  if( nextFinish < (*q)->latestFinish )
	    (*q)->latestFinish = nextFinish;
	  (*q)->uncompletedSuccessors
	    .erase( find( (*q)->uncompletedSuccessors.begin(),
			  (*q)->uncompletedSuccessors.end(), (*p) ) );
	}
      unfinishedNodes.erase( p );
    }
  /* Save earliest start/latest finish to project. These will probably
   * immediately change if the project is a subproject. Is this right?
   */
  earliestStart = startNode.earliestStart;
  latestFinish = endNode.latestFinish;
  return duration;
}

/* private functions needed by STL algorithm. */
bool KPTProject::emptyUncompletedSuccessor( KPTNode *node )
{
  return node->uncompletedSuccessors.empty();
}
bool KPTProject::emptyUncompletedPredecessor( KPTNode *node )
{
  return node->uncompletedPredecessors.empty();
}


void KPTProject::dump() const
{
  cout << "===============================" << endl;
  KPTNode::dump();
  cout << "===============================" << endl;
  list<KPTNode*>::const_iterator p;
  for( p = startNode.successors.begin(); p != startNode.successors.end(); ++p )
    (*p)->dump();
  cout << "===============================" << endl;
}

int main()
{
  KPTNode A( "A" );
  KPTNode B( "B" );
  KPTNode C( "C" );
  KPTNode D( "D" );
  KPTProject project( "Project" );
  project.addNode( A );
  project.addNode( B );
  project.addNode( C );
  project.addNode( D );
  A.duration = 7.3;
  B.duration = 1.4;
  C.duration = 5.2;
  D.duration = 6.0;
  project.createDependency( A, B );
  project.createDependency( C, B );
  project.createDependency( C, D );
  project.getDuration();
  project.dump();
  return 0;
}

--------------D5025E5856975D2BFEDF476C--