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

[John D Lamb]

Thomas Zander wrote:

> 
> The 3 lists are as follows;
> - m_nodes contains all child nodes in the logical structure.
>   (making table contains child node polishing wood)
> - m_dependChildNodes contains all nodes that are dependent on this node
>   to [finish|start] before they [start|end]
> - m_dependParentNodes contains all nodes that this nodes depends on to
>   [finish|start] before I can [start|end]
> 
I think we can assume that 
 - m_dependChildNodes contains all nodes that are dependent on this node
   to finish before they start
anything more complicated can be represented by dummy nodes of some
kind. For example If activity B can't start until A has started, create
a node A_start that must precede both A and B and has duration 0. In
practice, node like A_start are probably very rare. I haven't seen them
in the OR literature anywhere.

If we don't assume this, the PERT/CPM stuff is going to get slow and
complicated.

> 
> Your code examples don't make sense since the 2 tree structures are
> totally seperate. In my example the whole thing was in one 'tree' but
> it is entirely possible to have one node in project X being dependent on
> another node in project Y.
> 
> Maybe not in the calculations (yet) but in the data structure it should be.
> 
> >
> >   KPTRelation* getFirstDependChild() {
> >     if( m_parent == 0 )
> >       return 0;
> >     else {
> >       q = find_if( m_parent->m_relations.begin(),
> >                    m_parent->m_relations.end(),
> >                    is_successor( this ) );
> 
> Whoa!!! That is a private list, only for internal use, don't use it like that
> that is not OO.
> In this I mean that it is not nice to assume things about the internals of
> data you are pointing to, even if you are based on the same class.
> In other words; either store your own data, or use a method on the remote
> object for searching.
> 
Yes? My point was that the m_dependChildNodes and m_dependParentNodes
violate OOP just as much as my suggestion because if node A has a
dependChildNode (actually a KPTRelation) R it must have parent A its
child B must have R as a dependChildNode. My suggestion would get round
this, though not around the fact that there are constraints in the data
that cannot be encapsulated by OOP (at least not in C++).

Actually, I prefer m_dependChildNodes and m_dependParentNodes.

Here is how I would deal with adding a KPTRelation to a project. I'm not
sure a static function is sensible. I'm not even sure the function is in
the right class. But note how we can use the data structure to test the
precondition that cannot be encapsulated in the OO structure. (You may
have to guess what some of the helper functions do.) The STL guarantees
efficiency and that the iterators will always make sense. It also mixes
easily with the Qt stuff and can be hidden in KPTRelation.cc or
KPTNode.cc or ...

#include<iterator>
#include<list>
#include<algorithm>
...
class KPTRelation
{
public:
  ...

  /**
   * Construct a KPTRelation between two nodes.
   * @param s The parent node or predecessor.
   * @param t The child node or successor.
   * @param r A QList that will contain a directed path of KPTRelations
from
   * t to s if adding the relation would violate the postcondition.
   *
   * Preconditions:
   * there is no directed circuit of KPTRelations in the Project;
   * [s and t have a common (tree) parent].
   *
   * Postcondition:
   * there is no directed circuit of KPTRelations in the KPTProject.
   * If this would be violated the KPTRelation would not be added to
   * the KPTProject.
   */
  static void createRelation( KPTNode* const s, KPTNode* const t,
                              QList<KPTRelation> &r, ...  )
  {
    /* Make sure r is empty */
    r.clear();
    /* Use breadth first search (queue) to check efficiently whether
     * t is already joined to s
     */
    list<KPTRelation*> q;
    list<KPTRelation*>::iterator i;
    /* Create Relation and add to q */
    KPTRelation* new_relation = new KPTRelation( s, t, ... );
    q.push_back( new_relation );
    /* Check forward dependencies */
    for( i = q.begin(); i != q.end(); ++i )
      {
        /* get child node from i */
        KPTNode* n = (*i)->getChild();
        /* get child relations from n and add each to q if child node
         * is not already a child node in q.
         */
        for( QListIterator<KPTRelation> j( n->getDependChildNodes() );
             j.current(); ++j )
          {
            KPTNode *child = j.current()->getChild();
            if( child == s )
              {
                /* Add a path from t to s to r: first add j.current() */
                KPTRelation* relation = j.current();
                r.insert( 0, relation );
                for( KPTNode* n = relation->getParent(); n != t;
                     n = relation->getParent() )
                  {
                    relation = *find_if( q.begin(), q.end(),
                                         has_child_node( n ) );
                    r.insert( 0, relation );
                  }
                /* Adding the new relation would create a loop */
                delete new_relation;
                return;
              }
            else if( find_if( i, q.end(), has_child_node( s ) ) ==
q.end() )
              {
                q.push_back( j.current() );
              }
          }
      }
    /* New KPTRelation is checked and found to be OK. So add it to nodes
*/
    s->appendDependChildNode( new_relation );
    t->appendDependParentNode( new_relation );
  }
  ...  
protected:
  class has_child_node
  {
  public:
    has_child_node( KPTNode *const n ) : n(n) {}
    bool operator()( KPTRelation *const r ) const
    { return r->getChild() == n; }
  private:
    KPTNode *const n;
  };
  ...
};

> True, I used them, and then just rewrote them to a class to basically do
> the same thing.
> I think it is confusing to see that a struct has a destructor ;)

See example above...