/* -----------------------------------------
 * This is the node state BEFORE the search is initiated.
 * 1. initialize node_state_ with adjList all uncolored
 * 2. Does pre-coloring
 * ---------------------------------------*/
Node::Node(bool isRoot, int n, CProxy_Node parent) :
  nodeID_("0"), parent_(parent), uncolored_num_(n), is_root_(isRoot),
  child_num_(0), child_finished_(0),
  child_succeed_(0), is_and_node_(false), parentBits(1), parentPtr(NULL)

{
  __sdag_init();
  programStart = CkTimer();
  CkAssert(isRoot);  
  vertex v = vertex(chromaticNum_);
  node_state_ = std::vector<vertex>(vertices_, v);

  //preColor();
#ifdef  DEBUG 
  CkPrintf("After Precolor\n");
  printGraph();
#endif 

  int count = uncolored_num_;
  uncolored_num_ -= vertexRemoval();
  CkPrintf("Vertices removed by vertex removal in [MainChare] = %d\n", count-uncolored_num_);

#ifdef  DEBUG 
  CkPrintf("Vertex Removal\n");
  printGraph();
#endif 

  CProxy_counter(counterGroup).ckLocalBranch()->registerMe(nodeID_);
  run();
}

int main() {
	int ver = 8;
	graph *g;
	g = initGraph(ver);

	addEdge(g, 0, 7);
	addEdge(g, 0, 4);
	addEdge(g, 1, 3);
	addEdge(g, 1, 2);
	addEdge(g, 2, 1);
	addEdge(g, 2, 3);
	addEdge(g, 3, 0);
	addEdge(g, 3, 4);
	addEdge(g, 4, 5);
	addEdge(g, 5, 7);
	addEdge(g, 6, 5);
	addEdge(g, 7, 6);
	addEdge(g, 7, 4);

	printGraph(g);

	dfsinit(g, 2);

	printGraph(g);




}

int main()
{
	struct Graph *graph = NULL;
	struct Graph *Dijkstra_Graph = NULL;

	int V=5;
	/// create array
    graph = CreateGraph(V);
	addEdge(graph, 0, 1,1);
    addEdge(graph, 0, 4,2);
    addEdge(graph, 1, 2,2);
    addEdge(graph, 1, 3,3);
    addEdge(graph, 1, 4,5);
    addEdge(graph, 2, 3,1);
    addEdge(graph, 3, 4,4);

    //printf("Enter value");
    printGraph(graph);
    printf("Dijkstra Algorithm\n");
    Dijkstra_Graph = CreateGraph(V);
    


    // print the adjacency list representation of the above graph
  
    dijkstra_algorithm(graph , Dijkstra_Graph);
    printGraph(Dijkstra_Graph);

    
	return 0;
}

int main(int argc, char* argv[]){
   int i, n=8;
   List S = newList();
   Graph G = newGraph(n);
   Graph T=NULL, C=NULL;

   for(i=1; i<=n; i++) append(S, i);

   addArc(G, 1,2);
   addArc(G, 1,5);
   addArc(G, 2,5);
   addArc(G, 2,6);
   addArc(G, 3,2);
   addArc(G, 3,4);
   addArc(G, 3,6);
   addArc(G, 3,7);
   addArc(G, 3,8);
   addArc(G, 6,5);
   addArc(G, 6,7);
   addArc(G, 8,4);
   addArc(G, 8,7);
   printGraph(stdout, G);

   DFS(G, S);
   fprintf(stdout, "\n");
   fprintf(stdout, "x:  d  f  p\n");
   for(i=1; i<=n; i++){
      fprintf(stdout, "%d: %2d %2d %2d\n", i, getDiscover(G, i), getFinish(G, i), getParent(G, i));
   }
   fprintf(stdout, "\n");
   printList(stdout, S);
   fprintf(stdout, "\n");

   T = transpose(G);
   C = copyGraph(G);
   fprintf(stdout, "\n");
   printGraph(stdout, C);
   fprintf(stdout, "\n");
   printGraph(stdout, T);
   fprintf(stdout, "\n");

   DFS(T, S);
   fprintf(stdout, "\n");
   fprintf(stdout, "x:  d  f  p\n");
   for(i=1; i<=n; i++){
      fprintf(stdout, "%d: %2d %2d %2d\n", i, getDiscover(T, i), getFinish(T, i), getParent(T, i));
   }
   fprintf(stdout, "\n");
   printList(stdout, S);
   fprintf(stdout, "\n");

   freeList(&S);
   freeGraph(&G);
   freeGraph(&T);
   freeGraph(&C);
   return(0);
}

int main(int argc, char* argv[]){
	// Parameters
	char fileNameGp[1024]; // Name of the file that contains the pattern graph
	char fileNameGt[1024]; // Name of the file that contains the target graph
	int timeLimit=60;      // Default: CPU time limit set to 60 seconds
	int verbose = 0;       // Default: non verbose execution
	bool induced = false;  // Default: search for partial subgraph
	bool firstSol = false; // Default: search for all solutions
	bool isLabelled = false; // Default: non labelled graphs
	fileNameGp[0] = 0;
	fileNameGt[0] = 0;
	parse(&isLabelled, &timeLimit, &firstSol, &induced, &verbose, fileNameGp, fileNameGt, argv, argc);
	if (verbose >= 2)
		printf("Parameters: isLabelled=%d induced=%d firstSol=%d timeLimit=%d verbose=%d fileNameGp=%s fileNameGt=%s\n",
			   isLabelled, induced,firstSol,timeLimit,verbose,fileNameGp,fileNameGt);
	
	// Initialize graphs                                                                                                                            
	Tgraph *Gp = createGraph(fileNameGp, isLabelled);       // Pattern graph                                                                            
	Tgraph *Gt = createGraph(fileNameGt, isLabelled);       // Target graph                                                                             
	if (verbose >= 2){
		printf("Pattern graph:\n");
		printGraph(Gp);
		printf("Target graph:\n");
		printGraph(Gt);
	}

	// Initialize domains                                                                                                                           
	Tdomain *D = createDomains(Gp, Gt);
	if (!initDomains(induced, D, Gp, Gt)) return printStats(false);
	if (verbose >= 2) printDomains(D, Gp->nbVertices);

	// Check the global all different constraint                                                                                                    
	if ((!updateMatching(Gp->nbVertices,Gt->nbVertices,D->nbVal,D->firstVal,D->val,D->globalMatchingP)) ||
		(!ensureGACallDiff(induced,Gp,Gt,D))){
		nbFail++;
		return printStats(false);
	}

	// Math all vertices with singleton domains                                                                                                     
	int u;
	int nbToMatch = 0;
	int toMatch[Gp->nbVertices];
	for (u=0; u<Gp->nbVertices; u++){
		D->globalMatchingT[D->globalMatchingP[u]] = u;
		if (D->nbVal[u] == 1)
			toMatch[nbToMatch++] = u;
	}
	if (!matchVertices(nbToMatch,toMatch,induced,D,Gp,Gt)){
		nbFail++;
		return printStats(false);
	}
	
	
	// Solve
	return printStats(!solve(timeLimit,firstSol, induced, verbose, D, Gp, Gt));
}

int path(struct graph* graphe, int sommet1, int sommet2){
	tailAll(graphe);
	printf("Tail :\n");
	printGraph(graphe);
	branchFrom(graphe, sommet1);
	printf("Branch from sommet %d :\n",graphe->sommet[sommet1].data);
	printGraph(graphe);
	
	if(graphe->sommet[sommet2].state == BRANCH){
		return 1;
	}
	return 0;
}

/*main------------------------------------------------------------------------*/
int main(int argc, char* argv[]) {

    //input validation
    if (argc != 2) {
        printf("Usage: %s output\n", argv[0]);
        exit(1);
    }

    //open file
    FILE *out;
    out = fopen(argv[1], "w");

    //new graph
    Graph G = newGraph(10);
    Graph T;
    List S = newList();
    int i;
    for (i = 1; i <= 9; i++) {
        addArc(G, i, i + 1);
    }
    addArc(G, 1, 2);

    //add graph and print out the adjacency fields
    for (i = 1; i <= getOrder(G); i++) {
        append(S, i);
    }
    fprintf(out, "\nThe adjacency list of G is:\n");
    printGraph(out, G);

    //Run DFS and get the transpose
    DFS(G, S);
    T = transpose(G);
    fprintf(out, "\nTranspose of G is:\n");
    printGraph(out, T);

    //print out fields
    fprintf(out, "Order of G is %d\n", getOrder(G));
    fprintf(out, "Size of G is %d.\n", getSize(G));
    fprintf(out, "Parent of 10 is %d.\n", getParent(G, 10));
    fprintf(out, "Parent of 3 is %d.\n", getParent(G, 3));
    fprintf(out, "Discover time of 1 is %d.\n", getDiscover(G, 1));
    fprintf(out, "Finish time of 1 is %d.\n", getFinish(G, 1));
    fprintf(out, "Discover time of 9 is %d.\n", getDiscover(G, 9));
    fprintf(out, "Finish time of 9 is %d.\n", getFinish(G, 9));

    //close file
    fclose(out);

    //exit
    return (0);
}

int main(void) {
  if (trOrient())
    printf("Графът е транзитивно неориентируем! \n");
  else
    printGraph();
  return 0;
}

int main(int argc, char **argv) {
    srand(time(NULL));
    
    if (argc < 2) {
        printf("Mandatory parameter is missing. 0 - Generate Kruskal testcase; 1 - Generate Trading Salesman testcase.\n");
    } else if (atoi(argv[1]) == 0) {
        if (argc != 7)
            printf("Usage: 0 nbNodes nbEdges minWeight maxWeight outputName.\n");
        else {
            graph graph = createGraph(atoi(argv[2]), atoi(argv[3]), atof(argv[4]), atof(argv[5]));

            printGraph(&graph, argv[6]);
            //printDot(&graph, 1);

            destroyGraph(&graph);
        }
    } else if (atoi(argv[1]) == 1) {
        if (argc != 4)
            printf("Usage: 1 nbNodes outputName.\n");
        else {
            point *points = generatePoints(atoi(argv[2]));

            printGraphOfPoints(points, atoi(argv[2]), argv[3]);

            destroyPoints(points);
        }
    } else {
        printf("Illegal job id.\n");
        return 0;
    }

    return 0;
}

void dijkstra(graph* G, long initial_node, char debug)
{
	long i,j,k;
	long aN; //actualNode
	G->D[initial_node] = 0;
	aN = initial_node;

	printf("Running dijkstra on graph\n");

	if(debug)
		printGraph(G);

	for(i = 0; i < G->N; i++)
	{
		G->visited[aN] = VISITED;

		if(debug){
			printf("It[%d] aN [%d]",i, aN); printStatus(G); printf("\n");
		}

		//Find all nodes connected to aN
		for(j=0;j<G->N;j++){
			if( (G->node[aN][j] != NO_CONN) ){
				if( (G->D[aN] + G->node[aN][j]) < G->D[j] ){
					G->D[j] = (G->D[aN] + G->node[aN][j]);
				}
			}
		}

		aN = getNextNode(G);
	}
	printf("Finished Dijkstra\n");
}

int main()
{
    int V;
    scanf ("%d", &V);
    struct Graph* graph = createGraph(V);
    int i;

    for (i = 0; i < V; i++)
    {
		int vert, no_neghs;
	    scanf("%d%d", &vert, &no_neghs);
	    int j;
	    for (j = 0; j < no_neghs; j++)
	    {
	    	int neigh;
	    	scanf("%d", &neigh);
	    	addEdge(graph, vert, neigh);
	    }

    }
 
    printGraph(graph);
 
    return 0;
}

int main()
{
    ALGraph *graph = malloc(sizeof(ALGraph));
    createALGraph(graph);
    printGraph(graph);

    if(bellman_ford(graph, 0)>0)
    {
       printshortestPath(graph, 0);
    }
    else
    {
        printf("there is a negative circle\n");
    }
    /* 
    test = -1;
    if(test)
    {
        printf("true\n");
    }
    else
    {
        printf("false\n");
    }
    */
    return 0;
}

int main(int argc, char* argv[]){
   int i, s, max, min, d, n=35;
   Graph G = NULL;

   // Build graph G 
   G = newGraph(n);
   for(i=1; i<n; i++){
      if( i%7!=0 ) addEdge(G, i, i+1);
      if( i<=28  ) addEdge(G, i, i+7);
   }
   addEdge(G, 9, 31);
   addEdge(G, 17, 13);
   addEdge(G, 14, 33);

   // Print adjacency list representation of G
   printGraph(stdout, G);

   // Properties of this graph
   printf("Number of vertices %d", getOrder(G));
   printf("Number of edges: %d", getSize(G));

   // Free objects 
   freeGraph(&G);

   return(0);
}

int main()
{

    int V;
    int choice = 1;
    int src, dest;
    printf("\nHow many nodes you want to have in your graph\n");
    scanf("%d",&V);
    GRAPH *graph = createGraph(V);
    printf("\nEnter an Edge like SRC DEST : ex- 0  1\n");
    while(choice)
    {
        printf("\nENter Edge\n");
        scanf("%d %d",&src,&dest);

        addEdge(graph, src, dest);

        printf("\nContinue?");
        scanf("%d",&choice);

    }

    printGraph(graph);
    return 0;
}

void main() {
	struct graph *graph = createGraph();
	addVertex(graph, 1);
	addVertex(graph, 2);
	addVertex(graph, 3);
	addVertex(graph, 4);
	addVertex(graph, 5);

	addEdge(graph, 1, 2);
	addEdge(graph, 1, 3);
	addEdge(graph, 1, 4);
	addEdge(graph, 2, 1);
	addEdge(graph, 2, 3);
	addEdge(graph, 3, 2);
	addEdge(graph, 3, 1);
	addEdge(graph, 4, 1);
	addEdge(graph, 5, 2);
	addEdge(graph, 5, 3);
	addEdge(graph, 3, 5);
	addEdge(graph, 2, 5);

	printGraph(graph);
	bfsTraversal(graph);
	dfsTraversal(graph);
}

int main(int argc, char const *argv[])
{
    int V;  // The number of nodes
    printf("Enter the number of nodes : \n");
    scanf("%d", &V);

    // Create a Graph G
    struct Graph* G;
    G = (struct Graph*)malloc(sizeof(struct Graph));
    G->V = V;
    // Here the node at index i will have the value i. So, the zeroth index is left empty.
    G->arr = (struct listArray *)malloc((V+1)*sizeof(struct listArray));
    for (int i=1; i<=V; i++) {
        G->arr[i].next = NULL;
    }

    printf("Enter pair of nodes to add Edge :\n");
    printf("(Enter (0, 0) to terminate)\n");
    int node1, node2;
    while(true) {
        scanf("%d %d", &node1, &node2);
        if (node1==0 || node2==0) {break;}
        else
            addEdge(G, node1, node2);
            addEdge(G, node2, node2);
    }

    printGraph(G);

}

int main(){
	ALGrapth G;
	int i, j;

	CreateGraph(&G);

	printGraph(G);

	printf("从顶点1开始深度优先遍历序列");
	DFSTraverse(G, printVex);
	printf("\n");

	printf("从顶点7开始深度优先遍历序列");
	DFSTraverse(G, printVex, 6);
	printf("\n");

	printf("从顶点1开始广度优先遍历序列");
	BFSTraverse(G, printVex);
	printf("\n");

	printf("从顶点7开始广度优先遍历序列");
	BFSTraverse(G, printVex, 6);
	printf("\n");

	printf("\n");
	return 0;
}

void bagOfThreads_bt(struct row* boolMatrix, struct row* warPath, int numEdges, int numProcess) {
	int i, j;
	// Memory ID
    sem_t *sem = calloc(1,sizeof(sem_t)); 
    // Initializing semaphore
    sem_init(sem, 1, 0);

	// Initializes the shared memory and points to it

	// Copies over the original 2D array
    for(i = 0 ; i<numEdges; i++)
		for(j = 0; j < numEdges; j++)
			warPath[i].edgeNums[j] = boolMatrix[i].edgeNums[j];

	//processWarshall(mem_ptr);
	//printf("Done with creation \n");
	threadedWarshall_bt(warPath,numProcess,numEdges);
	printf("Final Graph\n");
	printGraph(warPath,numEdges);
	printf("End\n");

	// Free the shared memory
	//shmdt(mem_ptr);
	//shmctl(memory_id, IPC_RMID, NULL);
    //sem_destroy(sem);
    //munmap(sem, sizeof(sem_t));
    return;
}

int main(){

    int V = 10;
    Graph *graph = createGraph(V);
    if(graph == NULL) return -1;

    geraGrafo(graph);

    printGraph(graph);

    /*
    addEdge(graph, 0, 1, 5);
    addEdge(graph, 0, 4, 2);
    addEdge(graph, 1, 2, 3);
    addEdge(graph, 1, 3, 8);
    addEdge(graph, 1, 4, 1);
    addEdge(graph, 2, 3, 2);
    addEdge(graph, 3, 4, 1);
    addEdge(graph, 4, 2, 4);
    */

    listaHeap *cm = NULL;
    cm = (listaHeap*) dijkstra(graph, 0);

    int i;
    printf("%d:", cm->tam);
    for (i = 0; i < cm->tam; i++) {
        printf("id:%d, idNo:%d, peso:%d\n", i, cm[i].idNo, cm[i].peso);
    }

    printf("ok\n");

    return 0;
}

Graph kruskal(Graph& g)
{
    Graph N;
    Equiv e(g.numEdges);
    qsort((void*) g.arrayEdges, g.numEdges, sizeof(Edge), (QSORT_COMPARE_TYPE) compareEdges);
    if(tracer==2)
    {
        printf("\nThe array of edges after sorting:\n");
        printGraph(g);
    }
    for(int i = 0; i < g.numEdges; i++)
    {
        if(tracer==2)
        {
            printf("\nThe edges %i and %i are being considered.\n",g.arrayEdges[i].vertOne,g.arrayEdges[i].vertTwo);
        }
        if(!together(e, g.arrayEdges[i].vertOne, g.arrayEdges[i].vertTwo))
        {
            if(tracer==2)
            {
                printf("The edges %i and %i were combined.\n",g.arrayEdges[i].vertOne,g.arrayEdges[i].vertTwo);
            }
            combine(e, g.arrayEdges[i].vertOne, g.arrayEdges[i].vertTwo);
            N.arrayEdges[N.numEdges++] = g.arrayEdges[i];
        }
        else
        {
            if(tracer==2)
            {
                printf("The edges %i and %i were not combined.\n",g.arrayEdges[i].vertOne,g.arrayEdges[i].vertTwo);
            }
        }
    }
    return N;
}