Introduction

In 2009, as an undergraduate researcher, Amanda Olsen coded what was to be part of a Graph Theory Toolbox. Since there was none for Octave at the time, she coded a few good basic functions. Her work was basic upon the concept of using an adjacency matrix instead of an ordered pair. I was privileged to serve as her research advisor.

Paper

Ms. Olsen wrote in the context of airline travel in her paper octave_research_paper_ud.pdf. However, a version that was published in the LaGrange College undergraduate research publication Citation can be found here. This work relied upon Dr. Doug West’s “Introduction to Graph Theory”[1].

Octave Graph Theory Toolbox

Ms. Olsen coded the basic functions:

  • create_graph.m – Creates an adjacency matrix of input size n that is filled with zeros.
  • load_graph.m – This function takes an input the name of a .mat-file that contains an adjacency matrix and loads that file intro memory.
  • set_edge.m – This function takes as input the variable of the adjacency matrix and the two edges that are connected. Then, it sets that value as true.
  • shortest_path.m – This function takes a struct G with the necessary fields ‘adj’ and ‘label’ and two vertex labels str1 and str2. The function then formulates all paths from str1 to str2 found in the adjacency matrix in the field adj of the struct G. The output is the shortest path from str1 to str2.
  • complete_graph.m – This function file takes ones value, n, and creates an adjacency matrix for a complete graph on n vertices below the diagonal.

Download

Versions of the code can be found at:

A test graph can be found at test_graph.mat.

References

West, D. (2001). Introduction to graph theory (2nd ed.). Upper Saddle River, N.J.: Prentice Hall.

License

Creative Commons License
Octave Graph Theory Toolbox by Amanda Olsen and Jon Ernstberger is licensed under a Creative Commons Attribution 4.0 International License.

Octave Graph Theory Toolbox
Tagged on:         
%d bloggers like this: