Point Cloud Library (PCL)  1.9.1
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 #ifndef PCL_RECOGNITION_ORR_GRAPH_H_
47 #define PCL_RECOGNITION_ORR_GRAPH_H_
48 
49 #include <vector>
50 
51 namespace pcl
52 {
53  namespace recognition
54  {
55  template<class NodeData>
56  class ORRGraph
57  {
58  public:
59  class Node
60  {
61  public:
62  enum State {ON, OFF, UNDEF};
63 
64  Node (int id)
65  : id_ (id),
66  state_(UNDEF)
67  {}
68 
69  virtual ~Node (){}
70 
71  inline const std::set<Node*>&
72  getNeighbors () const
73  {
74  return (neighbors_);
75  }
76 
77  inline const NodeData&
78  getData () const
79  {
80  return (data_);
81  }
82 
83  inline void
84  setData (const NodeData& data)
85  {
86  data_ = data;
87  }
88 
89  inline int
90  getId () const
91  {
92  return (id_);
93  }
94 
95  inline void
96  setId (int id)
97  {
98  id_ = id;
99  }
100 
101  inline void
102  setFitness (int fitness)
103  {
104  fitness_ = fitness;
105  }
106 
107  static inline bool
108  compare (const Node* a, const Node* b)
109  {
110  return (static_cast<bool> (a->fitness_ > b->fitness_));
111  }
112 
113  friend class ORRGraph;
114 
115  protected:
116  std::set<Node*> neighbors_;
117  NodeData data_;
118  int id_;
119  int fitness_;
121  };
122 
123  public:
124  ORRGraph (){}
125  virtual ~ORRGraph (){ this->clear ();}
126 
127  inline void
128  clear ()
129  {
130  for ( typename std::vector<Node*>::iterator nit = nodes_.begin () ; nit != nodes_.end () ; ++nit )
131  delete *nit;
132 
133  nodes_.clear ();
134  }
135 
136  /** \brief Drops all existing graph nodes and creates 'n' new ones. */
137  inline void
138  resize (int n)
139  {
140  if ( !n )
141  return;
142 
143  for ( typename std::vector<Node*>::iterator nit = nodes_.begin () ; nit != nodes_.end () ; ++nit )
144  delete *nit;
145 
146  nodes_.resize (static_cast<size_t> (n));
147 
148  for ( int i = 0 ; i < n ; ++i )
149  nodes_[i] = new Node (i);
150  }
151 
152  inline void
153  computeMaximalOnOffPartition (std::list<Node*>& on_nodes, std::list<Node*>& off_nodes)
154  {
155  std::vector<Node*> sorted_nodes (nodes_.size ());
156  int i = 0;
157 
158  // Set all nodes to undefined
159  for ( typename std::vector<Node*>::iterator it = nodes_.begin () ; it != nodes_.end () ; ++it )
160  {
161  sorted_nodes[i++] = *it;
162  (*it)->state_ = Node::UNDEF;
163  }
164 
165  // Now sort the nodes according to the fitness
166  std::sort (sorted_nodes.begin (), sorted_nodes.end (), Node::compare);
167 
168  // Now run through the array and start switching nodes on and off
169  for ( typename std::vector<Node*>::iterator it = sorted_nodes.begin () ; it != sorted_nodes.end () ; ++it )
170  {
171  // Ignore graph nodes which are already OFF
172  if ( (*it)->state_ == Node::OFF )
173  continue;
174 
175  // Set the node to ON
176  (*it)->state_ = Node::ON;
177 
178  // Set all its neighbors to OFF
179  for ( typename std::set<Node*>::iterator neigh = (*it)->neighbors_.begin () ; neigh != (*it)->neighbors_.end () ; ++neigh )
180  {
181  (*neigh)->state_ = Node::OFF;
182  off_nodes.push_back (*neigh);
183  }
184 
185  // Output the node
186  on_nodes.push_back (*it);
187  }
188  }
189 
190  inline void
191  insertUndirectedEdge (int id1, int id2)
192  {
193  nodes_[id1]->neighbors_.insert (nodes_[id2]);
194  nodes_[id2]->neighbors_.insert (nodes_[id1]);
195  }
196 
197  inline void
198  insertDirectedEdge (int id1, int id2)
199  {
200  nodes_[id1]->neighbors_.insert (nodes_[id2]);
201  }
202 
203  inline void
204  deleteUndirectedEdge (int id1, int id2)
205  {
206  nodes_[id1]->neighbors_.erase (nodes_[id2]);
207  nodes_[id2]->neighbors_.erase (nodes_[id1]);
208  }
209 
210  inline void
211  deleteDirectedEdge (int id1, int id2)
212  {
213  nodes_[id1]->neighbors_.erase (nodes_[id2]);
214  }
215 
216  inline typename std::vector<Node*>&
217  getNodes (){ return nodes_;}
218 
219  public:
220  typename std::vector<Node*> nodes_;
221  };
222  } // namespace recognition
223 } // namespace pcl
224 
225 #endif /* PCL_RECOGNITION_ORR_GRAPH_H_ */
void resize(int n)
Drops all existing graph nodes and creates 'n' new ones.
Definition: orr_graph.h:138
void computeMaximalOnOffPartition(std::list< Node * > &on_nodes, std::list< Node * > &off_nodes)
Definition: orr_graph.h:153
void deleteUndirectedEdge(int id1, int id2)
Definition: orr_graph.h:204
This file defines compatibility wrappers for low level I/O functions.
Definition: convolution.h:45
std::vector< Node * > nodes_
Definition: orr_graph.h:220
static bool compare(const Node *a, const Node *b)
Definition: orr_graph.h:108
void insertDirectedEdge(int id1, int id2)
Definition: orr_graph.h:198
std::set< Node * > neighbors_
Definition: orr_graph.h:116
void deleteDirectedEdge(int id1, int id2)
Definition: orr_graph.h:211
std::vector< Node * > & getNodes()
Definition: orr_graph.h:217
const std::set< Node * > & getNeighbors() const
Definition: orr_graph.h:72
void insertUndirectedEdge(int id1, int id2)
Definition: orr_graph.h:191
const NodeData & getData() const
Definition: orr_graph.h:78
void setData(const NodeData &data)
Definition: orr_graph.h:84
void setFitness(int fitness)
Definition: orr_graph.h:102