Couenne 0.5.8
Loading...
Searching...
No Matches
CouenneDepGraph.hpp
Go to the documentation of this file.
1/* $Id: CouenneDepGraph.hpp 549 2011-03-26 17:44:33Z pbelotti $
2 *
3 * Name: CouenneDepGraph.hpp
4 * Author: Pietro Belotti
5 * Purpose: class for manipulating dependencies between variables
6 *
7 * (C) Carnegie-Mellon University, 2007-11.
8 * This file is licensed under the Eclipse Public License (EPL)
9 */
10
11#ifndef DEPGRAPH_HPP
12#define DEPGRAPH_HPP
13
14#include <vector>
15#include <set>
16
17#include "CouenneTypes.hpp"
18#include "CouenneExpression.hpp"
19#include "CouenneExprAux.hpp"
21
22namespace Couenne {
23
25struct compNode {
26 inline bool operator () (const DepNode *n0, const DepNode *n1) const;
27};
28
29
32
33class DepNode {
34
35public:
36
39
40protected:
41
43 int index_;
44
47 std::set <DepNode *, compNode> *depList_;
48
50 int order_;
51
54
55public:
56
59 DepNode (int ind):
60 index_ (ind),
61 depList_ (new std::set <DepNode *, compNode>),
62 order_ (-1),
63 color_ (DEP_WHITE) {}
64
67 {if (depList_) delete depList_;}
68
70 inline int Index () const
71 {return index_;}
72
74 inline int Order () const
75 {return order_;}
76
78 inline std::set <DepNode *, compNode> *DepList () const
79 {return depList_;}
80
82 bool depends (int xi, bool = false,
83 std::set <DepNode *, compNode> *already_visited = NULL) const;
84
87
89 void print (int = 0, bool descend = false) const;
90
92 enum dep_color &color ()
93 {return color_;}
94
97 std::set <DepNode *, compNode> *depList()
98 {return depList_;}
99
102 void replaceIndex (DepNode *oldVarNode, DepNode *newVarNode);
103};
104
105
107
108bool compNode::operator () (const DepNode *n0, const DepNode *n1) const
109{return (n0 -> Index () < n1 -> Index ());}
110
111
114
115class DepGraph {
116
117protected:
118
120 std::set <DepNode *, compNode> vertices_;
121
124
125public:
126
129
132 for (std::set <DepNode *, compNode>::iterator i = vertices_.begin ();
133 i != vertices_.end (); ++i)
134 delete (*i);
135 }
136
138 std::set <DepNode *, compNode> &Vertices ()
139 {return vertices_;}
140
142 inline int &Counter ()
143 {return counter_;}
144
146 void insert (exprVar *);
147
149 void insert (exprAux *);
150
152 void erase (exprVar *);
153
155 bool depends (int, int, bool = false);
156
158 void createOrder ();
159
161 void print (bool descend = false);
162
164 DepNode *lookup (int index);
165
167 bool checkCycles ();
168
172 void replaceIndex (int oldVar, int newVar);
173};
174
175}
176
177#endif
Dependence graph.
void insert(exprAux *)
insert new auxiliary if new
int counter_
counter to assign numbering to all nodes
void createOrder()
assign numbering to all nodes of graph
void print(bool descend=false)
debugging procedure
bool depends(int, int, bool=false)
does w depend on x?
void insert(exprVar *)
insert new variable if new
std::set< DepNode *, compNode > & Vertices()
return vertex set
void replaceIndex(int oldVar, int newVar)
replace, throughout the whole graph, the index of a variable with another in the entire graph.
int & Counter()
node index counter
DepNode * lookup(int index)
search for node in vertex set
std::set< DepNode *, compNode > vertices_
set of variable nodes
void erase(exprVar *)
delete element
bool checkCycles()
check for dependence cycles in graph
vertex of a dependence graph.
void createOrder(DepGraph *)
assign numbering to all nodes of graph
bool depends(int xi, bool=false, std::set< DepNode *, compNode > *already_visited=NULL) const
does this variable depend on variable with index xi?
enum dep_color & color()
return or set color of a node
DepNode(int ind)
fictitious constructor: only fill in index (such object is used in find() and then discarded)
dep_color
color used in DFS for checking cycles
std::set< DepNode *, compNode > * depList_
index nodes on which this one depends (forward star in dependence graph)
std::set< DepNode *, compNode > * depList()
index nodes on which this one depends (forward star in dependence graph)
int index_
index of variable associated with node
int Order() const
return index of this variable
int order_
order in which this variable should be updated, evaluated, etc.
enum dep_color color_
color used in DFS for checking cycles
void print(int=0, bool descend=false) const
debugging procedure
void replaceIndex(DepNode *oldVarNode, DepNode *newVarNode)
replace the index of a variable with another in the entire graph.
std::set< DepNode *, compNode > * DepList() const
return all variables it depends on
int Index() const
return index of this variable
Auxiliary variable.
variable-type operator
general include file for different compilers
ipindex Index
structure for comparing nodes in the dependence graph
bool operator()(const DepNode *n0, const DepNode *n1) const
structure for comparing nodes