GraphView

I. – OVERVIEW

GraphView displays graphs that have from three to eight vertices. The program is comprised of three phases beginning with user input, followed by the processing of those input parameters, after which the desired graphs are displayed.

Input

The input phase asks the user to specify at least one parameter that will determine which graphs are displayed. Users can set the number of vertices in each graph, the number of edges in each graph, and the minimum degree of each graph, or any combination of these three (for clarification see section II. – EXAMPLES).

Processing

GraphView uses adjacency matrices to represent graphs. After the input phase, the necessary data is extracted from files to generate these matrices based on the user specified and/or default values for the number of vertices and the number of edges. An adjacency matrix is then built for each graph that satisfies the user query. If a minimum degree is specified, all graphs that do not satisfy the minimum degree requirement have their adjacency matrices removed. (Descriptions of the different data files can be found in section III. – FILE FORMATS).

Output

A display window is generated that may contain up to twenty graphs at a time. The adjacency matrix for each graph that will be displayed in the window is read and used to draw the vertices and edges for that graph. Labels including the number of vertices, the number of edges, and the degree sequence are also displayed with each graph. The graphs are numbered from 1 to the total number of graphs that satisfy the user query. This graph number is called graphnum and is shown with each graph. In the lower right hand corner of the display window navigational keyboard commands are printed which the user can use to switch between pages of graphs.

II. – EXAMPLES

A series of examples follow to explain the functionality of user inputs. These are specifically chosen to show the different ways the user can enter a query. There are, in fact, multiple ways to enter a query that will produce the same graphs. Neither method shown is significantly faster than another so the user may enter a query however they prefer. Example text in bold designates user entered text.

Example 1

Please enter the number of vertices: 6

Please enter the number of edges: 3

Please enter the minimum degree:

There are 5 graph(s) that satisfy vertex and edge constraints…

This query will generate all graphs containing six vertices and three edges. The default minimum degree is zero.

Example 2

Please enter the number of vertices:

Please enter the number of edges: 4

Please enter the minimum degree:

There are 38 graph(s) that satisfy vertex and edge constraints…

This query will generate every graph with four edges for the default range of vertices. The default range for vertices is three to eight.

Example 3

Please enter the number of vertices: 5

Please enter the number of edges:

Please enter the minimum degree:

There are 33 graph(s) that satisfy vertex and edge constraints…

This query will generate every graph with five vertices. The default range of edges is 1 to n*(n-1)/2 where n is the number of vertices. In this example the range of edges is from one to ten (5*4/2).

Example 4

Please enter the number of vertices: 4 6

Please enter the number of edges: 3 4

Please enter the minimum degree:

There are 12 graph(s) that satisfy vertex and edge constraints…

This query will generate graphs with four vertices and three edges. It will also generate graphs with six vertices and four edges. You can separate multiple values with a comma or a space. Notice that the user specified vertices and edges are paired; in this example four vertices is paired with three edges, and six vertices is paired with four edges.

Example 5

Please enter the number of vertices: 4:6

Please enter the number of edges: 3

Please enter the minimum degree:

There are 12 graph(s) that satisfy vertex and edge constraints…

This query will generate graphs that have four to six vertices and three edges. The colon indicates a range of values. It should also be noted that the range is treated as one vertex when pairing with edges.

Example 6

Please enter the number of vertices: 3 5 7

Please enter the number of edges: 4 5

Please enter the minimum degree: 1

There are 27 graph(s) that satisfy vertex and edge constraints…

There are no graphs with 3 vertices and 4 edges

16 graph(s) do(es) not satisfy the minimum degree constraint, 11 will be generated…

This query will generate graphs that have five or seven vertices, five edges, and a minimum degree of one. Notice that there are three values for the number of vertices and two values for the number of edges. When this happens the remaining number of vertices is paired with the last specified number of edges; in this example seven vertices is paired with five edges.

Example 7

Please enter the number of vertices: 3 5

Please enter the number of edges: 4 8 9

Please enter the minimum degree: 3

There are 3 graph(s) that satisfy vertex and edge constraints…

There are no graphs with 3 vertices and 4 edges

1 graph(s) do(es) not satisfy the minimum degree constraint,

2 will be generated…

This query will generate graphs that have five vertices, eight or nine edges, and a minimum degree of three. Notice that there are two values for the number of vertices and three values for the number of edges. When this happens the remaining number of edges is paired with the last specified number of vertices; in this example five vertices is paired with nine edges.

III. – FILE FORMATS

Explanations of the data file formats are provided below to facilitate modifications to code modules or new applications of these files. There are three different types of data files used by this program: six data files, one index file, and adjacency matrix files. Detailed explanations follow.

Data Files

Each data file represents the information needed to construct any graph of a given number of vertices. Each line in the file contains a string that contains the basic information needed to generate the adjacency matrix of a vertex/edge pair (VE-pair). The string starts with a letter that gives credit to those who provided the graphs. Earl Whitehead of the University of Pittsburg provided the graphs containing seven and eight vertices and is represented by a ‘w’. Frank Harary provided the graphs containing three to six vertices and is represented by an ‘h’. The letter is followed by two digits for the number of vertices and two digits for the number of edges. The next four digits are used to number the graphs within a VE-pair. The remaining digits are used to generate the graph’s adjacency matrix.

w07060005000001000010001001101

This line is from the file 7data. It corresponds to the fifth graph that has seven vertices and 6 edges.

At runtime, after query parameters have been established, an empty matrix called plotinfo is generated that has three columns and r rows where r is the total number of graphs that satisfy the user query. As each line is read from the data file(s) the number of vertices and the number of edges is extracted from the string, and placed into plotinfo in columns one and two respectively, in row graphnum (see Table 1).

plotinfo

…
graphnum	07	06	deg.seq.
…

Table 1 – The contents of row graphnum in the matrix plotinfo after adding the number of vertices and the number of edges extracted from the line from 7data, shown above.

NOTE: graphum and plotinfo are “one based” data types, meaning that they both begin counting at the number one; i.e. the first row in plotinfo is row 1.

The substring containing the adjacency matrix information is broken up and reassembled into an n-by-n matrix, where n is the number of vertices. The string is broken up into n-1 substrings, where the first substring is the first n-1 bits of the string, the second is the next n-2 bits, the third is the next n-3 bits, and so on.

000001000010001001101

000001 00001 0001 001 10 1

These n-1 substrings form the upper-right triangle of the matrix.

1 2 3 . . . n

1 0 0 0 0 0 1

2 0 0 0 0 1

3 0 0 0 1

. 0 0 1

. 1 0

. 1

n

The rest of the matrix is a reflection of this triangle with a diagonal of ‘0’s separating the two halves.

1 2 3 . . . n

1 0 0 0 0 0 0 1

2 0 0 0 0 0 0 1

3 0 0 0 0 0 0 1

. 0 0 0 0 0 0 1

. 0 0 0 0 0 1 0

. 0 0 0 0 1 0 1

n 1 1 1 1 0 1 0

Every ‘1’ represents an edge connecting two vertices. The adjacency matrix is stored into an Adjacency Matrix File (see below).

Index File

The first six lines of the index file are used as a meta-index, i.e. an index for the index. Each of these lines is a number that indicates the first line in the index file that contains an entry for a given vertex. For example, suppose the index is searched to find information about graphs with six vertices. The line number indicating the first entry with six edges is extracted from the meta-index. This allows the program to skip over entries for three, four, and five vertices to avoid needless searching.

The remaining lines in the file each contain four integers delimited by commas, and represent each VE-pair. The first number is the number of vertices and the second is the number of edges. The third number corresponds to the line in the data file that the first graph matching the VE-pair appears; NOTE: this number is “zero based”, meaning that it starts counting at zero; i.e. the first line in a data file is the zero-ith line. The fourth number represents the total number of graphs that match the VE-pair.

This file is used for two reasons. The first is to predetermine the number of graphs that will be generated by any given query. This feature has been implemented to alert the user that processing is taking place (especially useful when a query returns hundreds of graphs). The other reason to use an index file is to quicken the data file access time.

7,6,39,41

This is a line from the index file. It is the entry for graphs with seven vertices and six edges. These graphs begin at line 39 (zero-based) in the file 7data, and there are 41 graphs for this VE-pair.

Adjacency Matrix File

After each adjacency matrix is read from a data file, and processed into a complete n-by-n matrix, they are temporarily stored on disk. This is done to reduce the use of memory. The files are named grplot*, where * corresponds to the graph number (see section I. – OVERVIEW: Output for clarification) for the current query. After the program completes these files are deleted from the hard disk.

0,0,0,0,0,0,1

0,0,0,0,0,0,1

0,0,0,0,0,0,1

0,0,0,0,0,0,1

0,0,0,0,0,1,0

0,0,0,0,1,0,1

1,1,1,1,0,1,0

This is a sample adjacency matrix file.

IV. – PROGRAM INSTALLATION/EXECUTION

The system uses seven MATLAB files (.m extension), six data files and one index file. All files are included with the software package that you have received. A more complete description of the files follows.

The code is contained in the following files:

MATLAB Files	Size (kb)
degSeq.m	4
filterByDeg.m	4
graph.m	8
graphPage.m	4
graphPlot.m	8
makeAdjMat.m	4
str2num2cell.m	4

Table 1 – GraphView code files and their sizes

The data files and index are contained in the following files. A file *data contains all graphs with * vertices where 3 ≤ * ≤ 8.

Data Files	Size (kb)
3data	1
4data	4
5data	4
6data	4
7data	32
8data	464
index	4

Table 2 – GraphView data and index files and their sizes

In order to execute this program all of the files listed in Tables 1 & 2 must be copied into a directory on your hard disk. A total of The directory name chosen will not affect program execution. After the files are copied to the directory, start MATLAB. When running MATLAB, change the working directory to the location that you copied the files. At the MATLAB command prompt, simply type “graph” (omitting the quotation marks, but entirely lowercase) and GraphView will begin execution.

V. – PROGRAM DIAGRAM

Figure 1 – Execution tree for GraphView.

The execution tree pictured in Figure 1 reflects the interactions between each program module. Each directed arrow represents a function call; the caller is at the tail of the arrow and the invoked method lies at the arrow head. For example, during program execution the function degSeq is called by graph. Further understanding of each function and its calls can be accomplished by examining the MATLAB code of the function.

VI. – SYSTEMS NOTES

GraphView uses several functions that are included with the MATLAB package. A list follows that includes used function names, arguments, and brief descriptions of the function and its arguments. Many functions are overloaded. The following descriptions only contain function headers with the arguments used in GraphView. More detailed explanations can be obtained by using the MATLAB Help. The MATLAB functions used fall into four categories, System Calls, String Manipulation, Input/Ouput, and Graphics Functions.

System

1. syntax: clear obj;

pre: obj is an object in memory

post: obj is deleted from memory

2. syntax: delete filename;

pre: filename is a file in the current working directory

post: filename is deleted from the current working directory

3. syntax: n = length(X);

pre: X is an array

post: n is assigned the length of array X

4. syntax: c = cell(m,n);

pre: m & n are integers

post: an empty m by n cell array c is created

5. syntax: M = mod(X,Y);

pre: X & Y are integers

post: M is assigned the value of X mod Y

6. syntax: k = waitforbuttonpress;

pre: none

post: k is assigned a value of 0 until a button is pressed, when it is assigned a 1

String Manipulation

1. syntax: x = str2num(s);

pre: s is a string

post: x is assigned the integer value of s

2. syntax: k = strcmp(s1,s2);

pre: s1 & s2 are strings

post: k is assigned a 1 if s1 & s2 are equal, a 0 if not

3. syntax: str = num2str(A);

pre: A is an integer

post: str is the string value of A

4. syntax: t = strtok(s);

pre: s is a string

post: t is the first token of s, where tokens are delimited by the standard whitespace characters

5. syntax: S = strvcat(s1,s2,...,sn);

pre: s1,s2,...,sn are strings

post: S is the vertical concatenation of strings s1,s2,...,sn

6. syntax: c = cellstr(S)

pre: S is an array of strings

post: c is a cell array where each cell contains one string from S

Input/Output

1. pre: s is a string

post: s is displayed in the MATLAB console

syntax: fprintf(s);

s – a string

2. pre: s is a string

post: the prompt s is displayed in the MATLAB console, user_entry is assigned a string value of the carriage-return terminated user input

syntax: user_entry = input(s,’s’);

3. pre: ‘filename’ is a string contained in quotation marks, row & col are integers, range may be an array of four integers in the form [R1 C1 R2 C2] to specify the upper-left and lower-right corners of the matrix being read

post: M is a matrix with values starting at row & col in file ‘filename’

syntax: M = csvread(‘filename’,row,col);

or M = csvread(‘filename’,row,col,range);

4. pre: filename is a string, m & n are integers

post: M is a matrix containing values from the file filename, m lines are read beginning at line n, the delimiter between values is a carriage return

syntax: M = textread(filename,’%s’,m,’delimeter’,’\n’,’headerlines’,n);

5. pre: filename is a string, M is a matrix

post: M is written to file filename where each value in M is delimited by commas

syntax: csvwrite(filename,M);

6. pre: filename is a string, delimiter is a character

post: M is a matrix containing values from file filename, which is delimited by delimiter

syntax: M = dlmread(filename,delimiter);

Graphics Functions

1. syntax: a = get(h,’ScreenSize’);

pre: h is a handle to a graphics object, ‘ScreenSize’ is one of many graphics attributes

post: a is the value of the attribute for object h

2. syntax: set(h,’FontSize’,x);

pre: h is the handle of a graphics object, ‘FontSize’ is a parameter, x is an integer

post: the parameter is assigned the value of x

3. syntax: figure(‘Position’,SS);

pre: ‘Position’ is a parameter, SS is an array of four integers

post: a figure window is created with its size specified by the first two values of SS and its origin specified by the second two values of SS

4. syntax: subplot(m,n,p)

pre: m, n & p are integers

post: the active figure window is broken up into m by n sections, where the current section is the pth section

5. syntax: close all hidden;

pre: none

post: all graphics objects are closed

6. syntax: clf reset;

pre: none

post: the active figure window is cleared

7. syntax: text(x,y,str,...);

pre: x & y are integers, str is a string

post: str is displayed at position (x,y) of a graphics object, many other attributes can be defined to format the string

8. syntax: line(x,y,...);

pre: x & y are arrays of integers

post: a line is drawn connecting (x1,y1) to (x2,y2) to (xn,yn)

9. syntax: axis([xmin xmax ymin ymax]);

pre: xmin, xmax, ymin & ymax are integers

post: axis limits are defined from xmin to xmax and from ymin to ymax

A Note About Function Arguments

MATLAB does not have an operator to specify whether or not a function argument is passed by value or by reference. In order to pass by reference, the variable must be assigned the value of the function. For example:

x = f(x);

In all other cases function arguments are passed by value. Any modifications of a variable inside a function are local and will not affect variables outside of that function.