/***************************************************************************
  This is part of the evolver toolkit for exploring genetic progamming.
  Copyright (C) 1996 Benjamin Bennett and Yeasah G. Pell

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

  This library 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
  Library General Public License for more details.

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

  Contact information: Benjamin Bennett<fiji@limey.net> and Yeasah
    G. Pell<yeasah@wpi.edu>
  *************************************************************************/

/***************************************************************************
  GNetwork - Functions to manipulate the network.

  The network and related functions.
 **************************************************************************/

#include "network.H"

GNetwork::GNetwork()
{
	source = -1;
	sink = -1;
	max_flow = -1;
}

GNetwork::~GNetwork()
{
}

GNetwork& GNetwork::operator=(GNetwork &input)
{
	int i;

	nodes.SetSize(0);
	pipes.SetSize(0);

	source = input.source;
	sink = input.sink;
	max_flow = input.max_flow;

	for (i=0; i < input.nodes.GetSize(); i++)
		nodes[i] = new GNetNode();

	for (i=0; i < input.pipes.GetSize(); i++)
	{
		pipes[i] = new GPipe(*(input.pipes[i]));
		AddPipe(pipes[i]);
	}

	return *this;
}

void GNetwork::Reset()
{
	int i;

	for(i=0; i < nodes.GetSize(); i++)
		nodes[i]->Reset();

	for(i=0; i < pipes.GetSize(); i++)
		pipes[i]->Reset();
}

int GNetwork::IncreaseFlow(int node, int pipe)
{
	int retval = -1;

	if(pipe >= 0 && pipe < QueryNumOutPipes(node))
		retval = nodes[node]->IncreaseFlow(pipe, (node == source));

	return retval;
}

int GNetwork::DecreaseFlow(int node, int pipe)
{
	int retval = -1;

	if(pipe >= 0 && pipe < QueryNumOutPipes(node))
		retval = nodes[node]->DecreaseFlow(pipe);
	
	return retval;
}

int GNetwork::QueryInputFlow(int node, int pipe)
{
	if(pipe >= 0 && pipe < QueryNumInPipes(node))
		return nodes[node]->QueryInputFlow(pipe);

	return -1;
}

int GNetwork::QueryOutputFlow(int node, int pipe)
{
	if(pipe >= 0 && pipe < QueryNumOutPipes(node))
		return nodes[node]->QueryOutputFlow(pipe);

	return -1;
}

int GNetwork::QueryNumInPipes(int node)
{
	if(node >= 0 && node < GetNumNodes())
		return nodes[node]->QueryNumInPipes();

	return -1;
}

int GNetwork::QueryNumOutPipes(int node)
{
	if(node >= 0 && node < GetNumNodes())
		return nodes[node]->QueryNumOutPipes();

	return -1;
}

int GNetwork::QueryCapacityIn(int node, int pipe)
{
	if(pipe >= 0 && pipe < QueryNumInPipes(node))
		return nodes[node]->QueryCapacityIn(pipe);

	return -1;
}

int GNetwork::QueryCapacityOut(int node, int pipe)
{
	if(pipe >= 0 && pipe < QueryNumOutPipes(node))
		return nodes[node]->QueryCapacityOut(pipe);

	return -1;
}

int GNetwork::SendMessageOut(int node, int pipe, int msg_id, int msg)
{
	if(pipe >= 0 && pipe < QueryNumOutPipes(node))
		return nodes[node]->SendMessageOut(pipe, msg_id-1, msg);

	return -1;
}

int GNetwork::SendMessageIn(int node, int pipe, int msg_id, int msg)
{
	if(pipe >= 0 && pipe < QueryNumInPipes(node))
		return nodes[node]->SendMessageIn(pipe, msg_id-1, msg);

	return -1;
}

int GNetwork::RecieveMessageOut(int node, int pipe, int msg_id, int &msg)
{
	if(pipe >= 0 && pipe < QueryNumOutPipes(node))
		return nodes[node]->RecieveMessageOut(pipe, msg_id-1, msg);

	return -1;
}

int GNetwork::RecieveMessageIn(int node, int pipe, int msg_id, int &msg)
{
	if(pipe >= 0 && pipe < QueryNumInPipes(node))
		return nodes[node]->RecieveMessageIn(pipe, msg_id-1, msg);

	return -1;
}

// adds a new node, returns the node number of the new node
int GNetwork::AddNode()
{
	GNetNode *node = new GNetNode();

	max_flow = -1;
	return nodes.Append(node);
}

// adds a new pipe from start to end with capacity capacity
int GNetwork::AddPipe(int start, int end, int capacity)
{
	GPipe *pipe = new GPipe(start, end, 0, capacity);

	max_flow = -1;
	pipes.Append(pipe);

	// source
	nodes[start]->AddPipe(pipe, 1); 
	// destination
	nodes[end]->AddPipe(pipe, 0); 

	return 1;
}

int GNetwork::AddPipe(GPipe *pipe)
{
	int source;
	int dest;

	max_flow = -1;
	source = pipe->GetSource();
	dest = pipe->GetDest();

	// source
	nodes[source]->AddPipe(pipe, 1);
	// destination
	nodes[dest]->AddPipe(pipe, 0); 

	return 1;
}

int GNetwork::GetSource()
{
	return source;
}

int GNetwork::GetSink()
{
	return sink;
}

int GNetwork::SetSource(int node)
{
	if ((node < 0) || (node >= nodes.GetSize()))
	{
		cerr << "GNetwork::set_source - invalid node " << node << endl;
		exit(1);
	}

	max_flow = -1;
	source = node;
	return source;
}

int GNetwork::SetSink(int node)
{
	if ((node < 0) || (node >= nodes.GetSize()))
	{
		cerr << "GNetwork::set_source - invalid node " << node << endl;
		exit(1);
	}

	max_flow = -1;
	sink = node;
	return sink;
}

// returns the number of nodes in the network
int GNetwork::GetNumNodes()
{
	return nodes.GetSize();
}

// prints out the network
void GNetwork::Print()
{
	for (int i=0; i<nodes.GetSize(); i++)
	{
		cout << "Node " << i << ":" << endl;
		nodes[i]->Print();
		cout << endl;
	}
}


// calculate the maximum flow through the network
// based on the Floyd-Fulkerson method
int GNetwork::CalcMaxFlow()
{
	GNetwork *temp_net;
	int i;

	// if we have already computed the flow the we are done
	if (max_flow >= 0)
		return max_flow;
	
	// create a copy of the network and reset it to hold the state
	temp_net = new GNetwork;
	temp_net->Reset();

	// calculate the flow at depth i
	max_flow = 0;
	i = 1;
	while(temp_net->CalcFlow(source, &max_flow, i))
		i += 1;

	delete temp_net;
	return max_flow;
}

// TODO finish this
// private function to calculate the flow at a particular depth
// returns 1 if there is still more possible flow
// returns 0 if a min-cut is found
int GNetwork::CalcFlow(int node, int *flow, int depth)
{
	int j, retval;
	
	cerr << "Do not call GNetwork::CalcFlow because the code is incomplete" 
		 << endl;

	if (depth == 1 && node != sink)
	{
		flow = 0;
		return 1;
	}

	for (j = 0; j < nodes[node]->QueryNumOutPipes(); j++)
	{
		nodes[node]->IncreaseFlow(j, (node == source));
		retval = CalcFlow(nodes[node]->GetDest(j), flow, depth-1);
		
	}

	return 0;
}