Undirected_Graph Component
Advisor(s): Bruce Weide
Participants: Shawn Craft
Start Date: Autumn Quarter 1998
Project Status: Active
Index:
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:
Return to Europa
Shawn
Craft <craft@cis.ohio-state.edu>
Last modified: Fri Dec 8 03:46:00 EST 2000