###################
##### AUTHORS #####
###################

Written by Vipin Vijayan (vvijayan@nd.edu)
and Vikram Saraph (vikram_saraph@brown.edu, vsaraph@nd.edu)
In collaboration with Prof. Tijana Milenkovic (tmilenko@nd.edu)

#######################
##### DESCRIPTION #####
#######################

This README describes the usage of the command line interface of
 DynaMAGNA++, which implements our dynamic network alignment
 algorithm, DynaMAGNA++. DynaMAGNA++ is a pairwise global aligner of
 dynamic networks and a genetic algorithm. It can either start the
 alignment process using an initial set of alignments, or start
 completely from scratch.

###################
##### OPTIONS #####
###################

-G | source network
-H | target network
Both networks are specified as .dy graphs.
A typical .dy file might look like:

====== BEGIN ======
1.0  4.0  g_a g_b
5.0  8.0  g_a g_b
2.0  3.0  g_a g_c
4.0  10.0 g_a g_c
15.0 20.0 g_a g_c
2.0 10.0 g_b g_c
12.0 15.0 g_b g_c
1.0 3.0 g_c g_d
======= END =======

------------------------------------------------------------

-i | initial population (default: random)
The initial population is specified by a plain text file. This text
file should contain the file names of each alignment to be
part of the initial population. For example, this file might look
like:

====== BEGIN ======
alignment1.aln
alignment2.aln
alignment3.aln
======= END =======

If the population size (see -p below) is larger than the number of
alignments given in the initial population file, the remainder of the
initial population is automatically filled with randomly generated
alignments. If, however, the population size is smaller, then the
program simply selects the first P alignments from the initial
population file, where P is the population size.

Each alignment files (with extension .aln) is usually an output from
another network alignment or similar method, and is given as text file
with two, space/tab-separated columns.  Each row is an aligned pair of
nodes, with the node in the first column belonging to the source
network, and the second belonging to the target. Such a file may look
like:

====== BEGIN ======
A	D
B	E
C	F
======= END =======

The initial population file provides a way to give the algorithm
something nonrandom to start with.  For example, one may wish to
include alignments generated by another algorithm into the initial
population.  If -i is not specified (default behavior), then DynaMAGNA++
uses a completely random initial population.

------------------------------------------------------------

-o | output file
This parameter specifies the prefix each output alignment should
have. Suppose we are aligning net1.gw with net2.gw. Then we might want
`net1_net2' to appear at the beginning of the name of each alignment
file outputted by MAGNA++. The -o parameter provides the means to do
this.

------------------------------------------------------------

-m | optimizing measure
DynaMAGNA++ is capable of optimizing the
dynamic edge conservation measure, dynamic symmetric substructure
score (DS^3) (see paper).  To optimize DS^3, pass `DS3' to the -m
flag.  Optionally, it can also optimize the following static edge
conservation measures: edge correctness (EC), induced conserved
structure (ICS), and symmetric substructure score (S^3).  To optimize
EC, pass `EC' to the -m flag; to optimize ICS, pass `ICS'; and to
optimize S^3, pass `S3'. Note that `DS3' (respectively `EC', `ICS' and
'S3') appear in the names of the outputted alignment files.

------------------------------------------------------------

-d | node comparison data file
DynaMAGNA++ allows us to add node similarity scores
for the node conservation measure.  The input for this is the file
name that contains the scores.  The scores must be similarity scores,
which means the higher the number, the more similar the nodes are.
The scores must also be non-negative real numbers.  The format of the
score data file is a list of node pairs with real numbers next to the
node pairs. For example, with the source graph of 2 nodes and target
graph of 3 nodes, the score file will look as follows.

<FILE START>
G_a H_a 0.9
G_a H_b 0.7
G_a H_c 0.5
G_b H_a 0.4
G_b H_b 0.85
G_b H_c 0.3
<FILE END>

The final node score is calculated by taking the average of the
similarity scores of the aligned node pairs.

------------------------------------------------------------

-a | alpha value
This value, which is between 0 and 1 inclusive, accounts for the the
weighting between the edge conservation and the node
conservation. Given edge conservation score, E, specified by the
option -m, and the node score N, specified by the option -d. The final
score is alpha*E + (1-alpha)*N By default alpha = 1, which means it
only uses edge scores by default.  If alpha = 0, then it uses only
node conservation, which is equivalent to solving the assignment
problem.

------------------------------------------------------------

-p | population size
This parameter specifies the size of the population used by
MAGNA++. Generally, a larger population size means better
alignments. This value also appears in the names of the outputted
alignment files.

------------------------------------------------------------

-e | elite percentage
This value tells MAGNA++ what percentage of the population it should
consider "elite," or how many of the better alignments are passed to
the next generation. By default, this value is 0.5, as DynaMAGNA++
discards half of the population with each new generation. The user is
free to vary this parameter, though 0.5 typically works best.

------------------------------------------------------------

-n | number of generations
This parameter specifies the number of generations for which to run
MAGNA++. Generally, running DynaMAGNA++ for more generations yields higher
quality alignments.

------------------------------------------------------------

-f | frequency of output
This parameter is used to specify how many times DynaMAGNA++ should output
the best alignment in the population.  For example, suppose the user
wants to run MAGNA++ for 1000 generations, with a frequency 5. Then
the best alignment from the population is written after generations 0,
200, 400, 600, 800, and 1000. (The best of the zeroth generation is
also outputted, regardless of the frequency). It is strongly
recommended that the frequency of output divide the number of
generations. By default, the frequency is set to 1, which means only
the best alignment from the very last generation is outputted.

------------------------------------------------------------

-t | number of threads
This parameter specifies the number of threads used to run MAGNA++.
The recommended number of threads is the number of cores available in
the computer.


##############################
##### SAMPLE EXECUTION 1 #####
##############################

Suppose we have networks test_graph1.dy and test_graph2.dy, with an
initial population defined by test_population.txt.  We want to
optimize edge correctness, and let DynaMAGNA++ run for 10 generations on a
population size of 10.  In addition, we want the best alignment of the
population halfway through execution. The following command does this.

./dynamagna -G test_graph1.dy -H test_graph2.dy -i test_population.txt -o test_run -m DS3 -p 10 -n 10 -f 2

After execution, as a result, the following three files are written in the same directory as the executable:
test_run_DS3_10_10_0.aln
test_run_DS3_10_10_5.aln
test_run_DS3_10_10_10.aln


##############################
##### SAMPLE EXECUTION 2 #####
##############################

Suppose we have networks test_graph1.dy and test_graph2.dy, with an
initial population defined by test_population.txt. And node score
similarity matrix file, nodescores.txt.  We want to optimize edge
correctness and node comparisons, and let MAGNA++ run for 10
generations on a population size of 10. We want to weight the edge
score and node score with 0.6.  In addition, we want the best
alignment of the population halfway through execution. The following
command does this.

./dynamagna -G test_graph1.dy -H test_graph2.dy -i test_population.txt -o test_run -m DS3 -p 10 -n 10 -f 2 -d nodescores.txt -a 0.6

After execution, as a result, the following three files are written in the same directory as the executable:
test_run_DS3_10_10_0.aln
test_run_DS3_10_10_5.aln
test_run_DS3_10_10_10.aln


##############################
##### SAMPLE EXECUTION 3 #####
##############################
./dynamagna -G ../data/network1.dy -H ../data/network2.dy -o ../results/x -m DS3 -p 20 -n 20 -i ../data/initalns.txt -a 0.5 -d ../data/simmat.txt
 where network1.dy and network2.dy are the dynamic networks
initalns.txt is the initial population file
exgdvsim.txt is the node similarity file
