HYPERRING MAXFLOW TEST
by
Mohammad Alsaffar
B.S., University of Colorado at Denver, 2000
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Computer Science
2003
This thesis for the Masters of Science
degree by
Mohammad Alsaffar
has been approved
by
Mike Radenkovic
Alsaffar, Mohammad (M.S., Computer Science)
HyperRing MaxHow Test
Thesis directed by Professor Tom Altman
ABSTRACT
This thesis is based on papers written by Professor Tom Altman dealing with
HyperRings and a theory that emerged from them. An Nnode HyperRing (HR) is
an Nnode graph in which all the edges connect nodes that are at distances of powers
of two from each other. In other words a graph G = (Y, E), a set of edges and nodes,
is called an HR with Nnodes if V = {0, ...,N 1} andE = {{u, v} vu modulo Nis
a power of 2}. HyperRings have a property called nodeconnectivity; this is the
same as the degree of a HyperRing. The degree of an HR can be easily calculated by
counting the number of adjacent edges of any single node in an HR. All nodes will
have the same number of adjacent edges in an HR. The connectivity of an HR is
what determines the limits and to some extent the performance of any system it
represents, for example a computer network.
For now, lets talk about the Associated Network How (ANF) graph of an N
HR. This is a flow network graph created from the NHR. It has twice the number of
ui
nodes, 2N. The edges in it are directed. This directed representation of the HR is
used to compute the MF.
The Maximum Flow (MF) of this ANF graph is an important characteristic; it
is the actual bottleneck of parallel processing when using this HR computer network.
It is the maximum amount of data that can pass through the network at any given
time.
The theory that my thesis tests is that the degree of an NHR is equal to the
MF of its ANF graph. I also tested semi HyperRings (semiHR). It is important to
test the theory rigorously and with larger numbers. For my thesis I wrote a computer
program that allows this.
This abstract accurately represents the content of the candidates thesis. I recommend
its publication.
Signed
Tom Altman
IV
CONTENTS
Figures...................................................................x
Chapter
1. Introduction...........................................................1
2. Developer Requirements.................................................4
3. HighLevel Design.................................................... 9
4. Detailed LowLevel Design 1............................................5
5. Testing and Analysis..................................................26
5.1 Test 1.......................................................... 26
5.1.1 Description.......................................................26
5.1.2 Inputs............................................................27
5.1.3 Output............................................................27
5.1.4 Analysis..........................................................28
5.2 Test 2..............................................................29
5.2.1 Description.......................................................29
5.2.2 Inputs............................................................29
5.2.3 Output............................................................29
v
5.2.4 Analysis............................................................31
5.3 Test 3................................................................32
5.3.1 Description....................................................... 32
5.3.2 Inputs..............................................................32
5.3.3 Output..............................................................32
5.3.4 Analysis............................................................34
5.4 Test 4...............................................................33
5.4.1 Description.........................................................34
5.4.2 Inputs..............................................................34
5.4.3 Output..............................................................34
5.4.4 Analysis............................................................35
5.5 Test 5................................................................36
5.5.1 Description....................................................... 36
5.5.2 Inputs............................................................ 36
5.5.3 Output..............................................................36
5.5.4 Analysis............................................................38
5.6 Test 6................................................................38
5.6.1 Description.........................................................38
5.6.2 Inputs..............................................................38
5.6.3 Output..............................................................39
5.6.4 Analysis............................................................39
vi
5.7 Test 7.............................................................. 40
5.7.1 Description.........................................................40
5.7.2 Inputs..............................................................40
5.7.3 Output..............................................................40
5.7.4 Analysis............................................................42
5.8 Test 8.........................:......................................42
5.8.1 Description....................................................... 42
5.8.2 Inputs..............................................................43
5.8.3 Screen Output................................:......................43
5.8.4 File Output.........................................................43
5.8.5 Analysis............................................................44
5.9 Test 9................................................................44
5.9.1 Description.........................................................44
5.9.2 Inputs..............................................................44
5.9.3 Screen Output.......................................................44
5.9.4 File Output.........................................................45
5.9.5 Analysis............................................................46
5.10 Test 10.............................................................47
5.10.1 Description........................................................47
5.10.2 Inputs.............................................................47
5.10.3 Screen Output......................................................47
vii
5.10.4 Analysis.............................................................48
5.11 Test 11..............................................................48
5.11.1 Description.........................................................48
5.11.2 Inputs..............................................................48
5.11.3 Screen Output.......................................................48
5.11.4 Analysis............................................................49
5.12 Test 12..............................................................49
5.12.1 Description.........................................................49
5.12.2 Inputs..............................................................49
5.12.3 Screen Output.......................................................49
5.12.4 Analysis............................................................50
5.13 Test 13............................................................ 50
5.13.1 Description.........................................................50
5.13.2 Inputs..............................................................50
5.13.3 Screen Output.......................................................50
5.13.4 Analysis............................................................51
5.14 Test 14..............................................................51
5.14.1 Description.........................................................51
5.14.2 Inputs..............................................................51
5.14.3 Screen Output.......................................................51
5.14.4 Analysis............................................................52
Vlll
5.15 Test 15............................................................52
5.15.1 Description.......................................................52
5.15.2 Inputs............................................................52
5.15.3 Screen Output.....................................................52
5.15.4 Analysis..........................................................53
5.16 Further Testing....................................................53
6. Conclusion............................................................55
Appendix
A. Test Runs............................................................58
B. Program Code.........................................................60
References...............................................................98
IX
FIGURES
Figure
1. An example of an 11HR
,2
x
1. Introduction
A graph G = (V, E), a set of edges and nodes, is called an HR with N nodes if
Y = {0,N 1} andE = {{u, v} vu modulo N is a power of 2}. An HR with N
nodes is denoted as an NHR. A 3HR is a triangle. One easy way to understand
HRs is to construct a small one with say five nodes. Arrange the nodes in a circle and
number them clockwise zero to four. The first power of two is two to the power of
zero, which is one. So connect all the nodes at distances of one from each other.
This creates a pentagon. The second power of two is two to the power of one, which
is two. Now connect all the nodes at distances of two from each other. The third
power of two is two to the power of two, which is four. Now connect all the nodes at
distances of four from each other. The fourth power of two is two to the power of
three, which is eight. Since we have only five nodes we stop here. Note that in the
process, near the end you will find that you are trying to connect nodes that are
already connected.
HyperRings are used in two main fields, networking and parallel processing.
A computer network can be built using the HR design allowing for fast and
dependable communication. These HyperRing networks can then be used for
parallel computing. They are commonly used as the design for communication in
computer networks. An example of an 11HR is shown on the next page.
1
6 ?
Fig. 1. An example of an ilHR.
A Hyperring is basically used as a design for a communications system or
communication in a system. Then we are interested in such things as speed, limits
and boundaries, and bottlenecks.
This thesis deals with bottlenecks in a communication system or
communication in a system. My goal is to show that the nodeconnectivity of a
system built using the HR design is a measure of, or can be used to calculate, the
bottleneck of this system. The nodeconnectivity of an HR can easily be calculated
by counting the number of adjacent edges of any node in the hyper ring, since they all
have the same number. This is a property or characteristic of HRs. However, to find
the bottleneck we must construct an Associated Network How (ANF) graph of the
HR and then find its Maximum How (MF). Then we compare this MF to the node
connectivity to see if they are the same, if they are then our theory is right and the
goal accomplished. The main part of my thesis work was to right such a program to
test this easily for multiple HRs and HRs with a large number of nodes.
2
The creation of the ANF of a given HR is not complicated. The nodes are
doubled and for each undirected edge (u, v) in the NHR, four directed edges are
created in the ANF graph: (u, u), (u\ v), (v, v), and (v, u). In an HR based system
this ANF graph allows us to see all the communication lines. Or in other words it
helps us find the disjoint paths in the original HR. The MF of this ANF then is a little
more complicated to calculate, but the algorithms can easily be found in any
algorithms textbook.
In calculating the MF however, we specify a node in the ANF as the source
and another as the sink or destination node. The various choices of these can yield
different MFs so my program also tests all such possibilities. However, only half of
the HR or ANF has to be tested for these possibilities since the design is symmetric.
My program also allows one to see the result of using a semiHR. This can
easily be created by removing half of the nodes from a given HR and all their
adjacent edges.
3
2. Developer Requirements
This document will describe the requirements of the program from a
developers point of view. Once these requirements have been met the program is
complete. Before reading this document, one should read the abstract or introduction
for this project.
When the program is run it will first output to the screen a brief oneparagraph
description of its use and purpose. Or in other words it will describe what it does.
The program will then ask for a number of nodes from the user. It will tell the
user that the correct input is a number greater than or equal to three and greater than
or equal to 5 if a semi HyperRing (semiHR) is desired for testing. After this input is
received it will be tested to see if it is greater than or equal to three. If not, the
program will allow the user to enter the number of nodes again till he/she gets it right.
Then the user will be asked if he/she desires a semiHR, if the user chooses a
semiHR, the number of nodes will be tested to see if the user entered a number
greater than or equal to five. If the user did not, the program will let the user know
this and continue without using a semiHR.
Next the user is asked if he/she wants to see the paths taken in the Associated
Network Flow (ANF) graph of the HR or semiHR, when calculating its Maximum
Flow (MF). Then the user will be asked if he would like the output sent to a file.
The user is then given a choice, two choices in the case of an HR, and three
4
choices in the case of a semiHR. These are test choices, that is, what type of
test the user would like to run. In both cases the first two choices are the same.
Choice number one is to run multiple MaxFlows with the sink going from 0 to
ceil(N/2) in the HR. The source must be a double prime node in the ANF and will be
defaulted to 0". In the case of a SemiHR, the sink is always the last node in the
SemiHR, which is removed after each mn, till only 2 nodes are left. The second
choice is to run one max flow where the user chooses the source and the sink. If the
user chooses this choice he/ she will be asked for the source and the sink and will be
given the valid inputs for both. The user will choose nodes from the HR or semiHR,
not from the ANF. If the user enters an invalid node for either the source or the sink,
he/she will be asked to enter it again till he/she gets it right. The third choice will
only be given in the case of a semiHR. This choice will allow the user to run
automatically multiple Maximum Hows with all possible combinations of sources
and sinks.
The above takes care of all the inputs the user will be allowed to make except
at the end the user will be allowed to run the program again and all stored data will be
reinitialized. From now on, in this document, if something is said to be output, it will
be output to either the screen or to a file depending on what the user chose. In the
case of a file the file will exist in the same directory as the program itself and it will
be named HR_MF_output.txt. Also this file will need to be deleted, renamed, or
5
moved by the user if he/she wishes to output to a file again, otherwise an error will be
output to the screen and the output will be sent to the screen as well.
Now lets discuss calculations and the generating of the graphs. In the case of
a semiHR or HR, an HR must still be created and the number of nodes it has along
with its degree will be printed to the screen. If a semiHR is chosen after the HR is
created a semiHR will be created from the HR by slicing it into two. If the HR has
an even number of nodes the semiHR will have exactly half of them. If the HR has
an odd number of nodes, say N, the semiHR will have (N + 1) / 2 number of nodes.
Also if a semiHR is being used the program will output that it has generated a semi
HR with the number of nodes in it. It will not output the degree of the semiHR, as
this is a flawed concept, a semiHR could have different degrees for its nodes. In
testing these we compare a MF of the ANF to the degree of the source and sink
mapped back to the semiHR.
After the HR or semiHR have been generated the ANF of the HR or semiHR
has to be generated, having double the number of nodes. No information about this
has to be printed to the screen.
Now for the actual testing. If the user chooses choice number one, that is, to
run multiple MaxHows with the sink going from 0 to ceil(N/2) in the HR. The
source must be a double prime node in the ANF and will be defaulted to 0". In the
case of a SemiHR, the sink is always the last node in the SemiHR, which is
removed after each testing loop ran, till only 2 nodes are left. The description of the
6
choice is exactly what the program needs to do. If the user chose to see the paths
used when calculating the MFs, all paths will be printed for each MF, one on each
line. At the end of each MF, the program will output the result telling the user what
the MF was and what the HR degree was. If the user didnt ask for the paths only the
result of each MF will be output. At the end the user will be told whether the HR
degree was equal to the MF in all cases or not, and this result will not be sent to a file
if file output is chosen. This will not be done in the case of a semiHR, because it
doesnt make sense. Also in the case of a semiHR the result of each MF will give
the MF, the sources degree, and the sinks degree. Lastly all paths will start from 0
this is always the source for this choice, and the rest of the nodes in the path will be
mapped back to the HR or semiHR, before being output.
If the user chooses choice number two, after getting a valid source and sink
from the user, the MF will be run and result output along with the path if the user
asked for it.
The format for this is the same as in choice one, except there is only one MF.
If the user chooses choice number three, which will only be given in the case
of a semiHR. The program will calculate all MFs using all combinations of sources
and sinks, outputting the result as discussed for choice one, for each MF. Also the
paths will also be output if the user asked for them for each MF as in choice number
one.
7
At the end of the test the user will be given the time it took for the HR
generation, ANF generation, and calculation of MF(s). This will not be output to a
file if the user chose file output. If the user did choose file output though, after the
times are output to the screen, the user will be told that the rest of the output is stored
in the file HR_MF_output.txt.
Lastly the user will be given a choice to run the program again and all stored
data will be reinitialized.
It is also required that the program run under Windows 98, 2000, and ME.
Also the program is not required to optimized for speed or memory space, it just
needs to be able to run the test and meet the above requirements.
8
3. HighLevel Design
This document will describe the user interface and give a birds eye view of
the program codes design. The source of this document the from the Developer
Requirements document, which should be read before reading this.
Ive decided it is best to take all the input up front from the user by calling a
single function in the main part of the program. First a short paragraph will be output
describing the program, something like the following.
This program takes as user input a positive number.
This number, say N, is used to create a NHyperRing,
(NHR) whose degree/nconnectivity, is calculated as it
is created. The Associative Network How (ANF) of this
NHR is then created, and its Maximum How (MF) from a
user provided source (s) and sink (t) is then found.
You can also choose to run multiple MFs going from the
1st s to multiple ts till N/2 since the HR is symmetric.
The purpose is to prove that this MF of the ANF graph is
equal to the degree/nconnectivity of the NHR. You may
also choose to use a semiHR instead, computed from the
original one. The input is taken upfront below.
Now I ask the user to enter the number of nodes outputting to the screen the
following.
Enter a +ve number >= 3, for the # of nodes in the HR, >= 5 for a semiHR:
Then I ask the user if he/she wants a semiHR as follows.
Do you want use a semiHR instead (y or n):
Then I ask the user if he/she wants to see the MF paths as follows.
9
Would you like to see the paths produced in calculating the MaxFlow; these
paths will be shown from the HR. ('y' or 'n'):
Then I ask the user if he/she would like the output directed to a file as follows.
Would you like to send the output to a file, ('y' or 'n'):
Then I ask the user for the type of test he/she would like to run, there will be two
choices, plus a third one will be given in the case of a semiHR. The first two are as
follows.
1. Run multiple MaxHows with the sink going
from 0 to ceil(N/2) in the HR. The source must
be a double prime node in the ANF and will be
defaulted to 0". In the case of a SemiHR, the
sink is always the last node in the SemiHR, which
is removed after each run, till only 2 nodes are
left.
2. Run one MaxHow choosing your own source and sink.
The third one in the case of a semiHR will be as follows.
3. Run multiple MaxHows with all combinations
of sources and sinks. For SemiHRs only.
Now all the input has been taken from the user and it is time to do the calculations
and output the result. No mater what the choices the first thing that is done is that an
HR is generated.
To generate the Hyper Ring I simply add edges to the graph between nodes
that are at distances of powers of two from each other. After the HR is generated, I
will output to the screen or to a file, whichever the user chose, a statement like the
following.
A Hyper Ring (HR) with x nodes has been generated, and has a degree of y.
10
Where x is the number of nodes the user chose and that have been used to create the
HR and y is the degree of the HR. The degree will be calculated while building the
HR.
If a semiHR is required I will slice the HR in half to create it and output to
the screen a statement like the following.
A semi HyperRing (semiHR) with x nodes has been generated.
Where x is the number of nodes in the semiHR.
Next the ANF of the HR or semiHR will be generated by doubling the nodes.
I will discuss this generation in the detailed design. However it is important to say
here that each node in the HR or semiHR, say x, will result in two nodes in the ANF,
x (x prime) and x (x double prime). Also the interface with the user, will, for the
most part, ignore the double primes since they dont exist in the HR or semiHR.
Nothing needs to be output to the screen for the ANF generation.
Now it is time to run the test. If test choice number one is chosen and an HR
is chosen instead of a semiHR, the test will be run as follows. Multiple MFs will be
run, the source will always be 0 (zero double prime) in the ANF. The sinks will be
all the single primes in the ANF or all the nodes that exist in the HR, starting from O
to the ceiling of N/2 where N is the number of nodes in the HR. If the user chose to
see the paths, then for each MF run, each path will be output to the screen or to a file
on a separate line. The path will always start at 0 and all other nodes output in the
path will be nodes from the original HR. The last node will obviously be the sink for
11
that MF, for each path. So the user will know what the source and sink were for each
MF. At the end of each MF, whether or not the user wanted to see the paths or not, a
statement like the following will be output.
The Maximum Flow of the ANF graph of the xHR is y.
Where x is the degree of the HR and y is the MF of the ANF of the xHR. For the
test to be successful in proving the theory, x must be equal to y. The program will
keep track of the results of each MF and at the end, output whether the MF was the
same as the HR degree in all tests, or not.
In the case of a semiHR for choice one, everything will be the same as
described in the above paragraph, except for a few changes. For a MF calculation,
the sink will always be the last node in the semiHR mapped to the ANF, which will
be removed after the MF, till there are only two nodes left. The result output after
each MF will be different than that for an HR, it will look like the following.
The MF of the ANF of the semiHR with sdeg x and tdeg y is z.
Where x is the degree of the semiHRs source, and y is the degree of the semiHRs
sink, for the current MF, whose value was calculated to be z. Also, since the degrees
of the nodes in the semiHR can be different, we dont keep track of whether the MF
was the same as the degree or not, and thus no such result has to be output after all the
MFs are run.
Now lets move on to the next test choice. Here the user chooses a source and
a sink. He/she will be given the valid values to choose from in the following manner.
12
Nodes in the (Semi)HR are going to be xy.
Enter the (Semi)HR node X whose corresponding X" in
the ANF is going to be used as the source for
the MF of the ANF graph:
Where x is always going to be 0 and y is going to be N 1, such that N is the number
of nodes in the HR or semiHR. If the user makes an invalid choice, he/she will be
asked to enter the source again, till a valid input is entered. A similar statement for
the sink will also be output and the user will enter the sink as well. Then the
computations will be done and all the output sent to the screen or to a file just like in
choice number one, except there will only be a single MF run, instead of multiple
ones.
The third test choice only applies to semiHR, and will only be given to the
user if he/she chose to use a semiHR. The output and computations are the same as
in choice number one with one major difference. We will be dealing with a semiHR
and all possible combinations of sources and sinks will be used to compute MFs. No
node will be removed from the semiHR.
No matter which test choice the user makes, during the computations, times
taken will be stored. Then after the test is complete the times will be output to the
screen for the HR generation, ANF generation and MF computation(s). These times
will be in seconds accurate to six decimal places. The times will only be accurate in
Windows. The program may be compiled for another operating system like Unix or
Linux, and may work fine, but the timing functions I use may work differently on
these systems. Ive run into this problem in the past. However, the program is
13
required to run in Windows only, so I will make sure they are accurate in Windows.
Also this output of times will not be output to a file if the user chose file output it will
only be output to the screen.
At this point in the program all dynamic data will be returned to the heap and
all variables will be reinitialized and the user will be asked if he/she wants to run
another test.
I have decided to use C++ as the programming language for this project, since
Im more familiar with it than any other. The Detailed Design document will give
further details about the actual code of the program.
14
4. Detailed LowLevel Design
This document will give details about the actual coding of the program. The
source for it is the Developer Requirements and HighLevel Design documents,
which should be read before reading this document. In these documents Ive
discussed, in its entirety, the user interface. All the outputs to the screen or to a file,
all the inputs the user will give. Ive also mentioned all the computations that need to
be made and the outputs that will result from these. Ive also stated that I will use
C++ as the programming language for this project.
I will store all graphs in a data structure. These graphs will include an HR, a
semiHR, and an ANF graph at the least. This structure will have the following data
in it.
int *wce; // Pointer to an array for weighted capacity edges.
int *flow; //To keep track edge flow, forward and backward.
int wce_sz; // Number of elements in array wee.
int flow_sz; // Number of elements in array flow = wce_sz 2.
int Vno; // Number of vertices.
int HRdeg; // The degree/connectivity of an HR graph.
int s; // Source.
int t; // Sink/destination.
No functions will be needed for this structure. *wce is a pointer for weighted
capacity edges in the graph. The edges of a graph will be stored here, each three
entries in this array will represent an edge, starting from index 0. The first one will
be a node, the second a node as well, between these nodes is the edge whose capacity
15
is in the third entry. The edges may be directed as in the ANF or undirected as in the
HR or semiHR. To show a directed edge (u, v) u will be stored in the first index and
v in the second for each edge. The number of elements in this array will be three
times the number of edges in the graph, and this number will be stored in wce_sz.
If there is no capacity or weight on an edge the third index will be 1, for each edge.
*flow is a pointer to another edge array, which keeps track of the forward and
backward flow of each edge in the graph. For each directed edge in the graph there
will be six entries in this array, starting from index 0. For a directed edge (u, v), the
first entry is u, second is v, and the third is the forward flow capacity of the edge.
The fourth entry is v, fifth u, and the sixth is the backward flow capacity of the edge.
This will only be needed for calculating a MF on an ANF. The size of this array will
thus be twice that of the wee array and will be stored in flow_sz. Vno is the
number of nodes in the graph. HRdeg is the degree if the graph is an HR. s and
t are the source and sink, respectively, for a single MF at any time in the execution
of the program. Any values that are not being used at any time in the execution of the
program should be set to 1 or NULL depending on the valid values. If 0 is a valid
value 1 should be used, otherwise NULL should be used.
Now that weve got our data structure in place lets move on and discuss the
design of the code from within main. First I will need to get all the input up front
from the user, this will be done by a function called get_input. It will take the
16
following parameters passed by reference and will return the number of nodes for the
HR.
graph& ANF
int& RandomMF
int& show_paths
int& outfile
int& semi
int& SemiAll
ANF is an instance of the graph structure. The number of nodes will be stored in
ANF.Vno when input from the user, and if the user chose to enter a source and sink
ANF.s and ANF.t will also be updated. If the user chooses test choice one
RandomMF will be set to TRUE (1), if not it will be set to FALSE(O). Similarly
show_paths will be set to TRUE if the user chose to see the paths during MF
calculation(s) or FALSE if not. In the same way, outfile is for file output, semi is
for a semiHR, and SemiAll is for test choice number three. Note that if
RandomMF is FALSE and SemiAll is false the user has chosen to enter the
source and sink for a single MF test, that is he/she has chosen choice number two, at
the end of this function.
Now in the main part of the program if the user chose not to use a semiHR, I
call a function named HR_MF_Test which takes the following parameters.
int &nodes
int outfile
graph &ANF
int randomMF
int show_paths
17
nodes is the number of nodes in the graph. All the rest have been discussed above.
In this function I am dealing with an HR and a semiHR is not needed. I first run a
function called HR_generator to generate an HR, and output its result as well as
keep track of how long it took. Then I call a function named ANF_generator and
output its result as well as keep track of how long it took. Then I call the function
named max_flow_ff to calculate the MF. If randomMF is true I call this function
in a loop with the source remaining as 0 in the ANF, and the sink going from 0 to
all single prime nodes in the ANF till N/2, where N is the number of nodes in the
graph. Also before each call to this MF function I must call a function named
fixANFmulti to restore the ANF before computing the next MF. If randomMF is
false then I simply call max_flow_ff once. For each call to max_flow_ff, I
output its result. I also keep track of the time taken for calculating the MF(s) here.
At the end of HR_MF_Test, I output the result if multiple MFs were run, whether
the test was successful or not. Then I output the times taken as described in the High
Level Design.
I will discuss all the functions I mentioned in the above paragraph later, but to
keep track of them heres a list.
HR_generator
ANF_generator
Max_flow_ff
FixANFmulti
18
Now lets return to the main part of the program, before we werent using a semiHR,
if we are and the test choice is two I will call a function named
Semi_HR_MF_Test. This function will take the following parameters.
int &nodes
int outfile
graph &ANF
int randomMF
int show_paths
Each of these parameters have been discussed above. This function is exactly like
HR_MF_Test discussed in the above paragraph with a few changes. Since we are
dealing with a semiHR, a function called semi_HR_generator will be called after
the HR is generated. If the user chose choice number one, that is randomMF is
TRUE, then multiple MFs will be computed with the source staying at 0 and the
sink being the last single prime node in the ANF, removing the node after each MF
computation. Before each call to max_flow_ff, fixANF will be called instead of
fixANFmulti, which was used in HR_MF_Test. The reason for this will be
discussed later. Another difference is that after each call to max_flow_ff,
fixSemiHR will be called to remove the last node and ANF_generator will be
called to generate the ANF again for the next MF computation. Also no end result is
output like in HR_MF_Test.
I will discuss the functions mentioned above later, but I will add them to the
following list to keep track..
HR_generator
ANF_generator
19
max_flow_ff
fixANFmulti
semi_HR_generator
fixANF
fixSemiHR
Now lets return to the main part of the program and here weve dealt with test choice
number one and two. However, if the user chose a semiHR and choice number three
a function called Semi_HR_MF_Test_All will be invoked. This function will take
the following parameters.
int& nodes
int outfile
graph& ANF
These have been discussed above. This function is just like HR_MF_Test except it
calls semi_HR_generator after the HR is generated and it calculates multiple MFs
only with all possible combinations of sources and sinks from, sources must be
double prime nodes in the ANF and sinks must be single prime nodes in the ANF.
Also no end result is output like in HR_MF_Test.
Now once again returning to the main part of the program for the last time.
The testing is now complete, all dynamic memory is returned to the heap and all
variables and data are reinitialized. Then the user is asked if he wants to run the
program again, if so loop around, otherwise exit.
It is time to discuss now the different functions mentioned above but not
discussed yet, the list is as follows.
HR_generator
ANF generator
20
max_flow_ff
fixANFmulti
fixANF
fixSemiHR
semi_HR_generator
HR_generator generates a hyper ring and stores it in an instance of the graph
structure. It takes the following parameters.
graph& HR
const int nodes
HR is an instance of the graph structure, which at the start of this function gets
initialized, nodes is the number of nodes in the graph to be generated, well call
these N. To add the nodes to the graph we simply make HR.Vno equal to N. To add
the edges we add an edge between two nodes if they are at distances of powers of two
from each other. We also calculate the HR degree as we build the HR. The
following is the pseudocode for this function.
For each power of two, x, starting from two to the power of 0, till x > (N 1)
For each node, y, starting from 0 to N 1
z = y + x
If edge (y, z) is not in the HR
Add (y, z) to the HR
If y = 0
HRdegree++
At the end the variable HR.HRdeg is set and returned.
Now the next function on the list is the ANF_generator. This function takes
the following as parameters.
graph& ANF
const graph& HR
21
ANF will be filled by this function and the HR will be used to do this. HR
may be an HR or a semiHR, in either case the generation of the ANF is the same.
The nodes will double and for each undirected edge (u, v) in the HR the ANF will
have four directed weighted capacity edges with capacity N to the power 2: (u\ u),
(u, v), (v\ v), and (v, v). The pseudocode is as follows.
ANF.Vno = HR.Vno 2
For each edge in HR (u, v)
Add the edges (u\ u), (u\ v), (v\ v), and (v\ v) if they dont
already exist.
Nothing is returned by this function.
The next function on our list of functions left to discuss is max_flow_ff.
This function takes as parameters the following.
graph& G
int show_paths
int outfile
This function may need to output the paths for MF and checks to see if it does by
show_paths. It checks to see if we need to output to a file or to the screen with
outfile. G is just the graph on which the MF will be calculated, in our case it will
be the ANF of an HR or semiHR. The pseudocode for this function is as follows.
For each edge (u, v) in G
Set the flow in G.flow of (u, v) to 0
Set the flow in G.flow of (v, u) to 0
While there exists a path p from s to t in the residual network G(f)
c(p) = minimum capacity in p
for each edge (u, v) in p
Set the flow in G.flow of (u, v) to its previous value + c(p)
Set the flow in G.flow of (v, u) to its previous value 1.
If show_paths = TRUE
22
If outfile = TRUE
Output p to file HR_MF_Output.txt
Else
Output p to the screen.
The MF is returned by this function. This is the Ford Fulkerson algorithm for
computing MF.
The next function on our list of functions remaining to be discussed is
fixANFmulti. This function is quite simple, it is used before running another MF in
HR_MF_Test and Semi_HR_MF_Test_All. It is needed to reset the capacity on
the edge from the source to the old sink, back to what it was; and set the capacity on
the edge from the source to the new sink to 1.
The next function on the list is fixANF. This simply sets the capacity on the
edge from the source to the sink to 1. It is used by Semi_HR_MF_Test. Here,
either only one MF needs to be run, or if multiples need be run, the old sink is
removed from the graph anyways, along with all its adjacent edges.
The next function on this list is fixSemiHR. This function is responsible for
removing the old sink and all its adjacent edges from the current semiHR after a MF
has been run, when dealing with test choice one, in function Semi_HR_MF__Test.
It simply goes through all the edged removing those that are adjacent to the last node
and then removes the last node. Note that the last node is the old sink.
The last function left to discuss on the list is semi_HR_generator. It creates
a semiHR by slicing the old HR in half. It takes the following parameters.
graph& HR
23
int& nodes
The pseudocode is as follows.
If nodes is even.
nodes = nodes / 2;
else
nodes = (nodes / 2) + 1;
HR.Vno = nodes
For each edge (u, v) in HR
If u < HR.Vno and v < HR.Vno
Keep edge (u, v) in the semiHR
Else
Toss edge (u, v)
At the end of this function HR is now a semiHR.
Now weve discussed all the main functions of the program, the main
variables, and the graph data structure as well. There is one helper function, however,
that I should discuss, that is BFS. This function will run a BreadthFirst Search
(BFS) on the ANF in the max_flow_ff function to retrieve a new path, if any is
remaining. This is a very common algorithm in Computer Science, so I wont go into
the details about it. I will say however that it does use a queue, which I will program
as a class in the files BFSqueue.h and BFSqueue.cpp. Other than these two files
there will be only one other file for the program, named HRMF_test.cpp, which
will contain everything else.
Lastly I would like to mention here that this program will not be coded using
the ObjectOriented Paradigm (OOP) offered by C++, except in the case of the BFS
queue. If I use OOP with classes there will be a lot of inheritance and abstraction,
this would cause the resulting executable to take up more time and space. Since I am
24
not optimizing the code for time and space I dont want to even less efficient. But
more importantly one other reason is that initially the project was small and I didnt
start with the OOP because it wasnt really needed. Now it has grown enough to be
able to use OOP effectively, due to additional requirements, but Ive run out of time
to change everything now.
25
5. Testing And Analysis
In this document I will run several tests on the completed and final version of
the program and analyze the results. Ive already done this several times in the course
of writing the program, but this will be an official document of testing. For each test
I will first give a brief description of what I am testing along with all the inputs that
will be given to the program for the different options. After this youll see an actual
output of the program and then I will analyze the results. There will be a progression
between the tests, which will be maintained in the description and analysis of each
test. All the input is taken up front, so I will include the complete input reception part
of the program output only in the first test, since it will be the same for all the others.
Before reading this document one should read at least the Abstract document to gain
an understanding of the program and the terms I will use.
5.1 Test 1
5.1.1 Description
For this test I will first try to enter a negative one for the number of nodes in
the HR, then a zero, then a 2. In all cases the program should simply ask me to re
enter, then I will enter the lower boundary value of nodes for an HR, which is 3, and
run the test. So I am testing the lower boundary value and invalid inputs for the
number of nodes.
26
5.1.2 Inputs
Nodes: 1,0,2, and then 3.
Semi HR: No.
Show paths: No.
Output to file: No.
Test choice: 1.
Another test: No.
5.1.3 Output
This program takes as user input a positive number.
This number, say N, is used to create a NHyperRing,
(NHR) whose degree/nconnectivity, is calculated as it
is created. The Associative Network Row (ANF) of this
NHR is then created, and its Maximum How (MF) from a
user provided source (s) and sink (t) is then found.
You can also choose to run multiple MFs going from the
1st s to multiple ts till N/2 since the HR is symetric.
The purpose is to prove that this MF of the ANF graph is
equal to the degree/nconnectivity of the NHR. You may
also choose to use a semiHR instead, computed from the
original one. The input is taken upfront below.
Enter a +ve number >= 3, for the # of nodes in the HR, >=
Enter a +ve number >= 3, for the # of nodes in the HR, >=
Enter a +ve number >= 3, for the # of nodes in the HR, >=
Enter a +ve number >= 3, for the # of nodes in the HR, >=
Do you want use a semiHR instead (y or n): n
Would you like to see the paths produced in
calculating the MaxRow; these paths will be shown
from the HR. ('y' or n'): n
Would you like to send the output to a file, ('y' or 'n'): n
Choose from the following.
for a semiHR: 1
for a semiHR: 0
for a semiHR: 2
for a semiHR: 3
27
1. Run multiple MaxFlows with the sink going
from 0 to ceil(N/2) in the HR. The source must
be a double prime node in the ANF and will be
defaulted to 0". In the case of a SemiHR, the
sink is always the last node in the SemiHR, which
is removed after each run, till only 2 nodes are
left.
2. Run one MaxFlow choosing your own source and sink.
choice: 1
A Hyper Ring (HR) with 3 nodes has been generated, and has a degree of 2.
The Maximum Flow of the ANF graph of the 2HR is 2.
The Maximum Flow of the ANF graph of the 2HR is 2.
HRdegree, 2 = MF in test(s).
TIMES (Only accurate in Windows!)
Hyper Ring Generator took: 0.000000 sec
Associated Network Flow Generator took: 0.000000 sec
Maximum Flow Computation took: 0.000000 sec
Would you like to run another test, (y or n): n
5.1.4 Analysis
This test shows the program doesnt allow numbers less than three to be
entered for the number of nodes in the HR. It also runs the test successfully with the
28
correct results for a three node HR. The HR degree was equal to the two MFs that
were calculated. I did the entire procedure on paper to make sure the output was
correct.
5.2 Test 2
5.2.1 Description
Now Ive tested invalid entries for the number of nodes, and the lowest valid
entry. Im now going to test with the lowest number still but changing one of the
other options this time, Im going to choose to see the paths also I will first enter a
negative one for the test choice then a zero, then a three, and then a one. This will
test invalid test choice entries, the program should just ask for input again.
5.2.2 Inputs
Nodes: 3.
Semi HR: No.
Show paths: Yes.
Output to file: No.
Test choice: 1,0, 3, and then 1.
Another test: No.
5.2.3 Output
Choose from the following.
1. Run multiple MaxHows with the sink going
from 0 to ceil(N/2) in the HR. The source must
be a double prime node in the ANF and will be
defaulted to 0". In the case of a SemiHR, the
sink is always the last node in the SemiHR, which
is removed after each run, till only 2 nodes are
left.
2. Run one MaxHow choosing your own source and sink.
29
choice: 1
Choose from the following.
1. Run multiple MaxHows with the sink going
from 0 to ceil(N/2) in the HR. The source must
be a double prime node in the ANF and will be
defaulted to 0". In the case of a SemiHR, the
sink is always the last node in the SemiHR, which
is removed after each run, till only 2 nodes are
left.
2. Run one MaxHow choosing your own source and sink
choice: 0
Choose from the following.
1. Run multiple MaxHows with the sink going
from 0 to ceil(N/2) in the HR. The source must
be a double prime node in the ANF and will be
defaulted to 0". In the case of a SemiHR, the
sink is always the last node in the SemiHR, which
is removed after each run, till only 2 nodes are
left.
2. Run one MaxHow choosing your own source and sink
choice: 3
Choose from the following.
1. Run multiple MaxHows with the sink going
from 0 to ceil(N/2) in the HR. The source must
be a double prime node in the ANF and will be
30
defaulted to 0". In the case of a SemiHR, the
sink is always the last node in the SemiHR, which
is removed after each run, till only 2 nodes are
left.
2. Run one MaxFlow choosing your own source and sink,
choice: 1
A Hyper Ring (HR) with 3 nodes has been generated, and has a degree of 2.
0"~>1~>0
0">2>0
The Maximum How of the ANF graph of the 2HR is 2.
0"~>1
0">2>l
The Maximum How of the ANF graph of the 2HR is 2.
HRdegree, 2 = MF in test(s).
TIMES (Only accurate in Windows!)
Hyper Ring Generator took: 0.000000 sec
Associated Network How Generator took: 0.000000 sec
Maximum How Computation took: 0.000000 sec
Would you like to run another test, (y or n): n
5.2.4 Analysis
This test shows the program doesnt allow numbers less than one or greater
than two to be entered for the test choice. It also runs the test successfully outputting
31
the paths for each of the two MFs. The paths are output in the correct format. The
HR degree was equal to the two MFs that were calculated. I did the entire procedure
on paper to make sure the output was correct.
5.3 Test 3
5.3.1 Description
Im going to test with the lowest number still but with changing one of the
other options this time, again, Im going to choose to output to a file without showing
the paths. Also I will try to choose a semiHR. This will test an invalid semiHR; the
program should just say that a semiHR cannot be used since there are less than five
nodes in the HR and continue.
5.3.2 Inputs
Nodes: 3.
Semi HR: Yes.
Show paths: No.
Output to file: Yes.
Test choice: 1.
Another test: No.
5.3.3 Output
Do you want use a semiHR instead (y or n): y
Sorry, you entered a number of nodes < 5! Continuing with full HR.
Would you like to see the paths produced in
calculating the MaxHow; these paths will be shown
from the HR. ('y' or 'n'): n
Would you like to send the output to a file, ('y' or 'n'): y
32
Choose from the following.
1. Run multiple MaxFlows with the sink going
from 0 to ceil(N/2) in the HR. The source must
be a double prime node in the ANF and will be
defaulted to 0". In the case of a SemiHR, the
sink is always the last node in the SemiHR, which
is removed after each run, till only 2 nodes are
left.
2. Run one MaxFlow choosing your own source and sink.
choice: 1
HRdegree, 2 = MF in test(s).
TIMES (Only accurate in Windows!)
Hyper Ring Generator took: 0.000000 sec
Associated Network Flow Generator took: 0.000000 sec
Maximum Flow Computation took: 0.000000 sec
Rest of the output stored in HR_MF_output.txt
Would you like to run another test, (yorn): n
5.3.4 Analysis
This test shows the program doesnt allow a semiHR with only three nodes
for the HR. It also runs the test successfully creating a file and sending the output to
it. The HR degree was equal to the two MFs that were calculated. I did the entire
procedure on paper to make sure the output was correct. The following is the
contents of the file created.
33
A Hyper Ring (HR) with 3 nodes has been generated, and has a degree of 2.
The Maximum How of the ANF graph of the 2HR is 2.
The Maximum How of the ANF graph of the 2HR is 2.
5.4 Test 4
5.4.1 Description
This test will be exactly the same as the last one, except Im going to use four
nodes and Im going to show the paths this time.
5.4.2 Inputs
Nodes: 5.
Semi HR: Yes.
Show paths: Yes.
Output to file: Yes.
Test choice: 1.
Another test: No.
5.4.3 Output
Do you want use a semiHR instead (y or n): y
Sorry, you entered a number of nodes < 5! Continuing with full HR.
Would you like to see the paths produced in
calculating the MaxHow; these paths will be shown
from the HR. ('y' or 'n'): y
Would you like to send the output to a file, ('y' or 'n'): y
Choose from the following.
34
1. Run multiple MaxFlows with the sink going
from 0 to ceil(N/2) in the HR. The source must
be a double prime node in the ANF and will be
defaulted to 0". In the case of a SemiHR, the
sink is always the last node in the SemiHR, which
is removed after each run, till only 2 nodes are
left.
2. Run one MaxFlow choosing your own source and sink.
choice: 1
HRdegree, 2 = MF in test(s).
TIMES (Only accurate in Windows!)
Hyper Ring Generator took: 0.000000 sec
Associated Network Flow Generator took: 0.000000 sec
Maximum Flow Computation took: 0.000000 sec
Rest of the output stored in HR_MF_output.txt
Would you like to run another test, (y or n): n
5.4.4 Analysis
This test shows the program doesnt allow a semiHR with only four nodes for
the HR. It also runs the test successfully creating a file and sending the output to it.
The paths are output in the correct format. The HR degree was equal to the two MFs
that were calculated. I did the entire procedure on paper to make sure the output was
correct. The following are the contents of the file created.
A Hyper Ring (HR) with 4 nodes has been generated, and has a degree of 3.
0"~>l>0
0">2>0
0">3>0
35
The Maximum Flow of the ANF graph of the 3HR is 3.
0"~>1
0">2>l
0">3>1
The Maximum Flow of the ANF graph of the 3HR is 3.
5.5 Test 5
5.5.1 Description
Now Ive tested all invalid inputs using test choice one. This test will be
exactly the same as the last one, except Im not going to try and use a semiHR, Im
not going to show the paths, and Im not going to output to a file. I will however
choose test choice number two this time and then also test invalid entries for the
source and sink, since here I will be asked to enter these.
5.5.2 Inputs
Nodes: 5.
Semi HR: No.
Show paths: No.
Output to file: No.
Test choice: 2.
Another test: No.
5.5.3 Output
Choose from the following.
1. Run multiple MaxFlows with the sink going
from 0 to ceil(N/2) in the HR. The source must
be a double prime node in the ANF and will be
defaulted to 0". In the case of a SemiHR, the
sink is always the last node in the SemiHR, which
is removed after each run, till only 2 nodes are
36
left.
2. Run one MaxFlow choosing your own source and sink,
choice: 2
Nodes in the (Semi)HR are going to be 03.
Enter the (Semi)HR node X whose corresponding X" in
the ANF is going to be used as the source for
the MF of the ANF graph: 1
Nodes in the (Semi)HR are going to be 03.
Enter the (Semi)HR node X whose corresponding X" in
the ANF is going to be used as the source for
the MF of the ANF graph: 4
Nodes in the (Semi)HR are going to be 03.
Enter the (Semi)HR node X whose corresponding X" in
the ANF is going to be used as the source for
the MF of the ANF graph: 0
Nodes in the (Semi)HR are going to be 03.
Enter the (Semi)HR node Y whose corresponding Y' in
the ANF is going to be used as the sink for
the MF of the ANF graph: 1
Nodes in the (Semi)HR are going to be 03.
Enter the (Semi)HR node Y whose corresponding Y' in
the ANF is going to be used as the sink for
the MF of the ANF graph: 4
Nodes in the (Semi)HR are going to be 03.
Enter the (Semi)HR node Y whose corresponding Y' in
the ANF is going to be used as the sink for
the MF of the ANF graph: 3
A Hyper Ring (HR) with 4 nodes has been generated, and has a degree of 3.
The Maximum Flow of the ANF graph of the 3HR is 3.
37
HRdegree, 3 = MF in test(s).
TIMES (Only accurate in Windows!)
Hyper Ring Generator took: 0.000000 sec
Associated Network Flow Generator took: 0.000000 sec
Maximum Flow Computation took: 0.000000 sec
Would you like to run another test, (y or n): n
5.5.4 Analysis
This test shows the program doesnt allow invalid input for test choice two. It
also runs the test successfully. The HR degree was equal to the two MFs that were
calculated. I did the entire procedure on paper to make sure the output was correct.
5.6 Test 6
5.6.1 Description
This test will be exactly the same as the last one, except I will show the paths
and output to a file. Also, since Ive done this before, I will also choose to ran
another test so the next test will be a continuation of the same program run, without
running the program again. I will stick with four nodes and test choice two, but I will
choose different sources and sinks than before.
5.6.2 Inputs
Nodes: 5.
Semi HR: No.
Show paths: Yes.
Output to file: Yes.
Test choice: 2.
Another test: Yes.
38
5.6.3 Output
Nodes in the (Semi)HR are going to be 03.
Enter the (Semi)HR node X whose corresponding X" in
the ANF is going to be used as the source for
the MF of the ANF graph: 3
Nodes in the (Semi)HR are going to be 03.
Enter the (Semi)HR node Y whose corresponding Y' in
the ANF is going to be used as the sink for
the MF of the ANF graph: 0
HRdegree, 3 = MF in test(s).
TIMES (Only accurate in Windows!)
Hyper Ring Generator took: 0.000000 sec
Associated Network How Generator took: 0.000000 sec
Maximum How Computation took: 0.000000 sec
Rest of the output stored in HR_MF_output.txt
Would you like to run another test, (y or n): y
5.6.4 Analysis
The test ran successfully. The HR degree was equal to the two MFs that were
calculated. I did the entire procedure on paper to make sure the output was correct.
The contents of the output file are as follows.
A Hyper Ring (HR) with 4 nodes has been generated, and has a degree of 3.
3">0
3">1>0
39
3">2~>0
The Maximum Flow of the ANF graph of the 3HR is 3.
5.7 Test 7
5.7.1 Description
This test will be run as a continuation of the last since I chose to run another
test at the end. I will this time switch over to a semiHR and enter 5 nodes. I will
choose not show the paths and not to output to file. I will however stick with test
choice number two, but I wont choose to run another test.
5.7.2 Inputs
Nodes: 5.
Semi HR: Yes.
Show paths: No.
Output to file: No.
Test choice: 2.
Another test: No.
5.7.3 Output
Would you like to run another test, (y or n): y
This program takes as user input a positive number.
This number, say N, is used to create a NHyperRing,
(NHR) whose degree/nconnectivity, is calculated as it
is created. The Associative Network How (ANF) of this
NHR is then created, and its Maximum How (MF) from a
user provided source (s) and sink (t) is then found.
You can also choose to run multiple MFs going from the
1st s to multiple ts till N/2 since the HR is symetric.
The purpose is to prove that this MF of the ANF graph is
equal to the degree/nconnectivity of the NHR. You may
also choose to use a semiHR instead, computed from the
40
original one. The input is taken upfront below.
Enter a +ve number >= 3, for the # of nodes in the HR, >= 5 for a semiHR: 5
Do you want use a semiHR instead (y or n): y
Would you like to see the paths produced in
calculating the MaxFlow; these paths will be shown
from the HR. ('y' or 'n'): n
Would you like to send the output to a file, ('y' or 'n'): y
Choose from the following.
1. Run multiple MaxHows with the sink going
from 0 to ceil(N/2) in the HR. The source must
be a double prime node in the ANF and will be
defaulted to 0". In the case of a SemiHR, the
sink is always the last node in the SemiHR, which
is removed after each run, till only 2 nodes are
left.
2. Run one MaxHow choosing your own source and sink.
3. Run multiple MaxHows with all combinations
of sources and sinks. For SemiHRs only.
choice: 2
Nodes in the (Semi)HR are going to be 02.
Enter the (Semi)HR node X whose corresponding X" in
the ANF is going to be used as the source for
the MF of the ANF graph: 0
Nodes in the (Semi)HR are going to be 02.
Enter the (Semi)HR node Y whose corresponding Y' in
41
the ANF is going to be used as the sink for
the MF of the ANF graph: 2
A Hyper Ring (HR) with 5 nodes has been generated, and has a degree of 5.
A semi HyperRing (semiHR) with 3 nodes has been generated.
The MF of the ANF of the semiHR with sdeg 2 and tdeg 2 is 2.
TIMES (Only accurate in Windows!)
Hyper Ring Generator took: 0.000000 sec
Associated Network Flow Generator took: 0.000000 sec
Maximum Flow Computation took: 0.000000 sec
Would you like to run another test, (y or n): n
5.7.4 Analysis
The test ran successfully. The HR sdegree was equal to the HR tdegree that
was equal to the MF that was calculated. Also I was given the third test choice this
time since I chose a semiHR. I did the entire procedure on paper to make sure the
output was correct.
5.8 Test 8
5.8.1 Description
To a certain extent I have now tested all the different options. From now on I
will always show the paths, always output to a file, and never choose to run another
42
test, but launch the program again. Also for HRs I will always choose test choice
one, and for semiHRs I will choose test choice number one first and then in another
test choose test choice number three. Also I will now have two outputs, screen output
and file output. This test is the same as the previous one except Im going start
following the rules I just mentioned, thus I will show the paths, and output to a file
and choose test choice number one.
5.8.2 Inputs
Nodes: 5.
Semi HR: Yes.
Show paths: Yes.
Output to file: Yes.
Test choice: 1.
Another test: No.
5.8.3 Screen Output
choice: 1
TIMES (Only accurate in Windows!)
Hyper Ring Generator took: 0.000000 sec
Associated Network Flow Generator took: 0.000000 sec
Maximum Flow Computation took: 0.000000 sec
Rest of the output stored in HR_MF_output.txt
Would you like to run another test, (y or n): n
5.8.4 File Output
A Hyper Ring (HR) with 5 nodes has been generated, and has a degree of 5.
43
A semi HyperRing (semiHR) with 3 nodes has been generated.
0">2
0">1>2
The MF of the ANF of the semiHR with sdeg 2 and tdeg 2 is 2.
5.8.5 Analysis
The test ran successfully. The HR sdegree was equal to the HR tdegree that
was equal to the MF that was calculated. Also I was given the third test choice this
time since I chose a semiHR. I did the entire procedure on paper to make sure the
output was correct.
5.9 Test 9
5.9.1 Description
This is the same test as above except I will choose test choice number three
for the first time in this document. I will stick with five nodes and using a semiHR.
5.9.2 Inputs
Nodes: 5.
Semi HR: Yes.
Show paths: Yes.
Output to file: Yes.
Test choice: 3.
Another test: No.
5.9.3 Screen Output
choice: 3
TIMES (Only accurate in Windows!)
44
Hyper Ring Generator took: 0.000000 sec
Associated Network Flow Generator took: 0.000000 sec
Maximum How Computation took: 0.000000 sec
Rest of the output stored in HR_MF_output.txt
Would you like to run another test, (y or n): n
5.9.4 File Output
A Hyper Ring (HR) with 5 nodes has been generated, and has a degree of 5.
A semi HyperRing (semiHR) with 3 nodes has been generated.
0">1>0
0">2>0
The MF of the ANF of the semiHR with sdeg 2 and tdeg 2 is 2.
0">l
0">2>1
The MF of the ANF of the semiHR with sdeg 2 and tdeg 2 is 2.
0">2
0">1>2
The MF of the ANF of the semiHR with sdeg 2 and tdeg 2 is 2.
l">0
1">2>0
The MF of the ANF of the semiHR with sdeg 2 and tdeg 2 is 2.
45
r~>o~>i
1>2>1
The MF of the ANF of the semiFIR with sdeg 2 and tdeg 2 is 2.
1">2
1">0>2
The MF of the ANF of the semiHR with sdeg 2 and tdeg 2 is 2.
2">0
2">1>0
The MF of the ANF of the semiHR with sdeg 2 and tdeg 2 is 2.
2">1
2">0>1
The MF of the ANF of the semiHR with sdeg 2 and tdeg 2 is 2.
2">0>2
2">1>2
The MF of the ANF of the semiHR with sdeg 2 and tdeg 2 is 2.
5.9.5 Analysis
The test ran successfully. The HR sdegree was equal to the HR tdegree that
was equal to the MF in all MF calculations. I did the entire procedure on paper to
make sure the output was correct.
46
5.10 Test 10
5.10.1 Description
Now Ive tested with HR and semiHR, using all the test choices available and
all the options available. Ive tested invalid input and all the boundary values. There
is no upper boundary value, except the largest value that can be stored in an integer
data type, that is 32767. However, this is too big of a number to ever test with
anyways. Now it is time to test larger numbers. I will no longer output the file
outputs, because they will be too long, however, they will be stored on the data CDR
that will accompany my thesis for review. The file name will contain the test number
that it is associated with. For this test I will test a 50 node HR.
5.10.2 Inputs
Nodes: 50.
Semi HR: No.
Show paths: Yes.
Output to file: Yes.
Test choice: 1.
Another test: No.
5.10.3 Screen Output
choice: 1
HRdegree, 12 = MF in test(s).
TIMES (Only accurate in Windows!)
Hyper Ring Generator took: 0.000000 sec
Associated Network Flow Generator took: 0.110000 sec
Maximum Flow Computation took: 1.430000 sec
47
Rest of the output stored in HR_MF_output.txt
Would you like to run another test, (y or n): n
5.10.4 Analysis
The test ran successfully. The HR degree did equal the MF in all the MF
calculations. I can no longer test on paper since the numbers are too big, I have to
rely on the program, as this is what it was designed for.
5.11 Test 11
5.11.1 Description
This test is the same as the above one, except I am going to use a semiHR
with test choice 1.
5.11.2 Inputs
Nodes: 50.
Semi HR: Yes.
Show paths: Yes.
Output to file: Yes.
Test choice: 1.
Another test: No.
5.11.3 Screen Output
choice: 1
TIMES (Only accurate in Windows!)
Hyper Ring Generator took: 0.000000 sec
Associated Network Flow Generator took: 0.000000 sec
Maximum Flow Computation took: 0.540000 sec
48
Rest of the output stored in HR_MF_output.txt
Would you like to run another test, (y or n): n
5.11.4 Analysis
The test ran successfully and it was quicker than the first test, since Im using
a semiHR this time. In all the MF calculations the HR sdegree equaled the HR t
degree which equaled the MFA
5.12 Test 12
5.12.1 Description
This test is the same as the above one, except I am going choose test choice 3.
5.12.2 Inputs
Nodes: 50.
Semi HR: Yes.
Show paths: Yes.
Output to file: Yes.
Test choice: 3.
Another test: No.
5.12.3 Screen Output
choice: 3
TIMES (Only accurate in Windows!)
Hyper Ring Generator took: 0.000000 sec
Associated Network Flow Generator took: 0.500000 sec
Maximum Flow Computation took: 3.680000 sec
49
Rest of the output stored in HR_MF_output.txt
Would you like to run another test, (y or n):
5.12.4 Analysis
The test ran successfully and it took a little longer than the last test, since I
chose test choice three this time. In the MF calculations this time, since we are doing
all combinations, the sdegrees, tdegrees, and MFs changed. However, the MF was
always equal tot the sdegree for any of the MF calculations.
5.13 Test 13
5.13.1 Description
Now I will choose 101 nodes and test an HR with test choice number one.
Note that unlike the last three tests, Im using an odd number of nodes this time.
5.13.2 Inputs
Nodes: 101.
Semi HR: Yes.
Show paths: Yes.
Output to file: Yes.
Test choice: 1.
Another test: No.
5.13.3 Screen Output
choice: 1
HRdegree, 14 = MF in test(s).
TIMES (Only accurate in Windows!)
Hyper Ring Generator took: 0.110000 sec
50
Associated Network Flow Generator took: 0.160000 sec
Maximum Flow Computation took: 15.670000 sec
Rest of the output stored in HR_MF_output.txt
Would you like to mn another test, (y or n): n
5.13.4 Analysis
The test ran successfully and it took longer than any of the previous test, since
I chose a larger number of nodes. In the MF calculations the HR degree was always
equal to the MF.
5.14 Test 14
5.14.1 Description
This test is the same as the above one, except I am going to use a semiHR
with test choice 1.
5.14.2 Inputs
Nodes: 101.
Semi HR: Yes.
Show paths: Yes.
Output to file: Yes.
Test choice: 1.
Another test: No.
5.14.3 Screen Output
choice: 1
TIMES (Only accurate in Windows!)
Hyper Ring Generator took: 0.110000 sec
51
Associated Network Flow Generator took: 0.000000 sec
Maximum Flow Computation took: 0.830000 sec
Rest of the output stored in HR_MF_output.txt
Would you like to run another test, (y or n): n
5.14.4 Analysis
The test ran successfully and it was quicker than the first test, since Im using
a semiHR this time. In all the MF calculations the HR sdegree equaled the HR t
degree which equaled the MF. However unlike the case with 50 nodes and a semi
HR in an earlier test, this time these three values were not the same for all the MF
calculations. They changed between MF calculations, but did remain equal to each
other for any particular MF calculation.
5.15 Test 15
5.15.1 Description
This test is the same as the above one, except I am going choose test choice 3.
5.15.2 Inputs
Nodes: 101.
Semi HR: Yes.
Show paths: Yes.
Output to file: Yes.
Test choice: 3.
Another test: No.
5.15.3 Screen Output
choice: 3
52
TIMES (Only accurate in Windows!)
Hyper Ring Generator took: 0.500000 sec
Associated Network How Generator took: 0.000000 sec
Maximum How Computation took: 79.690000 sec
Rest of the output stored in HR_MF_output.txt
Would you like to run another test, (yorn): n
5.15.4 Analysis
The test ran successfully and it took longer any other tests run yet, since I
chose test choice three and the highest number of nodes thus far. In the MF
calculations the sdegrees, tdegrees, and MFs changed as in the previous similar test
with 50 nodes and a semiHR. However, unlike before, the MF was not always equal
to the sdegree for any of the MF calculations. Therefore I can see now that Dr.
Altmans theory doesnt apply to semiHRs in the same way it does to HRs.
5.16 Further Testing
It should be noted that the above tests do not test all possibilities and
combinations. They dont test all invalid or valid inputs. They dont test all
combinations of options and test choices. Most importantly, they only test with; 3, 5,
50 and 101 nodes. However, in the course of my thesis work I did test much larger
numbers and did exhaust all combinations of options and test choices. I did not save
any output of these tests and did not show them in this document as it would become
too tedious and long. I will however, say that all the tests were successful and proved
53
that the theory in question to work on HRs, and showed the correct behavior for semi
HRs. Further testing files can be found on the data CDR accompanying my thesis.
These files are named as in the following example: Further_Testing_X_Y.txt,
where X is the further testing test number, and Y is the test choice being used. One
can easily see how many nodes are entered and whether or not a semiHR is being
used or not, by looking at the first two lines in the file. Also, in these files the paths
are always shown.
54
6. Conclusion
It is now time to reveal the conclusion of my thesis. I will start with analyzing
the results of my testing. The HRdegree of an HR is always equal to the MF of its
ANF using any source with any sink for calculating the MF. Thus the theory is
correct here. In the case of a semiHR there are two test choices involved. The first
one runs MF calculations on the ANF of the semiHR always keeping the source as
zero and always keeping the sink as the last node in the HR mapped to the ANF,
however this node is removed after each MF calculation. In this case, the HR s
degree and HR tdegree are both equal to each other and to the MF for any given MF
calculation. However, they may or may not change between different MF
calculations. In the second case, test choice three is chosen. Here I dont remove any
nodes from the semiHR, and all possible combinations of sources and sinks are used
to calculate MFs on the ANF. In this case, no similarities are guaranteed, the HR s
degree may or may not differ from the HR sdegree, and the MF may or may not
differ from either of these two degrees. This shows how the theory performs on semi
HRs instead of HRs; there is a dramatic difference. However, when using lower
numbers, there is more similarity in the results.
Now, I think it is important to talk about the uses of HyperRings. HRs are
used in two main fields, networking and parallel processing. A computer network
can be built using the HR design allowing for fast and dependable communication.
55
For more information on this see Tom Altmans paper, Fast and Dependable
Communication in HyperRings. These HyperRing networks can then be used for
parallel computing. For more information on this see Dr. Altmans paper, Parallel
Computing. The degree of the MF of the ANF of the HR gives the bottleneck of a
data pipe in a network or parallel processing. With this theory now tested, one
doesnt have to calculate the ANF and then the MF, one can simply check the degree
of the HR and since they are the same, get the communication bottlenecks one is
looking for.
During my thesis work I have encountered many obstacles, and gained much
experience and knowledge pertaining to my course of study. Ive learned how to deal
with a customer in the real world in order to make sure I have the correct
requirements for a software engineering project. Ive also learned how important
design, architecture, and documentation are in order to make the programming as
smooth as possible. Ive also learned how requirements change and what needs to
then be done. One has to change the documentation, design, architecture, and
program code, to compensate. Ive also gained experience in programming using
C++. Ive learned how to take an abstract theory or idea and turn it into a working
program. Ive learned how tedious testing and analysis of programs can be and why
there are separate test and analysis engineers in the real world. Ive also learned how
important small details like the formatting of the output and input requests can be.
56
Overall, this has definitely been an excellent learning experience for me and has
helped me prepare for my future in the field of Computer Science.
57
APPENDIX
A. Test Run
This program takes as user input a positive number.
This number, say N, is used to create a NHyperRing,
(NHR) whose degree/nconnectivity, is calculated as it
is created. The Associative Network Flow (ANF) of this
NHR is then created, and its Maximum How (MF) from a
user provided source (s) and sink (t) is then found.
You can also choose to run multiple MFs going from the
1st s to multiple ts till N/2 since the HR is symetric.
The purpose is to prove that this MF of the ANF graph is
equal to the degree/nconnectivity of the NHR. You may
also choose to use a semiHR instead, computed from the
original one. The input is taken upfront below.
Enter a +ve number >= 3, for the # of nodes in the HR, >= 5 for a semiHR:
287
Do you want use a semiHR instead (y or n): n
Would you like to see the paths produced in
calculating the MaxHow; these paths will be shown
from the HR. ('y' or 'n'): y
Would you like to send the output to a file, ('y' or 'n'): y
Choose from the following.
1. Run multiple MaxHows with the sink going
58
from 0 to ceil(N/2) in the HR. The source must
be a double prime node in the ANF and will be
defaulted to 0". In the case of a SemiHR, the
sink is always the last node in the SemiHR, which
is removed after each run, till only 2 nodes are
left.
2. Run one MaxHow choosing your own source and sink,
choice:
HRdegree, 18 = MF in test(s).
TIMES (Only accurate in Windows!)
Hyper Ring Generator took: 0.880000 sec
Associated Network How Generator took: 1.210000 sec
Maximum How Computation took: 1150.410000 sec
Rest of the output stored in HR_MF_output.txt
Would you like to run another test, (y or n): n
59
B. Program Code
This appendix consists of all the program code that was written for my thesis
project. There were three files: BFSqueue.h, BFSqueue.cpp, and HR
MF_Test.cpp. The first two files are short and the third one is the main file, and all
three files contents are below.
// queue.h
//PROGRAMMERS: MohammadAlsaffar.
// PURPOSE: To define the interface and declaration for a simple int Q class.
// VALUE SYMANTICS: Dynamic memory is freed, however there is no copy
// constructor, so an object of this class cannot be returned.
//DATE LAST MODIFIED: 12/03/2002.
#ifndef QUEUE_H
#define QUEUEJH
class queue
{
public:
queue(int m);
// Precondition: m is > 0.
// Postcondition: The maximum size of the Q has been set to max.
~queue();
//Precondition: None.
// Postcondition: Dynamic memory used by the queue has been freed,
void enq(int data);
60
// Precondition: data must be +ve.
// Postcondition: data is input into the FIFO Q. If more than
// max data is enqueued without dequeueing, the
// data will be overwritten.
int deq();
// Precondition: The Q is not empty.
// Postcondition: Returns the first data inserted, or a 1 if the
// Q is empty. The head is updated.
int empty Q;
//Precondition: None.
// Postcondition: Returns 1 if the Q is empty, and a 0 if not.
int head();
// Precondition: The Q is not empty.
// Postcondition: Returns the head of the Q, but the head remains.
// If the Q is empty a 1 is returned.
private:
int *Q; // Pointer for the Q array,
int max; // Maximum size of the Q.
int enqi; // Enqueue index,
int deqi; // Dequeue index.
#endif
// queue.cpp
// PROGRAMMERS: Mohammad Alsaffar.
// PURPOSE: The implementation file for queue.h or the queue class.
// DATE LAST MODIFIED: 12/03/2002.
#include
#include"BFSqueue.h"
61
// Constructor,
queue: :queue(int m)
{
max = m;
Q = new int[max];
enqi = 0;
deqi = 0;
}
// Destructor,
queue: :~queue()
{
delete(Q);
}
void queue: :enq(int data)
{
Q[enqi] = data;
if (enqi == (max 1))
enqi = 0;
else
enqi++;
}
int queue: :deq()
{
int temp = 0;
if (deqi == enqi)
{
cout"No data in Q."
return 1;
temp = Q[deqi];
if (deqi == (max 1))
else
deqi = 0;
deqi++;
return temp;
}
int queue: :empty()
{
if (enqi == deqi)
return 1;
return 0;
}
int queue: :head()
{
if (deqi == enqi)
return 1;
return Q[deqi];
}
// hr_link.cpp
//PROGRAMMER: MohammadAlsaffar.
// PURPOSE: To prove that the degree/connectivity of a Hyper Ring
// Graph (HR) or semiHR is equal to the MaxFlow (MF) of
// its Associated Network How Graph (ANF).
//DATE LAST MODIFIED: 12/03/2002.
#include
#include
#include // For gets.
#include // For atoi.
#include // For isdigit.
63
#include // For clock.
#include // For floor, ceil, and log.
#include"BFSqueue.h" // For BFS queue.
#define TRUE 1
#define FALSE 0
#define NODE_l 1
ofstream outs;
struct graph // To store a graph.
{
int *wce; // Pointer to an array for weighted capacity edges.
int *flow; // To keep track edge flow, forward and backward.
int wce_sz; // Number of elements in array wee.
int flow_sz; // Number of elements in array flow = wce_sz 2.
int Vno; // Number of vertices.
int HRdeg; // The degree/connectivity of an HR graph.
int s; // Source.
int t; // Sink/destination.
// Any values that dont apply should be set to 1 or NULL,
// depending on what the valid values are.
};
int get_input(graph &G, int &randomMF, int &show_paths, int &outfile,
int &semi, int &SemiAll);
//Precondition: None.
// Postcondition: Outputs a description of this program. Sets the
// source and the sink in "G," with user input.
// Returns a +ve number, provided by the user
// (for the number of nodes for the hyper ring). Asks
// user if he wants to output to a file, "semi" is
// for a full or semiHR.
int HR_generator(graph &HR, const int nodes);
// Precondition: "nodes" is +ve.
// Postcondition: A hyper ring with "nodes" number of nodes has been
// generated and stored in "HR." The degree of the
64
//
hyper ring is returned.
int semi_HR_generator(graph &HR, int &nodes);
// Precondition: "nodes" is +ve, "HR" is a Hyper Ring.
// Postcondition: The HR stored in "HR" has been cut in half and
// its semiHR is now stored in "HR." The degree of
// the hyper ring is returned.
int degree(graph &GR, int node);
// Precondition: "node" is a node in GR whose degree you want. GR
// has no repeated edges.
// Postcondition: The degree of "node" node in GR is returned, if
// "node" is not a node in GR, 0 is returned.
int HammingWeight(int x);
// Precondition: x is a +ve number.
// Postcondition: Returns the hamming weight of x or 1 if x is ve.
int FloorLog(int x);
// Precondition: x is a +ve number.
// Postcondition: Returns the floor of the log of x, or 1 if x is
// ve.
int CeilLog(int x);
// Precondition: x is a +ve number.
// Postcondition: Returns the ceiling of the log of x, or 1 if x is
// ve.
void ANF_generator(graph &ANF, const graph &HR);
// Precondition: "HR" is a hyper ring.
// Postcondition: The associated network flow graph of "HR" has been
// generated and stored in "ANF."
int fixANFmulti(graph &ANF, int old_s, int old_t, int ChangedOld);
// Precondition: ANF.t is the new sink, and old_t is the old one.
// Postcondition: The edge from ANF.s to ANF.t has capacity 1, and
// the edge from ANF.s to old_t has capacity
// it had before if it was changed.
void fixANF(graph &ANF);
// Precondition: ANF.t is the sink.
// Postcondition: The edge from ANF.s to ANF.t has capacity 1.
65
int max_flow_ff(graph &G, int show_paths, int outfile);
// Precondition: "G" is a directed graph with +ve capacities on
// every edge.
// Postcondition: The maximum flow from a userprovided source to a
// userprovided sink is computed and returned.
int BFS(graph &G, int *p, char *color);
// Precondition: G is a flow network graph, p is an array of size
// G.Vno + 1 color is also an array of size G.Vno + 1.
// Postcondition: A breadth first search on G starting at G.s as the
//
//
//
//
//
//
//
//
//
//
//
//
//
//
source, is run. p[] contains the predecessor
paths for the BFS tree, color contains the color
produced by BFS for each node/vertex. The only
new color is yellow which means the vertex is the
head of a flow edge. A flow edge is an edge that
is in the opposite direction of an original edge,
but has a capacity = to the flow, > 0, of the
original edge, thus when used the flow of the
original edge should be decreased instead of
increased. Original edges have priority over flow
edges, thus a flow edge will only be chosen if a
regular edge can't do the job. IfG.twas
reachable and was visited a 1 is returned, else a
0 is returned.
void print_times(double HRtime, double ANFtime, double MFtime);
// Precodition: "HRtime" is the time taken by this program for
// generating the hyper ring. "ANFtime" is the
// time taken by this program for generating the
// associated network flow. "MFtime" is the time taken
// by this program for computing the maxflow.
// Postcondition: The times are printed out with description.
void HR_MF_Test(int &nodes, int outfile, graph &ANF, int randomMF,
int show_paths);
void Semi_HR_MF_Test(int &nodes, int outfile, graph &ANF,
int randomMF, int show_paths);
void Semi_HR_MF_Test_All(int &nodes, int outfile, graph &ANF,
int show_paths);
66
int FixSemiHR(graph &HR, int nodes);
int main()
{
char again = 'y';
graph ANF; // For the associated network flow graph of the HR.
int nodes = 0, outfile = FALSE, semi = FALSE, randomMF = FALSE;
int show_paths = FALSE, SemiAll = FALSE;
while (again == 'y')
{
nodes = get_input(ANF, randomMF, show_paths, outfile, semi,
SemiAll);
FILE";
show_paths);
if(outfile)
{
outs .open( "HR_MF_Output.txt");
if (louts)
{
cout"ERROR OPENING OUTPUT
outfile = FALSE;
}
}
if(!semi)
{
HR_MF_Test(nodes, outfile, ANF, randomMF, show_paths);
}
else
{
if (ISemiAll)
{
Semi_HR_MF_Test(nodes, outfile, ANF, randomMF,
}
else
{
67
show_paths);
Semi_HR_MF_Test_All(nodes, outfile, ANF,
}
}
if(outfile)
{
cout"\n\nRest of the output stored in HR_MF_output.txt";
}
cout"\n\nWould you like to run another test, (y or n):
cinagain;
coutendlendlendlendl;
show_paths = FALSE;
randomMF = FALSE;
semi = FALSE;
if(outfile)
{
outs.close();
outfile = FALSE;
}
}
cout" Program Terminated.\n";
return 0;
}
// Get a +ve number from the user, get and set the source and sink
// for MaxFlow.
int get_input(graph &G, int &randomMF, int &show_paths, int &outfile,
int &semi, int &SemiAll)
{
cout"This program takes as user input a positive number."
"\nThis number, say N, is used to create a NHyperRing, "
"\n(NHR) whose degree/nconnectivity, is calculated as it"
"\nis created. The Associative Network Flow (ANF) of this "
"\nNHR is then created, and its Maximum Flow (MF) from a "
"\nuser provided source (s) and sink (t) is then found. \n"
68
"You can also choose to run multiple MFs going from the \n"
" 1st s to multiple ts till N/2 since the HR is symetric. \n"
"The purpose is to prove that this MF of the ANF graph is "
"\nequal to the degree/nconnectivity of the NHR. You may"
"\nalso choose to use a semiHR instead, computed from the "
"\noriginal one. The input is taken upfront below.\n\n\n";
int nodes = 0;
do
{
cout"Enter a +ve number >= 3, for the # of nodes in "
"the HR, >= 5 for a semiHR:
cinnodes;
} while(nodes < 3);
char semiHR = NULL;
do
{
cout"\nDo you want use a semiHR instead (y or n):
cinsemiHR;
} while((semiHR != 'y') && (semiHR != 'n'));
if((semiHR == 'y') && (nodes >= 5))
{
semi = TRUE;
}
else if(semiHR == 'y')
{
cout"\nSorry, you entered a number of nodes < 5! "
"Continuing with full HR.\n";
}
int source = 0, sink = 0, no_of_MFs = 0;
char want_paths = NULL;
do
{
coutendl"Would you like to see the paths produced in\n"
"calculating the MaxHow; these paths will be shown\n"
"from the HR. ('y' or 'n'):";
69
cinwant_paths;
} while((want_paths != 'y') && (want_paths != 'n'));
if(want_paths == 'y')
{
show_paths = TRUE;
}
else
{
show_paths = FALSE;
}
char out_to_file = NULL;
do
{
coutendl"Would you like to send the output to a file. "
"(y or 'n'):";
cinout_to_file;
} while((out_to_file != 'y') && (out_to_file != 'n'));
if(out_to_file == *y')
{
outfile = TRUE;
}
else
{
outfile = FALSE;
}
int upper = 2;
do
{
cout"\n\n\nChoose from the following.\n\n";
cout"l. Run multiple MaxHows with the sink goingVn"
"from 0 to ceil(N/2) in the HR. The source must\n"
"be a double prime node in the ANF and will be\n"
"defaulted to 0". In the case of a SemiHR, the\n"
"sink is always the last node in the SemiHR, which\n"
"is removed after each run, till only 2 nodes are\n"
"left.\n\n";
70
cout"2. Run one MaxHow choosing your own source and "
"sink.\n\n";
if (semi)
{
cout"3. Run multiple MaxHows with all combinations\n"
"of sources and sinks. For SemiHRs only.\n\n";
upper++;
}
cout"\tchoice:
cinno_of_MFs;
} while((no_of_MFs < 1)  (no_of_MFs > upper));
if(no_of_MFs == 1)
{
source = 1;
G.s = 2* source; // Constant.
randomMF = TRUE;
sink = 1;
G.t = (2 sink) 1; // Initial,
return nodes;
}
int temp_nodes = nodes;
if(no_of_MFs == 2)
{
if(semi)
{
if((nodes % 2) == 0) // "nodes" is even.
{
temp_nodes = nodes / 2;
}
else // "nodes" is odd.
{
temp_nodes = (nodes / 2) + 1;
}
}
coutendlendl;
71
do
{
cout"Nodes in the (Semi)HR are going to be 0
"temp_nodes 1"."
"\nEnter the (Semi)HR node X whose
corresponding X" in"
"\nthe ANF is going to be used as the source for"
"\nthe MF of the ANF graph:
cinsource;
} while((source < 0)  (source >= temp_nodes));
G.s = 2 (source + 1);
coutendl;
do
{
cout"Nodes in the (Semi)HR are going to be 0
"temp_nodes 1"."
"\nEnter the (Semi)HR node Y whose
corresponding Y' in"
"\nthe ANF is going to be used as the sink for"
"\nthe MF of the ANF graph:
cinsink;
} while((sink < 0)  (sink >= temp_nodes));
G.t = (2 (sink + 1)) 1;
}
if(no_of_MFs == 3)
{
source = 1;
G.s = 2 source; // Initial.
randomMF = TRUE;
Semi All = TRUE;
sink = 1;
G.t = (2* sink) 1; //Initial,
return nodes;
}
72
}
return nodes;
// Generate and store an HR given the number of nodes and edges,
int HR_generator(graph &HR, const int nodes)
{
// Set and/or initialize values of HR graph struct.
HR.flow = NULL;
HR.flow_sz = 0;
HR.Vno = nodes;
HR.wce = NULL;
HR.wce_sz = 0;
HR.HRdeg = 0;
HR.s = 0;
HR.t = 0;
// Now we need to fill in HR.wee, creating the HR.
// While we do this we'll caclulate the exact number of edges
// stored in HR.wce, and the degree of the HR.
int u = 0, v = 0; // Nodes of an edge.
int edge_exists = FALSE, wce_i = 0, limit = 0, i = 0;
if(HammingWeight(nodes) = 2)
{
HR.wce_sz = 3 nodes FloorLog(nodes);
HR. wee = new int[HR.wce_sz];
}
else // Hamming Weight must be >= 3
{
HR.wce_sz = 3 nodes CeilLog(nodes);
HR.wce = new int[HR.wce_sz];
}
for(int k = 1; k <= nodes; k++)
// k can never be greater than the number of nodes.
{
for(i = 0; i <= FloorLog(nodes); i++)
{
u = k;
v = k + (int)pow(2, i);
73
if((v > nodes) && (v <= (2 nodes)))
{
v = v nodes; // Loop around.
}
else if(v > (2 nodes)) // Shouldn't happen.
{
break;
}
else
{
// No looping around needed, continue.
}
// Check if edge already exists:
for (int j = 0; j < wce_i; j += 3)
{
if(((HR.wcej] == u) && (HR.wce[j + 1] = v)) 
((HR.wce[j] == y) && (HR.wce[j + 1] == u)))
{
edge_exists = TRUE;
}
}
if((!edge_exists) && (u != v))
{
if((u == NODE_l)  (v == NODE_l))
{
HR.HRdeg++;
}
HR.wce[wce_i++] = u;
HR.wce[wce_i++] = v;
HR.wce[wce_i++] = 1;
}
edge_exists = FALSE;
}
}
HR.wce_sz = wce_i;
74
}
return HR.HRdeg;
// Cut the original HR in half to create a semiHR.
int semi_HR_generator(graph &HR, int &nodes)
{
if((nodes % 2) == 0) // "nodes" is even.
{
nodes = nodes/ 2;
}
else // "nodes" is odd.
{
nodes = (nodes / 2) + 1;
}
HR.Vno = nodes;
HR.HRdeg = 0;
HR.s = 0;
HR.t = 0;
int *wce_temp = new int[HR.wce_sz];
int i = 0, j = 0;
for(i = 0; i < HR.wce_sz; i += 3)
{
if((HR.wce[i] <= nodes) && (HR.wce[i + 1] <= nodes))
{
wce_temp[j++] = HR.wce[i];
wce_temp[jH] = HR.wce[i + 1];
wce_temp[j++] = HR.wce[i + 2];
}
}
HR.wce_sz = j;
delete [] HR.wce;
HR. wee = new int[HR.wce_sz];
for(int k = 0; k < HR.wce_sz; k += 3)
{
HR.wce[k] = wce_temp[k];
75
HR.wce[k + 1] = wce_temp[k + 1];
HR.wce[k + 2] = wce_temp[k + 2];
}
delete [] wce_temp;
return HR.HRdeg;
}
// Find the degree of a node in a graph,
int degree(graph &G, int node)
{
int deg = 0;
for(int i = 0; i < G.wce_sz; i += 3)
{
if((G.wce[i] == node)  (G.wce[i + 1] == node))
{
deg++;
}
}
return deg;
}
// Find the hamming weight of a +ve number,
int HammingWeight(int x)
{
int hw = 0;
if(x < 0)
{
return 1;
}
while(x > 0)
{
if(x%2 == 1)
{
hw++;
76
}
x = (int)floor(x / 2);
}
return hw;
}
// Get the floor of the log of a number,
int FloorLog(int x)
{
int i = 1, equal = FALSE;
do
{
i++;
if(x == pow(2, i))
{
equal = TRUE;
break;
}
} while(x > (pow(2, i)));
if(equal)
{
return i;
}
else
{
return i;
}
}
// Get the ceiling of the log of a number,
int CeilLog(int x)
{
inti = 1;
77
do
{
i++;
if(x == pow(2, i))
{
break;
}
} while(x > (pow(2, i)));
return i;
}
// Generate the associated netwok flow graph of a hyper ring,
void ANF_generator(graph &ANF, const graph &HR)
{
ANF.wce_sz = 4 HR.wce_sz;
ANF.wce = new int[ANF. wce_sz];
ANF.flow = NULL;
ANF.flow_sz = (ANF.wce_sz / 3) 2;
ANF.Vno = HR.Vno 2;
ANF.HRdeg = 0;
// ANF.s already set in get_input.
// ANF.t aheady set in get_input.
// Fill in ANF.wce array, for each edge in the HR, we add four
// edges to the ANF. In the ANF there are 4 times as many edges
// and 2 times as many nodes, The ANF has prime and double prime
// nodes for each node in the HR. Thus a node X, in the HR, will
// result in an X' and an X" in the ANF. Thus the mapping I'm
// using is such that if the ANF has 6 nodes. Then these nodes
// correspond as follows:
//(1,2, 3,4, 5, 6) = (T, 1", 2', 2", 3', 3").
// Also the large capacity for double prime (") to prime (')
// edges is going to be set as nodes squared (NA2).
int HR_u = 0, HR_v = 0; // Represents edge in HR.
int u_p = 0, u_dp = 0, v_p = 0, v_dp = 0; // x_p = x, x_dp = x".
int ANF_i = 0; // Index for ANF.wce.
int M = ANF.Vno ANF.Vno; // Large capacity.
78
int edgel_exists = FALSE, edge2_exists = FALSE;
int edge3_exists = FALSE, edge4_exists = FALSE;
for(int i = 0; i < HR.wce_sz; i += 3)
{
HR_u = HR.wce[i];
HR_v = HR.wce[i +1];
u_p = (2 HR_u) 1;
u_dp = 2* HR_u;
v_p = (2 HR_v) 1;
v_dp = 2* HR_v;
// Check if any of the four edges already exist,
for (int j = 0; j < ANF_i; j += 3)
{
if((ANF.wce[j] == u_p) && (ANF.wce[j + 1] == u_dp))
{
edgel_exists = TRLfE;
}
else if((ANF.wce[j] == u_dp) && (ANF.wce[j + 1] == v_p))
{
edge2_exists = TRUE;
}
else if((ANF.wce[j] == v_p) && (ANF.wce[j + 1] == v_dp))
{
edge3_exists = TRUE;
}
else if((ANF.wce[j] == v_dp) && (ANF.wce[j + 1] == u_p))
{
edge4_exists = TRUE;
}
}
// Add edge from u' to u", with capacity 1, if none exists:
if(!edgel_exists)
{
ANF.wce[ANF_i++] = u_p;
ANF.wce[ANF_i++] = u_dp;
ANF.wce[ANF_i++] = 1;
}
// Add edge from u" to v', with capacity M = NA2, if none:
79
if(!edge2_exists)
{
ANF.wce[ANF_i++] = u_dp;
ANF.wce[ANF_i++] = v_p;
ANF.wce[ANF_i++] = M;
}
// Add edge from v' to v", with capacity 1, if none exists:
if(!edge3_exists)
{
ANF.wce[ANF_i++] = v_p;
ANF.wce[ANF_i++] = v_dp;
ANF.wce[AJSTF_i++] = 1;
}
// Add edge from v" to u', with capacity M = NA2, if none:
if(!edge4_exists)
{
ANF.wce[ANF_i++] = v_dp;
ANF.wce[ANF_i++] = u_p;
ANF.wce[ANF_i++] = M;
}
edgel_exists = FALSE;
edge2_exists = FALSE;
edge3_exists = FALSE;
edge4_exists = FALSE;
ANF.wce_sz = ANF_i;
}
int fixANFmulti(graph &ANF, int old_s, int old_t, int ChangedOld)
{
int ChangedNew = FALSE;
for(int i = 0; i < ANF.wce_sz; i += 3)
{
if((ANF.wce[i] == ANF.s) && (ANF.wce[i + 1] == ANF.t))
{
if(ANF.wce[i + 2] != 1) // = M.
80
{
ANF.wce[i + 2] = 1;
ChangedNew = TRUE;
}
}
if((ANF.s != old_s)  (ANF.t != old_t))
{
if((ANF.wce[i] == old_s) && (ANEwce[i + 1] == old_t))
{
if(Changed01d)
{
ANF.wce[i + 2] = ANF.Vno ANF.Vno;
}
}
}
}
return ChangedNew;
void fixANF(graph &ANF)
{
for(int i = 0; i < ANF.wce_sz; i += 3)
{
if((ANF.wce[i] == ANF.s) && (ANF.wce[i + 1] == ANF.t))
{
if(ANF.wce[i + 2] != 1) // = M.
{
ANF.wce[i + 2] = 1;
}
}
}
}
// Find and output max flow and cpu time.
int max_flow_ff(graph &G, int show_paths, int outfile)
{
int *p = new int[G.Vno +1]; // For predecessor path.
int *straight_path = new int[G.Vno + 1]; // For straight path.
81
int path_sz = 0; // No of nodes in above array.
char *color = new char[G.Vno + 1]; // For BFS vertex colors.
int min_rc = 32767, temp = 32767; // For minimum residual capacity.
int i = 0; // Counter for loops.
G.flow = new int[G.flow_sz]; // Declare flow array.
p[0] = 0;
color[0] = 'o';
for (i = 0; i < G.wce_sz; i += 3) // Set flows to 0.
{
G.flow[(i / 3) 2] = 0;
G.flow[((i / 3) 2) + 1] = 0;
}
int t = 0, h = 0; // Represents an edge.
while (BFS(G, p, color) == 1) // While there exists a path.
{
// For each path:
h = G.t;
t = p[h];
straight_path[path_sz++] = h;
temp = 32767;
min_rc = 32767; // Initialize.
do // Find minimum residual capacity in path.
{
if (color[h] != 'y') // Flow edge NOT used.
{
for (i = 0; i < G.wce_sz; i += 3)
{
if((G.wce[i] == t) && (G.wce[i+1] == h))
{
temp=G.wce[i+2]G.flow[(i/3)*2];
if (temp < min_rc)
min_rc = temp;
break;
}
}
82
i);
}
else // (color[h] == 'y') > Flow edge used.
{
for (i = 0; i < G.wce_sz; i += 3)
{
if((G.wce[i] == h) && (G.wce[i+1] = t))
{
temp = G.flow[(i / 3) 2];
if (temp < min_rc)
minjrc = temp;
}
break;
h = t;
t = p[h];
straight_path[path_szH] = h;
} while (h != G.s);
h = G.t;
t = p[G.t];
do // For each edge in the path, increase its flow.
{
if (color[h] != 'y') // Flow edge NOT used.
{
for (i = 0; i < G.wce_sz; i += 3)
{
if((G.wce[i] == t) && (G.wce[i+1] = h))
{
G.flow[(i/3)*2] += minjrc;
G.flow[((i/3) *2)+1 ]=G.flow [(i/3) *2] (
break;
}
}
}
else // (color[h] = 'y') > How edge used.
{
83
for (i = 0; i < G.wce_sz; i += 3)
{
if((G.wce[i] == h) && (G.wce[i+1] t))
{
G.flow[(i/3)*2] = min_rc;
G.flow[((i/3)*2)+l]=G.flow[(i/3)*2]*(
h = t;
t = p[h];
} while (h != G.s);
// Print out the path if the user wants it.
if(show_paths)
{
if(outfile)
{
outs(straight_path[path_sz 1] / 2) 1""~>";
for(i = (path_sz 2); i > 0; i)
{
if((straight_path[i] % 2) != 0)
{
outs((straight_path[i] + 1) / 2) 1"
}
if((i % 15) == 0) // To go to next line.
{
outsendl;
}
}
outs((straight_path[i] + 1) / 2) lendl;
}
else
{
cout(straight_path[path_sz 1] / 2) 1"">";
84
for(i = (path_sz 2); i > 0; i)
{
if((straight_path[i] % 2) != 0)
{
cout((straight_path[i] + 1) / 2) 1"
}
if((i % 15) == 0) // To go to next line.
{
coutendl;
}
}
cout((straight_path[i] + 1) / 2) lendl;
}
}
path_sz = 0;
int max_flow = 0;
for (i = 0; i < G.wce_sz; i += 3)
{
if (G.wce[i] == G.s)
{
max_flow += G.flow[(i / 3) 2];
}
}
delete [] p;
delete [] straight_path;
delete [] color;
delete [] G.flow;
return max_flow;
}
// Get any available path, using BFS.
85
int BFS(graph &G, int p[], char color[])
{
int i = 0; // Counter for loops,
queue Q(G.Vno + 1); // Declare a Q.
for (i = 1; i <= G.Vno; i++)
{
color[i] = 'w';
p[i] = i;
}
color[G.s] = 'g';
Q.enq(G.s);
int u = 0, v = 0;
while (Q.emptyO != 1)
{
u = Q.head();
for (i = 0; i < G.wce_sz; i += 3)
{
if (G.wce[i] == u)
{
v = G.wce[i + 1];
if (color[v] == 'w')
{
if (G.flow[(i / 3) 2] < G.wce[i + 2])
{
color[v] = 'g';
p[v] = u;
Q.enq(v);
}
}
// If v already visited by flow edge,
if (color[v] == 'y')
{
if (G.flow[(i / 3) 2] < G.wce[i + 2])
{
color[v] = 'g';
86
}
p[v] = u;
}
}
}
for (i = 0; i < G.wce_sz; i += 3)
{
if ((G.wce[i + 1] == u) && (G.flow[(i / 3) 2] > 0) &&
(G.flow[(i / 3) 2] <= G.wce[i + 2]))
{
v = G.wce[i];
if (color[v] == 'w')
{
color [v] = 'y';
p[v] = u;
Q.enq(v);
}
}
}
u = Q.deq();
color[u] = b';
}
if (color[G.t] == 'w') // If no path to G.t from G.s.
return 0;
else
return 1;
// Print timing data.
void print_times(double HRtime, double ANFtime, double MFtime)
{
cout.setf(ios: :fixed);
cout. setf(ios:: showpoint);
cout.precision(6);
cout"TIMES (Only accurate in Windows!)\n\n";
cout"Hyper Ring Generator took: "
HRtime" sec"endl;
87
cout"Associated Network Flow Generator took: "
ANFtime" sec"endl;
cout"Maximum Flow Computation took: "
MFtime" sec"endl;
}
// Run main test program.
void HR_MF_Test(int &nodes, int outfile, graph &ANF, int randomMF,
int show_paths)
{
graph HR; // For storing a hyper ring.
clock_t startHR, endHR, startANF, endANF, startMF, endMF;
int HRdegree = 0, mf = 0, success = TRUE;
startHR = clock(); // Start timer.
HRdegree = HR_generator(HR, nodes);
endHR = clock(); // End timer.
if(outfile)
{
outs" A Hyper Ring (HR) with "nodes" nodes has "
"been generated, and has a degree of "HRdegree
".\n\n\n";
}
else
{
cout"\n\n\nA Hyper Ring (HR) with "nodes" nodes has "
"been generated, and has a degree of "HRdegree
".\n\n\n";
}
startANF = clock(); // Start timer.
ANF_generator(ANF, HR);
endANF = clock(); // End timer.
int old_t = 0;
if(randomMF)
{
old_t = 0;
if(outfile)
{
coutendlendlendl;
}
else
{
outsendlendlendl;
}
int changed = FALSE;
startMF = clock(); // Start timer.
for(int i = 1; i <= ((nodes + 1) / 2); i++)
{
old_t = ANF.t;
ANF.t = (2 i) 1;
changed = fixANFmulti(ANF, ANF.s, old_t, changed);
mf = max_flow_ff(ANF, show_paths, outfile);
if(outfile)
{
outs"The Maximum Flow of the ANF graph of the "
HRdegree"HR is "mf".\n\n\n\n";
}
else
{
cout"The Maximum Flow of the ANF graph of the "
HRdegree"HR is "mf".\n\n\n\n";
}
if(HRdegree != mf)
{
success = FALSE; // Failure.
}
}
endMF = clock(); // End timer.
}
else
{
89
if(show_paths)
{
coutendlendlendl;
}
else
{
coutendl;
}
fixANF(ANF);
startMF = clock(); // Start timer.
mf = max_flow_ff(ANF, show_paths, outfile);
endMF = clock(); // End timer.
if(outfile)
{
outs"The Maximum Flow of the ANF graph of the "
HRdegree"HR is "mf".\n\n\n\n";
}
else
{
cout"The Maximum Flow of the ANF graph of the "
HRdegree"HR is "mf".\n\n\n\n";
}
if(HRdegree != mf)
{
success = FALSE; // Failure.
}
}
delete [] HR.wce;
delete [] ANF.wee;
if(success)
{
cout"HRdegree, "HRdegree" = MF in test(s).\n\n";
}
else
{
cout"FlRdegree, "HRdegree" != MF in test(s).\n\n";
}
90
