KiCad PCB EDA Suite
Loading...
Searching...
No Matches
test_connectivity_clusters.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program. If not, see <https://www.gnu.org/licenses/>.
18 */
19
21#include <boost/test/data/test_case.hpp>
22
24
25#include <board.h>
30
31#include <deque>
32#include <map>
33#include <set>
34
35/*
36 * SearchClusters() computes connected components and RN_NET builds a minimum spanning forest
37 * over them. Both are stated as properties here rather than as recorded numbers, so the
38 * checks stand on their own rather than on whatever the current implementation happens to
39 * produce.
40 */
41
42namespace
43{
44
45struct CONNECTIVITY_CLUSTER_FIXTURE
46{
47 SETTINGS_MANAGER m_settingsManager;
48 std::unique_ptr<BOARD> m_board;
49};
50
51
53const std::vector<wxString> c_boards = {
54 "issue22267",
55 "issue17429",
56 "issue16182",
57 "issue14559",
58 "issue8909",
59};
60
61} // namespace
62
63
64BOOST_FIXTURE_TEST_SUITE( ConnectivityClusters, CONNECTIVITY_CLUSTER_FIXTURE )
65
66
67
73{
74 std::shared_ptr<CN_CONNECTIVITY_ALGO> algo = aBoard->GetConnectivity()->GetConnectivityAlgo();
75
77 algo->SearchClusters( CN_CONNECTIVITY_ALGO::CSM_RATSNEST );
78
79 BOOST_REQUIRE( !clusters.empty() );
80
81 std::map<CN_ITEM*, size_t> clusterOf;
82 size_t placed = 0;
83
84 for( size_t ii = 0; ii < clusters.size(); ++ii )
85 {
86 for( CN_ITEM* item : *clusters[ii] )
87 {
88 BOOST_REQUIRE_MESSAGE( clusterOf.emplace( item, ii ).second,
89 "item appears in more than one cluster" );
90 placed++;
91 }
92 }
93
94 BOOST_CHECK_EQUAL( placed, clusterOf.size() );
95
96 // No adjacency between two items that both took part may span two clusters, or they would
97 // be one component and the search split them.
98 for( const auto& [item, cluster] : clusterOf )
99 {
100 for( CN_ITEM* neighbour : item->ConnectedItems() )
101 {
102 auto it = clusterOf.find( neighbour );
103
104 if( it == clusterOf.end() )
105 continue;
106
107 if( neighbour->Net() != item->Net() )
108 continue;
109
110 BOOST_REQUIRE_MESSAGE( it->second == cluster,
111 "connected items landed in different clusters" );
112 }
113 }
114
115 // Conversely each cluster has to be reachable end to end, or the search merged components
116 // that share no path.
117 for( const std::shared_ptr<CN_CLUSTER>& cluster : clusters )
118 {
119 std::set<CN_ITEM*> members( cluster->begin(), cluster->end() );
120 std::set<CN_ITEM*> seen;
121 std::deque<CN_ITEM*> queue;
122
123 queue.push_back( *cluster->begin() );
124 seen.insert( *cluster->begin() );
125
126 while( !queue.empty() )
127 {
128 CN_ITEM* current = queue.front();
129 queue.pop_front();
130
131 for( CN_ITEM* neighbour : current->ConnectedItems() )
132 {
133 if( members.count( neighbour ) && !seen.count( neighbour ) )
134 {
135 seen.insert( neighbour );
136 queue.push_back( neighbour );
137 }
138 }
139 }
140
141 BOOST_REQUIRE_EQUAL( seen.size(), members.size() );
142 }
143}
144
145
152static void checkRatsnestSpansClusters( BOARD* aBoard )
153{
154 std::shared_ptr<CONNECTIVITY_DATA> conn = aBoard->GetConnectivity();
155 std::shared_ptr<CN_CONNECTIVITY_ALGO> algo = conn->GetConnectivityAlgo();
156
157 std::map<int, std::set<const CN_CLUSTER*>> clustersPerNet;
158
159 for( const std::shared_ptr<CN_CLUSTER>& cluster :
160 algo->SearchClusters( CN_CONNECTIVITY_ALGO::CSM_RATSNEST ) )
161 {
162 // A kept island contributes no anchor, matching what AddCluster() skips.
163 if( cluster->IsOrphaned() && cluster->Size() == 1
164 && dynamic_cast<CN_ZONE_LAYER*>( *cluster->begin() ) )
165 {
166 continue;
167 }
168
169 if( cluster->OriginNet() > 0 )
170 clustersPerNet[cluster->OriginNet()].insert( cluster.get() );
171 }
172
173 size_t netsChecked = 0;
174 size_t edgesSeen = 0;
175
176 for( const auto& [net, netClusters] : clustersPerNet )
177 {
178 RN_NET* rn = conn->GetRatsnestForNet( net );
179
180 if( !rn || rn->GetNodeCount() == 0 )
181 continue;
182
183 const std::vector<CN_EDGE>& edges = rn->GetEdges();
184
185 BOOST_REQUIRE_MESSAGE( edges.size() == netClusters.size() - 1,
186 "net " << net << " has " << netClusters.size() << " clusters but "
187 << edges.size() << " ratsnest edges" );
188
189 for( const CN_EDGE& edge : edges )
190 BOOST_REQUIRE( edge.GetSourceNode() && edge.GetTargetNode() );
191
192 netsChecked++;
193 edgesSeen += edges.size();
194 }
195
196 BOOST_REQUIRE_MESSAGE( netsChecked > 0, "no net on this board exercised the ratsnest" );
197 BOOST_TEST_MESSAGE( "net count " << netsChecked << ", ratsnest edges " << edgesSeen );
198}
199
200
201// Filling these boards dominates, so both checks share one load
202BOOST_DATA_TEST_CASE( ClustersAndRatsnestMatchTheBoard, boost::unit_test::data::make( c_boards ), boardName )
203{
204 KI_TEST::LoadBoard( m_settingsManager, boardName, m_board );
205 KI_TEST::FillZones( m_board.get() );
206 m_board->BuildConnectivity();
207
210}
211
212
Information pertinent to a Pcbnew printed circuit board.
Definition board.h:411
std::shared_ptr< CONNECTIVITY_DATA > GetConnectivity() const
Return a list of missing connections between components/tracks.
Definition board.h:758
std::vector< std::shared_ptr< CN_CLUSTER > > CLUSTERS
CN_EDGE represents a point-to-point connection, whether realized or unrealized (ie: tracks etc.
CN_ITEM represents a BOARD_CONNECTED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
const std::vector< CN_ITEM * > & ConnectedItems() const
Represents a single outline of a zone fill on a particular layer.
Describe ratsnest for a single net.
unsigned int GetNodeCount() const
const std::vector< CN_EDGE > & GetEdges() const
void LoadBoard(SETTINGS_MANAGER &aSettingsManager, const wxString &aRelPath, std::unique_ptr< BOARD > &aBoard)
void FillZones(BOARD *m_board)
Class that computes missing connections on a PCB.
BOOST_DATA_TEST_CASE(ConvertToKicadUnit, boost::unit_test::data::make(altium_to_kicad_unit), input_value, expected_result)
Test conversation from Altium internal units into KiCad internal units.
static void checkRatsnestSpansClusters(BOARD *aBoard)
A ratsnest is a spanning forest over the clusters of a net, so it must hold exactly one edge fewer th...
static void checkClustersAreConnectedComponents(BOARD *aBoard)
Every item must land in exactly one cluster, each cluster must be internally reachable over the adjac...
BOOST_REQUIRE_EQUAL(rows.size(), 1)
BOOST_CHECK_EQUAL(std::any_cast< std::string >(rows[0].at("val")), "12345678901234567.89")
BOOST_REQUIRE_MESSAGE(dc.CacheTableInfo(table, { "part_id", "val" }), dc.GetLastError())
BOOST_REQUIRE(res.columns()==1)
BOOST_AUTO_TEST_SUITE_END()
BOOST_TEST_MESSAGE("Polyline has "<< chain.PointCount()<< " points")