Loading...
Searching...
No Matches
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
43namespace 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.