Week 9

This week we work upon the Project 9 - Graph; the task was to reverse engineer the Boost Graph Library and implement a Graph class which will bear the functionality of adding vertices and directed edges. It also provides methods to determine whether the graph is Directed Acyclic Graph (DAG), and if it is, it provide function to topologically sort the vertices. The most daunting task was to have a firm and robust design for the data structure to be used for the implementation. We ended up using a vector of sets, where the index of the vector would determine the vertex, and the corresponding set elements will represent the vertices that are connected to this vertex. As discussed in the class, there are other standard implementation of the graphs: adjacency lists (for graphs that are sparse), and adjacency matrix (for dense graph). Another challenging task was to write the algorithm for the topological sorting. Having done a bit of research, showed that it could be done using depth first traversal. We implemented a recursive function, and a three color scheme to traverse the graph (depth first). The colors determined whether the vertex has been visited, is yet to visit, or has its traversal completed.

In the class, we went over important iterators such as front_insert_iterator (/back_insert_iterator) and their corresponding function objects front_inserter (/back_inserter). These iterators conform to the STL conventions, and could be used with other STL algorithms such as copy. These come in handy when there is a situation such as,


vector x(10,2);
list y(5,3);

std::copy(x.begin(), x.end(), back_inserter(y));


This will result into copying of all the elements of x into y, after which y.size() == 15. However, to have the copy() and other STL algorithms work, the front and back inserters have a peculiar design. The operator *(), operator ++ () return *this of the same type as the class, while operator = (const T& v) also returns itself, but does x.push_front(v) (or x.push_back(v)). A similar design is followed by the ostream_iterator and istream_iterator. However, istream_iterator do maintain data member istream* in to consider the !=EOF criteria.

We learned about few more subtleties of C++ (rather I should say, very important subtleties that if not aware of can lead to programmer's frustration). We studied as to when an argument is taken as a function pointer, and when it's not. For eg.


A x(2,3,4); //constructor
A t; //default constructor

A z(); //function declaration whose return type is A



//LEGAL function declarations
int f(int);
int g(int x); //argument with a name
int h(int (x));

int q((int x)); //ILLEGAL


Likewise, few other examples,

int f(int (*p) ()); //named parameter, with a pointer notation
int g(int p()); //named parameter
int h(int ()); //no name
//all of above mean the same



int m (int (int)); valid
int n (int (int x)); probably unreasonable


In case of ambiguity, the declaration of function wins.