123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596 |
- /*
- 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
|