source: trunk/Couenne/src/problem/depGraph/depGraph.cpp @ 114

Last change on this file since 114 was 114, checked in by stefan, 13 years ago

for gcc 4.4

File size: 4.6 KB
Line 
1/*
2 * Name:    depGraph.cpp
3 * Author:  Pietro Belotti
4 * Purpose: methods for manipulating dependencies between variables
5 *
6 * (C) Carnegie-Mellon University, 2007.
7 * This file is licensed under the Common Public License (CPL)
8 */
9
10#include <cstdlib>
11#include <cstdio>
12#include "depGraph.hpp"
13
14//#define DEBUG
15
16// Methods of the class DepNode ///////////////////////////////////////////////////////////
17
18/// does this variable depend on variable with index xi?
19bool DepNode::depends (int xi, bool recursive, 
20                       std::set <DepNode *, compNode> *already_visited) const {
21
22  // check if any node of the forward star has index xi
23  for (std::set <DepNode *, compNode>::iterator i = depList_ -> begin (); 
24       i != depList_ -> end (); ++i) {
25
26    if (!already_visited || 
27        (already_visited -> find (*i) == already_visited -> end ())) {
28
29      if (((*i) -> Index () == xi) || // check current node
30        (recursive && 
31         ((*i) -> depends (xi, recursive, already_visited)))) // check deplist recursively
32      { 
33#ifdef DEBUG
34        printf ("%d <- ", (*i) -> Index ()); 
35        fflush (stdout);
36#endif
37        return true;
38      } else {
39        if (already_visited) {
40          already_visited -> insert (*i);
41          /*printf ("checked [%d]: ", (*i) -> Index ());
42          for (std::set <DepNode *, compNode>::iterator j = already_visited -> begin ();
43               j != already_visited -> end (); ++j)
44            printf ("%d ", (*j) -> Index ());
45            printf ("\n");*/
46        }
47      }
48    }
49  }
50
51  return false;
52}
53
54
55/// assign numbering to all nodes of graph
56void DepNode::createOrder (DepGraph *g) {
57
58  if (order_ != -1) return;
59
60  if (order_ == -2) {
61
62    printf ("detected cycle in creating order, exiting\n");
63    exit (-1);
64  }
65
66  order_ = -2;
67
68  for (std::set <DepNode *, compNode>::iterator i = depList_ -> begin();
69       i != depList_ -> end (); ++i)
70    if ((*i) -> Order () == -1)
71      (*i) -> createOrder (g);
72
73  if (order_ == -2)
74    order_ = g -> Counter () ++;
75}
76
77
78/// debugging procedure
79void DepNode::print (int indent, bool descend) const {
80
81  printf ("%d ", index_); 
82  if (order_ >= 0) printf ("[%d]", order_); 
83  fflush (stdout);
84
85  if (depList_ -> size () > 0) {
86    printf ("("); fflush (stdout);
87
88    for (std::set <DepNode *, compNode>::iterator i = depList_ -> begin();
89         i != depList_ -> end (); ++i)
90      if (descend)
91        (*i) -> print (indent + 1, descend);
92      else printf ("%d ", (*i) -> Index ());
93
94    printf (") "); fflush (stdout);
95  }
96}
97
98
99// Methods of the class DepGraph ////////////////////////////////////////////////////////////
100
101
102/// insert new variable if new
103void DepGraph::insert (exprVar *var) {
104
105  DepNode *el = new DepNode (var -> Index ());
106  std::set <DepNode *, compNode>::iterator i = vertices_ . find (el); 
107
108  if (i == vertices_ . end ())
109    vertices_.insert (el);
110  else delete el;
111}
112
113
114/// insert new auxiliary if new
115void DepGraph::insert (exprAux *aux) {
116
117  if (!aux) return;
118
119  DepNode *el = new DepNode (aux -> Index ());
120  std::set <DepNode *, compNode>::iterator i = vertices_ . find (el); 
121
122  if (i == vertices_ . end ()) {
123    vertices_.insert (el);
124    aux      -> Image () -> fillDepSet (el -> DepList (), this);
125  } else {
126    aux -> Image () -> fillDepSet ((*i) -> DepList (), this);
127    delete el;
128  }
129}
130
131
132/// erase element from graph
133void DepGraph::erase (exprVar *var) {
134
135  DepNode *el = new DepNode (var -> Index ());
136  std::set <DepNode *, compNode>::iterator i = vertices_ . find (el); 
137
138  if (i != vertices_ . end ())
139    vertices_.erase (i);
140  delete el;
141}
142
143/// does w depend on x?
144bool DepGraph::depends (int wi, int xi, bool recursive) {
145
146  DepNode *el = new DepNode (wi);
147  std::set <DepNode *, compNode>::iterator i = vertices_. find (el);
148  delete el;
149
150  std::set <DepNode *, compNode> already_visited;
151
152  if (i != vertices_. end ())               // if such element is in the set
153    return (*i) -> depends (xi, recursive, &already_visited); // then search it
154  else return false;
155}
156
157
158/// assign numbering to all nodes of graph
159void DepGraph::createOrder () {
160
161  for (std::set <DepNode *, compNode>::iterator i = vertices_. begin();
162       i != vertices_. end (); ++i)
163    (*i) -> createOrder (this);
164}
165
166
167/// debugging procedure
168void DepGraph::print (bool descend) {
169
170  printf ("Dependence graph: \n");
171  for (std::set <DepNode *, compNode>::iterator i = vertices_. begin();
172       i != vertices_. end (); ++i) {
173    (*i) -> print (0, descend);
174    printf ("\n");
175  }
176}
177
178
179/// search for node in vertex set
180DepNode *DepGraph::lookup (int index) {
181
182  DepNode *el = new DepNode (index), *ret;
183  std::set <DepNode *, compNode>::iterator i = vertices_ . find (el);
184
185  ret = (i == vertices_.end ()) ? NULL : (*i);
186
187  delete el;
188  return ret;
189}
Note: See TracBrowser for help on using the repository browser.