Project 3 Materials

Project 3 will be due at 5pm on the last day of classes, Monday December 9th. You will have to integrate the code we design in class with code from figures 8.9 and 8.10 to build a working circuit analysis program.

Lecture 1: The problem

The steady-state, DC operation of a simple electrical circuit is determined by a system of linear equations. We will write a program that will
- 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.

Lecture 2: From Component Descriptions to Matrix Entries

Our input format allows the user to refer to objects by name. There is no way in a compiled language like C++ to directly link the value of a string to a variable name. Instead, we must use a lookup table structure. This is called a symbol table.

decision 1: input organization

We need to be able to distinguish two kinds of names: nodes and components. We could either use two different symbol tables or one table with two kinds of entries. What criteria should we base the decision on?

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.

decision 2: row/column assignment

Since we read all the input before building the matrix, we can delay assigning row and column numbers to nodes and components until all the input has been read.

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 comps
One 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.

decision 3: symbol table design

Our symbol tables will allow lookup by name and number. The objects in the tables will know their own names. The table will be stored in sorted order using an insertion sort. Lookup by name will return the number, lookup by number will access the object (node or component) stored there.

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.

decision 3a: array sizes

We'll limit the program to a maximum of 20 circuit elements. For maximum flexibilty we'll let either symbol table grow to that size, too.

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 member ident of 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;
};

Testing the symbol table implementation

Whenever you write a module (class, function, or a group of closely related classes and functions) it's a good idea to write a test program for the. That way you can eliminate bugs from a small program instead of searching for them in a large one.

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;
}

Project Activity 1

Get the above code working. Run it with appropriate inputs to test a) sorting b) duplicate detection and c) overflow detection.

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.

Project Activity 2

Get the Gaussian elimination code from figure 8.10 working. Modify it to allow for augmented matrices up to 20 rows by 21 columns. (Use the same constant that you used to size the symbol table arrays).

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!

Circuit element class hierarchy

All circuit elements have identifiers so they can be symbol table entries. All elements generate equations (matrix rows) so we need a way to query them for their matrix entries.

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.

decision 4: column designation

We need a way to query circuit elements for their table entries. We could do that by name or we could do it by matrix index. Let's do it by name.

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;
    }
};

Reading the input file

We should be ready to read the input file now. The reason I made the components be able to display themselves is so that I could test the input code.
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;
}

Project Activity 3

Get the above code working. Convert it so it uses an input file rather than cin. You should prompt for the name of the file (see section 7.4).

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.

Printing the Equations

Here's some code
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;
}

Project Activity 4

Replace the component-table output section of the main() from activity 3 with the above and get it working. Verify that the equations printed correspond to the node and component laws for the circuit input.

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.

Project Activity 5

Define a base class that is a matrix with a read-only interface to the elements.

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.

Project Activity 6

Call transformMatrix on the copied matrix and format the output. Note: no row for V(Vref)!
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 mV
Note: 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