You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
332 lines
10 KiB
C++
332 lines
10 KiB
C++
/* -*- C++ -*-
|
|
* Copyright (C) 2018 Felix Salfelder
|
|
* Author: Felix Salfelder <felix@salfelder.org>
|
|
*
|
|
* This file is part of "Gnucap", the Gnu Circuit Analysis Package
|
|
*
|
|
* 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, 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, write to the Free Software
|
|
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
|
|
* 02110-1301, USA.
|
|
*------------------------------------------------------------------
|
|
* apply node ordering algorithms
|
|
*
|
|
* some code borrowed from c_delete.cc
|
|
*/
|
|
#include "globals.h"
|
|
#include "e_cardlist.h"
|
|
#include "c_comand.h"
|
|
//#include "u_nodemap.h"
|
|
#include "e_node.h"
|
|
#include "e_subckt.h"
|
|
#include <boost/graph/cuthill_mckee_ordering.hpp>
|
|
#include <boost/graph/adjacency_list.hpp>
|
|
#include <boost/graph/graph_utility.hpp>
|
|
/*--------------------------------------------------------------------------*/
|
|
// nodemap with non-upstream permute
|
|
class NODE_MAP {
|
|
private:
|
|
std::map<std::string, NODE*> _node_map;
|
|
explicit NODE_MAP(const NODE_MAP&);
|
|
|
|
public:
|
|
explicit NODE_MAP();
|
|
~NODE_MAP();
|
|
NODE* operator[](std::string);
|
|
NODE* new_node(std::string);
|
|
|
|
typedef std::map<std::string, NODE*>::iterator iterator;
|
|
typedef std::map<std::string, NODE*>::const_iterator const_iterator;
|
|
|
|
const_iterator begin()const {return _node_map.begin();}
|
|
const_iterator end()const {return _node_map.end();}
|
|
int how_many()const {return static_cast<int>(_node_map.size()-1);}
|
|
|
|
public:
|
|
void permute(unsigned* p) {
|
|
#ifndef NDEBUG
|
|
size_t size=how_many();
|
|
|
|
std::vector<bool> check(size+1);
|
|
for(unsigned i=0; i<=size; ++i){
|
|
check[p[i]] = true;
|
|
}
|
|
|
|
for(unsigned i=0; i<=size; ++i){
|
|
assert(check[i]);
|
|
}
|
|
#endif
|
|
|
|
for(iterator a=_node_map.begin(); a!=_node_map.end(); ++a){
|
|
int n=a->second->user_number();
|
|
a->second->set_user_number(int(p[n]));
|
|
}
|
|
}
|
|
};
|
|
/*--------------------------------------------------------------------------*/
|
|
namespace {
|
|
/*--------------------------------------------------------------------------*/
|
|
static void do_cmk(CARD_LIST* subckt, unsigned net_nodes=0)
|
|
{
|
|
// there should be nodes in _n. these are the ports.
|
|
// more nodes are in scope()->nodes()
|
|
// these need to be sorted somehow.
|
|
size_t how_many=size_t(subckt->nodes()->how_many());
|
|
trace2("finish", net_nodes, subckt->nodes()->how_many());
|
|
|
|
int internal_nodes=subckt->nodes()->how_many()-int(net_nodes);
|
|
int port_supernode=(bool)net_nodes;
|
|
|
|
boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS,
|
|
boost::property<boost::vertex_degree_t,int> > g(
|
|
size_t(internal_nodes+port_supernode)); // 1 dummy node for external ports.
|
|
|
|
unsigned n=unsigned(boost::num_vertices(g));
|
|
|
|
trace2("setup", port_supernode, n);
|
|
|
|
for(auto i : *subckt){
|
|
if(!i->is_device()){ untested();
|
|
continue;
|
|
}
|
|
trace2("user number", i->long_label(), i->net_nodes());
|
|
// create a clique for each set of ports
|
|
// this is an overapproximation, exact looks pretty expensive and perhaps
|
|
// make no difference (in most cases)
|
|
for(int j=0; j<i->net_nodes(); ++j){
|
|
trace1("connectto", i->n_(j).e_());
|
|
for(int k=0; k<j; ++k){
|
|
int n1 = i->n_(j).e_();
|
|
int n2 = i->n_(k).e_();
|
|
if(!n1){
|
|
// gnd. ignore.
|
|
}else if(!n2){
|
|
// gnd. ignore.
|
|
}else{
|
|
// squash ports into one supernode
|
|
n1 = std::max(0, n1-int(net_nodes)) + port_supernode - 1;
|
|
n2 = std::max(0, n2-int(net_nodes)) + port_supernode - 1;
|
|
|
|
if(n1!=n2){
|
|
assert(n1<int(n));
|
|
assert(n2<int(n));
|
|
boost::add_edge(unsigned(n1), unsigned(n2), g);
|
|
}else{
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
auto id=boost::get(boost::vertex_index, g);
|
|
|
|
std::vector<unsigned> inv_perm(n, -1u);
|
|
std::vector<unsigned> color(n, 0);
|
|
|
|
auto colormap=boost::make_iterator_property_map(&color[0], id, color[0]);
|
|
auto degreemap=boost::get(boost::vertex_degree, g);
|
|
|
|
if(port_supernode){
|
|
auto start=*(boost::vertices(g).first); // fix port supernode
|
|
cuthill_mckee_ordering(g, start, inv_perm.begin(), colormap, degreemap);
|
|
assert(id[inv_perm[0]]==0); // external port supernode fixed.
|
|
}else{
|
|
// do it fully automatically: choose initial node, and do all connected
|
|
// components
|
|
cuthill_mckee_ordering(g, inv_perm.begin(), colormap, degreemap);
|
|
}
|
|
|
|
#ifdef DEBUG
|
|
boost::print_graph(g);
|
|
#endif
|
|
|
|
for (unsigned c=0; c<n; ++c){
|
|
trace3("cmk", c, id[inv_perm[c]], colormap[c]);
|
|
}
|
|
|
|
std::vector<unsigned> o(how_many + 1, -1u); // include gnd.
|
|
|
|
for (unsigned c=0; c<=net_nodes; ++c){
|
|
o[c] = c; // gnd and external ports cannot be moved.
|
|
}
|
|
|
|
trace3("creating o", o.size(), port_supernode, id[inv_perm[0]]);
|
|
unsigned uncolored=0;
|
|
for (unsigned c=port_supernode; c!=inv_perm.size(); ++c){
|
|
if(id[inv_perm[c]]!=-1u){
|
|
trace3("map", c, id[inv_perm[c]]+net_nodes, c + net_nodes + 1 - port_supernode);
|
|
|
|
assert(id[inv_perm[c]]+net_nodes + 1 - port_supernode < o.size());
|
|
|
|
o[id[inv_perm[c]]+net_nodes + 1 - port_supernode] = c + net_nodes + 1 - port_supernode;
|
|
}else{ untested();
|
|
assert(port_supernode);
|
|
while(colormap[++uncolored]);
|
|
trace2("not mapped", c, uncolored);
|
|
o[uncolored+net_nodes] = c + net_nodes;
|
|
}
|
|
}
|
|
|
|
trace1("o", o.size());
|
|
for( auto idx : o ){
|
|
trace1("o", idx);
|
|
assert(idx!=-1u);
|
|
}
|
|
|
|
// create a permutation p of [0 ... how_many], but fix <net_nodes
|
|
|
|
if(subckt==&CARD_LIST::card_list){
|
|
// TODO: use _sim->_nm instead.
|
|
for(auto i : *subckt){
|
|
if(!i->is_device()){ untested();
|
|
continue;
|
|
}
|
|
for(int j=0; j<i->net_nodes(); ++j){
|
|
trace4("b4",i->n_(j).t_(), i->n_(j).e_(), CKT_BASE::_sim->_total_nodes, n);
|
|
unsigned on=CKT_BASE::_sim->_total_nodes;
|
|
assert(on==0 || on==n);
|
|
CKT_BASE::_sim->_total_nodes = n;
|
|
i->n_(j).map_subckt_node((int*)o.data(), NULL);
|
|
CKT_BASE::_sim->_total_nodes = on;
|
|
trace2("",i->n_(j).t_(), i->n_(j).e_());
|
|
}
|
|
}
|
|
}
|
|
|
|
subckt->nodes()->permute(o.data()); // change user numbers.
|
|
|
|
if(subckt==&CARD_LIST::card_list){
|
|
for(auto i : *subckt){
|
|
if(!i->is_device()){ untested();
|
|
continue;
|
|
}
|
|
for(int j=0; j<i->net_nodes(); ++j){
|
|
trace2("check",i->n_(j).t_(), i->n_(j).e_());
|
|
assert(i->n_(j).t_() == i->n_(j).e_());
|
|
|
|
}
|
|
}
|
|
}
|
|
}
|
|
class CMD_CMK : public CMD {
|
|
private:
|
|
void cmk_recursive( CARD_LIST* scope, unsigned net_nodes=0){
|
|
do_cmk(scope, net_nodes);
|
|
for (CARD_LIST::iterator i = scope->begin(); i != scope->end(); ++i) {
|
|
if ((*i)->is_device()){
|
|
// can only do models
|
|
}else if ( BASE_SUBCKT* c = dynamic_cast< BASE_SUBCKT*>(*i) ) {
|
|
cmk_recursive(c->subckt(), (*i)->net_nodes());
|
|
}else{
|
|
}
|
|
}
|
|
}
|
|
bool cmk_one(const std::string& name, CARD_LIST* Scope)const
|
|
{
|
|
assert(Scope);
|
|
|
|
std::string::size_type dotplace = name.find_first_of(".");
|
|
if (dotplace != std::string::npos) { untested();
|
|
// has a dot, look deeper
|
|
// Split the name into two parts:
|
|
// "container" -- where to look (all following the dot)
|
|
// "dev_name" -- what to look for (all before the dot)
|
|
std::string dev_name = name.substr(dotplace+1, std::string::npos);
|
|
std::string container = name.substr(0, dotplace);
|
|
// container name must be exact match
|
|
CARD_LIST::iterator i = Scope->find_(container);
|
|
if (i == Scope->end()) { untested();
|
|
// can't find "container" (probably .subckt) - no match
|
|
// try reverse
|
|
dotplace = name.find_last_of(".");
|
|
container = name.substr(dotplace+1, std::string::npos);
|
|
dev_name = name.substr(0, dotplace);
|
|
// container name must be exact match
|
|
i = Scope->find_(container);
|
|
}else{ untested();
|
|
}
|
|
if (i == Scope->end()) { untested();
|
|
// can't find "container" (probably .subckt) - no match
|
|
return false;
|
|
}else if ((**i).is_device()) { untested();
|
|
// found a match, but it isn't a container (subckt)
|
|
return false;
|
|
}else{ untested();
|
|
// found the container, look inside
|
|
return cmk_one(dev_name, (**i).subckt());
|
|
}
|
|
unreachable();
|
|
}else{
|
|
// no dots, look here
|
|
if (name.find_first_of("*?") != std::string::npos) { untested();
|
|
// there's a wild card. do linear search for all matches
|
|
bool didit = false;
|
|
{ untested();
|
|
CARD_LIST::iterator i = Scope->begin();
|
|
while (i != Scope->end()) { untested();
|
|
CARD_LIST::iterator old_i = i++;
|
|
// ^^^^^^^^^^^^ move i past the item being deleted
|
|
if (wmatch((**old_i).short_label(), name)) { untested();
|
|
if((*old_i)->is_device()){ untested();
|
|
}else if(BASE_SUBCKT* s=dynamic_cast<BASE_SUBCKT*>(*old_i)){ untested();
|
|
do_cmk(s->subckt(), (*old_i)->net_nodes());
|
|
didit = true;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return didit;
|
|
}else{
|
|
// no wild card. fast search for one exact match
|
|
CARD_LIST::iterator i = Scope->find_(name);
|
|
if (i != Scope->end()) {
|
|
if((*i)->is_device()){ untested();
|
|
}else if(BASE_SUBCKT* s=dynamic_cast<BASE_SUBCKT*>(*i)){
|
|
do_cmk(s->subckt(), (*i)->net_nodes());
|
|
return true;
|
|
}
|
|
}else{ untested();
|
|
return false;
|
|
}
|
|
}
|
|
unreachable();
|
|
}
|
|
unreachable();
|
|
return false;
|
|
}
|
|
//-----------------------------------
|
|
void do_it(CS& cmd, CARD_LIST* Scope)
|
|
{
|
|
_sim->uninit();
|
|
if (cmd.umatch(". ")) { untested();
|
|
do_cmk(&CARD_LIST::card_list);
|
|
}else if (cmd.umatch("all ")) {
|
|
cmk_recursive(&CARD_LIST::card_list);
|
|
}else{
|
|
while (cmd.more()) {
|
|
size_t mark = cmd.cursor();
|
|
bool didit = cmk_one(cmd.ctos(), Scope);
|
|
if (!didit) { untested();
|
|
cmd.warn(bWARNING, mark, "no match");
|
|
}
|
|
}
|
|
}
|
|
}
|
|
} p1;
|
|
DISPATCHER<CMD>::INSTALL d1(&command_dispatcher, "cmk|order_cmk", &p1);
|
|
/*--------------------------------------------------------------------------*/
|
|
}
|
|
/*--------------------------------------------------------------------------*/
|
|
/*--------------------------------------------------------------------------*/
|
|
// vim:ts=8:sw=2:noet:
|