Undirected_Graph Component

Index:

Abstract
Calendar
Project Development
Findings and Contributions
Links and References
Return to Europa

Abstract:

My research entails designing, specifying, coding, testing, debugging, and documenting different versions of an Undirected_Graph component for the RESOLVE/C++ Component Library. Each version uses the same kernel of operations to manipulate the state of an undirected graph. The implementation strategy changes for each version. The first five versions use the "classic" strategies (adjacency list, adjacency matrix, and edge list) in a variety of ways. The final version uses a strategy that will allow each operation to execute in constant time.

The significance of this inquiry is twofold. First, the Undirected_Graph component will follow the principles of object-oriented programming, software reusability, and "good" programming. Second, the final version will be the first to have each operation execute in constant time. Computer scientists using this version to implement "classic" graph algorithms will now be able to argue certain theoretical cases more easily. Also, the final version will allow for faster programs utilizing graphs. Finally, all versions of the Undirected_Graph component will eventually assist in the design, specification, coding, testing, debugging, and documentation of the Directed_Graph, Undirected_Weighted_Graph, and Directed_Weighted_Graph components.

Calendar:

early December 1998: presented first ideas about design of Undirected_Graph component

mid February 1999: presented newer ideas about kernel operations on an Undirected_Graph

late February 1999: defined the kernel operations on an Undirected_Graph and their specifications

March 11, 1999: met with Bruce Weide to determine next step in process

early October 1999: continued to specify the kernel operations

early February 2000: began a code and specification evaluation

mid March 2000: finished the code and specification evaluation

late March 2000: wrote the conventions and correspondences for each implementation; began to implement Adjacency List Using Queues

early April 2000: finished implementing Adjacency List Using Queues; presented implementation at Europa meeting

April through early June 2000: finished implementing other implementations

October 2000: presented conventions and correspondences at Europa meeting

November 2000: accepted to SIGCSE2001 conference in Charlotte for Undirected_Graph research

December 2000: evaluation of conventions and correspondences; begin writing Honors Thesis

Project Development:

At first, I thought I could combine Undirected_ and Directed_Graph into a single Graph component. But after my first presentation, it became apparent that such a design is impossible. So I proceeded to separate the two and to concentrate on first designing the Undirected_Graph component. My two tasks were to define the kernel operations on an Undirected_Graph and to provide a mathematical model for Undirected_Graph. I thought that node and edge labels were necessary parts of graphs and should be a part of the model. After my second and third presentations, however, this idea also did not seem to be the best way of designing the model. So I decided to leave labels out of the model. Then, during the third presentation, with the help of Bruce Weide, I defined the kernel operations and their specifications. Now I have to finish defining the mathematical model. I believed that graphs should be templates, so that the client could insert whichever implementation tool (adjacency list, adjacency matrix, edge list, partitionable array, etc.) he/she so chooses when a Graph is defined in a program. But Bruce convinced me that it should be an instance, since the implementers should be the only ones to use the tools. With Bruce's help, I defined the mathematical model and thus finished the design of the Undirected_Graph component. Now I am going to provide six different implementations of the Undirected_Graph component, based on different implementation tools.

I wrote conventions and correspondences for each "classic" implementation (Adjacency List Using Sets, Adjacency List Using Queues, Adjacency Matrix Using Arrays, Edge List Using Sets, and Edge List Using Queues). During my last presentation, Bruce, Paolo, and Scott Pike pointed out some problems with the convention and correspondence for Adjacency List Using Sets. During Winter Break, I am going to re-evaluate and rewrite all conventions and correspondences and begin my Honors Thesis.

I wrote an abstract for the SIGCSE2001 conference in Charlotte. Luckily, they accepted my abstract and invited me to attend the conference. I think that I will be going with Scott and Bruce. It should be fun. During Winter Break, I will begin my preparations for this conference.

Findings and Contributions:

To view the Undirected_Graph component online, go to the Software Component Engineering Home Page. Click on Component Catalog, then click on Undirected_Graph. Click on any link to view the specified portion of the component.

Links and References:

Software Component Engineering Home Page

  Return to Europa