Overview
The project will be able to account for simple graphs, disconnected graphs, and trees.
A simple graph does not need to have edges that cross when drawn, while a disconnected
graph, is a graph that has two nodes without a path between them. A tree is an acyclic
graph, which implies that for all vertices no path exists from the vertex to itself
without using the same edge twice.
The applet will consist of a place to
input the graph, buttons to activate the action listener, and displays to output
information. The inputting will be easy for the user who will first put the graph
in matrix form. Then the user will input the matrix with the names of all the
vertices on both the top and the left side, and the values of the edges in the
input boxes underneath and to the left of the appropriate vertices.
The matrix form will allow for direct, indirect, and weighted graphs
depending on the values for each edge. If the graph has separate values
for each edge then the graph is weighted, and the user can account by putting numbers
of difference values in the matrix. If the graph is not weighted then the user
can input a value of one. The user can decide whether the graph is to be indirect,
such that edges do not have direction, or direct, such that they do have direction.
If the user wants the graph to be direct then the matrix must be symmetric and if
the user wants the graph to be indirect then the graph must not be symmetric.
Next, the applet will contain a place for displaying the output. There will be a
text field for the numerical or boolean value found by the algorithm and a separate
text field for the explanation of the algorithm. Then there will be two separate
fields for time, one for actual time and the other for the expected time. Also,
the applet will be able to show each step of the algorithm.
The applet will be to find the shortest path, Hamiltonian and Euler paths, minimum
spanning trees, the best single source, longest path, its complement, whether its
bipartite or regular, and will also be able to use different search algorithms It
will also include any new algorithms found by the creator.
Finally, the applet will be part of a web page. On the page there will be explanations
of each algorithm and how they are to be used. Each solution will contain at least one
real world example and a few will have mathematical proofs. Also, on the page there
will be links to other graph theory information and a list of sources to provide proper
reading material for a better understanding of graph theory. It will also explain any
new algorithms invented during the process of this project and what was learned from
them.
Main Page