# CouenneDepGraph.hpp

Go to the documentation of this file.

    00001 /* $Id: CouenneDepGraph.hpp 549 2011-03-26 17:44:33Z pbelotti $
    00002  *
    00003  * Name:    CouenneDepGraph.hpp
    00004  * Author:  Pietro Belotti
    00005  * Purpose: class for manipulating dependencies between variables
    00006  *
    00007  * (C) Carnegie-Mellon University, 2007-11.
    00008  * This file is licensed under the Eclipse Public License (EPL)
    00009  */
    00010
    00011 #ifndef DEPGRAPH_HPP
    00012 #define DEPGRAPH_HPP
    00013
    00014 #include <vector>
    00015 #include <set>
    00016
    00017 #include "CouenneTypes.hpp"
    00018 #include "CouenneExpression.hpp"
    00019 #include "CouenneExprAux.hpp"
    00020 #include "CouenneProblemElem.hpp"
    00021
    00022 namespace Couenne {
    00023
    00025 struct compNode {
    00026   inline bool operator () (const DepNode *n0, const DepNode *n1) const;
    00027 };
    00028
    00029
    00032
    00033 class DepNode {
    00034
    00035 public:
    00036
    00038   enum dep_color {DEP_WHITE, DEP_GRAY, DEP_BLACK};
    00039
    00040 protected:
    00041
    00043   int index_;
    00044
    00047   std::set <DepNode *, compNode> *depList_;
    00048
    00050   int order_;
    00051
    00053   enum dep_color color_;
    00054
    00055 public:
    00056
    00059   DepNode  (int ind):
    00060     index_   (ind),
    00061     depList_ (new std::set <DepNode *, compNode>),
    00062     order_   (-1),
    00063     color_   (DEP_WHITE) {}
    00064
    00066   ~DepNode ()
    00067   {if (depList_) delete depList_;}
    00068
    00070   inline int Index () const
    00071   {return index_;}
    00072
    00074   inline int Order () const
    00075   {return order_;}
    00076
    00078   inline std::set <DepNode *, compNode> *DepList () const
    00079   {return depList_;}
    00080
    00082   bool depends (int xi, bool = false,
    00083                 std::set <DepNode *, compNode> *already_visited = NULL) const;
    00084
    00086   void createOrder (DepGraph *);
    00087
    00089   void print (int = 0, bool descend = false) const;
    00090
    00092   enum dep_color &color ()
    00093   {return color_;}
    00094
    00097   std::set <DepNode *, compNode> *depList()
    00098   {return depList_;}
    00099
    00102   void replaceIndex (DepNode *oldVarNode, DepNode *newVarNode);
    00103 };
    00104
    00105
    00107
    00108 bool compNode::operator () (const DepNode *n0, const DepNode *n1) const
    00109 {return (n0 -> Index () < n1 -> Index ());}
    00110
    00111
    00114
    00115 class DepGraph {
    00116
    00117 protected:
    00118
    00120   std::set <DepNode *, compNode> vertices_;
    00121
    00123   int counter_;
    00124
    00125 public:
    00126
    00128   DepGraph (): counter_ (0) {}
    00129
    00131   ~DepGraph () {
    00132     for (std::set <DepNode *, compNode>::iterator i = vertices_.begin ();
    00133          i != vertices_.end (); ++i)
    00134       delete (*i);
    00135   }
    00136
    00138   std::set <DepNode *, compNode> &Vertices ()
    00139   {return vertices_;}
    00140
    00142   inline int &Counter ()
    00143   {return counter_;}
    00144
    00146   void insert (exprVar *);
    00147
    00149   void insert (exprAux *);
    00150
    00152   void erase (exprVar *);
    00153
    00155   bool depends (int, int, bool = false);
    00156
    00158   void createOrder ();
    00159
    00161   void print (bool descend = false);
    00162
    00164   DepNode *lookup (int index);
    00165
    00167   bool checkCycles ();
    00168
    00172   void replaceIndex (int oldVar, int newVar);
    00173 };
    00174
    00175 }
    00176
    00177 #endif

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines