CouenneDepGraph.hpp

Go to the documentation of this file.

/* $Id: CouenneDepGraph.hpp 549 2011-03-26 17:44:33Z pbelotti $
 *
 * Name:    CouenneDepGraph.hpp
 * Author:  Pietro Belotti
 * Purpose: class for manipulating dependencies between variables
 *
 * (C) Carnegie-Mellon University, 2007-11.
 * This file is licensed under the Eclipse Public License (EPL)
 */

#ifndef DEPGRAPH_HPP
#define DEPGRAPH_HPP

#include <vector>
#include <set>

#include "CouenneTypes.hpp"
#include "CouenneExpression.hpp"
#include "CouenneExprAux.hpp"
#include "CouenneProblemElem.hpp"

namespace Couenne {

struct compNode {
  inline bool operator () (const DepNode *n0, const DepNode *n1) const;
};



class DepNode {

public:

  enum dep_color {DEP_WHITE, DEP_GRAY, DEP_BLACK};

protected:

  int index_;

  std::set <DepNode *, compNode> *depList_;

  int order_;

  enum dep_color color_;

public:

  DepNode  (int ind):
    index_   (ind),
    depList_ (new std::set <DepNode *, compNode>),
    order_   (-1),
    color_   (DEP_WHITE) {}

  ~DepNode () 
  {if (depList_) delete depList_;}

  inline int Index () const 
  {return index_;}

  inline int Order () const 
  {return order_;}

  inline std::set <DepNode *, compNode> *DepList () const 
  {return depList_;}

  bool depends (int xi, bool = false, 
                std::set <DepNode *, compNode> *already_visited = NULL) const;

  void createOrder (DepGraph *);

  void print (int = 0, bool descend = false) const;

  enum dep_color &color () 
  {return color_;}

  std::set <DepNode *, compNode> *depList()
  {return depList_;}

  void replaceIndex (DepNode *oldVarNode, DepNode *newVarNode);
};



bool compNode::operator () (const DepNode *n0, const DepNode *n1) const
{return (n0 -> Index () < n1 -> Index ());}



class DepGraph {

protected:

  std::set <DepNode *, compNode> vertices_;

  int counter_;

public:

  DepGraph (): counter_ (0) {}

  ~DepGraph () {
    for (std::set <DepNode *, compNode>::iterator i = vertices_.begin ();
         i != vertices_.end (); ++i) 
      delete (*i);
  }

  std::set <DepNode *, compNode> &Vertices () 
  {return vertices_;}

  inline int &Counter () 
  {return counter_;}

  void insert (exprVar *);

  void insert (exprAux *);

  void erase (exprVar *);

  bool depends (int, int, bool = false);

  void createOrder ();

  void print (bool descend = false);

  DepNode *lookup (int index);

  bool checkCycles ();

  void replaceIndex (int oldVar, int newVar);
};

}

#endif