Branch data Line data Source code
1 : : #include "meshkit/MKGraph.hpp"
2 : : #include "meshkit/MeshOp.hpp"
3 : : #include "lemon/core.h"
4 : : #include "lemon/adaptors.h"
5 : : #include "lemon/connectivity.h"
6 : : #include "lemon/math.h"
7 : : #include "lemon/graph_to_eps.h"
8 : :
9 : : namespace MeshKit
10 : : {
11 : :
12 : 38 : MKGraph::MKGraph()
13 [ + - ]: 38 : : mkGraph(), rootNode(NULL), leafNode(NULL), nodeMap(mkGraph, NULL)
14 : : {
15 : 38 : }
16 : :
17 : 42 : MKGraph::~MKGraph()
18 : : {
19 [ - + ]: 21 : }
20 : :
21 : 55 : void MKGraph::clear_graph()
22 : : {
23 : : // get all the non-root, non-leaf nodes
24 [ + - ]: 55 : std::vector<lemon::ListDigraph::Node> nodes;
25 [ + - ][ + - ]: 305 : for (lemon::ListDigraph::NodeIt nit(mkGraph); nit != lemon::INVALID; ++nit)
[ + - ][ + - ]
[ + + ]
26 [ + - ][ + - ]: 250 : if (nit != rootNode->get_node() && nit != leafNode->get_node())
[ + + ][ + - ]
[ + - ][ + + ]
[ + + ][ + - ]
[ + + # #
# # ]
27 [ + - ]: 140 : nodes.push_back(nit);
28 : :
29 : : // now delete all those nodes
30 : : // lemon will automatically delete all the edges connected to these nodes
31 [ + - ][ + - ]: 195 : for (std::vector<lemon::ListDigraph::Node>::iterator vit = nodes.begin(); vit != nodes.end(); vit++) {
[ + + ]
32 [ + - ][ + - ]: 140 : if (nodeMap[*vit]) delete nodeMap[*vit];
[ + - ][ + - ]
[ + - ][ + - ]
33 [ # # ][ # # ]: 0 : else mkGraph.erase(*vit);
34 : 55 : }
35 : :
36 : : // restore an edge between the root and leaf !! comment this out
37 : : // we are not creating it anymore in the constructor of MKCore
38 : : /*if (!mkGraph.valid(lemon::ArcLookUp<lemon::ListDigraph>(mkGraph)(rootNode->get_node(), leafNode->get_node())))
39 : : mkGraph.addArc(rootNode->get_node(), leafNode->get_node());*/
40 : 55 : }
41 : :
42 : 18 : void MKGraph::print_graph(const char * filename)
43 : : {
44 [ + - ][ + - ]: 255 : for (lemon::ListDigraph::NodeIt nit(mkGraph); nit != lemon::INVALID; ++nit) {
[ + - ][ + - ]
[ + + ]
45 [ + - ][ + - ]: 237 : std::cout << "Node: " << mkGraph.id(nit) << " ";
[ + - ][ + - ]
46 [ + - ][ + - ]: 237 : if (nit == rootNode->get_node()) std::cout << "root node" << std::endl;
[ + + ][ + - ]
[ + - ]
47 [ + - ][ + - ]: 219 : else if (nit == leafNode->get_node()) std::cout << "leaf node" << std::endl;
[ + + ][ + - ]
[ + - ]
48 [ + - ][ + - ]: 201 : else if (nodeMap[nit]) std::cout << nodeMap[nit]->get_name() << std::endl;
[ + - ][ + - ]
[ + - ][ + - ]
49 [ # # ][ # # ]: 0 : else std::cout << "(no MeshOp)" << std::endl;
50 : : }
51 [ + - ][ + - ]: 348 : for (lemon::ListDigraph::ArcIt ait(mkGraph); ait != lemon::INVALID; ++ait) {
[ + - ][ + - ]
[ + + ]
52 : : //lemon::ListDigraph::A
53 [ + - ]: 330 : lemon::ListDigraph::Node s=mkGraph.source(ait);
54 [ + - ]: 330 : lemon::ListDigraph::Node t=mkGraph.target(ait);
55 : :
56 [ + - ][ + - ]: 660 : std::cout << "Arc: "<< mkGraph.id(ait)<< " : "<< nodeMap[s]->get_name() << "(" << mkGraph.id(s)<< ") - " <<
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
57 [ + - ][ + - ]: 990 : nodeMap[t]->get_name() << "(" << mkGraph.id(t)<< ")\n";
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
58 : : }
59 : :
60 : : typedef lemon::dim2::Point<int> Point;
61 [ + - ]: 18 : lemon::ListDigraph::NodeMap< Point > coords(mkGraph);
62 : :
63 [ + - ]: 36 : lemon::Bfs<lemon::ListDigraph> bfs(mkGraph);
64 [ + - ]: 18 : bfs.init();
65 [ + - ][ + - ]: 18 : bfs.addSource(rootNode->get_node());
66 : :
67 [ + - ]: 36 : lemon::ListDigraph::NodeMap<std::string> label(mkGraph);
68 : :
69 [ + - ][ + + ]: 255 : while (!bfs.emptyQueue()) {
70 [ + - ]: 237 : lemon::ListDigraph::Node nd = bfs.processNextNode();
71 : : //assert(nd != lemon::INVALID && (nodeMap[nd] || (nd == leafNode->get_node() || nd == rootNode->get_node())));
72 [ + - ][ + - ]: 237 : std::cout << "BFS_Node, distance: " << bfs.dist(nd) << "\n ";
[ + - ][ + - ]
73 [ + - ][ + - ]: 237 : coords[nd]=Point(10*bfs.dist(nd), 10*mkGraph.id(nd));
[ + - ][ + - ]
74 [ + - ][ + - ]: 237 : if (nd == rootNode->get_node())
[ + + ]
75 [ + - ][ + - ]: 18 : label[nd]="Root";
76 : : else
77 : : {
78 [ + - ][ + - ]: 219 : if (nd == leafNode->get_node())
[ + + ]
79 [ + - ][ + - ]: 18 : label[nd] = "Leaf";
80 : : else
81 [ + - ][ + - ]: 237 : label[nd] = nodeMap[nd]->get_name();
[ + - ][ + - ]
82 : : }
83 : : }
84 : :
85 [ + - ]: 36 : std::string filen;
86 [ + + ]: 18 : if (filename)
87 [ + - ][ + - ]: 13 : filen=std::string(filename);
88 : : else
89 [ + - ]: 5 : filen = "graph.eps";
90 : :
91 : : graphToEps(mkGraph, filen).coords(coords).nodeTexts(label).
92 [ + - ][ + - ]: 36 : nodeTextSize(3).drawArrows().run();
[ + - ][ + - ]
[ + - ][ + - ]
93 : :
94 : 18 : }
95 : :
96 : 0 : void MKGraph::print_bfs_graph()
97 : : {
98 [ # # ]: 0 : lemon::Bfs<lemon::ListDigraph> bfs(mkGraph);
99 [ # # ]: 0 : bfs.init();
100 [ # # ][ # # ]: 0 : bfs.addSource(rootNode->get_node());
101 : :
102 [ # # ][ # # ]: 0 : while (!bfs.emptyQueue()) {
103 [ # # ]: 0 : lemon::ListDigraph::Node nd = bfs.processNextNode();
104 [ # # ][ # # ]: 0 : assert(nd != lemon::INVALID && (nodeMap[nd] || (nd == leafNode->get_node() || nd == rootNode->get_node())));
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # # #
# # ]
105 [ # # ][ # # ]: 0 : std::cout << "BFS_Node, distance: " << bfs.dist(nd) << ", ";
[ # # ][ # # ]
106 [ # # ][ # # ]: 0 : if (nd == rootNode->get_node()) std::cout << "root node" << std::endl;
[ # # ][ # # ]
[ # # ]
107 [ # # ][ # # ]: 0 : else if (nd == leafNode->get_node()) std::cout << "leaf node" << std::endl;
[ # # ][ # # ]
[ # # ]
108 [ # # ][ # # ]: 0 : else if (nodeMap[nd]) std::cout << nodeMap[nd]->get_name() << std::endl;
[ # # ][ # # ]
[ # # ][ # # ]
109 [ # # ][ # # ]: 0 : else std::cout << "(no MeshOp)" << std::endl;
110 : 0 : }
111 : 0 : }
112 : :
113 : : //! Get the MeshOp corresponding to a graph node
114 : 93 : MeshOp *MKGraph::get_meshop(lemon::ListDigraph::Node node) const
115 : : {
116 [ + - ]: 93 : return dynamic_cast<MeshOp*>(nodeMap[node]);
117 : : }
118 : :
119 : 1 : GraphNode *MKGraph::other_node(lemon::ListDigraph::Arc arc, GraphNode *node) const
120 : : {
121 [ + - ]: 1 : lemon::ListDigraph::Node src = mkGraph.source(arc);
122 [ + - ][ + - ]: 1 : if (src != node->get_node()) return get_node(src);
[ + - ][ + - ]
123 [ # # ][ # # ]: 1 : else return get_node(mkGraph.target(arc));
124 : : }
125 : :
126 : 0 : MeshOp *MKGraph::find_meshop(std::string op_name) const
127 : : {
128 [ # # ]: 0 : GraphNode *node = find_node(op_name);
129 [ # # ][ # # ]: 0 : return node ? dynamic_cast<MeshOp*>(node) : 0;
130 : : }
131 : :
132 : 0 : GraphNode *MKGraph::find_node(std::string op_name) const
133 : : {
134 : : // run BFS on forward graph
135 [ # # ]: 0 : lemon::Bfs<lemon::ListDigraph> bfs(mkGraph);
136 [ # # ]: 0 : bfs.init();
137 [ # # ][ # # ]: 0 : bfs.addSource(rootNode->get_node());
138 [ # # ][ # # ]: 0 : while (!bfs.emptyQueue()) {
139 [ # # ]: 0 : lemon::ListDigraph::Node nd = bfs.processNextNode();
140 [ # # ][ # # ]: 0 : assert(nd != lemon::INVALID && (nodeMap[nd] || (nd == leafNode->get_node() || nd == rootNode->get_node())));
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # # #
# # ]
141 [ # # ][ # # ]: 0 : if (nodeMap[nd] && nodeMap[nd]->get_name() == op_name) return nodeMap[nd];
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
142 : : }
143 : 0 : return NULL;
144 : : }
145 : :
146 : 142 : void MKGraph::insert_node(GraphNode *inserted, GraphNode *before, GraphNode *after)
147 : : {
148 : : // if inserted is a leaf node (i.e. is connected to leafNode), disconnect from that
149 [ + - ][ + - ]: 142 : if (mkGraph.target(inserted->out_arcs()) == leafNode->get_node())
[ + - ][ + - ]
[ + + ]
150 [ + - ][ + - ]: 110 : mkGraph.erase(inserted->out_arcs());
151 : :
152 : : // if inserted is a root node (i.e. is connected to rootNode), also disconnect that
153 [ + - ][ + - ]: 142 : if (mkGraph.source(inserted->in_arcs()) == rootNode->get_node())
[ + - ][ + - ]
[ + - ]
154 [ + - ][ + - ]: 142 : mkGraph.erase(inserted->in_arcs());
155 : :
156 [ + - ][ + - ]: 142 : lemon::ListDigraph::InArcIt iter, jter;
157 [ + + ]: 142 : if (after != NULL) { // if after is specified
158 [ + - ]: 103 : lemon::ListDigraph::Node after_node = after->get_node();
159 : :
160 : : // check if it is already connected
161 : 103 : bool b_connected = false;
162 [ + - ][ # # ]: 103 : for (iter = inserted->in_arcs(); iter != lemon::INVALID; ++iter) {
[ + - ][ + - ]
[ - + ]
163 [ # # ][ # # ]: 0 : if (mkGraph.source(iter) == after_node) {
[ # # ]
164 : 0 : b_connected = true;
165 : 0 : break;
166 : : }
167 : : }
168 : :
169 [ + - ][ + - ]: 103 : if (!b_connected) mkGraph.addArc(after_node, inserted->get_node()); // add a new arc
[ + - ]
170 : :
171 : : // remove the arc from after node
172 [ + - ][ + - ]: 299 : for (iter = before->in_arcs(); iter != lemon::INVALID; ++iter) {
[ + - ][ + - ]
[ + + ]
173 [ + - ][ + - ]: 196 : if (mkGraph.source(iter) == after_node) {
[ + + ]
174 [ + - ]: 71 : mkGraph.erase(iter);
175 : 71 : break;
176 : : }
177 : : }
178 : : }
179 : : else { // check all predecessors
180 [ + - ][ + - ]: 78 : for (iter = before->in_arcs(); iter != lemon::INVALID;) {
[ + - ][ + + ]
181 [ + - ]: 39 : lemon::ListDigraph::Node after_node = mkGraph.source(iter);
182 : :
183 : : // check if it is already connected
184 : 39 : bool b_connected = false;
185 [ + - ][ # # ]: 39 : for (jter = inserted->in_arcs(); jter != lemon::INVALID; ++jter) {
[ + - ][ + - ]
[ - + ]
186 [ # # ][ # # ]: 0 : if (mkGraph.source(jter) == after_node) {
[ # # ]
187 : 0 : b_connected = true;
188 : 0 : break;
189 : : }
190 : : }
191 : :
192 [ + - ][ + - ]: 39 : if (!b_connected) mkGraph.addArc(after_node, inserted->get_node()); // add a new arc
[ + - ]
193 : :
194 : 39 : jter = iter;
195 [ + - ]: 39 : ++iter;
196 [ + - ]: 39 : mkGraph.erase(jter); // remove the arc from after node
197 : : }
198 : : }
199 : :
200 : : // now link inserted to before
201 [ + - ][ + - ]: 142 : mkGraph.addArc(inserted->get_node(), before->get_node());
[ + - ]
202 : :
203 : : // if before is a root node (i.e. is connected to rootNode), also disconnect that
204 [ + - ][ + - ]: 142 : if (mkGraph.source(before->in_arcs()) == rootNode->get_node())
[ + - ][ + - ]
[ - + ]
205 [ # # ][ # # ]: 0 : mkGraph.erase(before->in_arcs());
206 : 142 : }
207 : :
208 : 14 : void MKGraph::add_arc(GraphNode *source, GraphNode *target)
209 : : {
210 : : // add an arc from one node to another, e.g. to add a dependency between them
211 : : // get the corresponding Lemon nodes
212 [ + - ]: 14 : lemon::ListDigraph::Node lsource = source->get_node(),
213 [ + - ]: 14 : ltarget = target->get_node();
214 : :
215 : : // if inserted is a leaf node (i.e. is connected to leafNode), disconnect from that
216 [ + - ][ + - ]: 14 : if (mkGraph.target(source->out_arcs()) == leafNode->get_node())
[ + - ][ + - ]
[ - + ]
217 [ # # ][ # # ]: 0 : mkGraph.erase(source->out_arcs());
218 : :
219 : : // if before is a root node (i.e. is connected to rootNode), also disconnect that
220 [ + - ][ + - ]: 14 : if (mkGraph.source(target->in_arcs()) == rootNode->get_node())
[ + - ][ + - ]
[ + + ]
221 [ + - ][ + - ]: 2 : mkGraph.erase(target->in_arcs());
222 : :
223 : : // now link them
224 [ + - ]: 14 : mkGraph.addArc(lsource, ltarget);
225 : 14 : }
226 : :
227 : : //! Run setup on the graph
228 : 51 : void MKGraph::setup(bool reset)
229 : : {
230 : : // run BFS on reversed graph
231 [ + - ]: 51 : lemon::ReverseDigraph<lemon::ListDigraph> rg(mkGraph);
232 [ + - ]: 51 : if (reset)
233 : : {
234 [ + - ]: 51 : lemon::Bfs<lemon::ReverseDigraph<lemon::ListDigraph> > rbfs1(rg);
235 [ + - ]: 51 : rbfs1.init();
236 [ + - ][ + - ]: 51 : rbfs1.addSource(leafNode->get_node());
237 [ + - ][ + + ]: 212 : while (!rbfs1.emptyQueue()) {
238 [ + - ]: 161 : lemon::ListDigraph::Node nd = rbfs1.processNextNode();
239 [ + - ][ + - ]: 161 : assert(nd != lemon::INVALID && (nodeMap[nd] || (nd == leafNode->get_node() || nd == rootNode->get_node())));
[ + - ][ + - ]
[ - + ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ - + ]
[ - + ][ + - ]
[ # # # #
# # ]
240 [ + - ][ + - ]: 161 : if (nodeMap[nd]) nodeMap[nd]->setup_called(false);
[ + - ][ + - ]
241 : 51 : }
242 : : }
243 : : bool called_one;
244 [ + + ]: 171 : do {
245 : 171 : called_one = false;
246 [ + - ]: 171 : lemon::Bfs<lemon::ReverseDigraph<lemon::ListDigraph> > rbfs2(rg);
247 [ + - ]: 171 : rbfs2.init();
248 [ + - ][ + - ]: 171 : rbfs2.addSource(leafNode->get_node());
249 [ + - ][ + + ]: 990 : while (!rbfs2.emptyQueue()) {
250 [ + - ]: 819 : lemon::ListDigraph::Node nd = rbfs2.processNextNode();
251 [ + - ][ + - ]: 819 : assert(nd != lemon::INVALID && (nodeMap[nd] || (nd == leafNode->get_node() || nd == rootNode->get_node())));
[ + - ][ + - ]
[ - + ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ - + ]
[ - + ][ + - ]
[ # # # #
# # ]
252 [ + - ][ + - ]: 819 : if (nodeMap[nd] && !nodeMap[nd]->setup_called()) {
[ + - ][ + - ]
[ + + ][ + + ]
253 [ + - ][ + - ]: 270 : nodeMap[nd]->setup_this();
254 [ + - ][ + - ]: 270 : nodeMap[nd]->setup_called(true);
255 : 819 : called_one = true;
256 : : }
257 : 171 : }
258 : : }
259 : : while (called_one);
260 : 51 : }
261 : :
262 : : //! Run execute on the graph
263 : 51 : void MKGraph::execute()
264 : : {
265 : :
266 : : typedef lemon::IterableIntMap<lemon::ListDigraph, lemon::ListDigraph::Node> topomap;
267 : :
268 : : // Run execute_this on all nodes in topological order
269 [ + - ]: 51 : topomap topo_levels( mkGraph );
270 [ + - ]: 51 : lemon::topologicalSort( mkGraph, topo_levels );
271 : :
272 [ + - ][ + + ]: 321 : for( int i = 0; i<topo_levels.size(); ++i){
273 [ + - ][ + - ]: 540 : for( topomap::ItemIt j(topo_levels, i); j != lemon::INVALID; ++j ){
[ + - ][ + - ]
[ + + ]
274 [ + - ]: 270 : GraphNode* gn = nodeMap[ j ];
275 [ - + ]: 270 : assert( gn );
276 [ + - ]: 270 : gn->execute_called(false);
277 : : }
278 : : }
279 : :
280 [ + - ][ + + ]: 321 : for( int i = 0; i<topo_levels.size(); ++i){
281 : :
282 [ + - ][ + - ]: 540 : for( topomap::ItemIt j(topo_levels, i); j != lemon::INVALID; ++j ){
[ + - ][ + - ]
[ + + ]
283 : :
284 [ + - ]: 270 : GraphNode* gn = nodeMap[ j ];
285 [ - + ]: 270 : assert( gn );
286 [ + - ][ + - ]: 270 : if (!gn->execute_called()) {
287 [ + - ]: 270 : gn->execute_this();
288 [ + - ]: 270 : gn->execute_called(true);
289 : : }
290 : : }
291 : 51 : }
292 : :
293 : 51 : }
294 : : // run execute on all nodes before this node (it may be a second run)
295 : 0 : void MKGraph::execute_before(GraphNode * upto)
296 : : {
297 : :
298 : : typedef lemon::IterableIntMap<lemon::ListDigraph, lemon::ListDigraph::Node> topomap;
299 : :
300 : : // Run execute_this on all nodes in topological order
301 [ # # ]: 0 : topomap topo_levels( mkGraph );
302 [ # # ][ # # ]: 0 : int upToId = mkGraph.id(upto->get_node());
303 [ # # ]: 0 : lemon::topologicalSort( mkGraph, topo_levels );
304 [ # # ][ # # ]: 0 : for( int i = 0; i<topo_levels.size(); ++i){
305 : :
306 [ # # ][ # # ]: 0 : for( topomap::ItemIt j(topo_levels, i); j != lemon::INVALID; ++j ){
[ # # ][ # # ]
[ # # ]
307 : :
308 [ # # ]: 0 : GraphNode* gn = nodeMap[ j ];
309 [ # # ]: 0 : assert( gn );
310 [ # # ][ # # ]: 0 : if (mkGraph.id(gn->get_node())==upToId)
[ # # ]
311 : 0 : return; // stop when we reached our node, do not execute again
312 [ # # ][ # # ]: 0 : if (!gn->execute_called()) {
313 [ # # ]: 0 : gn->execute_this();
314 [ # # ]: 0 : gn->execute_called(true);
315 : : }
316 : : }
317 : : }
318 : :
319 : 0 : return;
320 : : }
321 [ + - ][ + - ]: 156 : } // namespace MeshKit
|
