Abstracts Computer Science

Graph algorithms experimentation facility

by Donald George Sonom

We provide a facility to experiment with graph algorithms. The facility is implemented as a client to XAGE, a software environment developed under the direction of Dr. James Abello. XAGE allows a user to visually animate algorithmic actions with the capability of recording a session to be replayed later. Diverse graph representations and generation methods are offered. Several mechanisms allow a user to set up drivers to control input, output and execution of a set of external algorithms. This is achieved by using control files. External algorithms can be incorporated into the facility by a simple process of linking and registration. These algorithms now become internal algorithms. Input, output and execution of internal algorithms are controlled by scrolling menus. A user can execute in both a supervised and non-supervised fashion. In the nonsupervised mode a sequence of algorithms can be executed on a set of graphs and the results and the graphs are recorded (optionally) into a file. A special log file is provided to make annotations about interesting algorithmic events. This functionality is achieved by generating unique graph identifiers. To test the usefulness of our facility we have experimented with several graph algorithms. These include minimum vertex cover and maximum clique size heuristics and some visibility and circle graph related methods. As a by-product of our implementation we obtained several results about the structure of maximum independent sets for several classes of graphs. Some conjectures and open problems are proposed for further investigation.