All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
PlannerData.cpp
1 /*********************************************************************
2 * Software License Agreement (BSD License)
3 *
4 * Copyright (c) 2011, Rice University
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
17 * * Neither the name of the Rice University nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
33 *********************************************************************/
34 
35 /* Author: Ryan Luna */
36 
37 #include "ompl/base/PlannerData.h"
38 #include "ompl/base/PlannerDataGraph.h"
39 
40 #include <boost/graph/graphviz.hpp>
41 #include <boost/graph/graphml.hpp>
42 #include <boost/graph/prim_minimum_spanning_tree.hpp>
43 
44 // This is a convenient macro to cast the void* graph pointer as the
45 // Boost.Graph structure from PlannerDataGraph.h
46 #define graph_ reinterpret_cast<ompl::base::PlannerData::Graph*>(graphRaw_)
47 
50 const double ompl::base::PlannerData::INVALID_WEIGHT = std::numeric_limits<double>::infinity();
51 const unsigned int ompl::base::PlannerData::INVALID_INDEX = std::numeric_limits<unsigned int>::max();
52 
54 {
55  graphRaw_ = new Graph();
56 }
57 
59 {
60  freeMemory();
61 
62  if (graph_)
63  {
64  delete graph_;
65  graphRaw_ = NULL;
66  }
67 }
68 
70 {
71  freeMemory();
72  decoupledStates_.clear();
73 }
74 
76 {
77  unsigned int count = 0;
78  for (unsigned int i = 0; i < numVertices(); ++i)
79  {
80  PlannerDataVertex& vtx = getVertex(i);
81  // If this vertex's state is not in the decoupled list, clone it and add it
82  if (decoupledStates_.find(const_cast<State*>(vtx.getState())) == decoupledStates_.end())
83  {
84  const State* oldState = vtx.getState();
85  State* clone = si_->cloneState(oldState);
86  decoupledStates_.insert(clone);
87  // Replacing the shallow state pointer with our shiny new clone
88  vtx.state_ = clone;
89 
90  // Remove oldState from stateIndexMap
91  stateIndexMap_.erase(oldState);
92  // Add the new, cloned state to stateIndexMap
93  stateIndexMap_[clone] = i;
94  count++;
95  }
96  }
97 }
98 
99 unsigned int ompl::base::PlannerData::getEdges (unsigned int v, std::vector<unsigned int>& edgeList) const
100 {
101  std::pair<Graph::AdjIterator, Graph::AdjIterator> iterators = boost::adjacent_vertices(boost::vertex(v, *graph_), *graph_);
102 
103  edgeList.clear();
104  boost::property_map<Graph::Type, boost::vertex_index_t>::type vertices = get(boost::vertex_index, *graph_);
105  for (Graph::AdjIterator iter = iterators.first; iter != iterators.second; ++iter)
106  edgeList.push_back(vertices[*iter]);
107 
108  return edgeList.size();
109 }
110 
111 unsigned int ompl::base::PlannerData::getEdges (unsigned int v, std::map<unsigned int, const PlannerDataEdge*>& edgeMap) const
112 {
113  std::pair<Graph::OEIterator, Graph::OEIterator> iterators = boost::out_edges(boost::vertex(v, *graph_), *graph_);
114 
115  edgeMap.clear();
116  boost::property_map<Graph::Type, edge_type_t>::type edges = get(edge_type_t(), *graph_);
117  boost::property_map<Graph::Type, boost::vertex_index_t>::type vertices = get(boost::vertex_index, *graph_);
118  for (Graph::OEIterator iter = iterators.first; iter != iterators.second; ++iter)
119  edgeMap[vertices[boost::target(*iter, *graph_)]] = boost::get(edges, *iter);
120 
121  return edgeMap.size();
122 }
123 
124 unsigned int ompl::base::PlannerData::getIncomingEdges (unsigned int v, std::vector<unsigned int>& edgeList) const
125 {
126  std::pair<Graph::IEIterator, Graph::IEIterator> iterators = boost::in_edges(boost::vertex(v, *graph_), *graph_);
127 
128  edgeList.clear();
129  boost::property_map<Graph::Type, boost::vertex_index_t>::type vertices = get(boost::vertex_index, *graph_);
130  for (Graph::IEIterator iter = iterators.first; iter != iterators.second; ++iter)
131  edgeList.push_back(vertices[boost::source(*iter, *graph_)]);
132 
133  return edgeList.size();
134 }
135 
136 unsigned int ompl::base::PlannerData::getIncomingEdges (unsigned int v, std::map<unsigned int, const PlannerDataEdge*> &edgeMap) const
137 {
138  std::pair<Graph::IEIterator, Graph::IEIterator> iterators = boost::in_edges(boost::vertex(v, *graph_), *graph_);
139 
140  edgeMap.clear();
141  boost::property_map<Graph::Type, edge_type_t>::type edges = get(edge_type_t(), *graph_);
142  boost::property_map<Graph::Type, boost::vertex_index_t>::type vertices = get(boost::vertex_index, *graph_);
143  for (Graph::IEIterator iter = iterators.first; iter != iterators.second; ++iter)
144  edgeMap[vertices[boost::source(*iter, *graph_)]] = boost::get(edges, *iter);
145 
146  return edgeMap.size();
147 }
148 
149 double ompl::base::PlannerData::getEdgeWeight(unsigned int v1, unsigned int v2) const
150 {
151  Graph::Edge e;
152  bool exists;
153  boost::tie(e, exists) = boost::edge(boost::vertex(v1, *graph_), boost::vertex(v2, *graph_), *graph_);
154 
155  if (exists)
156  {
157  boost::property_map<Graph::Type, boost::edge_weight_t>::type edges = get(boost::edge_weight, *graph_);
158  return edges[e];
159  }
160 
161  return INVALID_WEIGHT;
162 }
163 
164 bool ompl::base::PlannerData::setEdgeWeight(unsigned int v1, unsigned int v2, double weight)
165 {
166  Graph::Edge e;
167  bool exists;
168  boost::tie(e, exists) = boost::edge(boost::vertex(v1, *graph_), boost::vertex(v2, *graph_), *graph_);
169 
170  if (exists)
171  {
172  boost::property_map<Graph::Type, boost::edge_weight_t>::type edges = get(boost::edge_weight, *graph_);
173  edges[e] = weight;
174  }
175 
176  return exists;
177 }
178 
179 bool ompl::base::PlannerData::edgeExists (unsigned int v1, unsigned int v2) const
180 {
181  Graph::Edge e;
182  bool exists;
183 
184  boost::tie(e, exists) = boost::edge(boost::vertex(v1, *graph_), boost::vertex(v2, *graph_), *graph_);
185  return exists;
186 }
187 
189 {
190  return vertexIndex(v) != INVALID_INDEX;
191 }
192 
193 unsigned int ompl::base::PlannerData::numVertices (void) const
194 {
195  return boost::num_vertices(*graph_);
196 }
197 
198 unsigned int ompl::base::PlannerData::numEdges (void) const
199 {
200  return boost::num_edges(*graph_);
201 }
202 
204 {
205  if (index >= boost::num_vertices(*graph_))
206  return NO_VERTEX;
207 
208  boost::property_map<Graph::Type, vertex_type_t>::type vertices = get(vertex_type_t(), *graph_);
209  return *(vertices[boost::vertex(index, *graph_)]);
210 }
211 
213 {
214  if (index >= boost::num_vertices(*graph_))
215  return const_cast<ompl::base::PlannerDataVertex&>(NO_VERTEX);
216 
217  boost::property_map<Graph::Type, vertex_type_t>::type vertices = get(vertex_type_t(), *graph_);
218  return *(vertices[boost::vertex(index, *graph_)]);
219 }
220 
221 const ompl::base::PlannerDataEdge& ompl::base::PlannerData::getEdge (unsigned int v1, unsigned int v2) const
222 {
223  Graph::Edge e;
224  bool exists;
225  boost::tie(e, exists) = boost::edge(boost::vertex(v1, *graph_), boost::vertex(v2, *graph_), *graph_);
226 
227  if (exists)
228  {
229  boost::property_map<Graph::Type, edge_type_t>::type edges = get(edge_type_t(), *graph_);
230  return *(boost::get(edges, e));
231  }
232 
233  return NO_EDGE;
234 }
235 
237 {
238  Graph::Edge e;
239  bool exists;
240  boost::tie(e, exists) = boost::edge(boost::vertex(v1, *graph_), boost::vertex(v2, *graph_), *graph_);
241 
242  if (exists)
243  {
244  boost::property_map<Graph::Type, edge_type_t>::type edges = get(edge_type_t(), *graph_);
245  return *(boost::get(edges, e));
246  }
247 
248  return const_cast<ompl::base::PlannerDataEdge&>(NO_EDGE);
249 }
250 
251 void ompl::base::PlannerData::printGraphviz (std::ostream& out) const
252 {
253  boost::write_graphviz(out, *graph_);
254 }
255 
256 void ompl::base::PlannerData::printGraphML (std::ostream& out) const
257 {
258  // Not writing vertex or edge structures.
259  boost::dynamic_properties dp;
260  dp.property("weight", get(boost::edge_weight_t(), *graph_));
261 
262  boost::write_graphml(out, *graph_, dp);
263 }
264 
266 {
267  std::map<const State*, unsigned int>::const_iterator it = stateIndexMap_.find(v.getState());
268  if (it != stateIndexMap_.end())
269  return it->second;
270  return INVALID_INDEX;
271 }
272 
274 {
275  return startVertexIndices_.size();
276 }
277 
279 {
280  return goalVertexIndices_.size();
281 }
282 
283 unsigned int ompl::base::PlannerData::getStartIndex (unsigned int i) const
284 {
285  if (i >= startVertexIndices_.size())
286  return INVALID_INDEX;
287 
288  return startVertexIndices_[i];
289 }
290 
291 unsigned int ompl::base::PlannerData::getGoalIndex (unsigned int i) const
292 {
293  if (i >= goalVertexIndices_.size())
294  return INVALID_INDEX;
295 
296  return goalVertexIndices_[i];
297 }
298 
299 bool ompl::base::PlannerData::isStartVertex (unsigned int index) const
300 {
301  return std::binary_search(startVertexIndices_.begin(), startVertexIndices_.end(), index);
302 }
303 
304 bool ompl::base::PlannerData::isGoalVertex (unsigned int index) const
305 {
306  return std::binary_search(goalVertexIndices_.begin(), goalVertexIndices_.end(), index);
307 }
308 
310 {
311  if (i >= startVertexIndices_.size())
312  return NO_VERTEX;
313 
314  return getVertex(startVertexIndices_[i]);
315 }
316 
318 {
319  if (i >= startVertexIndices_.size())
320  return const_cast<ompl::base::PlannerDataVertex&>(NO_VERTEX);
321 
322  return getVertex(startVertexIndices_[i]);
323 }
324 
326 {
327  if (i >= goalVertexIndices_.size())
328  return NO_VERTEX;
329 
330  return getVertex(goalVertexIndices_[i]);
331 }
332 
334 {
335  if (i >= goalVertexIndices_.size())
336  return const_cast<ompl::base::PlannerDataVertex&>(NO_VERTEX);
337 
338  return getVertex(goalVertexIndices_[i]);
339 }
340 
342 {
343  // Do not add vertices with null states
344  if (st.getState() == NULL)
345  return INVALID_INDEX;
346 
347  unsigned int index = vertexIndex(st);
348  if (index == INVALID_INDEX) // Vertex does not already exist
349  {
350  // Clone the state to prevent object slicing when retrieving this object
351  ompl::base::PlannerDataVertex *clone = st.clone();
352  Graph::Vertex v = boost::add_vertex(clone, *graph_);
353  boost::property_map<Graph::Type, boost::vertex_index_t>::type vertexIndexMap = get(boost::vertex_index, *graph_);
354 
355  // Insert this entry into the stateIndexMap_ for fast lookup
356  stateIndexMap_[clone->getState()] = numVertices()-1;
357  return vertexIndexMap[v];
358  }
359  return index;
360 }
361 
363 {
364  unsigned int index = addVertex(v);
365  if (index != INVALID_INDEX)
366  markStartState(v.getState());
367 
368  return index;
369 }
370 
372 {
373  unsigned int index = addVertex(v);
374 
375  if (index != INVALID_INDEX)
376  markGoalState(v.getState());
377 
378  return index;
379 }
380 
381 bool ompl::base::PlannerData::addEdge(unsigned int v1, unsigned int v2, const PlannerDataEdge &edge, double weight)
382 {
383  // If either of the vertices do not exist, don't add an edge
384  if (v1 >= numVertices() || v2 >= numVertices())
385  return false;
386 
387  // If an edge already exists, do not add one
388  if (edgeExists (v1, v2))
389  return false;
390 
391  // Clone the edge to prevent object slicing
392  ompl::base::PlannerDataEdge *clone = edge.clone();
393  const Graph::edge_property_type properties(clone, weight);
394 
395  Graph::Edge e;
396  bool added = false;
397  tie(e, added) = boost::add_edge(boost::vertex(v1, *graph_), boost::vertex(v2, *graph_), properties, *graph_);
398 
399  if (!added)
400  delete clone;
401 
402  return added;
403 }
404 
405 bool ompl::base::PlannerData::addEdge (const PlannerDataVertex & v1, const PlannerDataVertex & v2, const PlannerDataEdge &edge, double weight)
406 {
407  unsigned int index1 = addVertex(v1);
408  unsigned int index2 = addVertex(v2);
409 
410  // If neither vertex was added or already exists, return false
411  if (index1 == INVALID_INDEX && index2 == INVALID_INDEX)
412  return false;
413 
414  // Only add the edge if both vertices exist
415  if (index1 != INVALID_INDEX && index2 != INVALID_INDEX)
416  return addEdge (index1, index2, edge, weight);
417 
418  return true;
419 }
420 
422 {
423  unsigned int index = vertexIndex (st);
424  if (index != INVALID_INDEX)
425  return removeVertex (index);
426  return false;
427 }
428 
429 bool ompl::base::PlannerData::removeVertex (unsigned int vIndex)
430 {
431  if (vIndex >= boost::num_vertices(*graph_))
432  return false;
433 
434  // Retrieve a list of all edge structures
435  boost::property_map<Graph::Type, edge_type_t>::type edgePropertyMap = get(edge_type_t(), *graph_);
436 
437  // Freeing memory associated with outgoing edges of this vertex
438  std::pair<Graph::OEIterator, Graph::OEIterator> oiterators = boost::out_edges(boost::vertex(vIndex, *graph_), *graph_);
439  for (Graph::OEIterator iter = oiterators.first; iter != oiterators.second; ++iter)
440  delete edgePropertyMap[*iter];
441 
442  // Freeing memory associated with incoming edges of this vertex
443  std::pair<Graph::IEIterator, Graph::IEIterator> initerators = boost::in_edges(boost::vertex(vIndex, *graph_), *graph_);
444  for (Graph::IEIterator iter = initerators.first; iter != initerators.second; ++iter)
445  delete edgePropertyMap[*iter];
446 
447  // Remove this vertex from stateIndexMap_, and update the map
448  stateIndexMap_.erase(getVertex(vIndex).getState());
449  boost::property_map<Graph::Type, vertex_type_t>::type vertices = get(vertex_type_t(), *graph_);
450  for (unsigned int i = vIndex+1; i < boost::num_vertices(*graph_); ++i)
451  stateIndexMap_[vertices[boost::vertex(i, *graph_)]->getState()]--;
452 
453  // Remove this vertex from the start and/or goal index list, if it exists. Update the lists.
454  std::vector<unsigned int>::iterator it = std::find(startVertexIndices_.begin(), startVertexIndices_.end(), vIndex);
455  if (it != startVertexIndices_.end())
456  startVertexIndices_.erase(it);
457  for (size_t i = 0; i < startVertexIndices_.size(); ++i)
458  if (startVertexIndices_[i] > vIndex)
459  startVertexIndices_[i]--;
460 
461  it = std::find(goalVertexIndices_.begin(), goalVertexIndices_.end(), vIndex);
462  if (it != goalVertexIndices_.end())
463  goalVertexIndices_.erase(it);
464  for (size_t i = 0; i < goalVertexIndices_.size(); ++i)
465  if (goalVertexIndices_[i] > vIndex)
466  goalVertexIndices_[i]--;
467 
468  // If the state attached to this vertex was decoupled, free it here
469  State* vtxState = const_cast<State*>(getVertex(vIndex).getState());
470  if (decoupledStates_.find(vtxState) != decoupledStates_.end())
471  {
472  decoupledStates_.erase(vtxState);
473  si_->freeState(vtxState);
474  vtxState = NULL;
475  }
476 
477  // Slay the vertex
478  boost::clear_vertex(boost::vertex(vIndex, *graph_), *graph_);
479  boost::property_map<Graph::Type, vertex_type_t>::type vertexTypeMap = get(vertex_type_t(), *graph_);
480  delete vertexTypeMap[boost::vertex(vIndex, *graph_)];
481  boost::remove_vertex(boost::vertex(vIndex, *graph_), *graph_);
482 
483  return true;
484 }
485 
486 bool ompl::base::PlannerData::removeEdge (unsigned int v1, unsigned int v2)
487 {
488  Graph::Edge e;
489  bool exists;
490  boost::tie(e, exists) = boost::edge(boost::vertex(v1, *graph_), boost::vertex(v2, *graph_), *graph_);
491 
492  if (!exists)
493  return false;
494 
495  // Freeing memory associated with this edge
496  boost::property_map<Graph::Type, edge_type_t>::type edges = get(edge_type_t(), *graph_);
497  delete edges[e];
498 
499  boost::remove_edge(boost::vertex(v1, *graph_), boost::vertex(v2, *graph_), *graph_);
500  return true;
501 }
502 
504 {
505  unsigned int index1, index2;
506  index1 = vertexIndex(v1);
507  index2 = vertexIndex(v2);
508 
509  if (index1 == INVALID_INDEX || index2 == INVALID_INDEX)
510  return false;
511 
512  return removeEdge (index1, index2);
513 }
514 
516 {
517  std::map<const State*, unsigned int>::const_iterator it = stateIndexMap_.find(st);
518  if (it != stateIndexMap_.end())
519  {
520  getVertex(it->second).setTag(tag);
521  return true;
522  }
523  return false;
524 }
525 
527 {
528  // Find the index in the stateIndexMap_
529  std::map<const State*, unsigned int>::const_iterator it = stateIndexMap_.find(st);
530  if (it != stateIndexMap_.end())
531  {
532  if (!isStartVertex(it->second))
533  {
534  startVertexIndices_.push_back(it->second);
535  // Sort the indices for quick lookup
536  std::sort(startVertexIndices_.begin(), startVertexIndices_.end());
537  }
538  return true;
539  }
540  return false;
541 }
542 
544 {
545  // Find the index in the stateIndexMap_
546  std::map<const State*, unsigned int>::const_iterator it = stateIndexMap_.find(st);
547  if (it != stateIndexMap_.end())
548  {
549  if (!isGoalVertex(it->second))
550  {
551  goalVertexIndices_.push_back(it->second);
552  // Sort the indices for quick lookup
553  std::sort(startVertexIndices_.begin(), startVertexIndices_.end());
554  }
555  return true;
556  }
557  return false;
558 }
559 
561 {
562  // If f wasn't specified, use defaultEdgeWeight
564  if (!func)
565  func = boost::bind(&ompl::base::PlannerData::defaultEdgeWeight, this, _1, _2, _3);
566 
567  unsigned int nv = numVertices();
568  for (unsigned int i = 0; i < nv; ++i)
569  {
570  std::map<unsigned int, const PlannerDataEdge*> nbrs;
571  getEdges(i, nbrs);
572 
573  std::map<unsigned int, const PlannerDataEdge*>::const_iterator it;
574  for (it = nbrs.begin(); it != nbrs.end(); ++it)
575  setEdgeWeight(i, it->first, func(getVertex(i), getVertex(it->first), *it->second));
576  }
577 }
578 
580 {
581  std::vector<ompl::base::PlannerData::Graph::Vertex> pred(numVertices());
582 
583  // Ask boost nicely for the minimum spanning tree
584  boost::prim_minimum_spanning_tree(*graph_, &pred[0], boost::weight_map(get(boost::edge_weight, *graph_)).
585  vertex_index_map(get(boost::vertex_index, *graph_)).
586  root_vertex(boost::vertex(v, *graph_)));
587 
588  // Adding vertices to MST
589  for (std::size_t i = 0; i < pred.size(); ++i)
590  {
591  if (isStartVertex(i))
592  mst.addStartVertex(getVertex(i));
593  else if (isGoalVertex(i))
594  mst.addGoalVertex(getVertex(i));
595  else
596  mst.addVertex(getVertex(i));
597  }
598 
599  // Adding edges to MST
600  for (std::size_t i = 0; i < pred.size(); ++i)
601  {
602  if (pred[i] != i)
603  mst.addEdge(pred[i], i, getEdge(pred[i], i), getEdgeWeight(pred[i], i));
604  }
605 }
606 
608 {
609  // If this vertex already exists in data, return
610  if (data.vertexExists(getVertex(v)))
611  return;
612 
613  // Adding the vertex corresponding to v into data
614  unsigned int idx;
615  if (isStartVertex(v))
616  idx = data.addStartVertex(getVertex(v));
617  else if (isGoalVertex(v))
618  idx = data.addGoalVertex(getVertex(v));
619  else
620  idx = data.addVertex(getVertex(v));
621 
622  assert (idx != INVALID_INDEX);
623 
624  std::map<unsigned int, const PlannerDataEdge*> neighbors;
625  getEdges(v, neighbors);
626 
627  // Depth-first traversal of reachable graph
628  std::map<unsigned int, const PlannerDataEdge*>::iterator it;
629  for (it = neighbors.begin(); it != neighbors.end(); ++it)
630  {
631  extractReachable(it->first, data);
632  data.addEdge(idx, data.vertexIndex(getVertex(it->first)), *(it->second), getEdgeWeight(v, it->first));
633  }
634 }
635 
637 {
638  ompl::base::PlannerData::Graph* boostgraph = reinterpret_cast<ompl::base::PlannerData::Graph*>(graphRaw_);
639  return *boostgraph;
640 }
641 
643 {
644  const ompl::base::PlannerData::Graph* boostgraph = reinterpret_cast<const ompl::base::PlannerData::Graph*>(graphRaw_);
645  return *boostgraph;
646 }
647 
648 double ompl::base::PlannerData::defaultEdgeWeight(const base::PlannerDataVertex &v1, const base::PlannerDataVertex &v2, const base::PlannerDataEdge& /*e*/) const
649 {
650  return si_->distance(v1.getState(), v2.getState());
651 }
652 
654 {
655  return si_;
656 }
657 
658 void ompl::base::PlannerData::freeMemory(void)
659 {
660  // Freeing decoupled states, if any
661  for (std::set<State*>::iterator it = decoupledStates_.begin(); it != decoupledStates_.end(); ++it)
662  si_->freeState(*it);
663 
664  if (graph_)
665  {
666  std::pair<Graph::EIterator, Graph::EIterator> eiterators = boost::edges(*graph_);
667  boost::property_map<Graph::Type, edge_type_t>::type edges = get(edge_type_t(), *graph_);
668  for (Graph::EIterator iter = eiterators.first; iter != eiterators.second; ++iter)
669  delete boost::get(edges, *iter);
670 
671  std::pair<Graph::VIterator, Graph::VIterator> viterators = boost::vertices(*graph_);
672  boost::property_map<Graph::Type, vertex_type_t>::type vertices = get(vertex_type_t(), *graph_);
673  for (Graph::VIterator iter = viterators.first; iter != viterators.second; ++iter)
674  delete vertices[*iter];
675 
676  graph_->clear();
677  }
678 }
679 
681 {
682  return false;
683 }