//Programmer - Constantine Roussos
//Date 26-Jan-2000

//Program Name - Graph

//The program will read in a list of edges, create a graph
//process the graph and optionally write the new graph.

#include <iostream>
#include <fstream>
using namespace std;

const long MaxNodes = 1000;

class graph;

class baseEdge {		//edge in format nodeindx nodeindex edgeweight
public:			// This class is only used for external graph storage
	int lnode;
	int rnode;
	float edgeWeight;
};//end baseEdge

//The classes graph, node and edge form the internal representation of a
//graph as an array of nodes each containing a pointer to a linked list
//of the incident edges and adjacent nodes.
class edge {
	friend class graph; friend class node;
	//data structure
	float weight;
	int nodeindex;
	edge* edgeptr;
	//Methods
public:
	edge(float edgeweight, int nodeindx, edge* ptrToEdge);	//Constructor
	float retWeight() {return weight;}
	int retRnode() {return nodeindex;}
	edge* next() {return edgeptr;}
};//end edge class

class node {
	friend class graph;
	char* nodeinfo;		//information associated with a node
	int numEdges;
	edge* edgeptr;		//linked list of edges incident to this node
	//Methods
public:
	node();		//Constructor
	float findEdge(int rnode);
	bool insertEdge(edge* ptrToEdge);
};// end node class

class graph {
	int numNodes;
	bool directed;
	node nodes[MaxNodes];	//Graph is represented as an array of nodes
	//Methods				//Ideally graph should be dynamically created
public:					//to be correct size after # of nodes is known.
	graph();	//Constructor
	//Create a graph from its list of edges, # of nodes and type 
	void makeGraph(baseEdge edges[], int numberNodes, int numberEdges, bool directedGraph);
	void writeGraph();
	float findEdge(int lnode, int rnode);
};//end graph class


edge::edge(float edgeweight, int nodeindx, edge* ptrToEdge) {	//Constructor
	weight = edgeweight;	//Create the edge when info. is available
	nodeindex = nodeindx;	//note different spelling to differentiate
	edgeptr = ptrToEdge;
}//end edge Constructor


node::node() {		//Constructor
	nodeinfo = NULL;	//empty nodes are created when graph is created.
	numEdges = 0;
	edgeptr = NULL;
}// end node Constructor


 //return edgeweight, -1 if edge does not exist
float node::findEdge(int rnode) {
	float edgeweight = -1;
	edge* currEdgePtr = edgeptr;
	while(currEdgePtr != NULL) {
		if((currEdgePtr->retRnode()) == rnode) {
			edgeweight = currEdgePtr->retWeight();
		}//end if
		currEdgePtr = currEdgePtr->next();
	}//end while
return edgeweight;
}

bool node::insertEdge(edge* ptrToEdge) {

	if(findEdge(ptrToEdge->nodeindex) < 0) {  //if edge does not already exist
		//insert edge into beginning of node's edge list
		ptrToEdge->edgeptr = edgeptr;
		edgeptr = ptrToEdge;
		numEdges ++;
		return true;
	}//end if
	else {return false;}
}//end insertEdge

graph::graph() {	//graph Constructor
	numNodes = 0;
	directed=false;
}// end graph Constructor

 //return edgeweight, -1 if edge does not exist
float graph::findEdge(int lnode, int rnode) {
	//search the shorter node list for the edge and its weight.
	if(nodes[lnode].numEdges < nodes[rnode].numEdges) {
		return nodes[lnode].findEdge(rnode);
	}//end if
	else {
		return nodes[rnode].findEdge(lnode);
	}//end else
}//end findEdge

//Create a graph from a list of edges + numnodes and type
void graph::makeGraph(baseEdge edges[], int numberNodes, int numberEdges, bool directedGraph){
	int lnode; int rnode; float weight; 

	numNodes = numberNodes;		//Enter number of nodes in graph
	directed = directedGraph;	//Enter graph type (Undir/Dir)
	//Construct the graph from the edges in the edges array
	//For each edge (x, y) and its weight, w
	for(int edgeNum = 1; edgeNum <= numberEdges; edgeNum++) {
		//create a new edge, insert weight and dest. nodeindex
		lnode=edges[edgeNum].lnode;
		rnode = edges[edgeNum].rnode;
		weight = edges[edgeNum].edgeWeight;
		edge* ptrToEdge = new edge(weight, rnode, NULL);
		//insert edge into lnode's linked list of edges
		nodes[lnode].insertEdge(ptrToEdge);
		//if Undirected then do same for (y, x) with weight, w.
		if(!directed) {
				//create a new edge, insert weight and dest. nodeindex
			edge* ptrToEdge = new edge(weight, lnode, NULL);
			//insert edge into beginning of node rnode's edge list
			nodes[rnode].insertEdge(ptrToEdge);
		}//end if
	}//end for
}// end makeGraph

void graph::writeGraph() {
	char outputfilename[100]; 
	cout << "Enter name of output file to hold graph edges. \n";
	cin.getline(outputfilename, 100);
								//open input file and
	ofstream outputstream;		//declare output stream
	outputstream.open(outputfilename);

	outputstream << numNodes << " " << directed << endl;
	for(int nodeNum=1; nodeNum<=numNodes; nodeNum++) {
		edge* currEdgePtr = nodes[nodeNum].edgeptr;
		while(currEdgePtr != NULL) {
			outputstream << nodeNum << " " << currEdgePtr->nodeindex << " " ;
			outputstream << currEdgePtr->weight << endl;
			currEdgePtr = currEdgePtr->edgeptr;
		}//end while
	}//end for
	outputstream.close();
}// end writeGraph

int GetData(baseEdge edges[], int &numNodes, bool &directed, char* inputfilename){
	//int errStatus;
	//open input file and
	ifstream inputstream; //declare input stream
	inputstream.open(inputfilename);
	if(inputstream.fail()) {
		cout << "Error opening file " << inputfilename << endl;
		exit(1);
	}//end if
	int numEdges=0;
	//Read in number of nodes and graph type (Undir or Dir)
	inputstream >> numNodes;
	inputstream >> directed;
	while(! inputstream.eof()) {
		int lnode; int rnode; float edgeWeight;
		// read in edges as two integers
		inputstream >> lnode;
		inputstream >> rnode;
		inputstream >> edgeWeight;

		numEdges = numEdges + 1;
		edges[numEdges].lnode = lnode;
		edges[numEdges].rnode = rnode;
		edges[numEdges].edgeWeight = edgeWeight;
		inputstream.get();

	}//end while
	inputstream.close();
return numEdges;
}//end GetData

void displayEdgesFromArray(baseEdge edges[], int numNodes, bool directed, int E) {
	cout << "number of nodes = " << numNodes << endl;
	cout << "graph type = " << directed << endl;
	for(int edge = 1; edge <= E; edge++) {
		cout << edges[edge].lnode << ", " << edges[edge].rnode << ", ";
		cout << edges[edge].edgeWeight << endl;
	}//end for 
}// end function

int main() {
	graph G; graph H; //int errStatus;
	baseEdge edges[10000];	//Allow for up to 10000 edges
	int numNodes=0; bool directed=false;
	char inputfilename[100];

	cout << "Enter name of input file containing graph edges. \n";
	cin.getline(inputfilename, 100);

	int E = GetData(edges, numNodes, directed, inputfilename);
	cout << "Number of edges = " << E << endl;

	displayEdgesFromArray(edges, numNodes, directed, E);

	G.makeGraph(edges, numNodes, E, directed);

	G.writeGraph();
return 0;
}//end main