/***************************************************************************
    FPGA Brook Source Code
    Copyright (C) by Frank Franjo Plavec 2006-2012

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 1, or (at your option)
    any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

    The full text of the GNU General Public License in the file named
    LICENSE.cTool.
*****************************************************************************/

#include <iostream>
#include <sstream>
#include "graph.h"
#include <math.h>

using namespace std;

GraphNode::GraphNode (std::string name) {
	this->name = name;
	this->replication_factor = 1;
	this->reduce = false;
	this->copy_ptr = NULL;
	this->insize_dim0 = -1;
	this->insize_dim1 = -1;
	this->reducesize_dim0 = -1;
	this->reducesize_dim1 = -1;
	this->root_reduction_replica = NULL;
	this->replicated_leaves = -1;
	this->weight = -1;
	this->is_leaf = false;
	this->elements_to_process_1 = -1;
	this->elements_to_process_2 = -1;
	this->my_index = -1;
	this->total_elements_to_process = -1;
	this->counter_threshold = -1;
	this->node_order = -1;
	this->node_order_distributor = -1;
	this->trees = 0;
	this->visited = false;
	this->preceded_by_a_collector = false;
	this->reducenodehandling = Normal;
	this->nodes_in_phase_2 = -1;
	this->phase_2_ptr = NULL;
}


GraphNode::GraphNode (std::string name, unsigned int replication_factor) {
	this->name = name;
	this->replication_factor = replication_factor;
	this->reduce = false;
	this->copy_ptr = NULL;
	this->insize_dim0 = -1;
	this->insize_dim1 = -1;
	this->reducesize_dim0 = -1;
	this->reducesize_dim1 = -1;
	this->root_reduction_replica = NULL;
	this->replicated_leaves = -1;
	this->weight = -1;
	this->is_leaf = false;
	this->elements_to_process_1 = -1;
	this->elements_to_process_2 = -1;
	this->my_index = -1;
	this->total_elements_to_process = -1;
	this->counter_threshold = -1;
	this->node_order = -1;
	this->node_order_distributor = -1;
	this->trees = 0;
	this->visited = false;
	this->preceded_by_a_collector = false;
	this->reducenodehandling = Normal;
	this->nodes_in_phase_2 = -1;
	this->phase_2_ptr = NULL;
}


void GraphNode::addInEdge (GraphEdge *in_edge) {
	in_edges.push_back (in_edge);
}

GraphEdge & GraphNode::addOutEdge (GraphEdge &edge) {
	out_edges.push_back(edge);
	return out_edges.back();
}

// Locates an out edge from this node with a given name, whose destination pointer is NULL
// If no such node exists, returns NULL
GraphEdge* GraphNode::findEdgeNoDestinationPtr (std::string name) {

	std::list<GraphEdge>::iterator iter;

	for (iter=out_edges.begin(); iter != out_edges.end(); iter++) {
		if ((iter->name == name) && (iter->destination == NULL)) {
			return &(*iter);
		}
	}
	return NULL;
}



GraphEdge& GraphEdge::operator=(const GraphEdge &right) {
	this->name = right.name;
	this->destination = right.destination;
	this->dest_var = right.dest_var;
	this->source_var = right.source_var;
	this->stream_of_arrays = right.stream_of_arrays;
	this->array_size = right.array_size;
	this->word_size = right.word_size;
	return *this;
}


GraphNode& Graph::addNode (GraphNode &node) {
	this->nodes.push_back (node);
	return this->nodes.back();
}


GraphEdge& Graph::addEdge (std::string name, GraphNode &source, bool stream_of_arrays, int array_size, int word_size) {

	GraphEdge new_edge (name);
	GraphEdge& ret_val = source.addOutEdge (new_edge);
	ret_val.stream_of_arrays = stream_of_arrays;
	ret_val.array_size = array_size;
	ret_val.word_size = word_size;
	return ret_val;
}

GraphEdge& Graph::addEdge (std::string name, GraphNode &source, GraphNode &destination, bool stream_of_arrays, int array_size, int word_size) {

	GraphEdge new_edge (name, destination);
	GraphEdge &edge_in_the_graph = source.addOutEdge (new_edge);
	destination.addInEdge (&edge_in_the_graph);
	edge_in_the_graph.stream_of_arrays = stream_of_arrays;
	edge_in_the_graph.array_size = array_size;
	edge_in_the_graph.word_size = word_size;
	return edge_in_the_graph;
}

void Graph::addEdgeDestination (GraphEdge &edge, GraphNode &destination) {
	edge.destination = &destination;
}


// This function takes a graph with inputs and outputs specified and adds
// edges between nodes to create a proper dataflow graph
void Graph::Connect () {
	std::list<GraphNode>::iterator iter_i, iter_k;
	std::list<struct StreamStruct>::iterator iter_j, iter_w;
	GraphEdge *temp_edge;

	// Iterate over all nodes
	for (iter_i=nodes.begin(); iter_i != nodes.end(); iter_i++) {
		// For each node look at all its outputs
		for (iter_j=iter_i->out_streams.begin() ; iter_j != iter_i->out_streams.end(); iter_j++) {
			// Now iterate over all nodes and find where this stream is used as an input
			// Once found (a little lower below), we will add an edge between the two nodes
			for (iter_k=nodes.begin(); iter_k != nodes.end(); iter_k++) {
				// For each node look at all its inputs
				for (iter_w=iter_k->in_streams.begin(); iter_w != iter_k->in_streams.end(); iter_w++) {
					if ((iter_j->stream) == (iter_w->stream)) {
						// Time to add an edge
						temp_edge = &(this->addEdge ((iter_j->stream), (*iter_i), (*iter_k), false, 0, iter_j->word_size));
						// Make sure to add associated variables to the edges
						temp_edge->source_var = iter_j->stream_var;
						temp_edge->dest_var = iter_w->stream_var;
						if (iter_j->stream_of_arrays || iter_w->stream_of_arrays) {
							// If either source or destination (or both) is marked as carrying a stream of arrays, then this edge carries stream of arrays
							temp_edge->stream_of_arrays = true;
							if (iter_j->array_size != iter_w->array_size) {
								fatal ("Inside Graph::Connect(): Array sizes for a stream of arrays at the edge source and destination do not match");
							}
							if (iter_j->word_size != iter_w->word_size) {
								fatal ("Inside Graph::Connect(): Word sizes for a stream of arrays at the edge source and destination do not match");
							}
							temp_edge->array_size = iter_j->array_size;
							temp_edge->word_size = iter_j->word_size;
						}
					}
				}
			}
		}
	}
}

// This method should be called on an empty graph (without any nodes)
// This function traverses the "original" graph passed as a parameter
// and attempts to build a graph with desired replication.
// Nodes in the original graph whose replication factor is 1
// are simply copied to the empty graph
// Nodes whose replication factor is higher than 1 are replicated and 
// distributor/collector nodes are added where necessary
void Graph::Replicate (Graph &original) {
	std::list<GraphNode>::iterator orig_n_iter;
	std::list<GraphNode>::iterator copy_n_iter;
	std::list<GraphEdge>::iterator orig_e_iter;
	unsigned int j, collectors=0, distributors=0, col_dis=0, doubles=0, col_doubles=0;

	// First check that the new graph is empty
	if (!this->nodes.empty()) {
		cout << "\nIllegal operation: Replicate() method called on a graph that is not empty!\n";
		exit (1);
	}

	// Iterate over all nodes
	for (orig_n_iter=original.nodes.begin(); orig_n_iter != original.nodes.end(); orig_n_iter++) {
		// If replication factor is 1, simply copy the current node
		if (orig_n_iter->replication_factor == 1) {
			GraphNode new_node (orig_n_iter->name, orig_n_iter->replication_factor);
			if (orig_n_iter->isReduce()) {
				new_node.setReduce();
			}
			this->nodes.push_back (new_node);
			// Add a pointer from the old graph to the new graph
			orig_n_iter->copy_ptr = &(this->nodes.back());
			// Need to also update edges - will do that later down in the code after processing all nodes
		} else {
			// Otherwise the node has to be replicated
			if (!orig_n_iter->isReduce()) {
				// If it is not a reduce kernel, simply create appropriate number of replicas
				for (j=0; j<orig_n_iter->replication_factor; j++) {
					// Will reuse replication factor variable to keep track of the replica id for the node
					// i.e. replication factor in the replicated graph actually contains a different number
					// for each replica of the original node
					string new_name = orig_n_iter->name.substr(0, orig_n_iter->name.size()-1);
					ostringstream instance_number;
					instance_number << j;
					new_name += instance_number.str();
					GraphNode new_node (new_name, j);
					// old_last pointer will point to the previously added node
					GraphNode* old_last = NULL;
					if (j != 0) {
						old_last = &(this->nodes.back());
					}
					this->nodes.push_back (new_node);
					if (0 == j) {
						// Add a pointer from the old graph to the first replica in the new graph
						orig_n_iter->copy_ptr = &(this->nodes.back());
					} else {
						// For all other replicas, link them together
						// i.e. add a pointer from the previous replica to the newly added replica
						old_last->copy_ptr = &(this->nodes.back());
					}
				}
			} else {
				int dimensions = 1;
				// If it is a reduce kernel, it requires special handling
				// First check that the dimensions have been properly set
				if (orig_n_iter->insize_dim0 == -1 || orig_n_iter->reducesize_dim0 == -1) {
					cerr << "\nError GraphReplicate001: Either input or output size along dimension 0 has not been set properly\n";
					exit (1);
				}
				if (orig_n_iter->insize_dim1 != -1 && orig_n_iter->reducesize_dim1 != -1) {
					dimensions = 2;
				}
				// Extract the word_size from the edges
				int word_size;
				if (orig_n_iter->in_edges.size() != 0)  {
					word_size = orig_n_iter->in_edges.front()->word_size;
				} else if (orig_n_iter->out_edges.size() != 0) {
					word_size = orig_n_iter->out_edges.front().word_size;
				} else {
					fatal ("Inside of Graph::Replicate: Cannot determine word size because the node has no input or output edges");
				}
				if (dimensions == 1) {
					// First check that the replication factor is not higher than the theoretical limit for reduction kernels
					if (orig_n_iter->replication_factor > (orig_n_iter->insize_dim0/2.0)) {
						cerr << "\nError GraphReplicate002: Replication factor for the reduction kernel " << orig_n_iter->name << " is higher than the theoretical limit.\n";
						cerr << "\nReplication factor cannot be higher than HALF the number of input elements (i.e. half the input stream size) of a reduction kernel.\n";
						cerr << "\nIn this case maximum allowable replication factor is " << orig_n_iter->insize_dim0/2.0 << ".\n";
						exit (1);
					}
					// Variable tree_limit contains the maximum speedup achievable by building a single tree
					double tree_limit = ((1.0*orig_n_iter->insize_dim0)/(orig_n_iter->reducesize_dim0))/2.0;
					if ((1.0*orig_n_iter->replication_factor) <= tree_limit) {
						// This means we can achieve desired speedup just by building a single tree
						build_trees (*orig_n_iter, 1, orig_n_iter->insize_dim0, orig_n_iter->reducesize_dim0, orig_n_iter->replication_factor, collectors, doubles, (*((orig_n_iter->in_edges).begin()))->dest_var, (*((orig_n_iter->out_edges).begin())).source_var, word_size);
						orig_n_iter->trees = 1;
					} else  {
						// If we are here, it means we need to build more than one tree
						int num_trees;
						// Essentially increase the number of trees, until the number of trees satisfies the desired replication
						// start with 2, because we already know it cannot be done with only one tree
						// This is probably a convoluted way of doing this, but it's the first thing that came to my mind :)
						for (num_trees = 2; ((1.0*orig_n_iter->replication_factor)/num_trees) > tree_limit; num_trees++);
						// Now build num_trees of an appropriate size
						build_trees (*orig_n_iter, num_trees, orig_n_iter->insize_dim0, orig_n_iter->reducesize_dim0, ((1.0*orig_n_iter->replication_factor)/num_trees), collectors, doubles, (*((orig_n_iter->in_edges).begin()))->dest_var, (*((orig_n_iter->out_edges).begin())).source_var, word_size);
						orig_n_iter->trees = num_trees;
					}
				} else {
					// Replicating 2-D reduction kernel is divided into 2 special cases and one general case:
					if ((orig_n_iter->reducesize_dim0 == 1 && orig_n_iter->reducesize_dim1 == 1) || (orig_n_iter->insize_dim0 == orig_n_iter->reducesize_dim0)) {
						int inputs, outputs;
						if  (orig_n_iter->reducesize_dim0 == 1 && orig_n_iter->reducesize_dim1 == 1) {
							// Special case 1: the output has only one element
							// This is equivalent to 1-D reduction with (orig_n_iter->insize_dim0 * orig_n_iter->insize_dim1) elements on the input
							// and 1 element on the output
							inputs = (orig_n_iter->insize_dim0 * orig_n_iter->insize_dim1);
							outputs = 1;
						} else {
							// Special case 2: the output has the same number of rows as the input
							// This is equivalent to 1-D reduction with (orig_n_iter->insize_dim0 * orig_n_iter->insize_dim1) elements on the input
							// and (orig_n_iter->reducesize_dim0 * orig_n_iter->reducesize_dim1) elements on the output
							inputs = (orig_n_iter->insize_dim0 * orig_n_iter->insize_dim1);
							outputs = (orig_n_iter->reducesize_dim0 * orig_n_iter->reducesize_dim1);
						}
						orig_n_iter->reducenodehandling = Reduce_2d_1d;
						orig_n_iter->insize_dim0 = inputs;
						orig_n_iter->insize_dim1 = -1;
						orig_n_iter->reducesize_dim0 = outputs;
						orig_n_iter->reducesize_dim1 = -1;
						// Now have to change the name of the kernel from 2d2d into 1d1d
						string temp_string("_2d2d_replica_");
						size_t loc = orig_n_iter->name.find(temp_string, 0);
						orig_n_iter->name.replace (loc, temp_string.length(), "_1d1d_replica_");
						// The rest is the same as for the 1-D case
						// First check that the replication factor is not higher than the theoretical limit for reduction kernels
						if (orig_n_iter->replication_factor > (orig_n_iter->insize_dim0/2.0)) {
							cerr << "\nError GraphReplicate003: Replication factor for the reduction kernel " << orig_n_iter->name << " is higher than the theoretical limit.\n";
							cerr << "\nReplication factor cannot be higher than HALF the number of input elements (i.e. half the input stream size) of a reduction kernel.\n";
							cerr << "\nIn this case maximum allowable replication factor is " << orig_n_iter->insize_dim0/2.0 << ".\n";
							exit (1);
						}
						// Variable tree_limit contains the maximum speedup achievable by building a single tree
						double tree_limit = ((1.0*orig_n_iter->insize_dim0)/(orig_n_iter->reducesize_dim0))/2.0;
						if ((1.0*orig_n_iter->replication_factor) <= tree_limit) {
							// This means we can achieve desired speedup just by building a single tree
							build_trees (*orig_n_iter, 1, orig_n_iter->insize_dim0, orig_n_iter->reducesize_dim0, orig_n_iter->replication_factor, collectors, doubles, (*((orig_n_iter->in_edges).begin()))->dest_var, (*((orig_n_iter->out_edges).begin())).source_var, word_size);
							orig_n_iter->trees = 1;
						} else  {
							// If we are here, it means we need to build more than one tree
							int num_trees;
							// Essentially increase the number of trees, until the number of trees satisfies the desired replication
							// start with 2, because we already know it cannot be done with only one tree
							for (num_trees = 2; ((1.0*orig_n_iter->replication_factor)/num_trees) > tree_limit; num_trees++);
							// Now build num_trees of an appropriate size
							build_trees (*orig_n_iter, num_trees, orig_n_iter->insize_dim0, orig_n_iter->reducesize_dim0, ((1.0*orig_n_iter->replication_factor)/num_trees), collectors, doubles, (*((orig_n_iter->in_edges).begin()))->dest_var, (*((orig_n_iter->out_edges).begin())).source_var, word_size);
							orig_n_iter->trees = num_trees;
						}
						// Now have to change the name of the kernel back from 1d1d into 2d2d
						temp_string = "_1d1d_replica_";
						loc = orig_n_iter->name.find(temp_string, 0);
						orig_n_iter->name.replace (loc, temp_string.length(), "_2d2d_replica_");

					} else {
						// General case is handled here
						// We need to implement a 2-phase 2-D reduction
						// In the first phase we reduce elements of each row, which is equivalent to 1-D reduction from X*Y to X*B elements
						// In the second phase we perform a 2-D reduction from [X,B] into [A,B]
						// First check that the replication factor is not higher than the theoretical limit for reduction kernels
						// The two phases have different maximum achievable speedups, so we have to compare it to both expressions
						if ((orig_n_iter->replication_factor > (orig_n_iter->insize_dim0*orig_n_iter->insize_dim1/2.0)) || (orig_n_iter->replication_factor > (orig_n_iter->insize_dim0*orig_n_iter->insize_dim0*orig_n_iter->insize_dim1/(2.0*orig_n_iter->reducesize_dim0)))) {
							cerr << "\nError GraphReplicate004: Replication factor for the reduction kernel " << orig_n_iter->name << " is higher than the theoretical limit.\n";
							cerr << "\nReplication factor cannot be higher than HALF the number of input elements (i.e. half the input stream size) of a reduction kernel.\n";
							cerr << "\nIn this case maximum allowable replication factor is the lower of the following two numbers:" << orig_n_iter->insize_dim0*orig_n_iter->insize_dim1/2.0 << " and " << orig_n_iter->insize_dim0*orig_n_iter->insize_dim0*orig_n_iter->insize_dim1/(2.0*orig_n_iter->reducesize_dim0) << ".\n";
							exit (1);
						}
						// We have to distinguish between two cases
						// If the desired speedup can be achieved without accelerating the second phase, we only replicate the first phase
						if (orig_n_iter->replication_factor <= (unsigned int)(orig_n_iter->insize_dim1/orig_n_iter->reducesize_dim1)) {
							// The above condition tests whether the desired speedup is lower than the speedup of the second phase
							// because the reduction was split into two phases (each phase achieves higher throughput than the original
							// reduction performed by 1 node)
							// In this case we only need to replicate the first phase, because the second phase is fast enough without replication
							// In this case if Y == B, that means the first phase has nothing to do, but that is probably error,
							// because that would mean that replication factor is <= 1, which is something we have guarded against in the code above
							if (orig_n_iter->insize_dim1 == orig_n_iter->reducesize_dim1) {
								cerr << "\nError GraphReplicate006: Something weird is going on! Replication factor for the reduction kernel " << orig_n_iter->name << " is a very unusual number.\n";
								cerr << "\nReplication factor is " << orig_n_iter->replication_factor << ", while the second dimension of input stream and output stream are the same.\n";
								cerr << "\nReplication factor should be an integer greater than 0.\n";
								exit (1);
							}
							// In the first phase we reduce elements of each row, which is equivalent to 1-D reduction from X*Y to X*B elements
							// First preserve the original sizes of input and reduce streams
							int insize_dim0_preserved, insize_dim1_preserved, reducesize_dim0_preserved, reducesize_dim1_preserved;
							insize_dim0_preserved = orig_n_iter->insize_dim0;
							insize_dim1_preserved = orig_n_iter->insize_dim1;
							reducesize_dim0_preserved = orig_n_iter->reducesize_dim0;
							reducesize_dim1_preserved = orig_n_iter->reducesize_dim1;
							orig_n_iter->reducenodehandling = Reduce_2d_2Phase;
							orig_n_iter->insize_dim0 = orig_n_iter->insize_dim0*orig_n_iter->insize_dim1;
							orig_n_iter->insize_dim1 = -1;
							orig_n_iter->reducesize_dim0 = insize_dim0_preserved*reducesize_dim1_preserved;
							orig_n_iter->reducesize_dim1 = -1;
							// Now have to change the name of the kernel from 2d2d into 1d1d
							string temp_string("_2d2d_replica_");
							size_t loc = orig_n_iter->name.find(temp_string, 0);
							orig_n_iter->name.replace (loc, temp_string.length(), "_1d1d_replica_");
							// Check if the mere act of splitting the 2-D reduction in 2-phases achieved the desired speedup
							if (orig_n_iter->replication_factor <= (unsigned)((insize_dim0_preserved/reducesize_dim0_preserved))) {
								// In this case we only need one node with 1d1d reduction, because the first phase is
								// already faster than the non-replicated case 
								string new_name = orig_n_iter->name.substr(0, orig_n_iter->name.size()-1);
								ostringstream instance_number;
								instance_number << "0";
								new_name += instance_number.str();
								GraphNode new_node (new_name, 0);
								new_node.setReduce();
								new_node.is_leaf = true;
								new_node.my_index = 0;
								int elements_to_process = insize_dim1_preserved/reducesize_dim1_preserved;
								new_node.elements_to_process_1 = elements_to_process;
								new_node.elements_to_process_2 = elements_to_process;
								new_node.total_elements_to_process = insize_dim0_preserved*insize_dim1_preserved;
								this->nodes.push_back (new_node);
								// Add a pointer from the old graph to the first replica in the new graph
								orig_n_iter->copy_ptr = &(this->nodes.back());
								orig_n_iter->root_reduction_replica = &(this->nodes.back());
								orig_n_iter->replicated_leaves = 1;
								orig_n_iter->trees = 1;
							} else {
								// The rest is the same as for the 1-D case
								// Variable tree_limit contains the maximum speedup achievable by building a single tree
								// (relative to the reduction implemented as a single kernel - even without 2 phases)
								double tree_limit = (1.0*orig_n_iter->insize_dim0*orig_n_iter->insize_dim1)/(2.0*orig_n_iter->reducesize_dim0*orig_n_iter->reducesize_dim1);
								if ((1.0*orig_n_iter->replication_factor) <= tree_limit) {
									// This means we can achieve desired speedup just by building a single tree
									// The speedup of the tree does not have to be equal the original required speedup,
									// but rather original speedup divided by the speedup already achieved through splitting the original reduction into two phases
									// That speedup for phase 1 was X/A, therefore, the tree only has to achieve speedup of S/(X/A), where S is the original desired speedup
									build_trees (*orig_n_iter, 1, orig_n_iter->insize_dim0, orig_n_iter->reducesize_dim0, ((1.0*orig_n_iter->replication_factor)/(orig_n_iter->insize_dim0/orig_n_iter->reducesize_dim0)), collectors, doubles, (*((orig_n_iter->in_edges).begin()))->dest_var, (*((orig_n_iter->out_edges).begin())).source_var, word_size);
									orig_n_iter->trees = 1;
								} else  {
									// If we are here, it means we need to build more than one tree
									int num_trees;
									// Essentially increase the number of trees, until the number of trees satisfies the desired replication
									// start with 2, because we already know it cannot be done with only one tree
									for (num_trees = 2; ((1.0*orig_n_iter->replication_factor)/num_trees) > tree_limit; num_trees++);
									// Now build num_trees of an appropriate size
									// Again take into account that X/A speedup has already been achieved by splitting the original reduction into 2 phases
									build_trees (*orig_n_iter, num_trees, orig_n_iter->insize_dim0, orig_n_iter->reducesize_dim0, (((1.0*orig_n_iter->replication_factor)/num_trees)/(orig_n_iter->insize_dim0/orig_n_iter->reducesize_dim0)), collectors, doubles, (*((orig_n_iter->in_edges).begin()))->dest_var, (*((orig_n_iter->out_edges).begin())).source_var, word_size);
									orig_n_iter->trees = num_trees;
								}
							}
							// Now have to change the name of the kernel back from 1d1d into 2d2d for the second phase
							temp_string = "_1d1d_replica_";
							loc = orig_n_iter->name.find(temp_string, 0);
							orig_n_iter->name.replace (loc, temp_string.length(), "_2d2d_replica_");
							
							// In the second phase, we need to perform 2-D reduction [X,B] into [A,B]
							// We already know that X != A, because that was handled elsewhere
							// We also know that the second phase does not have to be replicated, because that will be handled below
							// Therefore, we just have to instantiate 1 node that performs 2-D reduction with appropriate sizes
							// and connect it to the root of the tree implementing the first phase
							// The new node becomes the root
							string new_name = orig_n_iter->name;
							// Make the replica number for this node be equal 0, because this is the only 2d2d node
							GraphNode new_node (new_name, 0);
							new_node.setReduce();
							this->nodes.push_back (new_node);
							GraphNode* new_root = &(this->nodes.back());
							orig_n_iter->phase_2_ptr = new_root;
							orig_n_iter->nodes_in_phase_2 = 1;
							// Also add an edge into the graph
							GraphEdge &temp_edge = this->addEdge (orig_n_iter->name, *(orig_n_iter->root_reduction_replica), *(new_root), false, 0, orig_n_iter->out_streams.front().word_size);
							temp_edge.source_var = orig_n_iter->out_streams.front().stream_var;
							temp_edge.dest_var = orig_n_iter->in_streams.front().stream_var;
							if (orig_n_iter->out_streams.front().stream_of_arrays || orig_n_iter->in_streams.front().stream_of_arrays) {
								// If either source or destination (or both) is marked as carrying a stream of arrays, then this edge carries stream of arrays
								temp_edge.stream_of_arrays = true;
								if (orig_n_iter->out_streams.front().array_size != orig_n_iter->in_streams.front().array_size) {
									fatal ("Inside Graph::Connect(): Array sizes for a stream of arrays at the edge source and destination do not match (2)");
								}
								if (orig_n_iter->out_streams.front().word_size != orig_n_iter->in_streams.front().word_size) {
									fatal ("Inside Graph::Connect(): Word sizes for a stream of arrays at the edge source and destination do not match (2)");
								}
								temp_edge.array_size = orig_n_iter->out_streams.front().array_size;
								temp_edge.word_size = orig_n_iter->out_streams.front().word_size;
							}
							orig_n_iter->root_reduction_replica = new_root;
							new_root->insize_dim0 = insize_dim0_preserved;
							new_root->insize_dim1 = reducesize_dim1_preserved;
							new_root->reducesize_dim0 = reducesize_dim0_preserved;
							new_root->reducesize_dim1 = reducesize_dim1_preserved;
							// Add a pointer from the last replica (before adding the new node) to the new root
							// First find the last replica
							GraphNode *temp = orig_n_iter->copy_ptr;
							while (temp->copy_ptr != NULL) {
								temp = temp->copy_ptr;
							}
							// Then link the replicas together
							temp->copy_ptr = new_root;

						} else {
							// Otherwise the second phase has to be replicated as well
							// First preserve the original sizes of input and reduce streams
							int insize_dim0_preserved, insize_dim1_preserved, reducesize_dim0_preserved, reducesize_dim1_preserved;
							insize_dim0_preserved = orig_n_iter->insize_dim0;
							insize_dim1_preserved = orig_n_iter->insize_dim1;
							reducesize_dim0_preserved = orig_n_iter->reducesize_dim0;
							reducesize_dim1_preserved = orig_n_iter->reducesize_dim1;
							orig_n_iter->reducenodehandling = Reduce_2d_2Phase_Both_Replicated;
							// In this case if Y == B, that means the first phase has nothing to do
							if (orig_n_iter->insize_dim1 == orig_n_iter->reducesize_dim1) {
								// Nothing to do in the first phase, because there is no reduction within rows
							} else {
								// Do the first phase
								// In the first phase we reduce elements of each row, which is equivalent to 1-D reduction from X*Y to X*B elements
								orig_n_iter->insize_dim0 = orig_n_iter->insize_dim0*orig_n_iter->insize_dim1;
								orig_n_iter->insize_dim1 = -1;
								orig_n_iter->reducesize_dim0 = insize_dim0_preserved*reducesize_dim1_preserved;
								orig_n_iter->reducesize_dim1 = -1;
								// Now have to change the name of the kernel from 2d2d into 1d1d
								string temp_string("_2d2d_replica_");
								size_t loc = orig_n_iter->name.find(temp_string, 0);
								orig_n_iter->name.replace (loc, temp_string.length(), "_1d1d_replica_");
								// Check if the mere act of splitting the 2-D reduction in 2-phases achieved the desired speedup
								if (orig_n_iter->replication_factor <= (unsigned)((insize_dim0_preserved/reducesize_dim0_preserved))) {
									// In this case we only need one node with 1d1d reduction, because the first phase is
									// already faster than the non-replicated case 
									string new_name = orig_n_iter->name.substr(0, orig_n_iter->name.size()-1);
									ostringstream instance_number;
									instance_number << "0";
									new_name += instance_number.str();
									GraphNode new_node (new_name, 0);
									new_node.setReduce();
									new_node.is_leaf = true;
									new_node.my_index = 0;
									int elements_to_process = insize_dim1_preserved/reducesize_dim1_preserved;
									new_node.elements_to_process_1 = elements_to_process;
									new_node.elements_to_process_2 = elements_to_process;
									new_node.total_elements_to_process = insize_dim0_preserved*insize_dim1_preserved;
									this->nodes.push_back (new_node);
									// Add a pointer from the old graph to the first replica in the new graph
									orig_n_iter->copy_ptr = &(this->nodes.back());
									orig_n_iter->root_reduction_replica = &(this->nodes.back());
									orig_n_iter->replicated_leaves = 1;
									orig_n_iter->trees = 1;
								} else {
									// The rest is the same as for the 1-D case
									// Variable tree_limit contains the maximum speedup achievable by building a single tree
									// (relative to the reduction implemented as a single kernel - even without 2 phases)
									double tree_limit = (1.0*orig_n_iter->insize_dim0*orig_n_iter->insize_dim1)/(2.0*orig_n_iter->reducesize_dim0*orig_n_iter->reducesize_dim1);
									if ((1.0*orig_n_iter->replication_factor) <= tree_limit) {
										// This means we can achieve desired speedup just by building a single tree
										// The speedup of the tree does not have to be equal the original required speedup,
										// but rather original speedup divided by the speedup already achieved through splitting the original reduction into two phases
										// That speedup for phase 1 was X/A, therefore, the tree only has to achieve speedup of S/(X/A), where S is the original desired speedup
										build_trees (*orig_n_iter, 1, orig_n_iter->insize_dim0, orig_n_iter->reducesize_dim0, ((1.0*orig_n_iter->replication_factor)/(orig_n_iter->insize_dim0/orig_n_iter->reducesize_dim0)), collectors, doubles, (*((orig_n_iter->in_edges).begin()))->dest_var, (*((orig_n_iter->out_edges).begin())).source_var, word_size);
										orig_n_iter->trees = 1;
									} else  {
										// If we are here, it means we need to build more than one tree
										int num_trees;
										// Essentially increase the number of trees, until the number of trees satisfies the desired replication
										// start with 2, because we already know it cannot be done with only one tree
										for (num_trees = 2; ((1.0*orig_n_iter->replication_factor)/num_trees) > tree_limit; num_trees++);
										// Now build num_trees of an appropriate size
										// Again take into account that X/A speedup has already been achieved by splitting the original reduction into 2 phases
										build_trees (*orig_n_iter, num_trees, orig_n_iter->insize_dim0, orig_n_iter->reducesize_dim0, (((1.0*orig_n_iter->replication_factor)/num_trees)/(orig_n_iter->insize_dim0/orig_n_iter->reducesize_dim0)), collectors, doubles, (*((orig_n_iter->in_edges).begin()))->dest_var, (*((orig_n_iter->out_edges).begin())).source_var, word_size);
										orig_n_iter->trees = num_trees;
									}
								}
								// Now have to change the name of the kernel back from 1d1d into 2d2d for the second phase
								temp_string = "_1d1d_replica_";
								loc = orig_n_iter->name.find(temp_string, 0);
								orig_n_iter->name.replace (loc, temp_string.length(), "_2d2d_replica_");
							}
							// Do the second phase
							// First find out how exactly the second phase should be replicated, which depends on the desired speedup
							if (orig_n_iter->replication_factor <= (unsigned)(insize_dim1_preserved)) {
								// If replication factor is Y or lower, desired speedup can be achieved with B (or fewer) simple replicas
								// First find out how many replicas should be produced
								// Any number that divides B is acceptable as the number of replicas (as long as it meets the desired speedup)
								int replicas_phase2 = 0;
								for (replicas_phase2=2; replicas_phase2 < reducesize_dim1_preserved; replicas_phase2++) {
									if ((reducesize_dim1_preserved%replicas_phase2 == 0) && ((unsigned)(insize_dim1_preserved*replicas_phase2/reducesize_dim1_preserved) >= orig_n_iter->replication_factor)) {
										// We found the smallest number that works, stop
										break;
									}
								}
								// At this point we have the number of replicas to use
								// If the number of replicas is B, then each replica's task is equivalent to 1-D -> 1-D reduction
								if (replicas_phase2 == reducesize_dim1_preserved) {
									// Therefore, we change the name of the kernel from 2d2d into 1d1d
									string temp_string("_2d2d_replica_");
									size_t loc = orig_n_iter->name.find(temp_string, 0);
									orig_n_iter->name.replace (loc, temp_string.length(), "_1d1d_replica_");
									// We also set the sizes of inputs and outputs
									// The reduction is now equivalent to X->A 1-D -> 1-D reduction
									orig_n_iter->insize_dim0 = insize_dim0_preserved;
									orig_n_iter->insize_dim1 = -1;
									orig_n_iter->reducesize_dim0 = reducesize_dim0_preserved;
									orig_n_iter->reducesize_dim1 = -1;
								} else {
									// Otherwise, each replica performs a 2-D -> 2-D reduction
									// However, we still have to set the sizes of inputs and outputs
									// The reduction is now equal to  <X,B/replicas_phase2> -> <A,B/replicas_phase2> 2-D -> 2-D reduction
									orig_n_iter->insize_dim0 = insize_dim0_preserved;
									orig_n_iter->insize_dim1 = reducesize_dim1_preserved/replicas_phase2;
									orig_n_iter->reducesize_dim0 = reducesize_dim0_preserved;
									orig_n_iter->reducesize_dim1 = reducesize_dim1_preserved/replicas_phase2;
								}
								// Create the required number of replicas
								GraphNode* first_node_phase_2 = NULL;
								for (int i=0; i<replicas_phase2; i++) {
									string new_name = orig_n_iter->name.substr(0, orig_n_iter->name.size()-1);
									ostringstream instance_number;
									instance_number << i;
									new_name += instance_number.str();
									GraphNode new_node (new_name, i);
									new_node.insize_dim0 = orig_n_iter->insize_dim0;
									new_node.insize_dim1 = orig_n_iter->insize_dim1;
									new_node.reducesize_dim0 = orig_n_iter->reducesize_dim0;
									new_node.reducesize_dim1 = orig_n_iter->reducesize_dim1;
									// old_last pointer will point to the previously added node
									GraphNode* old_last = NULL;
									if (i != 0) {
										old_last = &(this->nodes.back());
									}
									this->nodes.push_back (new_node);
									if (0 == i) {
										// Save a pointer to the first replica
										first_node_phase_2 = &(this->nodes.back());
									} else {
										// For all other replicas, link them together
										// i.e. add a pointer from the previous replica to the newly added replica
										old_last->copy_ptr = &(this->nodes.back());
									}
								}
								orig_n_iter->phase_2_ptr = first_node_phase_2;
								orig_n_iter->nodes_in_phase_2 = replicas_phase2;
								GraphNode *distributor;
								// Create a distributor node to connect the two phases
								// (or collector/distributor node, in case the root node of the first phase is a collector)
								if (orig_n_iter->root_reduction_replica->name.find(BRCC_COLLECTOR, 0) != string::npos) {
									// The existing root is a collector, so we need to modify it to become collector/distributor
									ostringstream number;
									number << "_" << col_dis++;
									orig_n_iter->root_reduction_replica->name = string(BRCC_COLLECTOR_DISTRIBUTOR) + number.str();
									distributor = orig_n_iter->root_reduction_replica;
								} else {
									// Otherwise, the existing root is not a collector, so we need to introduce a new distributor node
									string temp_string = BRCC_DISTRIBUTOR;
									ostringstream number;
									number << "_" << distributors++;
									temp_string += number.str();
									GraphNode new_node (temp_string);
									this->nodes.push_back (new_node);
									distributor = &(this->nodes.back());
									// Add edge from the old root node to the new distributor node
									GraphEdge &temp_edge = this->addEdge ("temp_edge_to_phase2", *(orig_n_iter->root_reduction_replica), *distributor, false, 0, orig_n_iter->out_streams.front().word_size);
									temp_edge.source_var = orig_n_iter->out_streams.front().stream_var;
									if (orig_n_iter->out_streams.front().stream_of_arrays) {
										// If the source is marked as carrying a stream of arrays, then this edge carries stream of arrays
										temp_edge.stream_of_arrays = true;
										temp_edge.array_size = orig_n_iter->out_streams.front().array_size;
										temp_edge.word_size = orig_n_iter->out_streams.front().word_size;
									}
									// Make the distributor node the new root
									orig_n_iter->root_reduction_replica = distributor;
								}
								// Add edge from the distributor to every replica in phase 2 (replicas are conveniently linked through copy_ptr)
								GraphNode* temp = first_node_phase_2;
								while (temp != NULL) {
									GraphEdge &temp_edge = this->addEdge ("temp_edge_to_phase2", *distributor, *temp, false, 0, orig_n_iter->in_streams.front().word_size);
									temp_edge.dest_var = orig_n_iter->in_streams.front().stream_var;
									if (orig_n_iter->in_streams.front().stream_of_arrays) {
										// If the source is marked as carrying a stream of arrays, then this edge carries stream of arrays
										temp_edge.stream_of_arrays = true;
										temp_edge.array_size = orig_n_iter->in_streams.front().array_size;
										temp_edge.word_size = orig_n_iter->in_streams.front().word_size;
									}
									temp = temp->copy_ptr;
								}
								// Finally, add a pointer from the last replica (before adding the phas 2 nodes) to the first node in phase 2
								// First find the last replica
								temp = orig_n_iter->copy_ptr;
								while (temp->copy_ptr != NULL) {
									temp = temp->copy_ptr;
								}
								// Then link the replicas together
								temp->copy_ptr = first_node_phase_2;
							} else {
								//  Otherwise each of B replicas has to have one or more trees built (or we need more than B replicas, depending how you look at it)
								// Since this case is unlikely to ever be needed, I will not waste my time implementing it
								cout << "\nReplicating 2-D reduce kernels (the most general case) not supported yet!\n";
								exit (1);
							}
						}
					}
				}
			}
		}
	}
	// Iterate over all nodes to connect edges
	for (orig_n_iter=original.nodes.begin(); orig_n_iter != original.nodes.end(); orig_n_iter++) {
		// If replication factor is 1 (i.e. source is not replicated)
		if (orig_n_iter->replication_factor == 1) {
			// For every out edge
			for (orig_e_iter=orig_n_iter->out_edges.begin(); orig_e_iter!=orig_n_iter->out_edges.end(); orig_e_iter++) {
				// Check if the target of the edge is replicated
				GraphNode *target = orig_e_iter->destination;
				if (target->replication_factor == 1) {
					// If the target is not replicated, simply copy the existing edge to the new graph
					GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *(orig_n_iter->copy_ptr), *(target->copy_ptr), orig_e_iter->stream_of_arrays, orig_e_iter->array_size, orig_e_iter->word_size);
					temp_edge.source_var = orig_e_iter->source_var;
					temp_edge.dest_var = orig_e_iter->dest_var;
				} else {	// the target is replicated
					if ((orig_e_iter->destination->replicated_leaves != -1) && (orig_e_iter->destination->trees > 1)) {
						// If we are dealing with a replicated reduction kernel that contains multiple trees,
						// we only need one edge, because the double round-robin distributor is already there
						GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *(orig_n_iter->copy_ptr), *(orig_e_iter->destination->copy_ptr), false, 0, orig_e_iter->word_size);
						temp_edge.source_var = orig_e_iter->source_var;
					} else {
						// For other replicated kernels, a distributor is added here
						// Add distributor node
						string temp_string = BRCC_DISTRIBUTOR;
						ostringstream number;
						number << "_" << distributors++;
						temp_string += number.str();
						GraphNode new_node (temp_string);
						this->nodes.push_back (new_node);
						GraphNode *distributor = &(this->nodes.back());
						// Add edge from the source node to the new distributor node
						GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *(orig_n_iter->copy_ptr), *distributor, orig_e_iter->stream_of_arrays, orig_e_iter->array_size, orig_e_iter->word_size);
						temp_edge.source_var = orig_e_iter->source_var;
						// Add edge from the distributor to every replica (replicas are conveniently linked through copy_ptr)
						// Be careful about replicated reduction kernels. We only need to link it to the leaves of the reduction tree
						GraphNode* temp = orig_e_iter->destination->copy_ptr;
						if (orig_e_iter->destination->replicated_leaves == -1) {
							// This means we are dealing with an ordinary kernel, just connect edges to all replicas
							while (temp != NULL) {
								GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *distributor, *temp, orig_e_iter->stream_of_arrays, orig_e_iter->array_size, orig_e_iter->word_size);
								temp_edge.dest_var = orig_e_iter->dest_var;
								temp = temp->copy_ptr;
							}
						} else {
							// Otherwise, we are dealing with a replicated reduction kernel, in which case we only connect it to leaf nodes
							for (int node_counter=0; node_counter < orig_e_iter->destination->replicated_leaves; node_counter++) {
// __FIX_ME - The following check is here just for debugging - can remove it eventually
								if (NULL == temp) { cerr << "\nError Graph::Replicate::493782558483: Something's gone horribly wrong; temp is NULL\n"; exit(1);}
								GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *distributor, *temp, false, 0, orig_e_iter->word_size);
								temp_edge.dest_var = orig_e_iter->dest_var;
								temp = temp->copy_ptr;
							}
						}
					}
				}
			}
		} else {	// edge source is replicated
			// For every out edge
			for (orig_e_iter=orig_n_iter->out_edges.begin(); orig_e_iter!=orig_n_iter->out_edges.end(); orig_e_iter++) {
				// Check if the target of the edge is replicated
				GraphNode *target = orig_e_iter->destination;
				// If the target is not replicated
				if (target->replication_factor == 1) {
					// Check if we are dealing with replicated reduction kernel at the source
					if ((orig_n_iter->replicated_leaves == -1) || (orig_n_iter->reducenodehandling == Reduce_2d_2Phase_Both_Replicated)) {
						// This means we are dealing with an ordinary kernel at the source, which is replicated
						// or we are dealing with replicated reduction kernel, with two phases, in which the second phase has been replicated
						// and the second phase is not a tree
						// Since the target is not replicated, add a collector
						string temp_string = BRCC_COLLECTOR;
						ostringstream number;
						number << "_" << collectors++;
						temp_string += number.str();
						GraphNode new_node (temp_string);
						this->nodes.push_back (new_node);
						GraphNode *collector = &(this->nodes.back());
						// Add edge from every replica to the collector (replicas are conveniently linked through copy_ptr)
						GraphNode* temp;
						if (orig_n_iter->reducenodehandling == Reduce_2d_2Phase_Both_Replicated) {
							temp = orig_n_iter->phase_2_ptr;
						} else {
							temp = orig_n_iter->copy_ptr;
						}
						while (temp != NULL) {
							GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *temp, *collector, orig_e_iter->stream_of_arrays, orig_e_iter->array_size, orig_e_iter->word_size);
							temp_edge.source_var = orig_e_iter->source_var;
							temp = temp->copy_ptr;
						}
						// Add edge from the collector to the target
						GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *collector, *(orig_e_iter->destination->copy_ptr), orig_e_iter->stream_of_arrays, orig_e_iter->array_size, orig_e_iter->word_size);
						temp_edge.dest_var = orig_e_iter->dest_var;
					}  else {
						// This means that the source is a replicated reduction kernel
						// this means that we do not need a collector, because the reduction tree already has a single root node
						// Add edge from the reduction tree root to the target
						GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *(orig_n_iter->root_reduction_replica), *(orig_e_iter->destination->copy_ptr), false, 0, orig_e_iter->word_size);
						temp_edge.source_var = orig_e_iter->source_var;
						temp_edge.dest_var = orig_e_iter->dest_var;
					}
				} else {	// both source and target are replicated
					// Check if either source, or target (or both) are reduction kernels
					if ((orig_n_iter->replicated_leaves == -1) && (orig_e_iter->destination->replicated_leaves == -1)) {
						// This means that neither source nor target are reduction kernels
						if (orig_n_iter->replication_factor == target->replication_factor) {
							// If the replication factors are the same, we simply add edges between corresponding replicas
							// Replicas are conveniently linked through copy_ptr
							// We also add numbers to edge names so that FIFO names end up being unique
							GraphNode* temp_origin = orig_n_iter->copy_ptr;
							GraphNode* temp_destination = orig_e_iter->destination->copy_ptr;
							unsigned int counter=0;
							while (temp_origin != NULL && temp_destination != NULL) {
								string temp_name = orig_e_iter->name;
								ostringstream suffix;
								suffix << "_replica_" << counter++;
								temp_name += suffix.str();
								GraphEdge &temp_edge = this->addEdge (temp_name, *temp_origin, *temp_destination, orig_e_iter->stream_of_arrays, orig_e_iter->array_size, orig_e_iter->word_size);
								temp_edge.source_var = orig_e_iter->source_var;
								temp_edge.dest_var = orig_e_iter->dest_var;
								temp_origin = temp_origin->copy_ptr;
								temp_destination = temp_destination->copy_ptr;
							}
						} else {	// replication factors do not match
							// If replication factors do not match, we add a collector/distributor (C/D) node
// The following code was an optimization attempt for the case where replication factors do not match, but one divides the other
// The simple idea is that in such a case we don't need a collector/distributor node, but can use several collectors (when source has more replicas
// than destination) or several distributors (when destination has more replicas). This could alleviate potential bottlenecks that C/D nodes may present.
// Unfortunately, this idea doesn't work in a general case because it results in different distribution of elements among replicas compared to what a C/D node would produce.
// It still has a merit in certain cases when both collectos and distributors can be arranged in the same way on both ends of a replicated kernel
// Consider three kernels A->B->C. A is replicated 2 times, B is replicated 4 times and C is replicated two times. In such a case it would work
// But if C is replicated only once, a collector before C would not restore the original element order.
// For now I will let go of this idea altogether, but will leave this code in place for future development.
							//if ((orig_n_iter->replication_factor%target->replication_factor == 0) || (target->replication_factor%orig_n_iter->replication_factor == 0)) {
							//	// Since replication factors are divisible we add collectors or distributors, depending whether source or target has larger replication factor
							//	// As an example, if source is replicated 6 times and destination 2 times, we use 2 collector nodes (each with 3 inputs, i.e. 3-to-1 collector)
							//	// On the other hand, if source is replicated 2 times and destination 6 times, we use 2 distributor nodes (each with 3 outputs, i.e. 1-to-3 distributor)
							//	if (orig_n_iter->replication_factor > target->replication_factor) {
							//		// Since the source is replicated more than the target, add collectors
							//		// Add as many collectors as there are replicas in the target node
							//		// First obtain the pointer to the first replica of the source and target nodes
							//		GraphNode *temp_source, *temp_destination;
							//		temp_source = orig_n_iter->copy_ptr;
							//		temp_destination = orig_e_iter->destination->copy_ptr;
							//		for (unsigned int i=0; i < target->replication_factor; i++) {
							//			string temp_string = BRCC_COLLECTOR;
							//			ostringstream number;
							//			number << "_" << collectors++;
							//			temp_string += number.str();
							//			GraphNode new_node (temp_string);
							//			this->nodes.push_back (new_node);
							//			GraphNode *collector = &(this->nodes.back());
							//			// Add edge from the appropriate number of source replicas to this collector (replicas are conveniently linked through copy_ptr)
							//			for (unsigned int j=0; j < (orig_n_iter->replication_factor/target->replication_factor); j++) {
							//				GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *temp_source, *collector, orig_e_iter->stream_of_arrays, orig_e_iter->array_size, orig_e_iter->word_size);
							//				temp_edge.source_var = orig_e_iter->source_var;
							//				temp_source = temp_source->copy_ptr;
							//			}
							//			// Add edge from the collector to the target
							//			GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *collector, *(temp_destination), orig_e_iter->stream_of_arrays, orig_e_iter->array_size, orig_e_iter->word_size);
							//			temp_edge.dest_var = orig_e_iter->dest_var;
							//			temp_destination = temp_destination->copy_ptr;
							//		}
							//	} else {
							//		// Since the target is replicated more than the source, add distributors
							//		// Add as many distributors as there are replicas in the source node
							//		// First obtain the pointer to the first replica of the source and target nodes
							//		GraphNode *temp_source, *temp_destination;
							//		temp_source = orig_n_iter->copy_ptr;
							//		temp_destination = orig_e_iter->destination->copy_ptr;
							//		for (unsigned int i=0; i < orig_n_iter->replication_factor; i++) {
							//			string temp_string = BRCC_DISTRIBUTOR;
							//			ostringstream number;
							//			number << "_" << distributors++;
							//			temp_string += number.str();
							//			GraphNode new_node (temp_string);
							//			this->nodes.push_back (new_node);
							//			GraphNode *distributor = &(this->nodes.back());
							//			// Add edge from the current source node to the new distributor node
							//			GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *(temp_source), *distributor, orig_e_iter->stream_of_arrays, orig_e_iter->array_size, orig_e_iter->word_size);
							//			temp_edge.source_var = orig_e_iter->source_var;
							//			temp_source = temp_source->copy_ptr;
							//			// Add edge from the distributor to the appropriate number of target replicas (replicas are conveniently linked through copy_ptr)
							//			for (unsigned int j=0; j < (target->replication_factor/orig_n_iter->replication_factor); j++) {
							//				GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *distributor, *temp_destination, orig_e_iter->stream_of_arrays, orig_e_iter->array_size, orig_e_iter->word_size);
							//				temp_edge.dest_var = orig_e_iter->dest_var;
							//				temp_destination = temp_destination->copy_ptr;
							//			}
							//		}
							//	}
							//} else {
							//	// If replication factors do not match and are not divisible by one another, we add a collector/distributor (C/D) node
								string temp_string = BRCC_COLLECTOR_DISTRIBUTOR;
								ostringstream number;
								number << "_" << col_dis++;
								temp_string += number.str();
								GraphNode new_node (temp_string);
								this->nodes.push_back (new_node);
								GraphNode *cd = &(this->nodes.back());
								// Add edges from each replica of the original node to the C/D node
								// Replicas are conveniently linked through copy_ptr
								GraphNode* temp_origin = orig_n_iter->copy_ptr;
								while (temp_origin != NULL) {
									GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *temp_origin, *cd, orig_e_iter->stream_of_arrays, orig_e_iter->array_size, orig_e_iter->word_size);
									temp_edge.source_var = orig_e_iter->source_var;
									temp_origin = temp_origin->copy_ptr;
								}
								// Add edges from the C/D node to each replica of the destination node
								// Replicas are conveniently linked through copy_ptr
								GraphNode* temp_destination = orig_e_iter->destination->copy_ptr;
								while (temp_destination != NULL) {
									GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *cd, *temp_destination, orig_e_iter->stream_of_arrays, orig_e_iter->array_size, orig_e_iter->word_size);
									temp_edge.dest_var = orig_e_iter->dest_var;
									temp_destination = temp_destination->copy_ptr;
								}
							//}
						}
					} else {
						// Either source, or target (or both) are reduction kernels
						// Let us distinguish between these three cases
						if ((orig_n_iter->replicated_leaves != -1) && (orig_e_iter->destination->replicated_leaves == -1)) {
							// Source is reduction, the target is not.
							if (orig_n_iter->reducenodehandling == Reduce_2d_2Phase_Both_Replicated) {
								// In this case the source is a replicated 2-D reduction with 2 phases (both replicated),
								// so it does NOT have a collector at the end
								// Check if the replication factor of the 2nd phase matches replication factor of the destination
								if  (orig_n_iter->nodes_in_phase_2 == orig_e_iter->destination->replication_factor) {
									// If they match, we simply have to connect corresponding nodes
									GraphNode *temp_src, *temp_dest;
									temp_src = orig_n_iter->phase_2_ptr;
									temp_dest = orig_e_iter->destination->copy_ptr;
									while ((temp_src != NULL) && (temp_dest != NULL)) {
										GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *temp_src, *temp_dest, false, 0, orig_e_iter->word_size);
										temp_edge.source_var = orig_e_iter->source_var;
										temp_edge.dest_var = orig_e_iter->dest_var;
										temp_src = temp_src->copy_ptr;
										temp_dest = temp_dest->copy_ptr;
									}
								} else {
									// If the replication factors do not match, we need a collector/distributor node
									string temp_string = BRCC_COLLECTOR_DISTRIBUTOR;
									ostringstream number;
									number << "_" << col_dis++;
									temp_string += number.str();
									GraphNode new_node (temp_string);
									this->nodes.push_back (new_node);
									GraphNode *cd = &(this->nodes.back());
									// Add edges from each replica of the source node to the C/D node
									// Replicas are conveniently linked through copy_ptr
									GraphNode* temp_origin = orig_n_iter->phase_2_ptr;
									int node_counter = 0;
									while (temp_origin != NULL) {
										temp_origin->node_order = node_counter++;
										GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *temp_origin, *cd, false, 0, orig_e_iter->word_size);
										temp_edge.source_var = orig_e_iter->source_var;
										temp_origin = temp_origin->copy_ptr;
									}
									// Add edges from the C/D node to each replica of the destination node
									// Replicas are conveniently linked through copy_ptr
									GraphNode* temp_destination = orig_e_iter->destination->copy_ptr;
									while (temp_destination != NULL) {
										GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *cd, *temp_destination, false, 0, orig_e_iter->word_size);
										temp_edge.dest_var = orig_e_iter->dest_var;
										temp_destination = temp_destination->copy_ptr;
									}
								}
							} else {
								// In this case, the source is NOT a 2-phase reduction							
								// Therefore, the source has only one node (the root) to connect
								// If the source has multiple trees, the root node is a collector,
								// and it should be changed into a collector distributor
								if (orig_n_iter->trees > 1) {
									// We do this by simply changing the name
									string temp_string = BRCC_COLLECTOR_DISTRIBUTOR;
									GraphNode *collector_distributor = orig_n_iter->root_reduction_replica;
									collector_distributor->name = temp_string;
									// Now connect the collector distributor to every replica of the destination
									GraphNode* temp = orig_e_iter->destination->copy_ptr;
									while (temp != NULL) {
										GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *collector_distributor, *temp, false, 0, orig_e_iter->word_size);
										temp_edge.dest_var = orig_e_iter->dest_var;
										temp = temp->copy_ptr;
									}
								} else {
									// Add distributor node
									string temp_string = BRCC_DISTRIBUTOR;
									ostringstream number;
									number << "_" << distributors++;
									temp_string += number.str();
									GraphNode new_node (temp_string);
									this->nodes.push_back (new_node);
									GraphNode *distributor = &(this->nodes.back());
									// Add edge from the source's root node to the new distributor node
									GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *(orig_n_iter->root_reduction_replica), *distributor, false, 0, orig_e_iter->word_size);
									temp_edge.source_var = orig_e_iter->source_var;
									// Add edge from the distributor to every replica (replicas are conveniently linked through copy_ptr)
									GraphNode* temp = orig_e_iter->destination->copy_ptr;
									while (temp != NULL) {
										GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *distributor, *temp, false, 0, orig_e_iter->word_size);
										temp_edge.dest_var = orig_e_iter->dest_var;
										temp = temp->copy_ptr;
									}
								}
							}
						}  else if ((orig_n_iter->replicated_leaves == -1) && (orig_e_iter->destination->replicated_leaves != -1)) {
							// Source is not a reduction, the target is a reduction, but they are both replicated							
							if (orig_e_iter->destination->trees > 1) {
								// If the target is a replicated reduction kernel that contains multiple trees,
								// the double round-robin distributor is already there
								// Since the source is replicated (but not a reduction), it has several replicas
								// that need to be connected to a collector
								// Label the double distributor node to indicate that it is preceded by a collector node
								orig_e_iter->destination->copy_ptr->preceded_by_a_collector = true;
								string temp_string = BRCC_COLLECTOR;
								ostringstream number;
								number << "_" << collectors++;
								temp_string += number.str();
								GraphNode new_node (temp_string);
								this->nodes.push_back (new_node);
								GraphNode *collector = &(this->nodes.back());
								// Add edge from every replica of the source to the collector
								GraphNode* temp = orig_n_iter->copy_ptr;
								while (temp != NULL) {
									GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *temp, *collector, false, 0, orig_e_iter->word_size);
									temp_edge.source_var = orig_e_iter->source_var;
									temp = temp->copy_ptr;
								}
								// Add edge from the collector to the target
								GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *collector, *(orig_e_iter->destination->copy_ptr), false, 0, orig_e_iter->word_size);
								temp_edge.dest_var = orig_e_iter->dest_var;
							} else {
								// If the target does not contain multiple trees:
								// Check if the source's replication factor matches the # of leaf nodes in the target
								if (orig_n_iter->replication_factor == target->replicated_leaves) {
									// If so, simply add an edge between corresponding replicas
									// Replicas are conveniently linked through copy_ptr
									// We also add numbers to edge names so that FIFO names end up being unique
									GraphNode* temp_origin = orig_n_iter->copy_ptr;
									GraphNode* temp_destination = orig_e_iter->destination->copy_ptr;
									unsigned int counter=0;
									while (temp_origin != NULL && temp_destination != NULL) {
										string temp_name = orig_e_iter->name;
										ostringstream suffix;
										suffix << "_replica_" << counter++;
										temp_name += suffix.str();
										GraphEdge &temp_edge = this->addEdge (temp_name, *temp_origin, *temp_destination, false, 0, orig_e_iter->word_size);
										temp_edge.source_var = orig_e_iter->source_var;
										temp_edge.dest_var = orig_e_iter->dest_var;
										temp_origin = temp_origin->copy_ptr;
										temp_destination = temp_destination->copy_ptr;
									}
								} else {
									// If these two numbers do not match, we need a collector/distributor (C/D) node
									// Unless the number of leaves in the target is 1 (there is one convoluted case like that)
									string temp_string;
									ostringstream number;
									if (target->replicated_leaves == 1) {
										temp_string = BRCC_COLLECTOR;
										number << "_" << collectors++;
									} else {
										temp_string = BRCC_COLLECTOR_DISTRIBUTOR;
										number << "_" << col_dis++;
									}
									temp_string += number.str();
									GraphNode new_node (temp_string);
									this->nodes.push_back (new_node);
									GraphNode *cd = &(this->nodes.back());
									// Add edges from each replica of the original node to the C/D node
									// Replicas are conveniently linked through copy_ptr
									GraphNode* temp_origin = orig_n_iter->copy_ptr;
									while (temp_origin != NULL) {
										GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *temp_origin, *cd, false, 0, orig_e_iter->word_size);
										temp_edge.source_var = orig_e_iter->source_var;
										temp_origin = temp_origin->copy_ptr;
									}
									// Add edges from the C/D node to each leaf of the reduction tree
									// Replicas are conveniently linked through copy_ptr
									GraphNode* temp_destination = orig_e_iter->destination->copy_ptr;

									for (int node_counter=0; node_counter < orig_e_iter->destination->replicated_leaves; node_counter++) {
// __FIX_ME - The following check is here just for debugging - can remove it eventually
										if (NULL == temp_destination) { cerr << "\nError Graph::Replicate::435409075754: Something's gone horribly wrong; temp_destination is NULL\n"; exit(1);}
										GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *cd, *temp_destination, false, 0, orig_e_iter->word_size);
										temp_edge.dest_var = orig_e_iter->dest_var;
										temp_destination = temp_destination->copy_ptr;

									}
								}
							}
						} else {
							// Both source and destination are reductions and they are both replicated.
							// Therefore, the source has only one node (the root) to connect
							// unless it is a 2-phase reduction
							if (orig_e_iter->destination->trees > 1) {
								// If the target is a replicated reduction kernel that contains multiple trees,
								// the double round-robin distributor is already there
								if (orig_n_iter->reducenodehandling == Reduce_2d_2Phase_Both_Replicated) {
									// If the source has 2-phases (both replicated), we need to add a collector node to the 2nd phase
									string temp_string = BRCC_COLLECTOR;
									ostringstream number;
									number << "_" << collectors++;
									temp_string += number.str();
									GraphNode new_node (temp_string);
									this->nodes.push_back (new_node);
									GraphNode *collector = &(this->nodes.back());
									// Add edge from every replica of the source to the collector
									GraphNode* temp = orig_n_iter->phase_2_ptr;
									while (temp != NULL) {
										GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *temp, *collector, false, 0, orig_e_iter->word_size);
										temp_edge.source_var = orig_e_iter->source_var;
										temp = temp->copy_ptr;
									}
									// Set the new collector as the root
									orig_n_iter->root_reduction_replica = collector;
									// We also have to set preceded_by_a_collector to true in the double distributor node
									orig_e_iter->destination->copy_ptr->preceded_by_a_collector = true;
								}
								// Regardless whether the source has 2 phases or not,
								// we need one edge from the root to the double round-robin distributor
								GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *(orig_n_iter->root_reduction_replica), *orig_e_iter->destination->copy_ptr, false, 0, orig_e_iter->word_size);
								temp_edge.source_var = orig_e_iter->source_var;								
							} else {
								// In this case destination is a replicated reduction kernel with only one tree

								if (orig_n_iter->reducenodehandling == Reduce_2d_2Phase_Both_Replicated) {
									// In this case the source is a replicated 2-D reduction with 2 phases (both replicated),
									// so it does NOT have a collector at the end
									// Check if the replication factor of the 2nd phase matches the number of leaves in the tree of the destination
									if  (orig_n_iter->nodes_in_phase_2 == orig_e_iter->destination->replicated_leaves) {
										// If they match, we simply have to connect corresponding nodes
										GraphNode *temp_src, *temp_dest;
										temp_src = orig_n_iter->phase_2_ptr;
										temp_dest = orig_e_iter->destination->copy_ptr;
										while ((temp_src != NULL) && (temp_dest != NULL)) {
											GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *temp_src, *temp_dest, false, 0, orig_e_iter->word_size);
											temp_edge.source_var = orig_e_iter->source_var;
											temp_edge.dest_var = orig_e_iter->dest_var;
											temp_src = temp_src->copy_ptr;
											temp_dest = temp_dest->copy_ptr;
										}
									} else {
										// If the replication factors do not match, we need a collector/distributor node
										string temp_string = BRCC_COLLECTOR_DISTRIBUTOR;
										ostringstream number;
										number << "_" << col_dis++;
										temp_string += number.str();
										GraphNode new_node (temp_string);
										this->nodes.push_back (new_node);
										GraphNode *cd = &(this->nodes.back());
										// Add edges from each replica of the source node to the C/D node
										// Replicas are conveniently linked through copy_ptr
										GraphNode* temp_origin = orig_n_iter->phase_2_ptr;
										int node_counter = 0;
										while (temp_origin != NULL) {
											temp_origin->node_order = node_counter++;
											GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *temp_origin, *cd, false, 0, orig_e_iter->word_size);
											temp_edge.source_var = orig_e_iter->source_var;
											temp_origin = temp_origin->copy_ptr;
										}
										// Add edges from the C/D node to each replica of the destination node
										// Replicas are conveniently linked through copy_ptr
										GraphNode* temp_destination = orig_e_iter->destination->copy_ptr;
										while (temp_destination != NULL) {
											GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *cd, *temp_destination, false, 0, orig_e_iter->word_size);
											temp_edge.dest_var = orig_e_iter->dest_var;
											temp_destination = temp_destination->copy_ptr;
										}
									}
								} else {
									// In this case, the source is NOT a 2-phase reduction							
									// That means that it has only one root node
									// Add distributor node
									string temp_string = BRCC_DISTRIBUTOR;
									ostringstream number;
									number << "_" << distributors++;
									temp_string += number.str();
									GraphNode new_node (temp_string);
									this->nodes.push_back (new_node);
									GraphNode *distributor = &(this->nodes.back());
									// Add edge from the source's root node to the new distributor node
									GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *(orig_n_iter->root_reduction_replica), *distributor, false, 0, orig_e_iter->word_size);
									temp_edge.source_var = orig_e_iter->source_var;
									// Add edge from the distributor to every leaf of the reduction tree
									GraphNode* temp = orig_e_iter->destination->copy_ptr;
									// Otherwise, we are dealing with a replicated reduction kernel, in which case we only connect it to leaf nodes
									for (int node_counter=0; node_counter < orig_e_iter->destination->replicated_leaves; node_counter++) {
// __FIX_ME - The following check is here just for debugging - can remove it eventually
										if (NULL == temp) { cerr << "\nError Graph::Replicate::493782558483: Something's gone horribly wrong; temp is NULL\n"; exit(1);}
										GraphEdge &temp_edge = this->addEdge (orig_e_iter->name, *distributor, *temp, false, 0, orig_e_iter->word_size);
										temp_edge.dest_var = orig_e_iter->dest_var;
										temp = temp->copy_ptr;
									}
								}
							}
						}
					}
				}
			}
		}
	}
}

void Graph::build_trees (GraphNode &original, int num_trees, int in_size, int reduce_size, double speedup, unsigned int &collectors, unsigned int &doubles, std::string in_stream_name, std::string reduce_stream_name, int word_size) {

	// First find out the number of elements each kernel can process
	int max_elements;
	// We start with 2, because nothing lower makes any sense for a reduction operation
	for (max_elements=2; ((1.0*in_size/reduce_size)/max_elements) >= speedup; max_elements++);
	// The above loop overshoots by 1, so we need to compensate for that
	max_elements--;
	// As we build the tree from left to right (or from leaves to the root), we will keep track of
	// how many kernels are produced in each column (column = 1 level of the tree => picture the tree sideways, with leaves
	// on the left and root on the right. Column refers to all nodes that are aligned one above another).
	// We have to keep adding new columns until there is only one kernel left in a column
	int kernels_in_a_column = 0;
	int elements_left = in_size/reduce_size;
	int replica_counter = 0;
	int column_counter = 0;
	int order_counter = 0;
	GraphNode *final_collector = NULL, *double_distributor = NULL;

	if (num_trees > 1) {
		// If we need to build more than one tree, we need one final collector node
		// that will merge results from the roots of different trees
		string temp_string = BRCC_COLLECTOR;
		ostringstream number;
		number << "_" << collectors++;
		temp_string += number.str();
		GraphNode new_node_collector (temp_string);
		this->nodes.push_back (new_node_collector);
		final_collector = &(this->nodes.back());
		// We also need a double round-robin distributor node
		temp_string = BRCC_DOUBLE_DISTRIBUTOR;
		ostringstream number2;
		number2 << "_" << doubles++;
		temp_string += number2.str();
		GraphNode new_node_double (temp_string);
		new_node_double.trees = num_trees;
		new_node_double.insize_dim0 = original.insize_dim0;
		new_node_double.insize_dim1 = original.insize_dim1;
		new_node_double.reducesize_dim0 = original.reducesize_dim0;
		new_node_double.reducesize_dim1 = original.reducesize_dim1;
		this->nodes.push_back (new_node_double);
		double_distributor = &(this->nodes.back());
	}
	for (int tree = 0; tree < num_trees; tree++) {
		kernels_in_a_column = 0;
		elements_left = in_size/reduce_size;
		column_counter = 0;
		// Handle the first column (i.e. column 0), as a special case
		while (elements_left > 0) {
			// Add another kernel
			// Will reuse replication factor to keep track of the replica id for the node
			// i.e. replication factor in the replicated graph actually contains a different number
			// for each replica of the original node
			string new_name = original.name.substr(0, original.name.size()-1);
			ostringstream instance_number;
			instance_number << replica_counter;
			new_name += instance_number.str();
			GraphNode new_node (new_name, replica_counter);
			new_node.setReduce();
			// All nodes in the first column have weight 1
			new_node.weight = 1;

			// old_last pointer will point to the previously added node
			GraphNode* old_last = NULL;
			if (replica_counter != 0) {
				old_last = &(this->nodes.back());
			}
			this->nodes.push_back (new_node);
			if ((0 == kernels_in_a_column)) {
				// Add a pointer from the old graph to the first replica in the new graph
				original.copy_ptr = &(this->nodes.back());
			}
			if (replica_counter != 0) {
				// For all other replicas, link them together
				// i.e. add a pointer from the previous replica to the newly added replica
				old_last->copy_ptr = &(this->nodes.back());
			}
			if ((0 == replica_counter) && (num_trees > 1)) {
				double_distributor->copy_ptr = &(this->nodes.back());
			}
			// If there are multiple trees, add edges from the double distributor to the new leaf node
			if (num_trees > 1) {
				GraphEdge &temp_edge = this->addEdge (original.name, *double_distributor, (this->nodes.back()), false, 0, word_size);
				temp_edge.dest_var = in_stream_name;
				// Set the order number, so that double-distributor can be correctly connected to the leaves of trees
				this->nodes.back().node_order_distributor = order_counter++;
			}
			elements_left -= max_elements;
			replica_counter++;
			kernels_in_a_column++;
		}
		// Make note of the number of kernels in the first column (i.e. leaves of the replication tree)
		original.replicated_leaves = kernels_in_a_column;
		if ((num_trees > 1) && (tree == 0)) {
			double_distributor->replicated_leaves = kernels_in_a_column;
		}
		column_counter++;
		// Handle other columns by implementing Huffman algorithm
		// We will use copy_ptr to implement a linked list sorted by weight
		// The priority_list pointer will point to the first node in the linked list
		GraphNode* priority_list = original.copy_ptr;
		// Label each leaf node with the number of elements it needs to process
		GraphNode *temp = priority_list;
		int my_index = 0;
		int elements_to_process_1 = (int) ceil((1.0*in_size)/reduce_size/original.replicated_leaves);
		int elements_to_process_2 = (int) floor((1.0*in_size)/reduce_size/original.replicated_leaves);
		int temp_in_size = in_size;
		int temp_reduce_size = reduce_size;
		if (num_trees > 1) {
			if (original.reducesize_dim0%num_trees == 0) {
				temp_in_size = original.insize_dim0/num_trees;
				temp_reduce_size = original.reducesize_dim0/num_trees;
			} else {
				if (tree < original.reducesize_dim0%num_trees) {
					temp_in_size = (original.insize_dim0/original.reducesize_dim0)*(int) ceil((1.0*reduce_size)/num_trees);
					temp_reduce_size = (int) ceil((1.0*reduce_size)/num_trees);
				} else {
					temp_in_size = (original.insize_dim0/original.reducesize_dim0)*(int) floor((1.0*reduce_size)/num_trees);
					temp_reduce_size = (int) floor((1.0*reduce_size)/num_trees);
				}
			}
		}
		int counter_threshold = (temp_in_size/temp_reduce_size)%original.replicated_leaves;
		while (NULL != temp) {
			temp->is_leaf = true;
			temp->elements_to_process_1 = elements_to_process_1;
			temp->elements_to_process_2 = elements_to_process_2;
			temp->my_index = my_index++;
			// The following condition takes into account that the my_index variable has been incremented above
			if (my_index <= (temp_in_size%original.replicated_leaves)) {
				temp->total_elements_to_process = (int) ceil((1.0*temp_in_size)/original.replicated_leaves);
			} else {
				temp->total_elements_to_process = (int) floor((1.0*temp_in_size)/original.replicated_leaves);
			}
			temp->counter_threshold = counter_threshold;
			temp = temp->copy_ptr;
		}

		// This is how the algorithm should proceed
		// According to the paper entitled "Combinatorial Merging" by Golumbic, M.C.
		// Given the set of initial nodes C, with |C| elements, that are to be mapped to
		// a graph whose nodes can have at most r inputs, the optimal tree can be built by
		// finding q, such that |C| = q + k(r - 1); 2 <= q <= r, and k>0
		// Once we have that q, the algorithm is simple
		// In the first iteration take q nodes from C with lowest weights and connect them to a new node
		// In all subsequent iterations, take r nodes from C with lowest weights and connect them to a new node
		// The algorithm is guaranteed to always have exactly r nodes to choose all the way till the end
		// (the formula is designed in such a way that this will be true)
		// The algorithm provides minimal latency AND minimizes the number of nodes
		// In our case, C is the set of all leaves, and r is equal to max_elements
		// Let us determine q
		int huffman_q=0;
		if (original.replicated_leaves <= max_elements) {
			// If all leaves can be reduced by one node, then they will all be handled in the first step
			huffman_q = original.replicated_leaves;
		} else if ((original.replicated_leaves % (max_elements-1)) >= 2) {
			huffman_q = original.replicated_leaves % (max_elements-1);
		} else if (max_elements == 2) {
			// Since q has to be equal to, or larger than 2, none of the other formulae give us correct value when r is 2
			huffman_q = 2;
		} else {
			// Since q has to be equal to, or larger than 2, compute it like that
			huffman_q = (max_elements-1) + (original.replicated_leaves % (max_elements-1));
		}
		int iteration = 0;
		// Once we have processed all elements, the list head will not have the next element
		for (iteration=0; priority_list->copy_ptr != NULL; iteration++) {
			int loop_limit = (iteration == 0) ? huffman_q : max_elements;
			// old_last pointer will point to the previously added node
			GraphNode* old_last = NULL;
			old_last = &(this->nodes.back());
			// First, add a collector node
			string temp_string = BRCC_COLLECTOR;
			ostringstream number;
			number << "_" << collectors++;
			temp_string += number.str();
			GraphNode new_node_collector (temp_string);
			this->nodes.push_back (new_node_collector);
			GraphNode *collector = &(this->nodes.back());
			// Add another kernel
			// Will reuse replication factor to keep track of the replica id for the node
			// i.e. replication factor in the replicated graph actually contains a different number
			// for each replica of the original node
			string new_name = original.name.substr(0, original.name.size()-1);
			ostringstream instance_number;
			instance_number << replica_counter;
			new_name += instance_number.str();
			GraphNode new_node_kernel (new_name, replica_counter);
			new_node_kernel.setReduce();
			this->nodes.push_back (new_node_kernel);
			// Now add all necessary edges to the graph
			// Grab the desired number of nodes from the input, and keep track of the maximum weight
			int max_weight = -1;
			for (int i=0; i<loop_limit; i++) {
				GraphEdge &temp_edge = this->addEdge (original.name, *priority_list, *collector, false, 0, word_size);
				priority_list->node_order = i;
				temp_edge.source_var = reduce_stream_name;
				if (priority_list->weight > max_weight) {
					max_weight = priority_list->weight;
				}
				priority_list = priority_list->copy_ptr;
			}
			// Link replicas together
			// i.e. insert the new node into the linked list. The linked list is sorted according to weight,
			// so that the Huffman algorithm can always take the nodes in order
			GraphNode* new_kernel = &(this->nodes.back());
			new_kernel->weight = max_weight+1;
			// The following number tells us how many nodes have been combined into the new node
			new_kernel->elements_to_process_1 = new_kernel->elements_to_process_2 = loop_limit;
			// The following number tells how many elements will be processed by this node in total
			// This number should be equal to (number of nodes that were combined into this node) * (number of output elements of the reduction)
			// (at least for a single tree)
			// The rationale for this is as follows: this node contributes to every element of the output, and combines all elements on its inputs
			// to produce one output
			int temp_reduce_size = reduce_size;
			if (num_trees > 1) {
				if (original.reducesize_dim0%num_trees == 0) {
					temp_reduce_size = original.reducesize_dim0/num_trees;
				} else {
					if (tree < original.reducesize_dim0%num_trees) {
						temp_reduce_size = (int) ceil((1.0*reduce_size)/num_trees);
					} else {
						temp_reduce_size = (int) floor((1.0*reduce_size)/num_trees);
					}
				}
			}
			new_kernel->total_elements_to_process = loop_limit * temp_reduce_size;
			// If the weight of the new node is larger or equal to the last element's (which has the largest weight so far)
			// then we can simply add it to the end (saves us some time in searching the list
			if (new_kernel->weight >= old_last->weight) {
				old_last->copy_ptr = new_kernel;
				if (priority_list == NULL) {
					// If the list is empty, add the node to the head
					priority_list = new_kernel;
				}
			} else {
				// Otherwise we have to search the list to find a spot for the new node
				if (priority_list == NULL) {
					// If the list is empty, add the node to the head
					priority_list = new_kernel;
				} else {
					GraphNode *temp=NULL, *old_temp=NULL;
					temp = priority_list;
					while ((temp != NULL) && (temp->weight < new_kernel->weight)) {
						old_temp = temp;
						temp = temp->copy_ptr;
					}
					// Once we're here, old_temp points to the node AFTER which we should insert the new node
					// Unless it is NULL, in which case we need to modify the list head
					if (NULL == old_temp) {
						new_kernel->copy_ptr = temp;
						priority_list = new_kernel;
					} else {
						new_kernel->copy_ptr = temp;
						old_temp->copy_ptr = new_kernel;
					}
				}
			}
			// Add edge from the collector to the target (i.e. the newly created kernel node)
			GraphEdge &temp_edge = this->addEdge (original.name, *collector, *new_kernel, false, 0, word_size);
			temp_edge.dest_var = in_stream_name;
			replica_counter++;
		}
		if (num_trees > 1) {
			// The last added node is the root of the tree
			// We should add an edge from it to the final collector
			GraphEdge &temp_edge = this->addEdge (original.name, (this->nodes.back()), *final_collector, false, 0, word_size);
			(this->nodes.back()).node_order = tree;
			temp_edge.source_var = reduce_stream_name;
		}
	}
	if (num_trees == 1) {
		// The root of the tree is the last kernel replica added to the tree
		original.root_reduction_replica = &(this->nodes.back());
	} else {
		original.root_reduction_replica = final_collector;
		original.copy_ptr = double_distributor;
	}
	// The total number of replica nodes (in all trees) is stored in the replica_counter variable
	original.replicated_nodes = replica_counter;

}

void Graph::debugPrint () {
	int i;
	std::list<GraphNode>::iterator iter_i;
	std::list<struct StreamStruct>::iterator iter_j;


	for (iter_i=nodes.begin(), i=0; iter_i != nodes.end(); iter_i++, i++) {
		cout << "\nKernel #" << i << ": " << iter_i->name;
		if (iter_i->isReduce()) cout << " is a REDUCE kernel";
		cout << "\nInputs: ";
		for (iter_j=iter_i->in_streams.begin(); iter_j != iter_i->in_streams.end(); iter_j++) {
			cout << (iter_j->stream) << ", ";
		}
		cout << "\nOutputs: ";
		for (iter_j=iter_i->out_streams.begin(); iter_j != iter_i->out_streams.end(); iter_j++) {
			cout << (iter_j->stream) << ", ";
		}
	}

}

void Graph::debugPrintEdges () {
	int i;
	std::list<GraphNode>::iterator iter_i;
	std::list<GraphEdge>::iterator iter_j;

	for (iter_i=nodes.begin(), i=0; iter_i != nodes.end(); iter_i++, i++) {
		cout << "\nKernel #" << i << ": " << iter_i->name;
		if (iter_i->isReduce()) cout << " is a REDUCE kernel";
		if (iter_i->replication_factor != 1) cout << " with replication factor: " << iter_i->replication_factor;
		cout << "\nEdges: ";
		for (iter_j=iter_i->out_edges.begin(); iter_j != iter_i->out_edges.end(); iter_j++) {
			cout << iter_j->name << " associated with a variable " << iter_j->source_var << " to " << iter_j->destination->name << " associated with variable " << iter_j->dest_var << ", ";
		}
	}

}

// The following method outputs a graph in .dot format, which can be visualized using dot2ps utility
void Graph::printDot (std::stringstream &out) {

	int i;
	std::list<GraphNode>::iterator iter_i;
	std::list<struct StreamStruct>::iterator iter_j;
	std::list<GraphEdge>::iterator edge_iter;

	out << "digraph dataflow_graph\n{\nsize=\"7,10\";\n";

	for (iter_i=nodes.begin(), i=0; iter_i != nodes.end(); iter_i++, i++) {
		out << "\n" << iter_i->name << " [label=\"" << iter_i->name;
		if (iter_i->isReduce()) {
			out << "(R)";
		}
		out << "\\nInputs: ";
		for (iter_j=iter_i->in_streams.begin(); iter_j != iter_i->in_streams.end(); iter_j++) {
			out << (iter_j->stream) << ", ";
		}
		out << "\\nOutputs: ";
		for (iter_j=iter_i->out_streams.begin(); iter_j != iter_i->out_streams.end(); iter_j++) {
			out << (iter_j->stream) << ", ";
		}
		if (iter_i->replication_factor != 1) {
			out << "\\nReplication factor: " << iter_i->replication_factor;
		}
		out << "\"];\n";
		for (edge_iter=iter_i->out_edges.begin(); edge_iter != iter_i->out_edges.end(); edge_iter++) {
			out << "\n" << iter_i->name << "-> " << edge_iter->destination->name << " [label= \"" << edge_iter->name;
			if (edge_iter->stream_of_arrays) {
				out << " (ARRAY)" << "\"";
			} else {
				out << "\"";
			}
			out << "]; ";
		}
	}
	out << "\n}\n";
}
