Menge
Modular Pedestrian Simulation Framework for Research and Development
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Graph.h
Go to the documentation of this file.
1 /*
2 
3 License
4 
5 Menge
6 Copyright and trademark 2012-14 University of North Carolina at Chapel Hill.
7 All rights reserved.
8 
9 Permission to use, copy, modify, and distribute this software and its documentation
10 for educational, research, and non-profit purposes, without fee, and without a
11 written agreement is hereby granted, provided that the above copyright notice,
12 this paragraph, and the following four paragraphs appear in all copies.
13 
14 This software program and documentation are copyrighted by the University of North
15 Carolina at Chapel Hill. The software program and documentation are supplied "as is,"
16 without any accompanying services from the University of North Carolina at Chapel
17 Hill or the authors. The University of North Carolina at Chapel Hill and the
18 authors do not warrant that the operation of the program will be uninterrupted
19 or error-free. The end-user understands that the program was developed for research
20 purposes and is advised not to rely exclusively on the program for any reason.
21 
22 IN NO EVENT SHALL THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL OR THE AUTHORS
23 BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
24 DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS
25 DOCUMENTATION, EVEN IF THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL OR THE
26 AUTHORS HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
28 THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL AND THE AUTHORS SPECIFICALLY
29 DISCLAIM ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
30 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE AND ANY STATUTORY WARRANTY
31 OF NON-INFRINGEMENT. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND
32 THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL AND THE AUTHORS HAVE NO OBLIGATIONS
33 TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
34 
35 Any questions or comments should be sent to the authors {menge,geom}@cs.unc.edu
36 
37 */
38 
45 #ifndef __GRAPH_H__
46 #define __GRAPH_H__
47 
48 #include "mengeCommon.h"
49 #include "Resource.h"
50 #include "GraphVertex.h"
51 
52 namespace Menge {
53 
54  // Forward declarations
55  class GraphEdge;
56  class RoadMapPath;
57  namespace BFSM {
58  class Goal;
59  }
60 
61  namespace Agents {
62  class BaseAgent;
63  }
64 
70  class MENGE_API Graph : public Resource {
71  public:
77  Graph( const std::string & fileName );
78 
79  protected:
83  ~Graph();
84 
85  public:
91  virtual const std::string & getLabel() const { return LABEL; }
92 
96  void clear();
97 
110  static Resource * load( const std::string & fileName );
111 
120  RoadMapPath * getPath( const Agents::BaseAgent * agent, const BFSM::Goal * goal );
121 
127  inline size_t getVertexCount() const { return _vCount; }
128 
138  const GraphVertex * getVertex( size_t i ) const;
139 
144  static const std::string LABEL;
145 
146  protected:
147 
156  size_t getClosestVertex( const Vector2 & point, float radius );
157 
168  RoadMapPath * getPath( size_t startID, size_t endID );
169 
179  inline float computeH( size_t v, const Vector2 & goal ) { return abs( _vertices[v].getPosition() - goal ); }
180 
184  size_t _vCount;
185 
190 
195  void initHeapMemory();
196 
201  size_t DATA_SIZE;
202 
207  size_t STATE_SIZE;
208 
214  unsigned int * _HEAP;
215 
222  unsigned int * _PATH;
223 
231  float * _DATA;
232 
238  bool * _STATE;
239  };
240 
245 
253  GraphPtr loadGraph( const std::string & fileName ) throw ( ResourceException );
254 } // namespace Menge
255 
256 #endif // __GRAPH_H__
unsigned int * _PATH
The full set of data for reconstructing the path. For any given entry i, the value at i is the index ...
Definition: Graph.h:222
The core namespace. All elements of Menge are contained in this namespace.
Definition: AgentGenerator.cpp:43
ResourcePtr< Graph > GraphPtr
forward declaration of graph resource pointer. see graph.h for more details
Definition: VelCompRoadMap.h:63
A roadmap graph and the infrastructure for performing graph searches. NOTE: This implementation assum...
Definition: Graph.h:70
float * _DATA
The block of data for tracking the f, g, and h data for nodes. (This is where DATA_SIZE = 3N comes fr...
Definition: Graph.h:231
The base, abstract class defining goals.
Definition: Goal.h:110
Basic class for managing on-disk resources.
Definition: Resource.h:98
GraphPtr loadGraph(const std::string &fileName)
Loads the graph of the given name.
Definition: Graph.cpp:304
A base exception for resources to throw.
Definition: Resource.h:58
bool * _STATE
Block of data for reportin node state (if its in a heap or if its no longer used for calculation...
Definition: Graph.h:238
GraphVertex * _vertices
An array containing all vertices.
Definition: Graph.h:189
size_t DATA_SIZE
The size of a block of data used for COST in the A* algorithm (3N, N = number of nodes) ...
Definition: Graph.h:201
unsigned int * _HEAP
The full set of data to serve as the heap There are N entries in a single heap and one heap per threa...
Definition: Graph.h:214
The namespace contains the Behavior Finite State Machine (BFSM) definition.
size_t getVertexCount() const
Return the number of vertices in the graph.
Definition: Graph.h:127
A path on a roadmap between vertices.
Definition: RoadMapPath.h:82
A graph vertex.
Definition: GraphVertex.h:56
Defines the basic agent properties and functionality that all simulation agents share.
Definition: BaseAgent.h:123
The basic class for all on-disk resources.
virtual const std::string & getLabel() const
Returns a unique resource label to be used to identify different resource types which use the same un...
Definition: Graph.h:91
size_t _vCount
The number of vertices.
Definition: Graph.h:184
The namespace that contains the basic simulation mechanisms.
size_t STATE_SIZE
The size of a block of data used for STATE in the A* algorithm (2N, N = number of nodes) ...
Definition: Graph.h:207
The definition of a graph vertex for performing graph searches and path planning. ...
float computeH(size_t v, const Vector2 &goal)
Compute's "h" for the A* algorithm. H is the estimate of the cost of a node to a goal point...
Definition: Graph.h:179
static const std::string LABEL
The unique label for this data type to be used with resource management.
Definition: Graph.h:144