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
96
|
/*
Copyright 2010 Intel Corporation
Use, modification and distribution are subject to the Boost Software License,
Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt).
*/
//compare_schematics.hpp
#ifndef BOOST_POLYGON_TUTORIAL_COMPARE_SCHEMATICS_HPP
#define BOOST_POLYGON_TUTORIAL_COMPARE_SCHEMATICS_HPP
#include <string>
#include "schematic_database.hpp"
bool compare_connectivity(std::string& ref_net, std::string& net,
schematic_database& reference_schematic,
schematic_database& schematic,
std::vector<std::size_t>& reference_to_internal_device_map,
std::size_t node_id) {
std::set<std::size_t>& ref_nodes = reference_schematic.nets[ref_net];
std::set<std::size_t>& nodes = schematic.nets[net];
for(std::set<std::size_t>::iterator itr = ref_nodes.begin();
itr != ref_nodes.end() && *itr < node_id; ++itr) {
if(nodes.find(reference_to_internal_device_map[*itr]) == nodes.end())
return false;
}
return true;
}
bool compare_schematics_recursive
(schematic_database& reference_schematic,
schematic_database& schematic,
std::vector<std::size_t>& reference_to_internal_device_map,
std::set<std::size_t>& assigned_devices, std::size_t node_id){
//do check of equivalence up to this node
for(std::size_t i = 0; i < node_id; ++i) {
for(std::size_t j = 0; j < reference_schematic.devices[i].terminals.size(); ++j) {
device& rd = reference_schematic.devices[i];
device& xd = schematic.devices[reference_to_internal_device_map[i]];
if(rd.type == "PIN") {
if(rd.terminals[j] != xd.terminals[j])
return false;
} else {
//connectivity must be the same
if(j == 1) {
//gate has to be the same net
if(!compare_connectivity(rd.terminals[1], xd.terminals[1], reference_schematic, schematic,
reference_to_internal_device_map, node_id))
return false;
} else {
//order of nets in source and drain is not important so check both ways and accept either
if(!compare_connectivity(rd.terminals[j], xd.terminals[0], reference_schematic, schematic,
reference_to_internal_device_map, node_id) &&
!compare_connectivity(rd.terminals[j], xd.terminals[2], reference_schematic, schematic,
reference_to_internal_device_map, node_id))
return false;
}
}
}
}
if(node_id >= reference_schematic.devices.size())
return true; //final success
//recurse into subsequent nodes
for(std::size_t i = 0; i < schematic.devices.size(); ++i) {
if(reference_schematic.devices[node_id].type !=
schematic.devices[i].type)
continue; //skip dissimilar devices
//avoid multi-assignment of devices
if(assigned_devices.find(i) == assigned_devices.end()) {
reference_to_internal_device_map[node_id] = i;
std::set<std::size_t>::iterator itr = assigned_devices.insert(assigned_devices.end(), i);
if(compare_schematics_recursive(reference_schematic, schematic,
reference_to_internal_device_map,
assigned_devices, node_id + 1))
return true;
assigned_devices.erase(itr);
}
}
//could not find match between schematics
return false;
}
//this is a trivial brute force comparison algorithm because comparing
//schematics does not require the use of Boost.Polygon and doing it more
//optimally does not add to the tutorial
inline bool compare_schematics(schematic_database& reference_schematic,
schematic_database& schematic) {
std::vector<std::size_t>
reference_to_internal_device_map(reference_schematic.devices.size(), 0);
std::set<std::size_t> assigned_devices;
return compare_schematics_recursive(reference_schematic, schematic,
reference_to_internal_device_map,
assigned_devices, 0);
}
#endif
|
