1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
/*
VeroRoute - Qt based Veroboard/Perfboard/PCB layout & routing application.
Copyright (C) 2017 Alex Lawrow ( dralx@users.sourceforge.net )
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#pragma once
#include "Common.h"
// Keeps track of connectivity between a set of points (e.g. target pins in the routing algorithm)
// Quicker to use struct than a std::pair
struct CONNECTION
{
CONNECTION(size_t a, size_t b) : first(a), second(b) {}
size_t first = 0;
size_t second = 0;
};
class ConnectionMatrix
{
public:
ConnectionMatrix() {}
~ConnectionMatrix() { DeAllocate(); }
void Allocate(size_t N)
{
m_N = N;
const size_t N2 = m_N * m_N;
m_p = new bool[N2];
m_pp = new bool*[m_N];
memset(m_p, 0, N2 * sizeof(bool));
for (size_t i = 0; i < m_N; i++) m_pp[i] = m_p + i * m_N;
for (size_t i = 0; i < m_N; i++) m_pp[i][i] = true; // Each point is connected to itself
m_cost = static_cast<unsigned int>(N2 - m_N); // Cost = number of false values in the connection matrix
}
void DeAllocate()
{
if ( m_pp ) delete[] m_pp;
if ( m_p ) delete[] m_p;
m_pp = nullptr;
m_p = nullptr;
}
void Connect(size_t j, size_t k)
{
// Make j-k connection and enforce transitivity
std::list<CONNECTION> list; // Helper for updating the connection matrix
list.push_back( CONNECTION(j,k) );
while ( !list.empty() )
{
auto iter = list.begin(); // Read info from first list entry ...
const auto a = iter->first;
const auto b = iter->second;
list.erase( iter ); // ... then remove the list entry
if ( !m_pp[a][b] ) // If no a-b connection ...
{
m_pp[a][b] = m_pp[b][a] = true; // Make a-b connection ...
m_cost -= 2; // Update cost
for (size_t c = 0; c < m_N; c++) // Update 1st-order transitive relations
{
if ( m_pp[a][c] )
{
if ( !m_pp[b][c] ) list.push_back( CONNECTION(b,c) ); // a-c connection ==> b-c connection
}
else
{
if ( m_pp[b][c] ) list.push_back( CONNECTION(a,c) ); // b-c connection ==> a-c connection
}
}
}
}
}
const bool& GetAreConnected(size_t j, size_t k) const { return m_pp[j][k]; }
const unsigned int& GetCost() const { return m_cost; }
private:
size_t m_N = 0; // Number of points in the set
bool* m_p = nullptr; //
bool** m_pp = nullptr; // m_pp[j][k] is true if points j and k are connected
unsigned int m_cost = UINT_MAX; // Zero ==> all points are connected
};
|
