/* Process is:
 *   Pick node A, pick a node B adj to A, pick a node C adj to B, pick a
 *   node D adj to C, pick a node E adj to D. And each node can only
 *   appear once in the subgraph.
 */
#define HUGE_GRAPHS 0

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <assert.h>
#include <time.h> 
#include <map>        
#include <set>
#include <utility>
#include <unordered_map>
#include <unordered_set> 
#include <iostream>
#include <iterator>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

#define PROGRESS_INFO 1 /* Print status to stdout */
#define PATH_MAX 256 //Oleksii


typedef long long int64; // sadly, long long is not standard in C++ ... yet

struct temp_data /* linked list of edges */
{
  struct temp_data *next;
  int dst;
};


/* Handy macros; for details see the definition of edges_for */
#define DEGREE(x) (edges_for[x + 1] - edges_for[x])
#define foreach_adj(x,y) for(x = edges_for[y]; x != edges_for[y+1]; x++)

void die(char *msg)
{
  fprintf(stderr, "ERROR: %s\n", msg);
  exit(1);
}

void count(FILE *f, char *outname)
{
  int V, E, E_undir, i, j, k;
  time_t start_time = time(0);
  
  //scanning first three lines of the leda file
  fscanf(f, "LEDA.GRAPH\n");
  fscanf(f, "%*s\n");
  fscanf(f, "%*s\n");
  
  // stores number of nodes in the variable "V"
  do { if( fscanf(f, "%d\n", &V) < 0 ) V = -1; }
  while(V < 0);
  
  
  char **node_names = new char*[V];
  
  char buf[101];
  for(i = 0; i < V; i++)
  {
    if(fscanf(f, "|{ %100[^}] }|\n", buf) < 1) die("Invalid input file");
    node_names[i] = strdup(buf);
    
    // checks if name of the node in not NULL
    assert(node_names[i] != NULL);
  }
  
  // stores the number of edges in the variable "E_undir"
  fscanf(f, "%d", &E_undir);
  E = E_undir * 2;
  
  // checks if E_undir is is non negative
  assert(E_undir >= 0);
  
  struct temp_data **heads = new temp_data*[V]; 
  struct temp_data *links = new temp_data[E]; 
  for(i = 0; i < V; i++)
    heads[i] = NULL;
  
  struct temp_data *link;
  
#if HUGE_GRAPHS
  /* Use a map (sparse associated array) for the adjacency matrix */
  /* Use int64 as the index, with high 32 bits encoding row, low 32 bits encoding column */
#define Connect(i,j) (adjmat[((int64)(i))<<32 | j] = 1)
#define Connected(i,j) (adjmat[((int64)(i))<<32 | j])
  std::map<const int64, char> adjmat;
  for(i = 0; i < V; i++)
    Connect(i,i); /* optimization hack */
#else
  /* allocate some space for the adjacency matrix */
  char **adjmat = new char*[V]; 
  /* Use a bit vector to store each row of the adjancency matrix, so
   * that each edge takes up only one bit.
   */
#define Connect(i,j) (adjmat[i][(j)/8] |= 1<<((j)%8))
#define Connected(i,j) (adjmat[i][(j)/8] & (1<<((j)%8)))
  for(i = 0; i < V; i++)
  {
    /* calloc zeroes the memory for us */
    adjmat[i] = (char *) calloc(V/8+1, sizeof(char));
    if(!adjmat[i]) { perror("calloc"); exit(1); }
    
    Connect(i,i); /* optimization hack */
  }
#endif
  /* First stores edges in linked lists by node (vertex) so we know how many
   * edges there are for each node, then copy to an array for efficiency.
   */

  std::unordered_map<int, float> weights[V]; //storing edge weights
  std::unordered_set<float> eweights; //storing edge weights

  int count;

  /* add data to linked list for intermediate storage */
  for(i = 0; i < E_undir; i++)
  {
    int src = -1, dst = -1, tmp=0;

    fscanf(f, "%d %d %d |{ %100[^}] }|\n", &src, &dst, &tmp, buf);

    src -= 1; /* LEDA graph files are 1-indexed */
    dst -= 1;
    
    
    if(src < 0 || dst < 0)
    {
      fprintf(stderr,"Error: node numbers must be greater than zero.\n");
      exit(1);
    }
    
    if(src == dst) continue; /* ignore self-loops */
    
    /* See if edge is already in list */
    int bad = 0;
    for(link = heads[src]; link; link = link->next)
    {
      if(link->dst == dst)
      {
        bad = 1; /* don't allow parallel edges */
    break;
      }
    }
    if(bad) continue;
    
    struct temp_data *ntemp1 = &links[i*2];
    struct temp_data *ntemp2 = &links[i*2+1];
    
    /* Add to front of node's linked list */
    ntemp1->next = heads[src]; ntemp1->dst = dst;
    ntemp2->next = heads[dst]; ntemp2->dst = src;
    heads[src] = ntemp1;
    heads[dst] = ntemp2;
    
    //creating adjacency matrix with 0 1 values
    Connect(src, dst);
    Connect(dst, src);
    
    float value = (int)(atof(strdup(buf)) * 100 + .5);
    float valuex = (float)value / 100;
    weights[src][dst] = valuex;
    weights[dst][src] = valuex;
    eweights.insert(valuex);

  }

  // sort all of the weights in the network
  std::vector<float> sweights(eweights.begin(), eweights.end());
  std::sort(sweights.begin(), sweights.end());
  int wsize = sweights.size();

  
  /* The edges[] array stores edges by node sequentially, so the last edge
   of node n is followed by the first edge of n+1. edges_for[] stores
   a pointer to the first edge of a node. */
  
  int **edges_for = new int*[V+1]; 
  int *edges = new int[E*2+1];
  
  int *edge_last = &edges[0];
  
  for(i = 0; i < V; i++)
  {
    edges_for[i] = edge_last;
    for(link = heads[i]; link; link = link->next)
    {
      *edge_last = link->dst;
      edge_last++;
    }
  }
  
  
  edges_for[i] = edge_last;


// adjacent nodes
  int *pb, *pc;
  int a, b, c;
  
  for(a = 0; a < V; a++) // O(V)
  {
  #if PROGRESS_INFO
    fprintf(stderr, "\rnode # %5d (%.1f%%) [%d seconds elapsed]", a,
            100.0 * (float) a / V, (time(0) - start_time));
  #endif

    // store 1 2-hop nodes and weights in unordered map
  	std::set<int> onehop, twohop, thop; //storing 1-hop, 1 and 2-hop, and 2-hop  neighbors

  	int64 *ncount[4]; // 4 because of four types of edge weights
	/* allocate space for node type counts */
	for(i = 0; i < 4; i++)
	{
	    ncount[i] = (int64 *) calloc(wsize, sizeof(int64));
	    if(!ncount[i]) { perror("calloc"); exit(1); }
	}

    foreach_adj(pb, a)
    {
      b = *pb;
      
      if(b == a) continue;
        
        // 1-hop neighbors
      	onehop.insert(b);

      foreach_adj(pc, b)
      {
        c = *pc;
        if(c == a || c == b) continue;
        
        // upto 2-hop neighbors
        twohop.insert(c);
        
      }

    }


	std::set_difference(twohop.begin(), twohop.end(), onehop.begin(), onehop.end(), 
                        std::inserter(thop, thop.begin()));

  // converting sets to vectors for fast iteration
  std::vector<int> onehopv(onehop.begin(), onehop.end());
  std::vector<int> thopv(thop.begin(), thop.end());


  // 1-hop neighbors
  for (auto itr1 = onehopv.begin(); itr1 != onehopv.end(); ++itr1) {

    float key = weights[a][*itr1];

    int index = lower_bound(sweights.begin(), sweights.end(), key) - sweights.begin(); // log(E)

    ncount[0][index]++;

  }

  // among 1-hop neighbors
  for (auto itr1 = onehopv.begin(); itr1 != --onehopv.end(); ++itr1) { // O(max_degree)

    for (auto itr2 = itr1; itr2 != onehopv.end(); ++itr2) { // O(max_degree)

      if( *itr1 != *itr2 && Connected(*itr1, *itr2) ){

        float key = weights[*itr1][*itr2];

        int index = lower_bound(sweights.begin(), sweights.end(), key) - sweights.begin(); // log(E)

        ncount[1][index]++;

      }

    }

  }

  // 2-hop neighbors
  for (auto itr1 = onehopv.begin(); itr1 != onehopv.end(); ++itr1) {

    for (auto itr2 = thopv.begin(); itr2 != thopv.end(); ++itr2) {

      if( Connected(*itr1, *itr2) ){

        float key = weights[*itr1][*itr2];

        int index = lower_bound(sweights.begin(), sweights.end(), key) - sweights.begin(); // log(E)

        ncount[2][index]++;

      }

    }

  }

  // among 2-hop neighbors
  for (auto itr1 = thopv.begin(); itr1 != --thopv.end(); ++itr1) {

    for (auto itr2 = itr1; itr2 != thopv.end(); ++itr2) {

      if( *itr1 != *itr2 && Connected(*itr1, *itr2) ){

        float key = weights[*itr1][*itr2];

        int index = lower_bound(sweights.begin(), sweights.end(), key) - sweights.begin(); // log(E)

        ncount[3][index]++;

      }

    }

  }


   /************** BEGIN OUTPUT *************************/
  char temp[PATH_MAX];

  /* print neighbor weights */
  int t=1;
  FILE *e_out;

  sprintf(temp, "%s_%s", outname, node_names[a]);
  e_out = fopen(temp, "w");
  if(!e_out) { perror(temp); exit(1); }


  if(e_out)
  {
      for(j = 0; j < wsize; j++)
      {
          fprintf(e_out, "%f", sweights[j]);

          for(i = 0; i < 4; i++)
          {
              fprintf(e_out, " %lld", ncount[i][j]);
          }

          fprintf(e_out, "\n");
      }
  }


  
  if(e_out != stdout) fclose(e_out);



  }


  #if PROGRESS_INFO
  fprintf(stderr, "\nCounting complete.\n");
  #endif

 
}




int main(int argc, char *argv[])
{
  if(argc != 3)
  {
    fprintf(stderr, "Usage: %s <input graph> <output name>\n", argv[0]);
    return 1;
  }
  
  FILE *fp = fopen(argv[1], "r");
  if(!fp) { perror(argv[1]); return 1; }
  
  count(fp, argv[2]);
  
  fclose(fp);

  return 0;

}
