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.
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”.
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.
Versions of the code can be found at:
A test graph can be found at test_graph.mat.
West, D. (2001). Introduction to graph theory (2nd ed.). Upper Saddle River, N.J.: Prentice Hall.
Octave Graph Theory Toolbox by Amanda Olsen and Jon Ernstberger is licensed under a Creative Commons Attribution 4.0 International License.