Point Cloud Library (PCL)  1.9.1-dev
orr_graph.h
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Point Cloud Library (PCL) - www.pointclouds.org
5  * Copyright (c) 2010-2012, Willow Garage, Inc.
6  *
7  * All rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * * Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  * * Redistributions in binary form must reproduce the above
16  * copyright notice, this list of conditions and the following
17  * disclaimer in the documentation and/or other materials provided
18  * with the distribution.
19  * * Neither the name of Willow Garage, Inc. nor the names of its
20  * contributors may be used to endorse or promote products derived
21  * from this software without specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
29  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
31  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
33  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34  * POSSIBILITY OF SUCH DAMAGE.
35  *
36  *
37  */
38 
39 /*
40  * orr_graph.h
41  *
42  * Created on: Nov 23, 2012
43  * Author: papazov
44  */
45 
46 #pragma once
47 
48 #include <vector>
49 
50 namespace pcl
51 {
52  namespace recognition
53  {
54  template<class NodeData>
55  class ORRGraph
56  {
57  public:
58  class Node
59  {
60  public:
61  enum State {ON, OFF, UNDEF};
62 
63  Node (int id)
64  : id_ (id),
65  state_(UNDEF)
66  {}
67 
68  virtual ~Node (){}
69 
70  inline const std::set<Node*>&
71  getNeighbors () const
72  {
73  return (neighbors_);
74  }
75 
76  inline const NodeData&
77  getData () const
78  {
79  return (data_);
80  }
81 
82  inline void
83  setData (const NodeData& data)
84  {
85  data_ = data;
86  }
87 
88  inline int
89  getId () const
90  {
91  return (id_);
92  }
93 
94  inline void
95  setId (int id)
96  {
97  id_ = id;
98  }
99 
100  inline void
101  setFitness (int fitness)
102  {
103  fitness_ = fitness;
104  }
105 
106  static inline bool
107  compare (const Node* a, const Node* b)
108  {
109  return a->fitness_ > b->fitness_;
110  }
111 
112  friend class ORRGraph;
113 
114  protected:
115  std::set<Node*> neighbors_;
116  NodeData data_;
117  int id_;
118  int fitness_;
120  };
121 
122  public:
123  ORRGraph (){}
124  virtual ~ORRGraph (){ this->clear ();}
125 
126  inline void
127  clear ()
128  {
129  for ( typename std::vector<Node*>::iterator nit = nodes_.begin () ; nit != nodes_.end () ; ++nit )
130  delete *nit;
131 
132  nodes_.clear ();
133  }
134 
135  /** \brief Drops all existing graph nodes and creates 'n' new ones. */
136  inline void
137  resize (int n)
138  {
139  if ( !n )
140  return;
141 
142  for ( typename std::vector<Node*>::iterator nit = nodes_.begin () ; nit != nodes_.end () ; ++nit )
143  delete *nit;
144 
145  nodes_.resize (static_cast<std::size_t> (n));
146 
147  for ( int i = 0 ; i < n ; ++i )
148  nodes_[i] = new Node (i);
149  }
150 
151  inline void
152  computeMaximalOnOffPartition (std::list<Node*>& on_nodes, std::list<Node*>& off_nodes)
153  {
154  std::vector<Node*> sorted_nodes (nodes_.size ());
155  int i = 0;
156 
157  // Set all nodes to undefined
158  for ( typename std::vector<Node*>::iterator it = nodes_.begin () ; it != nodes_.end () ; ++it )
159  {
160  sorted_nodes[i++] = *it;
161  (*it)->state_ = Node::UNDEF;
162  }
163 
164  // Now sort the nodes according to the fitness
165  std::sort (sorted_nodes.begin (), sorted_nodes.end (), Node::compare);
166 
167  // Now run through the array and start switching nodes on and off
168  for ( typename std::vector<Node*>::iterator it = sorted_nodes.begin () ; it != sorted_nodes.end () ; ++it )
169  {
170  // Ignore graph nodes which are already OFF
171  if ( (*it)->state_ == Node::OFF )
172  continue;
173 
174  // Set the node to ON
175  (*it)->state_ = Node::ON;
176 
177  // Set all its neighbors to OFF
178  for ( typename std::set<Node*>::iterator neigh = (*it)->neighbors_.begin () ; neigh != (*it)->neighbors_.end () ; ++neigh )
179  {
180  (*neigh)->state_ = Node::OFF;
181  off_nodes.push_back (*neigh);
182  }
183 
184  // Output the node
185  on_nodes.push_back (*it);
186  }
187  }
188 
189  inline void
190  insertUndirectedEdge (int id1, int id2)
191  {
192  nodes_[id1]->neighbors_.insert (nodes_[id2]);
193  nodes_[id2]->neighbors_.insert (nodes_[id1]);
194  }
195 
196  inline void
197  insertDirectedEdge (int id1, int id2)
198  {
199  nodes_[id1]->neighbors_.insert (nodes_[id2]);
200  }
201 
202  inline void
203  deleteUndirectedEdge (int id1, int id2)
204  {
205  nodes_[id1]->neighbors_.erase (nodes_[id2]);
206  nodes_[id2]->neighbors_.erase (nodes_[id1]);
207  }
208 
209  inline void
210  deleteDirectedEdge (int id1, int id2)
211  {
212  nodes_[id1]->neighbors_.erase (nodes_[id2]);
213  }
214 
215  inline typename std::vector<Node*>&
216  getNodes (){ return nodes_;}
217 
218  public:
219  typename std::vector<Node*> nodes_;
220  };
221  } // namespace recognition
222 } // namespace pcl
void resize(int n)
Drops all existing graph nodes and creates &#39;n&#39; new ones.
Definition: orr_graph.h:137
void deleteUndirectedEdge(int id1, int id2)
Definition: orr_graph.h:203
This file defines compatibility wrappers for low level I/O functions.
Definition: convolution.h:45
std::vector< Node * > nodes_
Definition: orr_graph.h:219
static bool compare(const Node *a, const Node *b)
Definition: orr_graph.h:107
void insertDirectedEdge(int id1, int id2)
Definition: orr_graph.h:197
std::set< Node * > neighbors_
Definition: orr_graph.h:115
void deleteDirectedEdge(int id1, int id2)
Definition: orr_graph.h:210
std::vector< Node * > & getNodes()
Definition: orr_graph.h:216
const std::set< Node * > & getNeighbors() const
Definition: orr_graph.h:71
void insertUndirectedEdge(int id1, int id2)
Definition: orr_graph.h:190
const NodeData & getData() const
Definition: orr_graph.h:77
void setData(const NodeData &data)
Definition: orr_graph.h:83
void setFitness(int fitness)
Definition: orr_graph.h:101
void computeMaximalOnOffPartition(std::list< Node *> &on_nodes, std::list< Node *> &off_nodes)
Definition: orr_graph.h:152