ASA_2011_GRAPHS
Sample Data and Code for "Graph Algorithms"
ASA_2011_GRAPHS
contains MATLAB programs which
were used during labs, demonstrations,
and lectures associated with the "Graph Algorithms" portion of
the class "Algorithms for Science Applications II", as taught
at the Scientific Computing Department, Florida State University,
Spring Semester 2011.
The Latex documents associated with this topic are available at
-
asa_2011_graphs,
Algorithms for Science Applications:
Lecture Notes on Graph Algorithms,
Department of Scientific Computing,
Florida State University, Spring Semester 2011.
-
asa_2011_graphs_homework,
Algorithms for Science Applications:
Homework Assignments on Graph Algorithms,
Department of Scientific Computing,
Florida State University, Spring Semester 2011.
-
asa_2011_graphs_lab,
Algorithms for Science Applications:
Lab on Graph Algorithms,
Department of Scientific Computing,
Florida State University, Spring Semester 2011.
The PDF versions of the documents are available as
-
asa_2011_graphs.pdf,
Algorithms for Science Applications:
Lecture Notes on Graph Algorithms,
Department of Scientific Computing,
Florida State University, Spring Semester 2011.
-
asa_2011_graphs_homework1.pdf,
Algorithms for Science Applications:
Homework #1 on Graph Algorithms,
Department of Scientific Computing,
Florida State University, Spring Semester 2011.
-
asa_2011_graphs_homework2.pdf,
Algorithms for Science Applications:
Homework #2 on Graph Algorithms,
Department of Scientific Computing,
Florida State University, Spring Semester 2011.
-
asa_2011_graphs_lab.pdf,
Algorithms for Science Applications:
Lab on Graph Algorithms,
Department of Scientific Computing,
Florida State University, Spring Semester 2011.
Licensing:
The computer code and data files described and made available on this web page
are distributed under
the GNU LGPL license.
Related Data and Programs:
ASA_2011_GEOMETRY
MATLAB programs which
were used during labs, demonstrations and lectures for the "Geometry Algorithms"
portion of the class "Algorithms for Science Applications II".
ASA_2011_IMAGES
MATLAB programs which
were used during labs, demonstrations and lectures for the "Image Algorithms"
portion of the class "Algorithms for Science Applications II".
DIJKSTRA
a MATLAB program which
runs a simple example of Dijkstra's minimum distance algorithm for graphs.
GRAFFITI
is a dataset directory which
contains 195 abstract graphs, with adjacency and embedding information,
stored in the GRF format.
GRAFPACK
is a FORTRAN90 library which
carries out operations on abstract graphs.
GRAPH_REPRESENTATION,
a data directory of examples which
representing abstract mathematical graphs in various ways.
GRAPH_REPRESENTATION,
a MATLAB library which
can express the representation of an abstract mathematical graph
in several ways.
GRF,
a data directory which
contains examples of GRF files,
an abstract graph file format, 2D graphics;
GRF_DISPLAY,
a MATLAB program which
reads a GRF file defining a mathematical graph and
displays it in the MATLAB graphics window.
GRF_DISPLAY_OPEN_GL,
a C++ program which
reads a GRF file defining a mathematical graph and
displays it in an OpenGL graphics window.
GRF_IO,
a MATLAB library which
reads or writes a GRF file;
SUBSET
is a MATLAB library which
enumerates combinations, partitions, subsets, index sets,
trees, and other combinatorial objects.
TABLE_GRAPH_CODE,
a FORTRAN90 program which
reads a TABLE file
representing the adjacency matrix of a graph, and computes the graph code.
Reference:
-
Edsger Dijkstra,
A note on two problems in connexion with graphs,
Numerische Mathematik,
Volume 1, 1959, pages 269-271.
-
Peter Eades, Ian Fogg, David Kelly,
SPREMB: A System for Developing Graph Algorithms,
Congressus Numerantium,
Volume 66, December 1988.
-
Alan Gibbons,
Algorithmic Graph Theory,
Cambridge University Press, 1985,
ISBN: 0-5212-8881-9,
LC: QA166.G53.
-
Joseph ORourke,
Computational Geometry in C,
Second Edition,
Cambridge, 1998,
ISBN: 0521649765,
LC: QA448.D38.
-
Stephen Skiena,
Implementing Discrete Mathematics:
Combinatorics and Graph Theory in Mathematica,
Addison Wesley, 1990.
-
Krishnaiyan Thulasiraman, M Swamy,
Graphs: Theory and Algorithms,
John Wiley, 1992,
ISBN: 0471513563,
LC: QA166.T58.
Source Code:
-
dfs_stack.m
carries out a depth-first search using a stack.
-
dfs_stack_test.m
uses dfs_stack to carry out a depth-first search.
-
disconnected.grf
a GRF description of the "disconnected" graph.
-
disconnected.png
a PNG image of the "disconnected" graph.
-
disconnected_edges.txt
the edge list for the disconnected graph.
-
disconnected_node_adjs.txt
the node-to-node adjacency matrix for the disconnected graph.
-
disconnected_node_labels.txt
the labels of the nodes for the disconnected graph.
-
disconnected_nodes.txt
the coordinates of the nodes for the disconnected graph.
-
mst.grf,
a GRF description of the MST (minimum spanning tree) graph.
-
mst.png,
a PNG image.
-
mst_edge_lengths.txt,
the edge lengths;
-
mst_edges.txt,
the edge list;
-
mst_node_adjs.txt,
the node-to_node adjacency matrix;
-
mst_node_dists.txt,
the node-to-node distance matrix;
-
mst_node_labels.txt,
the node labels;
-
mst_nodes.txt,
node coordinates.
-
museum.grf,
a GRF description of the museum graph;
-
museum.png,
a PNG image of the museum graph.
-
museum_adjacency_matrix.txt,
the adjacency matrix;
-
museum_adjacency_structure.txt,
the adjacency structure;
-
museum_edges.txt,
the edge list;
-
museum_incidence_matrix.txt,
the incidence matrix;
-
museum_node_coordinates.txt,
node coordinates.
-
museum_node_labels.txt,
node labels.
-
next_perm.m,
compute the "next" permutation.
-
next_perm_test.m,
test the next_perm function.
-
rand_int.m,
return a random integer between 1 and I.
-
rand_int2.m,
return a random integer between I1 and I2
-
rand_perm.m,
returns a random permutation of integers 1 to N.
-
rand_perm_test.m,
test the rand_perm function.
-
simple.grf,
a GRF file;
-
simple.png,
a PNG image.
-
simple_adjacency_matrix.txt,
the adjacency matrix for a simple graph.
-
simple_edges.txt,
the edge list;
-
simple_node_labels.txt,
node labels.
-
simple_nodes.txt,
node coordinates.
-
tsp.grf,
a GRF file;
-
tsp.png,
a PNG image.
-
tsp_brute.m,
a brute force approach to the Traveling Salesman problem.
-
tsp_node_adjs.txt,
the adjacency matrix;
-
tsp_node_dists.txt,
the distance matrix;
-
tsp_node_labels.txt,
node labels.
-
tsp_nodes.txt,
node coordinates.
Last modified on 28 July 2011.