AdjacencyList.h
1 /*********************************************************************
2 * Software License Agreement (BSD License)
3 *
4 * Copyright (c) 2015, 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 #ifndef ADJACENCY_LIST_
38 #define ADJACENCY_LIST_
39 
40 #include <vector>
41 #include <boost/thread/mutex.hpp>
42 
43 namespace ompl
44 {
45  // An undirected graph containing vertices and weighted edges
46  // Edges are stored using an adjacency list.
47  // Only one edge per vertex pair is allowed.
48  class AdjacencyList
49  {
50  public:
51  AdjacencyList();
52 
53  // Initialize the graph with n vertices and no edges
54  AdjacencyList(int n);
55 
56  ~AdjacencyList();
57 
58  // Remove all vertices and edges
59  void clear();
60 
61  // Add a new vertex to the graph. The id of the vertex is returned
62  // Note: Vertex removal is not supported to simplify the implementation,
63  // provide stability of vertex descriptors, and for performance reasons
64  int addVertex();
65  // Return the number of vertices in the graph
66  int numVertices() const;
67  // Return true if a vertex with the given id exists
68  bool vertexExists(int v) const;
69 
70  // Return true if v1 and v2 are connected in the graph (in the same connected component)
71  // NOTE: THIS FUNCTION MAY NOT BE CORRECT IF EDGES ARE EVER REMOVED FROM THE GRAPH
72  bool inSameComponent(int v1, int v2) const;
73  // Return the number of connected components in the graph
74  // NOTE: THIS FUNCTION MAY NOT BE CORRECT IF EDGES ARE EVER REMOVED FROM THE GRAPH
75  int numConnectedComponents() const;
76  // Return the connected component set the vertex belongs to
77  int getComponentID(int vtx) const;
78 
79  // Add an edge between v1 and v2 in the graph with the (optional) weight
80  // If the edge already exists, false is returned
81  bool addEdge(int v1, int v2, double weight = 1.0);
82  // Remove the edge between v1 and v2. False is returned if the edge does not exist
83  // NOTE: USING THIS FUNCTION TRASHES CONNECTED COMPONENT CAPABILITIES
84  bool removeEdge(int v1, int v2);
85  // Return the number of edges in the graph
86  int numEdges() const;
87  // Returns the weight of the edge between vertices v1 and v2. An exception is thrown when the edge does not exist
88  double getEdgeWeight(int v1, int v2) const;
89  // Update the edge weight between v1 and v2
90  bool setEdgeWeight(int v1, int v2, double weight);
91  // Returns true if an edge exists between vertices v1 and v2
92  bool edgeExists(int v1, int v2) const;
93 
94  // Returns number of adjacent vertices for the given vertex
95  int numNeighbors(int vtx) const;
96  // Returns the adjacent vertices of the given vertex
97  void getNeighbors(int vtx, std::vector<int>& nbrs) const;
98  // Return the adjacent vertices of the given vertex and the weights associated with each edge
99  void getNeighbors(int vtx, std::vector<std::pair<int, double> >& nbrs) const;
100 
101  // Dijkstra's shortest path search from v1 to v2. If a path exists, the solution is stored in path and true is returned.
102  bool dijkstra(int v1, int v2, std::vector<int>& path) const;
103 
104  // Dijkstra's shortest path search starting from v1. The predecessors of each node are stored in predecessors.
105  // If the predecessor of a node is itself, it is not reachable from vtx (or is equal to vtx).
106  // The total distance from vtx to each node is stored in distance. A value of double::max() indicates an unreachable node.
107  void dijkstra(int vtx, std::vector<int>& predecessors, std::vector<double>& distance) const;
108 
109  protected:
110 
111  // Mutex, for thread safety
112  mutable boost::mutex lock_;
113 
114  // Obscured to prevent unnecessary inclusion of BGL throughout the rest of the code.
115  void* graphRaw_;
116 
117  // Obscured to prevent unnecessary inclusion of BGL throughout the rest of the code.
118  void* disjointSetsRaw_;
119  };
120 }
121 
122 #endif
Main namespace. Contains everything in this library.