- Read in a description of a circuit,

- Generate the system of equations in the form of an augmented matrix (section 8.3),

- Use the book's implementation of Gaussian Elimination to solve the system of equations and

- Print a table of results.

The input (problem instance) describes the interconnections of two kinds of components: batteries and resistors. The graphical representation of such a circuit is called a schematic diagram; an example is here. The lines connecting terminals define nodes; regardless of how they wander around the page, any terminals joined by lines are connected to the same node.

To represent a circuit in a form that we can input, we make
the following assumptions:

All components and nodes are named (uniquely) by the user.

One node must be named Vref.

The user designates one terminal as + and one as - on each component.

The electrical current through a component is directed from its +
terminal to its - terminal.

A solution consists of values for the voltage present at each
node and the current through each component. For convenience,
we will also output the voltage *across* each component.
If the voltage at the node connected to the plus terminal is
designated V(+) and the voltage at the negative terminal (node)
is V(1), the voltage difference is V(+)-V(-).

Three kinds of equations appear in our system.

- The equations Vref = 0 defines a reference point for voltages. This is
necessary since all the other equations are in terms of
voltage differences.

- For each node other than Vref,
Kirchoff's current law
requires that the sum of currents *into* that node be zero. Since we
treat the current through a + terminal as directed away from the attached
node, the equation is
(sum - terminal currents) - (sum + terminal currents) = 0.

Finally, each type of component enforces a relationship between
current and voltage.

- A battery sets delta-V = V(+)-V(-) = Vb (battery voltage) and leaves
the current free.
- A resistor follows Ohm's law: I = current = delta-V/resistance. Resistance
is a constant characteristic of each individual resistor. We rewrite
the resistance equation in the form

V(+)-V(-)- R*I = 0

to keep constants on the right-hand-side.

The input format will be a table having columns

cname value units +node -node

where

Cname is a user-defined component name, typically something like B1 or R3. We will use these names to label the corresponding rows in the output table. It is an error to use a name twice in one input table.

Value is the numeric value of the component's characteristic constant: that is, the voltage of a battery or the resistance of a resistor.

Units specifies the units for the component value with an optional metric multiplier. V represents voltage and we will use O (capital-oh) to represent Ohms since we don't have a capital Omega in our character set. On output we will use A (Amperes) for current. An optional leading K or m specifies a multiplier of 1000 or 1/1000 on the value. Note that the O or V in the units field is the only way we can know whether the input line designates a battery or a resistor.

The +node and -node columns contain user-defined node names.

After working through the two possibilities, I decided to use
two tables. The considerations are:

1) A sinlge table can directly map to and from
matrix row and column numbers.

2) Detecting misuse of a name would require a lookup in both
tables. Ugly and error prone.

On the other hand,

3) When building the matrix from the input data and when
formatting the output from the matrix, we need to be able
to loop over nodes and components separately.

4) The mechanisms for putting two different kinds of objects
in the same table in C++ require coding tricks that aren't safe.

Let's put all the nodes first, in alphabetical order, then all the components. The table below give a logical index map in the matrix row/column space.

n0 n1 n2 n3 c0 c1 c2 c3 c4 Const | | | | | 0 ......... nn-1 nn+0 ........... nn+nc-1 nn+nc nn=4 nodes nc=5 compsOne of the nodes is Vref, of course. The Const column is the column containing the result vector in the augmented matrix representation of section 8.3.

We must now confront a subtle issue. Because we actually have two
different kinds of nodes (reference and regular) and two kinds of
components (batteries and resistors), we can't just allocate a
bunch of them in an array. Instead we will allocate them as needed,
using the `new` operator.

Any time you use new, you must see to it that delete gets called to destroy the object you created. Objects created with ordinary declarations are destroyed when the function returns, but dynamic objects must be destroyed explicitly. We will make the symbol table objects responsible for destroying the circuit elements they contain.

Finally, we need to deal with the fact that we want symbol tables
for two different kinds of things. After trying to treat them as
one kind of thing I concluded that wasn't a good idea, and writing
out the code for a symbol table twice is certainly not a good idea.
So, we'll use the *template* mechanism.

Here's the code:

// Symbol table template. // // Symbol tables assume responsiblity for the dynamically // created objects of type T stored in them. T must have a public // data memberidentof type string. // // Public properties of a symbol table include the number // of objects stored in it, access to those objects using // array index syntax, and lookup of index by identifier value. // // When a new object is placed in the table it is inserted in // order (as defined by the < operator), causing the indices // to be recomputed. Lookup of a name not in the list returns -1. // const maxelements = 20; template <class T> class symtab { private: T *list[maxelements]; int num_entries; public: symtab() { num_entries = 0; } ~symtab() { for ( int i = 0; i < num_entries; i++ ) delete list[i]; num_entries = 0; } int count() { return num_entries; } int lookup(const string &key); void insert(T *p); T &operator[] ( int i ) { assert( i >= 0 && i < num_entries ); return *(list[i]); // note pointer dereference syntax } }; // for lookup just use linear search template <class T> int symtab<T>::lookup ( const string &key ) { for ( int i = 0; i < num_entries; i++ ) if ( list[i]->ident == key ) return i; return -1; } // insert an entry using insertion sort. template <class T> void symtab<T>::insert ( T *p ) { assert ( p && num_entries < maxelements ); int i = 0; // scan to insertion point while ( i < num_entries && list[i]->ident < p->ident ) i++; if ( i < num_entries ) // check for duplicate assert ( p->ident != list[i]->ident ); // move all higher items up one slot for ( int j = num_entries; j > i; --j ) list[j] = list[j-1]; // insert new entry list[i] = p; // and count it ++num_entries; };

Here's an interactive test driver for the symtab class. It's designed to allow you to enter a bunch of strings, then indicate end-of-file. It then prints out the symbols in order.

// we need a class to store in the table. this will do: class table_entry { public: string ident; table_entry(const string &s) { ident = s; } }; int main() { string s; symtab<table_entry> tab; cin >> s; while ( !cin.fail() ) { int i = tab.lookup(s); if ( i == -1 ) tab.insert(new table_entry(s)); else cout << "present at " << i << endl; cin >> s; } for ( int i = 0; i < tab.count(); i++ ) cout << tab[i].ident << endl; return 0; }

Replace the linear search in lookup with a binary search and test thoroughly. Why is this replacement valid?

Your compiler's string class is broken. Use this code instead.

Design several tests. Some should exercise the error detection statements in the code. Others should be set up to verify the computation -- that means you need to know what the answer shoule be!

Because the method of computing the matrix entries varies
between element types, that function must be virtual.
Since we will have a hierarchy of classes with dynamically
allocated instances, we **must** declare a virtual destructor.

That leaves us needing a way to designate the result column. Let's use the empty string for that purpose.

// common ancestor class of all circuit elements, // suitable for symbol table insertion. class element { public: string ident; virtual double coefficient(const string &ename); virtual ~element() {} }; // subclass nodebase, the type suitable for inclusion in the // nodes symbol table. No additional interface. class nodebase: public element { protected: nodebase() {} // can't build one directly }; // subclass vref: just for Vref class vref: public nodebase { public: vref(const string &name) { assert ( name == "Vref" ); ident = name; } double coefficient(const string &ename) { // a one on the diagonal, zeroes off-diagonal and a zero result if ( ename == ident ) return 1; else return 0; } ~vref() {} }; // subclass node, for general nodes class node: public nodebase { public: node(const string *name) { ident = name; } ~node() {} // coefficient routine needs to look for connected components double coefficient(const string &ename); }; // subclass component: has terminals, // can display itself in input format class comp: public element { public: string t_plus, t_minus; // names of connected nodes // display through a virtual function is weird protected: virtual display(ostream &os); friend ostream &operator<< ( ostream &os, const comp &c ); }; ostream &operator<< ( ostream &os, const comp &c ) { c.disp(os); return os; } // Now we can write node::coefficient, but it needs to // be able to find the components symbol table. // Decision: make the symbol tables global. symtab<comp> comp_table; symtab<node> node_table; double node::coefficient ( const string &ename ) { int i = comp_table.lookup(ename); if ( i < 0 ) return 0; // not a component name // see if one of the terminals is connected to this node if ( comp_table[i].t_plus == ident ) return 1; if ( comp_table[i].t_minus == ident ) return -1; // nope return 0; } // Now we just have to write a subclass for each component type class battery: public comp { private: double voltage; public: battery(const string &name, double volts, const string &tp, const string &tm ) { ident = name; voltage = volts; t_plus = tp; t_minus = tm; } void disp(ostream &os) { double v = voltage; string units = ""; if ( fabs(v) < 1 ) { v *= 1000; units += "m"; } else if ( fabs(v) > 999 ) { v /= 1000; units += "K"; } os << setw(10) << ident << setw(10) << voltage << setw(4) << units + "V" << setw(10) << t_plus << setw(10) << t_minus << endl; } double coefficient(const string &ename) { if ( ename == "" ) return voltage; if ( ename == t_plus ) return 1; if ( ename == t_minus ) return -1; return 0; } }; class resistor: public comp { private: double resistance; public: resistor(const string &name, double rval, const string &tp, const string &tm ) { ident = name; resistance = rval; t_plus = tp; t_minus = tm; } void disp(ostream &os) { double r = resistance; string units = ""; if ( fabs(r) < 1 ) { v *= 1000; units += "m"; } else if ( fabs(r) > 999 ) { v /= 1000; units += "K"; } os << setw(10) << ident << setw(10) << voltage << setw(4) << units + "O" << setw(10) << t_plus << setw(10) << t_minus << endl; } double coefficient(const string &ename) { if ( ename == t_plus ) return 1; if ( ename == t_minus ) return -1; if ( ename == ident ) return -resistance; return 0; } };

int main() { string ename; double value; string units; string tpname, tmname; comp *p; node_table.insert(new vref("Vref")); cin >> ename >> value >> units >> tpname >> tmname; while ( !cin.fail() ) { cin >> ename >> value >> units >> tpname >> tmname; if ( comp_table.lookup(ename) != -1 || node_table(ename) != -1 ) ) { cout << ename << ": duplicate name" << endl; exit(1); } if ( comp_table.lookup(tpname) != -1 ) { cout << tpname << ": component used as node" << endl; exit(1); } if ( node_table.lookup(tpname) == -1 ) { node_table.insert(new node(tpname)); } if ( comp_table.lookup(tmname) != -1 ) { cout << tpname << ": component used as node" << endl; exit(1); } if ( node_table.lookup(tmname) == -1 ) { node_table.insert(new node(tmname)); } if ( units.length() > 1 ) switch ( units[0] ) { case 'm': value /= 1000; units = units.substr(1); break; case 'K': value *= 1000; units = units.substr(1); break; default: cout << units << ": bad units" << endl; exit(1); } if ( units == "V" ) p = new battery(ename, value, tpname, tmname); else if ( units == "O" ) p = new resistor(ename, value, tpname, tmname); else { cout << "no component type defined for " << units << endl; exit(1); } comp_table.insert(p); } if ( cin.eof() ) { cout << "results:" << endl; for ( i = 0; i < comp_table.count(); ++i ) { cout << comp_table[i]; } } else { cout << "error encountered" << endl; exit(1); } return 0; }

Prepare an input file with several components of each type and verify that the test program prints an equivalent table.

Prepare additional input files to test the error detection code in the input loop.

int nn = node_table.count(); int nc = comp_table.count(); for ( int i = 0; i < nn + nc; ++i ) { element &e = i < nn ? node_table[i] : comp_table[i-nn]; cout << setw(6) << e.ident << ": "; string sep = " "; for ( j = 0; j < nn; ++j ) { double c = e.coefficient(node_table[j].ident); if ( c != 0 ) { if ( c < 0 ) sep = "- "; cout << sep << fabs(c) << " V(" << node_table[j].ident << ") "; sep = "+ "; } } for ( j = 0; j < nc; ++j ) { double c = e.coefficient(comp_table[j].ident); if ( c != 0 ) { if ( c < 0 ) sep = "- "; cout << sep << fabs(c) << " I(" << comp_table[j].ident << ") "; sep = "+ "; } } cout << "= " << e.coefficient("") << endl; }

Think about how that's happening. Each call to coefficient is
being dispatched to the proper implementation based on the *subtype*
of element that the object e belongs to.

Modify the class definition of Matrix so that it is a subclass of that base class.

Give matrix a copy constructor

Matrix ( const matrixbase &src );Derive another subclass, circuit, that provides coefficients by looking up circuit elements in the symbol tables and calling their coefficient routines.

After inputing a circuit desription, declare a Matrix object using the copy constructor. Print the Matrix (using cout << m) and verify that the coefficients match those in the equation printout from activity 4.

Node Voltage n1 10 V n2 100 mV Component Currents Voltages b1 1 A 10 V r1 1 A 9.9 V r2 500 mA 100 mV r3 500 mA 100 mVNote: I manually estimated the above, assuming the following input file. It won't round so nicely in practice.

The input was b1 .01 KV n1 Vref r1 9.1 KO n1 n2 r2 180 O n2 Vrev r3 180 O n2 Vrev