Changeset 1681:84e43c7ca1e3 in lemon-0.x
- Timestamp:
- 09/12/05 13:24:54 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2201
- Files:
-
- 1 added
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
demo/grid_graph_demo.cc
r1680 r1681 2 2 #include <lemon/graph_adaptor.h> 3 3 #include <lemon/graph_to_eps.h> 4 #include <lemon/bfs.h> 4 5 #include <lemon/xy.h> 5 6 … … 11 12 12 13 int main() { 13 GridGraph graph(5, 7); 14 ifstream in("grid_graph_demo.in"); 15 int width, height; 16 in >> width >> height; 17 int start_x, start_y; 18 in >> start_x >> start_y; 19 int stop_x, stop_y; 20 in >> stop_x >> stop_y; 21 22 GridGraph graph(width, height); 23 GridGraph::Node start = graph(start_x - 1, start_y - 1); 24 GridGraph::Node stop = graph(stop_x - 1, stop_y - 1); 25 GridGraph::NodeMap<bool> filter(graph); 26 27 for (int j = 0; j < height; ++j) { 28 in >> ws; 29 for (int i = 0; i < width; ++i) { 30 char c; in >> c; 31 filter[graph(i, j)] = (c == '.'); 32 } 33 } 34 35 typedef NodeSubGraphAdaptor<GridGraph, 36 GridGraph::NodeMap<bool> > FilteredGraph; 37 38 FilteredGraph filtered(graph, filter); 39 40 Bfs<FilteredGraph> bfs(filtered); 41 std::cout << "The length of shortest path: " << 42 bfs.run(start, stop) << std::endl; 43 14 44 GridGraph::NodeMap<xy<double> > coord(graph); 15 45 for (int i = 0; i < graph.width(); ++i) { 16 46 for (int j = 0; j < graph.height(); ++j) { 17 coord[graph(i, j)] = xy<double>( i * 10.0, j * 10.0);47 coord[graph(i, j)] = xy<double>( i * 10.0, j * 10.0); 18 48 } 19 49 } 20 graphToEps(graph, "grid_graph.eps").scaleToA4(). 50 51 FilteredGraph::EdgeMap<Color> color(filtered, Color(0.0, 0.0, 0.0)); 52 53 for (GridGraph::Node node = stop; 54 node != start; node = bfs.predNode(node)) { 55 color[bfs.pred(node)] = Color(1.0, 0.0, 0.0); 56 } 57 58 graphToEps(filtered, "grid_graph.eps").scaleToA4(). 21 59 title("Grid graph"). 22 60 copyright("(C) 2005 LEMON Project"). … … 25 63 nodeScale(.45). 26 64 drawArrows(). 65 edgeColors(color). 27 66 run(); 67 68 std::cout << "The shortest path is written to grid_graph.eps" << std::endl; 69 28 70 return 0; 29 71 } -
lemon/graph_adaptor.h
r1669 r1681 207 207 208 208 209 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap> 209 template <typename _Graph, typename NodeFilterMap, 210 typename EdgeFilterMap, bool checked = true> 210 211 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> { 211 212 public: … … 226 227 227 228 public: 228 // SubGraphAdaptorBase(Graph& _graph,229 // NodeFilterMap& _node_filter_map,230 // EdgeFilterMap& _edge_filter_map) :231 // Parent(&_graph),232 // node_filter_map(&node_filter_map),233 // edge_filter_map(&edge_filter_map) { }234 229 235 230 typedef typename Parent::Node Node; … … 240 235 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 241 236 } 237 242 238 void first(Edge& i) const { 243 239 Parent::first(i); 244 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 245 } 240 while (i!=INVALID && (!(*edge_filter_map)[i] 241 || !(*node_filter_map)[Parent::source(i)] 242 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 243 } 244 246 245 void firstIn(Edge& i, const Node& n) const { 247 246 Parent::firstIn(i, n); 248 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 249 } 247 while (i!=INVALID && (!(*edge_filter_map)[i] 248 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 249 } 250 250 251 void firstOut(Edge& i, const Node& n) const { 251 252 Parent::firstOut(i, n); 252 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 253 while (i!=INVALID && (!(*edge_filter_map)[i] 254 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 253 255 } 254 256 … … 257 259 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 258 260 } 261 259 262 void next(Edge& i) const { 260 263 Parent::next(i); 261 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 262 } 264 while (i!=INVALID && (!(*edge_filter_map)[i] 265 || !(*node_filter_map)[Parent::source(i)] 266 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 267 } 268 263 269 void nextIn(Edge& i) const { 264 270 Parent::nextIn(i); 265 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 266 } 271 while (i!=INVALID && (!(*edge_filter_map)[i] 272 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 273 } 274 267 275 void nextOut(Edge& i) const { 268 276 Parent::nextOut(i); 269 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 277 while (i!=INVALID && (!(*edge_filter_map)[i] 278 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 270 279 } 271 280 … … 315 324 return i; 316 325 } 317 318 326 }; 327 328 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap> 329 class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false> 330 : public GraphAdaptorBase<_Graph> { 331 public: 332 typedef _Graph Graph; 333 typedef GraphAdaptorBase<_Graph> Parent; 334 protected: 335 NodeFilterMap* node_filter_map; 336 EdgeFilterMap* edge_filter_map; 337 SubGraphAdaptorBase() : Parent(), 338 node_filter_map(0), edge_filter_map(0) { } 339 340 void setNodeFilterMap(NodeFilterMap& _node_filter_map) { 341 node_filter_map=&_node_filter_map; 342 } 343 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) { 344 edge_filter_map=&_edge_filter_map; 345 } 346 347 public: 348 349 typedef typename Parent::Node Node; 350 typedef typename Parent::Edge Edge; 351 352 void first(Node& i) const { 353 Parent::first(i); 354 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 355 } 356 357 void first(Edge& i) const { 358 Parent::first(i); 359 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 360 } 361 362 void firstIn(Edge& i, const Node& n) const { 363 Parent::firstIn(i, n); 364 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 365 } 366 367 void firstOut(Edge& i, const Node& n) const { 368 Parent::firstOut(i, n); 369 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 370 } 371 372 void next(Node& i) const { 373 Parent::next(i); 374 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 375 } 376 void next(Edge& i) const { 377 Parent::next(i); 378 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 379 } 380 void nextIn(Edge& i) const { 381 Parent::nextIn(i); 382 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 383 } 384 385 void nextOut(Edge& i) const { 386 Parent::nextOut(i); 387 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 388 } 389 390 /// This function hides \c n in the graph, i.e. the iteration 391 /// jumps over it. This is done by simply setting the value of \c n 392 /// to be false in the corresponding node-map. 393 void hide(const Node& n) const { node_filter_map->set(n, false); } 394 395 /// This function hides \c e in the graph, i.e. the iteration 396 /// jumps over it. This is done by simply setting the value of \c e 397 /// to be false in the corresponding edge-map. 398 void hide(const Edge& e) const { edge_filter_map->set(e, false); } 399 400 /// The value of \c n is set to be true in the node-map which stores 401 /// hide information. If \c n was hidden previuosly, then it is shown 402 /// again 403 void unHide(const Node& n) const { node_filter_map->set(n, true); } 404 405 /// The value of \c e is set to be true in the edge-map which stores 406 /// hide information. If \c e was hidden previuosly, then it is shown 407 /// again 408 void unHide(const Edge& e) const { edge_filter_map->set(e, true); } 409 410 /// Returns true if \c n is hidden. 411 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } 412 413 /// Returns true if \c n is hidden. 414 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 415 416 /// \warning This is a linear time operation and works only if s 417 /// \c Graph::NodeIt is defined. 418 /// \todo assign tags. 419 int nodeNum() const { 420 int i=0; 421 Node n; 422 for (first(n); n!=INVALID; next(n)) ++i; 423 return i; 424 } 425 426 /// \warning This is a linear time operation and works only if 427 /// \c Graph::EdgeIt is defined. 428 /// \todo assign tags. 429 int edgeNum() const { 430 int i=0; 431 Edge e; 432 for (first(e); e!=INVALID; next(e)) ++i; 433 return i; 434 } 319 435 }; 320 436 … … 376 492 */ 377 493 template<typename _Graph, typename NodeFilterMap, 378 typename EdgeFilterMap >494 typename EdgeFilterMap, bool checked = true> 379 495 class SubGraphAdaptor : 380 496 public IterableGraphExtender< 381 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap > > {497 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > { 382 498 public: 383 499 typedef _Graph Graph; … … 408 524 \author Marton Makai 409 525 */ 410 template<typename Graph, typename NodeFilterMap >526 template<typename Graph, typename NodeFilterMap, bool checked = true> 411 527 class NodeSubGraphAdaptor : 412 528 public SubGraphAdaptor<Graph, NodeFilterMap, 413 ConstMap<typename Graph::Edge,bool> 529 ConstMap<typename Graph::Edge,bool>, checked> { 414 530 public: 415 531 typedef SubGraphAdaptor<Graph, NodeFilterMap, … … 561 677 class EdgeSubGraphAdaptor : 562 678 public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 563 EdgeFilterMap > {679 EdgeFilterMap, false> { 564 680 public: 565 681 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
Note: See TracChangeset
for help on using the changeset viewer.