/*
 *
 *  Created on: Nov 4, 2011
 *      Author: stakisko
 *      Email : konmpar at gmail com
 */
/*
 
#include <stdio.h>
#include <stdlib.h>
 
typedef struct _node node;
typedef struct _acne acne;
 
/*
 * There are two structures.
 * 'Node' represent each node having childrens acnes represent each connected to him nodes.
 * 'Acne' represent each acne connecting two Nodes.
 */
 
struct _node {
	int distance; // distance from the first node
	struct _acne *children[100]; // going to nodes
	int edgeno; // how many nodes are connected to
	int name;
};
 
struct _acne {
	int value; // distance between these edges
	int from; // acne connecting from
	int to; // to
	struct _node *edge;
};
 
/*
 * for every node we are going in (the parameter) we search its connected childs nodes and
 * calculate their distances. then we are going in again( recursion ) in the node with the
 * minimum distance
 *
 * */
 
int traverse(struct _node *node){
 
	if(node->edgeno<=0)
		return 0;
 
	printf("start of node %d\n", node->name);
	printf("\tchildrens: %d\n", node->edgeno);
 
	int mindistance = node->children[0]->value;
	int minnode = 0;
 
	int i;
 
	for(i=0;i<node->edgeno; i++){
 
		if(node->distance + node->children[i]->value < node->children[i]->edge->distance ){
			node->children[i]->edge->distance = node->distance + node->children[i]->value;
		}
 
		if (mindistance > node->children[i]->edge->distance){
			mindistance = node->children[i]->edge->distance;
			minnode = i;
		}
 
		printf("\tfrom %d to %d with distance %d\n", node->children[i]->from, node->children[i]->to, node->children[i]->edge->distance);
 
	}
 
	printf("\tmin node %d\n", node->children[minnode]->to);
 
	printf("end of node\n-----------------------\n");
 
	traverse(node->children[minnode]->edge);
 
	return 0;
}
 
// main function
int main(int argc, char *argv[]){
 
	FILE *ifp;
 
	int t, t1, t2;
	int nodesNo = 0;
	int edgesNo = 0;
 
	ifp = fopen("/home/kostas/Downloads/dijkstra1.dat", "r");
 
	if (ifp == NULL) {
	  fprintf(stderr, "Can't open input file dijkstra.dat!\n");
	  exit(1);
	}
 
	fscanf(ifp, "%d %d", &nodesNo, &edgesNo);
 
	struct _node nodes[nodesNo];
	struct _acne acnes[edgesNo];
	int i = 0; // count the acnes
	int previous = 0;
	int k = 0; // count childs for every node
 
	/*
	 * Files content should be in the format
	 * n N
	 * startNode endNode distance
	 * startNode endNode distance
	 * .
	 * .
	 * .
	 * startNode endNode distance
	 *
	 * where n is the total number of Nodes and N is the total number of Acnes
	 *
	 */
	while(fscanf(ifp, "%d %d %d", &t, &t1, &t2) == 3){ /* read from file */
 
		/*
		 * Then for every line we create a node and also
		 * an acne to place the connected edges.
		 *
		 */
		if(previous != t)
			k = 0;
 
		nodes[t].distance = 65000; // infinite
		nodes[t].name = t;
 
		acnes[i].from = t;
		acnes[i].to = t1;
		acnes[i].value = t2;
		acnes[i].edge = &nodes[t1];
 
		nodes[t].children[k] = &acnes[i];
 
		nodes[t].edgeno = k+1;
 
		i++;
		k++;
		previous = t;
	}
 
	// set firsts node's distance
	nodes[0].distance = 0;
 
	// set last node
	nodes[nodesNo-1].distance = 65000;
	nodes[nodesNo-1].edgeno = 0;
        nodes[nodesNo-1].name = nodesNo-1;
 
	int j;
	for(j=0; j< (sizeof(nodes)/sizeof(*nodes));j++)
		printf("node %d, distance %d, edgeno %d\n", nodes[j].name, nodes[j].distance, nodes[j].edgeno);
 
	for(j=0; j< sizeof(acnes)/sizeof(*acnes);j++)
		printf("from %d, to %d, value %d\n", acnes[j].from, acnes[j].edge->name, acnes[j].value);
 
	printf("\n-----------\n");
	traverse(&nodes[0]);
	printf("\n-----------\n");
 
	for(j=0; j< (sizeof(nodes)/sizeof(*nodes));j++)
		printf("nnode %d, distance %d\n", nodes[j].name, nodes[j].distance);
 
	return 0;
}