Boost C++ Libraries of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.


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
#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 !=
      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,
                                      assigned_devices, node_id + 1))
        return true;
  //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) {
    reference_to_internal_device_map(reference_schematic.devices.size(), 0);
  std::set<std::size_t> assigned_devices;
  return compare_schematics_recursive(reference_schematic, schematic, 
                                      assigned_devices, 0);