Directory: | ./ |
---|---|
File: | include/hpp/core/connected-component.hh |
Date: | 2024-08-10 11:29:48 |
Exec | Total | Coverage | |
---|---|---|---|
Lines: | 18 | 18 | 100.0% |
Branches: | 2 | 4 | 50.0% |
Line | Branch | Exec | Source |
---|---|---|---|
1 | // | ||
2 | // Copyright (c) 2014 CNRS | ||
3 | // Authors: Florent Lamiraux | ||
4 | // | ||
5 | |||
6 | // Redistribution and use in source and binary forms, with or without | ||
7 | // modification, are permitted provided that the following conditions are | ||
8 | // met: | ||
9 | // | ||
10 | // 1. Redistributions of source code must retain the above copyright | ||
11 | // notice, this list of conditions and the following disclaimer. | ||
12 | // | ||
13 | // 2. Redistributions in binary form must reproduce the above copyright | ||
14 | // notice, this list of conditions and the following disclaimer in the | ||
15 | // documentation and/or other materials provided with the distribution. | ||
16 | // | ||
17 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | ||
18 | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | ||
19 | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | ||
20 | // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | ||
21 | // HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | ||
22 | // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | ||
23 | // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | ||
24 | // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | ||
25 | // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | ||
26 | // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | ||
27 | // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH | ||
28 | // DAMAGE. | ||
29 | |||
30 | #ifndef HPP_CORE_CONNECTED_COMPONENT_HH | ||
31 | #define HPP_CORE_CONNECTED_COMPONENT_HH | ||
32 | |||
33 | #include <hpp/core/config.hh> | ||
34 | #include <hpp/core/fwd.hh> | ||
35 | #include <hpp/core/node.hh> | ||
36 | #include <hpp/util/serialization-fwd.hh> | ||
37 | |||
38 | namespace hpp { | ||
39 | namespace core { | ||
40 | /// Connected component | ||
41 | /// | ||
42 | /// Set of nodes reachable from one another. | ||
43 | class HPP_CORE_DLLAPI ConnectedComponent { | ||
44 | public: | ||
45 | typedef ConnectedComponent* RawPtr_t; | ||
46 | typedef std::set<RawPtr_t> RawPtrs_t; | ||
47 | |||
48 | // variable for ranking connected components | ||
49 | static unsigned int globalFinishTime_; | ||
50 | 82 | static ConnectedComponentPtr_t create() { | |
51 |
1/2✓ Branch 2 taken 82 times.
✗ Branch 3 not taken.
|
82 | ConnectedComponent* ptr = new ConnectedComponent(); |
52 | 82 | ConnectedComponentPtr_t shPtr(ptr); | |
53 | 82 | ptr->init(shPtr); | |
54 | 82 | return shPtr; | |
55 | } | ||
56 | /// Merge two connected components. | ||
57 | /// | ||
58 | /// \param other connected component to merge into this one. | ||
59 | /// \note other will be empty after calling this method. | ||
60 | virtual void merge(const ConnectedComponentPtr_t& other); | ||
61 | |||
62 | 348 | virtual ~ConnectedComponent() {} | |
63 | |||
64 | /// Add node in connected component | ||
65 | /// \param node node to add. | ||
66 | 82 | virtual void addNode(const NodePtr_t& node) { nodes_.push_back(node); } | |
67 | /// Access to the nodes | ||
68 | 1501 | const NodeVector_t& nodes() const { return nodes_; } | |
69 | |||
70 | /// \name Reachability | ||
71 | /// \{ | ||
72 | |||
73 | /// Whether this connected component can reach cc | ||
74 | /// \param cc a connected component | ||
75 | bool canReach(const ConnectedComponentPtr_t& cc); | ||
76 | |||
77 | /// Whether this connected component can reach cc | ||
78 | /// \param cc a connected component | ||
79 | /// \retval cc2Tocc1 list of connected components between cc2 and cc1 | ||
80 | /// that should be merged. | ||
81 | bool canReach(const ConnectedComponentPtr_t& cc, RawPtrs_t& cc2Tocc1); | ||
82 | |||
83 | // Get connected components reachable from this | ||
84 | 40 | const RawPtrs_t& reachableTo() const { return reachableTo_; } | |
85 | |||
86 | // Get connected components that can reach this | ||
87 | 40 | const RawPtrs_t& reachableFrom() const { return reachableFrom_; } | |
88 | /// \} | ||
89 | |||
90 | 34 | ConnectedComponentPtr_t self() { return weak_.lock(); } | |
91 | |||
92 | 180 | bool operator<(const ConnectedComponent& rhs) const { | |
93 | 180 | return this->current_id < rhs.current_id; | |
94 | } | ||
95 | |||
96 | protected: | ||
97 | /// Constructor | ||
98 | 94 | ConnectedComponent() | |
99 | 94 | : nodes_(), explored_(false), weak_(), current_id(static_id++) { | |
100 |
1/2✓ Branch 1 taken 94 times.
✗ Branch 2 not taken.
|
94 | nodes_.reserve(1000); |
101 | 94 | } | |
102 | 82 | void init(const ConnectedComponentPtr_t& shPtr) { weak_ = shPtr; } | |
103 | |||
104 | private: | ||
105 | static void clean(RawPtrs_t& set); | ||
106 | |||
107 | NodeVector_t nodes_; | ||
108 | // List of CCs from which this connected component can be reached | ||
109 | RawPtrs_t reachableFrom_; | ||
110 | // List of CCs that can be reached from this connected component | ||
111 | RawPtrs_t reachableTo_; | ||
112 | // status variable to indicate whether or not CC has been visited | ||
113 | mutable bool explored_; | ||
114 | ConnectedComponentWkPtr_t weak_; | ||
115 | friend class Roadmap; | ||
116 | |||
117 | static int static_id; | ||
118 | const int current_id; | ||
119 | |||
120 | HPP_SERIALIZABLE(); | ||
121 | }; // class ConnectedComponent | ||
122 | } // namespace core | ||
123 | } // namespace hpp | ||
124 | #endif // HPP_CORE_CONNECTED_COMPONENT_HH | ||
125 |