<repo_name>mv123453715/CCU_2019_Data_Structure<file_sep>/HW1/Linux版本/Minimize_the_table_size.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define bool int
#define false 0
#define true 1


main()
{
// rule value
    int rule_number = 0;
    char rule_point1[ 100 ][1000] = {'/0'}; //rule_point1
    char rule_point2[ 100 ][1000] = {'/0'}; //rule_point2
    char rule_port[ 100 ][1000] = {'/0'};   //rule_port

// input value
    int input_number = 0;
    char input_point1[ 100 ][1000] = {'/0'};
    char input_point2[ 100 ][1000] = {'/0'};


//determine rule
    //char star[1] = "*";
    bool isfind_port = true;
    int i=0;
    int j=0;

//file input rule
    FILE *fin;
	fin=fopen("input.txt","r");
    fscanf(fin,"%d\n",&rule_number);
    //printf( "rule_number:%d\n",rule_number );
    for (i=0;i<rule_number;i++)
    {
        fscanf(fin,"%s ",&rule_point1[i]);
        fscanf(fin,"%s ",&rule_point2[i]);
        fscanf(fin,"%s\n",&rule_port[i]);
    }//for

//file input input_point
    fscanf(fin,"%d\n",&input_number);
    for (i=0;i<input_number;i++)
    {
        fscanf(fin,"%s ",&input_point1[i]);
        fscanf(fin,"%s\n",&input_point2[i]);

    }//for
    fclose(fin);

//output file
    FILE *fout;
    fout = fopen( "output.txt","w" );
    fprintf( fout,"%d\n",input_number );
    for (i=0;i<input_number;i++){
        fprintf( fout,"%s ",input_point1[i] );
        fprintf( fout, "%s ",input_point2[i] );

//determine
//****************************************************
//if Fully equal
//else if number1 = * , input_point_number2 is correspond to rule_point_number2
//else if number2 = * , input_point_number1 is correspond to rule_point_number1
//else if number1 = * ,number2 = *
//esle drop
//****************************************************
        for (j=0;j<rule_number;j++){
            //printf( "i:%d\n",i );
            //printf( "j:%d\n",j );
            //printf( "input_point1[i]:%s\n",input_point1[i] );
            //printf( "rule_point1[j]:%s\n",rule_point1[j] );
            //printf( "strcmp(rule_point1[j],star)%d\n",strcmp(rule_point1[j],"*") );
            if ( strcmp(input_point1[i],rule_point1[j])==0 && strcmp(input_point2[i],rule_point2[j] )==0 ) {
                fprintf( fout, "%s",rule_port[j] );
                isfind_port = true;
                //printf( "strcmp(input_point1[i],rule_point1[j]) && strcmp(input_point2[i],rule_point2[j] )\n" );
                //printf( "rule_port[j]:%s\n",rule_port[j] );
                break;
            }//if

            else if( strcmp(rule_point1[j],"*")==0 && strcmp(input_point2[i],rule_point2[j] )==0 ){
                fprintf( fout, "%s",rule_port[j] );
                isfind_port = true;
                //printf( "strcmp(rule_point1[j],star) && strcmp(input_point2[i],rule_point2[j] )\n" );
                //printf( "rule_port[j]:%s\n",rule_port[j] );
                break;
            }//else if

            else if( strcmp(input_point1[i],rule_point1[j] )==0 && strcmp(rule_point2[j],"*")==0 ){
                fprintf( fout, "%s",rule_port[j] );
                isfind_port = true;
                //printf( "strcmp(input_point1[i],rule_point1[j] ) && strcmp(rule_point2[j],star)\n" );
                //printf( "rule_port[j]:%s\n",rule_port[j] );
                break;
            }//else if
            else if( strcmp(rule_point1[j], "*")==0 && strcmp(rule_point2[j],"*")==0 ){
                fprintf( fout, "%s",rule_port[j] );
                isfind_port = true;
                //printf( "strcmp(rule_point1[j], star) && strcmp(rule_point2[j],star)\n" );
                //printf( "rule_port[j]:%s\n",rule_port[j] );
                break;
            }//else if
            else{
                isfind_port = false;
            }//else
        }//for
        if ( isfind_port == false ){
            fprintf( fout,  "drop" );
            isfind_port = true ;
        }//if

        fprintf( fout, "\n" );

    }//for
    fclose(fout);


//debug

    printf("%d\n",rule_number);

    for (i=0;i<rule_number;i++)
    {
        printf("%s ",rule_point1[i]);
        printf("%s ",rule_point2[i]);
        printf("%s\n",rule_port[i]);
    }//for



    printf("%d\n",input_number);
    for (i=0;i<input_number;i++)
    {
        printf("%s ",input_point1[i]);
        printf("%s\n",input_point2[i]);

    }//for

}//main
<file_sep>/HW1/Minimize_the_table_size_opt.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_LINE 1024
#define bool int
#define false 0
#define true 1


main()
{
// rule value
    int rule_number = 0;
    char rule_point1[ 1024 ]; //rule_point1
    char rule_point2[ 1024 ]; //rule_point2
    char rule_port[ 1024 ];   //rule_port

// input value
    int input_number = 0;
    char input_point1[ 1024 ];
    char input_point2[ 1024 ];


//determine rule
	char star[1] = "*";
    bool isfind_port = true;

//file input rule
    FILE *fin;
	fin=fopen("input.txt","r");
    fscanf(fin,"%d\n",&rule_number);

    for (int i=0;i<rule_number;i++)
    {
        fscanf(fin,"%c ",&rule_point1[i]);
        fscanf(fin,"%c ",&rule_point2[i]);
        fscanf(fin,"%c\n",&rule_port[i]);
    }//for

//file input input_point
    fscanf(fin,"%d\n",&input_number);
    for (int i=0;i<input_number;i++)
    {
        fscanf(fin,"%c ",&input_point1[i]);
        fscanf(fin,"%c\n",&input_point2[i]);

    }//for
    fclose(fin);

//output file
    FILE *fout;
    fout = fopen( "output.txt","w" );
    fprintf( fout,"%d\n",rule_number);
    for (int i=0;i<input_number;i++){
        fprintf( fout,"%c ",input_point1[i] );
        fprintf( fout, "%c ",input_point2[i] );

//determine
//****************************************************
//if Fully equal
//else if number1 = * , input_point_number2 is correspond to rule_point_number2
//else if number2 = * , input_point_number1 is correspond to rule_point_number1
//else if number1 = * ,number2 = *
//esle drop
//****************************************************
        for (int j=0;j<rule_number;j++){
            if ( (input_point1[i] == rule_point1[j]) && (input_point2[i] == rule_point2[j] ) ) {
                fprintf( fout, "%c",rule_port[j] );
                isfind_port = true;
                break;
            }//if

            else if( (rule_point1[j] == star[0]) &&(input_point2[i] == rule_point2[j] ) ){
                fprintf( fout, "%c",rule_port[j] );
                isfind_port = true;
                break;
            }//else if

            else if( (input_point1[i] == rule_point1[j] ) && (rule_point2[j] == star[0]) ){
                fprintf( fout, "%c",rule_port[j] );
                isfind_port = true;
                break;
            }//else if
            else if( (rule_point1[j] == star[0]) && (rule_point2[j] == star[0]) ){
                fprintf( fout, "%c",rule_port[j] );
                isfind_port = true;
                break;
            }//else if
            else{
                isfind_port = false;
            }//else
        }//for
        if ( isfind_port == false ){
            fprintf( fout,  "drop" );
            isfind_port = true ;
        }//if
        fprintf( fout, "\n" );

    }//for
    fclose(fout);


//debug
    /*
    printf("%d\n",rule_number);

    for (int i=0;i<rule_number;i++)
    {
        printf("%c ",rule_point1[i]);
        printf("%c ",rule_point2[i]);
        printf("%c\n",rule_port[i]);
    }//for



    printf("%d\n",input_number);
    for (int i=0;i<input_number;i++)
    {
        printf("%c ",input_point1[i]);
        printf("%c\n",input_point2[i]);

    }//for
    */
}//main
<file_sep>/README.md
# CCU_2019_Data_Structure
## HW1 : Minimize the table size(network)
## HW2 : Loop-Free Route Updates for Software-Defined Networks (TON, 2018)
## HW3 : Accept or reject a flow with 2-segment routing “Optimized Network Traffic Engineering using Segment Routing,” in IEEE INFOCOM 2015
## HW4 :“Constant query time (1+𝜖)-approximate distance oracle for planar graphs,” in TCS 2019
<file_sep>/HW4/DS_HW4_406410114_Exact_Distance_Query.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include <math.h>
#define SIZE 100
#define V 100
typedef struct link_input{
	int linkID;
	int firstNodeID;
	int secondNodeID; // sorting
	double distance;
} link_input;

typedef struct node{
	int point;
	double weight;
	struct node *next;
} node;

typedef struct flow_input{
	int flowID;
	int sourceID;
	int destinationID; // sorting
} flow_input;


struct DataItem {
   int node1;
   int node2;
   double distance;
   int key;
   struct DataItem *next;
};

typedef struct node_dis{
    char type;// 's':sample  'n' :not sample
    double shortest_dis;
    int shortest_dis_sample;
    int shortest_dis_sample_index;
	double distance[100];
    int sml_than_sht_num;
    int sml_than_sht_node[100];
    double sml_than_sht_dis[100];
} node_dis;



struct DataItem* dummyItem;
struct DataItem* item;
int node_num = 0,link_num =0,flow_num =0,n,hash_prime,sample_node_num,nd_dis_smp_i = 0,hash_pair_num = 0,hash_tb_size;
int sample_node[100];
node_dis node_dis_sample[100];
double wei_graph[100][100];
link_input link_info[10000];
flow_input flow_path[10000];
node node_info[1000] = { 0,0,NULL };



int hashCode(int key );
//struct DataItem* hashArray = malloc(sizeof(struct DataItem) * hash_tb_size);
struct DataItem* hashArray[SIZE];
struct DataItem *search(int key ) ;
void insert(int key,int node1,int node2,double distance);
int compute_key(int node1,int node2 );
void display();
void ReadInput();
void create_wei_graph( node node_info[] );
int minDistance(int dist[], bool sptSet[]);
int printSolution(int dist[]);
void dijkstra(double graph[V][V], int src,char mode[]) ;
int seclect_next_sample();
void Debug_node_dis_sample();
double pair_distance_search( int src,int des );
void store_to_hash_tb();

int main() {
    int i,j,k;
    double pari_distance;
    //=======================================read_input================================================================//
    ReadInput();
    //=======================================compute hash_tb_size and  sample_node_num=================================//
    hash_tb_size = ceil(pow((float)node_num,1.5));
    sample_node_num =ceil(sqrt((float)node_num));

    //=======================================hash_pair_num=============================================================//
    for ( i = node_num- sample_node_num; i< node_num ; i++)
        hash_pair_num+=i;
    //printf( "hash_pair_num:%d\n",hash_pair_num );

    //=======================================generate graph=============================================================//
    create_wei_graph( node_info );

    //=======================================boot =========================================================================//
    for ( i =0 ; i < node_num ; i++ ){
        node_dis_sample[i].type = 'n';
        node_dis_sample[i].sml_than_sht_num =0;
    }//for

    //=======================================first sample_node is 0 ======================================================//
    sample_node[0] = 0;
    node_dis_sample[0].type = 's';

    //printf( "sample_node_num:%d\n",sample_node_num );

    //=======================================select other sample  ======================================================//
    for (i =0 ; i < sample_node_num ; i++){
        dijkstra(wei_graph, sample_node[i],"sample_node");  //sample_node
        sample_node[nd_dis_smp_i] = seclect_next_sample();
    }//for

    //======================================= store smaller_than_shortest_distance =====================================//
    for (i =0 ; i < node_num ; i++){
        dijkstra(wei_graph, i,"smaller_than_shortest_dis");  //smaller_than_shortest_dis
    }//for

    //======================================= store into has table =====================================================//
    store_to_hash_tb();
    printf( "%d\n",hash_pair_num );

    //======================================= pair_distance_search =====================================================//
    for ( i = 0;i < flow_num;i++ ){
        pari_distance = pair_distance_search( flow_path[i].sourceID,flow_path[i].destinationID );
        printf( "%d %d %d %.0lf\n",i,flow_path[i].sourceID,flow_path[i].destinationID,pari_distance );
    }//for


    //Debug_node_dis_sample();

   return 0;
}



void dijkstra(double graph[V][V], int src,char mode[]) // shortest path
{
    int path[V],path_i=0,sou_des_trace[V][V],sdt_i = 0;
    int dist[V];
    // distance from src to i

    for ( int i = 0 ;i<node_num;i++){
        for(int j= 0 ;j<node_num ;j++)
            sou_des_trace[i][j] = -1;
    }//for


    bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest
    // path tree or shortest distance from src to i is finalized

    // Initialize all distances as INFINITE and stpSet[] as false
    for (int i = 0; i < node_num; i++)
        dist[i] = INT_MAX, sptSet[i] = false;   //所有的距離都最大  且還沒選過

    // Distance of source vertex from itself is always 0
    dist[src] = 0;  //source點

    // Find shortest path for all vertices
    for (int count = 0; count < node_num - 1; count++) {
        // Pick the minimum distance vertex from the set of vertices not
        // yet processed. u is always equal to src in the first iteration.
        int u = minDistance(dist, sptSet);

        // Mark the picked vertex as processed
        sptSet[u] = true;   //改成true
        //path[path_i] = u;  //走過路徑
        //path_i++;

        // Update dist value of the adjacent vertices of the picked vertex.
        for (int v = 0; v < node_num; v++){
            //sdt_i=0;
            // Update dist[v] only if is not in sptSet, there is an edge from
            // u to v, and total weight of path from src to  v through u is
            // smaller than current value of dist[v]
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v]){  //假設是false 並且graph不是0  dist有值  可以到
                dist[v] = dist[u] + graph[u][v];  //
                //sou_des_trace[v][sdt_i] = u;
                //printf( "sou_des_trace[%d][sdt_i]:%d\n",v,sou_des_trace[v][sdt_i] );
                //sdt_i++;
            }//if
        }//for
    }//for






    // print the constructed distance array
    //printf( "%s\n",mode );
    // append node to sample node distance
    if ( strcmp(mode,"sample_node")==0 ){
        //printf( "%c\n",mode );
        for ( int i = 0; i<node_num;i++ )
            node_dis_sample[i].distance[nd_dis_smp_i] =dist[i];
    nd_dis_smp_i++;
    }//if

    bool record = false;
    bool sample = false;

    //smaller_than_shortest_distance
    if ( strcmp(mode,"smaller_than_shortest_dis")==0 ){
        for ( int i=0;i<node_num;i++ ){
            record = false;
            sample = false;
            if ((dist[i] <= node_dis_sample[src].shortest_dis) && ( dist[i]!=0 )){
                for ( int j = 0 ; j<sample_node_num;j++){
                    if ( sample_node[j] == i )
                        sample =true;
                }//for
                for ( int j = 0;j<node_dis_sample[i].sml_than_sht_num;j++ ){
                    //printf( "node_dis_sample[%d].sml_than_sht_node[%d]:%d\n",i,j,node_dis_sample[i].sml_than_sht_node[j] );
                    //printf( "src:%d\n",src );
                    if ( node_dis_sample[i].sml_than_sht_node[j] == src )
                        record = true;
                }//for

                //it is not sample node  and not record
                if ( record == false && sample ==false && node_dis_sample[src].type == 'n' ){
                    node_dis_sample[src].sml_than_sht_node[node_dis_sample[src].sml_than_sht_num] = i;
                    node_dis_sample[src].sml_than_sht_dis[node_dis_sample[src].sml_than_sht_num] = dist[i];
                    node_dis_sample[src].sml_than_sht_num++;
                    hash_pair_num++;
                }//false
            }//if
        }//for
    }//if



    printSolution(dist);
}//dijkstra


int seclect_next_sample(){
    int i,j;
    int max_dis_node,sht_sample_node = 0;
    double shortest_dis,longest_dis ;

    //every node update shortest_distance
    for ( i = 0 ;i<node_num;i++ ){
        //printf( "i:%d\n",i );
        for ( j = 0 ; j< nd_dis_smp_i;j++ ){
            if ( j == 0 ){
                shortest_dis =node_dis_sample[i].distance[j];
                sht_sample_node = j;
                //printf( "shortest_dis:%lf\n",shortest_dis );
                //printf( "sample_node[sht_sample_node]:%d\n",sample_node[sht_sample_node] );
            }//if
            else {
                if ( node_dis_sample[i].distance[j] < shortest_dis ){
                    shortest_dis =node_dis_sample[i].distance[j];
                    sht_sample_node = j;
                    //printf( "shortest_dis:%lf\n",shortest_dis );
                    //printf( "sample_node[sht_sample_node]:%d\n",sample_node[sht_sample_node] );
                }//if
            }//else
        }//for
        node_dis_sample[i].shortest_dis = shortest_dis;
        node_dis_sample[i].shortest_dis_sample = sample_node[sht_sample_node];
        node_dis_sample[i].shortest_dis_sample_index = sht_sample_node;
    }//for

    //select the distance which is to nearest sample node  longest node
    for ( i = 0 ;i<node_num;i++ ){
        if ( node_dis_sample[i].shortest_dis > longest_dis ){
            longest_dis = node_dis_sample[i].shortest_dis;
            max_dis_node = i;
        }//if
    }//for

    //return
    if ( nd_dis_smp_i < sample_node_num  )
        node_dis_sample[max_dis_node].type = 's';
    return max_dis_node;
}//seclect_next_sample


void store_to_hash_tb(){
    int i,j,k,key;

    //sample node
    for ( i=0;i<node_num;i++ ){
        for ( j = 0;j<sample_node_num;j++ ){
            if ( i != sample_node[j]  ){ // 自己不用存

                //compute key
                key = compute_key(i,sample_node[j] );
                insert( key,i,sample_node[j],node_dis_sample[i].distance[j] );
                //printf( "i:%d\n",i );
                //printf( "key:%d\n",key );
                //printf( "sample_node[%d]:%d\n",j,sample_node[j] );
                //printf( "node_dis_sample[%d].distance[%d]:%lf\n",i,j,node_dis_sample[i].distance[j] );
            }//if
        }//for
    }//for

    //smaller_than_shortest_distance
    for (  i=0;i<node_num;i++  ){
        for ( j = 0 ; j<node_dis_sample[i].sml_than_sht_num;j++ ){
            key = compute_key(i,node_dis_sample[i].sml_than_sht_node[j] );
            insert( key,i,node_dis_sample[i].sml_than_sht_node[j],node_dis_sample[i].sml_than_sht_dis[j] );
        }//for
    }//for


    //display();




}//store_to_hash_tb()


int compute_key(int node1,int node2 ) {
   return ((node1+1)*(node2+1))%hash_prime%hash_tb_size;
}

int hashCode(int key) {
   return key % SIZE;
}

void insert(int key,int node1,int node2,double distance) {

    struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
    item->node1 = node1;
    item->node2 = node2;
    item->distance = distance;
    item->key = key;
    item->next = NULL;
    //get the hash
    int hashIndex = hashCode(key);
    struct DataItem *now_ptr = (struct DataItem*) malloc(sizeof(struct DataItem));
    now_ptr = hashArray[hashIndex];
    //printf( " hashArray[hashIndex]:%d", hashArray[hashIndex] );
    //printf( " now_ptr:%d\n", now_ptr );
    if ( now_ptr == NULL ){
        //printf( "hashIndex:%d is null.\n",hashIndex );
        hashArray[hashIndex] = item;
    }//if
    else {

        while ( now_ptr->next != NULL ){
            //printf(" (%d,%d,%d,%lf)\n",now_ptr->key,now_ptr->node1,now_ptr->node2,now_ptr->distance);
            now_ptr = now_ptr->next;
        }//while

        //printf( "hashIndex:%d is not null.\n",hashIndex );
        now_ptr->next = item;
        //printf(" (%d,%d,%d,%lf)\n",now_ptr->key,now_ptr->node1,now_ptr->node2,now_ptr->distance);
    }//else
}



struct DataItem *search(int key) {
   //get the hash
   int hashIndex = hashCode(key);

   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {

      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];

      //go to next cell
      ++hashIndex;

      //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;
}



double pair_distance_search( int src,int des ){
    //printf( "src:%d des:%d\n",src,des );
    int i,j,k;
    int index;
    double distance;
    double src_to_des_dis ,des_to_src_dis;


    //case 1: src = des ,return 0
    //case 2: src is sample and des is sample ,directly search des to src
    //case 3: src is sample and des is not sample ,directly search des to src
    //case 4: src is sample and des is not sample ,directly search  src to des
    //case 5:  src is not sample and des is not sample ,compare  src_to_des and des_to_src
    if ( src == des )
        return 0.0;
    else if ( node_dis_sample[src].type == 's' && node_dis_sample[des].type == 's' ){
        for ( i = 0 ;i<sample_node_num;i++ ){
            if ( sample_node[i] == des )
                index = i;
        }//for
        distance = node_dis_sample[src].distance[index] ;
        return distance;
    }//if
    else if (  node_dis_sample[src].type == 's' && node_dis_sample[des].type == 'n'  ){
        //printf( "s,n\n" );
        for ( i = 0 ;i<sample_node_num;i++ ){
            if ( sample_node[i] == src )
                index = i;
        }//for

        //printf( "index;%d\n",index );
        distance = node_dis_sample[des].distance[index] ;
        return distance;
    }//else if
    else if (  node_dis_sample[src].type == 'n' && node_dis_sample[des].type == 's'  ){
        for ( i = 0 ;i<sample_node_num;i++ ){
            if ( sample_node[i] == des )
                index = i;
        }//for
        distance = node_dis_sample[src].distance[index] ;
        return distance;
    }//else if

    else if (   node_dis_sample[src].type == 'n' && node_dis_sample[des].type == 'n'  ){

        //compute source to destination
        //printf( "src:%d des:%d\n",src,des );
        //printf( "=========================compute source to destination=====================\n" );
        bool is_smaller_than_shortest_dis = false;
        for ( i = 0 ;i<node_dis_sample[src].sml_than_sht_num;i++ ){
            if ( des == node_dis_sample[src].sml_than_sht_node[i]  ){
                //printf( "is_smaller_than_shortest_dis is true\n" );
                is_smaller_than_shortest_dis = true;
                src_to_des_dis = node_dis_sample[src].sml_than_sht_dis[i];
            }//if
        }//for

        if ( is_smaller_than_shortest_dis == false ){
            //printf( "is_smaller_than_shortest_dis is false\n" );
            src_to_des_dis = node_dis_sample[src].shortest_dis
                            + node_dis_sample[des].distance[node_dis_sample[src].shortest_dis_sample_index];
            //printf( "node_dis_sample[src].shortest_dis:%lf\n",node_dis_sample[src].shortest_dis );
            //printf( "node_dis_sample[des].distance[node_dis_sample[src].shortest_dis_sample_index]:%lf\n",node_dis_sample[des].distance[node_dis_sample[src].shortest_dis_sample_index] );
            //printf ( "src_to_des_dis:%lf\n",src_to_des_dis );
        }//if
        //compute destination to source

        //printf( "=========================compute destination to source=====================\n" );
        is_smaller_than_shortest_dis = false;
        for ( i = 0 ;i<node_dis_sample[des].sml_than_sht_num;i++ ){
            if ( src == node_dis_sample[des].sml_than_sht_node[i]  ){
                 //printf( "is_smaller_than_shortest_dis is true\n" );
                is_smaller_than_shortest_dis = true;
                //printf( "node_dis_sample[des].sml_than_sht_dis[%d]:%lf\n",i,node_dis_sample[des].sml_than_sht_dis[i] );
                //printf( "src:%d,i:%d\n",src,i );
                des_to_src_dis = node_dis_sample[des].sml_than_sht_dis[i];
                //printf ( "des_to_src_dis:%lf\n",des_to_src_dis );
            }//if
        }//for

        if ( is_smaller_than_shortest_dis == false ){
            //printf( "is_smaller_than_shortest_dis is false\n" );
            des_to_src_dis = node_dis_sample[des].shortest_dis
                            + node_dis_sample[src].distance[node_dis_sample[des].shortest_dis_sample_index];
            //printf( "node_dis_sample[des].shortest_dis:%lf\n",node_dis_sample[des].shortest_dis );
            //printf( "node_dis_sample[src].distance[node_dis_sample[des].shortest_dis_sample_index]:%lf\n",node_dis_sample[src].distance[node_dis_sample[des].shortest_dis_sample_index] );
            //printf ( "des_to_src_dis:%lf\n",des_to_src_dis );
        }//if


        //take smaller distance

        //printf ( "des_to_src_dis:%lf\n",des_to_src_dis );

        if ( src_to_des_dis<des_to_src_dis )
            distance = src_to_des_dis;
        else
            distance = des_to_src_dis;

        return distance;
    }//else if

}//pair_distance_search


void display() {

    int i = 0,num = 0;
    printf( "key , node1, node2,distance\n" );
    for(i = 0; i<SIZE; i++) {
        if(hashArray[i] != NULL){
            struct DataItem *now_ptr = (struct DataItem*) malloc(sizeof(struct DataItem));
            now_ptr = hashArray[i];
            while ( now_ptr !=NULL  ){
                printf(" (%d,%d,%d,%lf)\n",now_ptr->key,now_ptr->node1,now_ptr->node2,now_ptr->distance);
                now_ptr = now_ptr->next;
                num++;
            }//while
        }//if
    }

    printf("num:%d\n",num);


    /*
    int i = 0;
    printf( "key , node1, node2,distance\n" );
    for(i = 0; i<SIZE; i++) {

        if(hashArray[i] != NULL)
            printf(" (%d,%d,%d,%lf)\n",hashArray[i]->key,hashArray[i]->node1,hashArray[i]->node2,hashArray[i]->distance);
        else
            printf(" ~~ ");
    }

    printf("\n");
    */
}



void ReadInput(){
//*****************************************

//******************************************
    //int input_number = 0;
    int input = 0;
    double d_input ;

//determine rule
    int i=0;
//file input rule

    //FILE *fin;
	//fin=fopen(filename,"r");
    scanf("%d",&node_num);
    //printf( "node_num:%d\n",node_num );
    scanf("%d",&link_num);
    scanf("%d",&hash_prime);
    //printf( "node_num:%d\n",node_num );

    for (i=0;i<link_num;i++)
    {
        scanf("%d",&input);
        link_info[i].linkID = input ;
        scanf("%d",&input);
        link_info[i].firstNodeID = input ;
        scanf("%d",&input);
        link_info[i].secondNodeID = input ;
        scanf("%lf",&d_input);
        link_info[i].distance = d_input ;
    }//for

    scanf("%d",&flow_num);
    //printf( "flow_num:%d\n",flow_num );

    for (i=0;i<flow_num;i++)
    {
        scanf("%d",&input);
        flow_path[i].flowID = input ;
        scanf("%d",&input);
        flow_path[i].sourceID = input ;
        scanf("%d",&input);
        flow_path[i].destinationID = input ;
    }//for


    //int node_index = -1 ;
    //int max_finode_id =  link_info[node_num-1].firstNodeID ;
    node *now_ptr = (node *) malloc(sizeof(node));
    for ( i=0;i<node_num;i++ ){
        now_ptr = &node_info[node_num];
        now_ptr->next = NULL;
    }//for

    //create Adjacency Lists  use pointer array
    for ( i=0;i<link_num;i++ ){
        //printf( "-----------------------round--------------------------\n" );
        //printf( "link_info[i].firstNodeID :%d\n",link_info[i].firstNodeID );
        //printf( "node_index :%d\n ",node_index  );
        //first node
        now_ptr = &node_info[link_info[i].firstNodeID];
        node *new_ptr = (node *) malloc(sizeof(node));
        while ( now_ptr->next != NULL )
            now_ptr = now_ptr->next;

        new_ptr->point = link_info[i].secondNodeID;
        //printf( "new_ptr->point:%d\n",new_ptr->point );
        new_ptr->weight = link_info[i].distance;
        //printf( "new_ptr->linkCapacity:%d\n",new_ptr->linkCapacity );
        now_ptr->next = new_ptr;
        now_ptr = now_ptr->next;
        now_ptr->next = NULL;

        //second node
        now_ptr = &node_info[link_info[i].secondNodeID];
        node *new_ptr2 = (node *) malloc(sizeof(node));
        while ( now_ptr->next != NULL )
            now_ptr = now_ptr->next;

        new_ptr2->point = link_info[i].firstNodeID;
        //printf( "new_ptr2->point:%d\n",new_ptr2->point );
        new_ptr2->weight = link_info[i].distance;
        //printf( "new_ptr2->linkCapacity:%d\n",new_ptr2->linkCapacity );
        now_ptr->next = new_ptr2;
        now_ptr = now_ptr->next;
        now_ptr->next = NULL;
    }//for

}//ReadInput


void create_wei_graph( node node_info[] ){
    int i,j;

    for ( i=0;i<node_num;i++ ){
        for ( j=0;j<node_num;j++ ){
            //wei_graph[i][j]=  -1.0;
            wei_graph[i][j]=  0;
        }//for
    }//for



    for ( i=0;i<node_num;i++ ){
        for ( j=0;j<node_num;j++ ){
            node *now_ptr = (node *) malloc(sizeof(node));
            now_ptr = &node_info[i];
            while ( now_ptr->next != NULL ){
                //wei_graph[i][now_ptr->next->point] = now_ptr->next->weight;
                wei_graph[i][now_ptr->next->point] = now_ptr->next->weight;
                now_ptr = now_ptr->next;
            }//wile
        }//for
    }//for

    /*
    printf( "wei_graph\n" );
    for ( i=0;i<node_num;i++ ){
        for ( j=0;j<node_num;j++ ){
            printf( "%lf ",wei_graph[i][j] );
        }//for

        printf( "\n" );
    }//for
    */



}//shorest_path


int minDistance(int dist[], bool sptSet[])
{
    // Initialize min value
    int min = INT_MAX, min_index;  //

    for (int v = 0; v < node_num; v++)
        if (sptSet[v] == false && dist[v] <= min){

            min = dist[v], min_index = v;  //  距離  並且回傳index
            //printf( " min_index:%d\n", min_index );
        }//if


    return min_index;
}

int printSolution(int dist[])
{
    printf("Vertex \t\t Distance from Source\n");
    for (int i = 0; i < node_num; i++)
        printf("%d \t\t %d\n", i, dist[i]);
}






void Debug_node_dis_sample(){
    int i,j,k;

    printf( "================sample node====================\n" );
    for( i=0;i<nd_dis_smp_i ;i++ ){
        printf( "sample_node[%d]:%d\n",i,sample_node[i] );
    }//for

    printf( "================Debug_node_dis_sample====================\n" );
    for ( i = 0 ; i<node_num;i++ ){
        printf("node_dis_sample[%d].type:%c\n",i,node_dis_sample[i].type);
        printf("node_dis_sample[%d].shortest_dis:%lf\n",i,node_dis_sample[i].shortest_dis);
        printf("node_dis_sample[%d].sml_than_sht_num:%d\n",i,node_dis_sample[i].sml_than_sht_num);
        printf("node_dis_sample[%d].shortest_dis_sample:%d\n",i,node_dis_sample[i].shortest_dis_sample);
        printf("node_dis_sample[%d].shortest_dis_sample_index:%d\n",i,node_dis_sample[i].shortest_dis_sample_index);
        for( j=0;j<nd_dis_smp_i ;j++ ){
            printf("node_dis_sample[%d].distance[%d]:%lf\n",i,j,node_dis_sample[i].distance[j]);
        }//for
        for ( j = 0;j<node_dis_sample[i].sml_than_sht_num;j++ ){
            printf( "node_dis_sample[%d].sml_than_sht_node[%d]:%d\n",i,j,node_dis_sample[i].sml_than_sht_node[j] );
            printf( "node_dis_sample[%d].sml_than_sht_dis[%d]:%lf\n",i,j,node_dis_sample[i].sml_than_sht_dis[j] );
        }//for
    }//for
}//Debug_node_dis_sample
<file_sep>/HW2/CODE/DS_HW2_406410114.c


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

//node_struct
typedef struct node{
	int point;
	char type[10] ;
	int white_index; // sorting
	int heap;
	struct node *original_path;
	struct node *next_path;
	struct node *solution_path;
} node;

//update_buffer
typedef struct update_infor{
	int update_point ;
	int distance_max ;
	int white_index;
	int heap_same;
} update_infor;


int number = 0,turn = 1;
void Debug_Print_Node_Point( node node_point[],int number );
node * ReadInput( node node_point[], char *filename );
void * PointRedConnectNextpath( node node_point[]);
void Print_Node_Point( node node_point[],int number );
void * AddPointType( node node_point[]);
//void * Odd_Shortcut_Phase( node node_point[],int up_info[]);
void * Odd_Shortcut_Phase_Mnay( node node_point[],update_infor up_info[]);
//void * Even_Prune_Phase( node node_point[],int update_point,int distance_max);
void * Even_Prune_Phase_Many( node node_point[],update_infor up_info[]);
int * IsFinishOddEven( node node_point[]);
void * PointBlackDisconnectNextpath( node node_point[]);
int * IsFinishRed( node node_point[]);
int * IsFinishBlack( node node_point[]);
update_infor up_info_many[1000] = {0,0};


int main()
{
//*****************************************
//1.ReadInput
//2.add type
//3.PointRedConnectNextpath
//4.odd and even
//5.PointBlackDisconnectNextpath
//6.print_result
//******************************************

    node node_point[1000];
    int round = 0,i = 0,isfinoddeven = 0,j = 0,isfinred = 0,isfinblack=0;
    int debug_i =0;
    int result[1000][100];

    //1.ReadInput
    ReadInput( node_point, "input.txt" );

    //2.add type

    //if no point return 0
    if ( number == 0 )
        return 0;
    AddPointType( node_point);
    //Debug_Print_Node_Point( node_point,number );
    //store result
    for ( i = 0 ; i < number ; i++ ){
        if ( node_point[i].original_path == NULL )
            result[round][i] = -1;
        else
            result[round][i] = node_point[i].original_path->point ;
    }//for
    round++;
    //Print_Node_Point( node_point,number );
    //printf( "ori:\n" );
    //Debug_Print_Node_Point( node_point,number );

    isfinred = IsFinishRed( node_point);
    //3.PointRedConnectNextpath

    for ( j =0 ; j < number ; j++ ){
        if ( isfinred == 0 )
            break;
        if((strcmp(node_point[j].type,"red") == 0)){
            PointRedConnectNextpath( node_point);
            //Print_Node_Point( node_point,number );
            //store result
            for ( i = 0 ; i < number ; i++ ){
                if ( node_point[i].original_path == NULL )
                    result[round][i] = -1;
                else
                    result[round][i] = node_point[i].original_path->point ;
            }//for
            round++;
            break;
        }//if
    }//for

    //printf( "red:\n" );
    //Debug_Print_Node_Point( node_point,number );
    //determine IsFinishOddEven
    isfinoddeven = IsFinishOddEven( node_point);

    //4.odd and even
    for ( round ; isfinoddeven == 0  ;debug_i++ ){
        // reset buffer
        for ( j = 0 ; j <1000;j++ ){
            up_info_many[j].update_point = 0;
            up_info_many[j].distance_max = 0;
            up_info_many[j].white_index = 0;
        }//for


        //odd
        Odd_Shortcut_Phase_Mnay( node_point,up_info_many);
        //printf( "odd_round%d:\n",round );
        //Debug_Print_Node_Point( node_point,number );
        //store result
        for ( i = 0 ; i < number ; i++ ){
            if ( node_point[i].original_path == NULL )
                result[round][i] = -1;
            else
                result[round][i] = node_point[i].original_path->point ;
        }//for
        round++;


        //check is_finish
        if ( IsFinishOddEven( node_point)==true )
            break;

        //even
        Even_Prune_Phase_Many( node_point,up_info_many);
        //printf( "even_round%d:\n",round );
        //Debug_Print_Node_Point( node_point,number );

        //store result
        for ( i = 0 ; i < number ; i++ ){
            if ( node_point[i].original_path == NULL )
                result[round][i] = -1;
            else
                result[round][i] = node_point[i].original_path->point ;
        }//for
        round++;
        //Debug_Print_Node_Point( node_point,number );
        //Print_Node_Point( node_point,number );
        isfinoddeven = IsFinishOddEven( node_point);

    }//for

    //5.PointBlackDisconnectNextpath

    isfinblack =IsFinishBlack( node_point);
    for ( j =0 ; j < number && isfinblack!=0 ; j++ ){
        if((strcmp(node_point[j].type,"black") == 0)){
            PointBlackDisconnectNextpath( node_point);
            //Print_Node_Point( node_point,number );
            //store result
            for ( i = 0 ; i < number ; i++ ){
                if ( node_point[i].original_path == NULL )
                    result[round][i] = -1;
                else
                    result[round][i] = node_point[i].original_path->point ;
            }//for
            round++;
            break;
        }//if
    }//for

    //6.print_result
    printf( "%d\n",round );
    for ( i = 0 ; i < round ; i++ ){
        for ( j = 0; j <number ; j++ ){
            printf( "%d",result[i][j] );
            if ( j < number-1 )
                printf( " " );
        }//for
        printf( "\n" );
    }//for
    //Print_Node_Point( node_point,number );
    //Debug_Print_Node_Point( node_point,number );


    return 0 ;
}//main

//1.ReadInput
node * ReadInput( node node_point[], char *filename ){
//*****************************************
//point: point number
//type : red or black or white
// white_index  :  white_point index
// node *original_path:solid line
// node *next_path ; dotted line
//  node *solution_path : answer
//******************************************
    int input_number = 0;
    int node_number = 0 ;

//determine rule
    int i=0;
    int j=0;
//file input rule

    FILE *fin;
	fin=fopen(filename,"r");
    fscanf(fin,"%d\n",&number);
    //printf( "number:%d\n",number );


    for (i=0;i<number;i++)
    {
        node_point[i].point = i ;
    }//for

    for (i=0;i<number;i++)
    {
        fscanf(fin,"%d",&node_number);
        //printf("node_number%d\n",node_number);
        if (node_number == -1)
            node_point[i].original_path = NULL ;
        else
            node_point[i].original_path = &node_point[node_number] ;

        if ( i < number-1 )
            fscanf(fin," ");
        //printf("node_point[i].original_path:%d\n",node_point[i].original_path);
    }//for
    fscanf(fin,"\n");

    for (i=0;i<number;i++)
    {
        fscanf(fin,"%d ",&node_number);
        if (node_number == -1) {
            node_point[i].next_path = NULL ;
            node_point[i].solution_path = NULL ;
        }//if
        else{
            node_point[i].next_path = &node_point[node_number] ;
            node_point[i].solution_path = &node_point[node_number] ;
        }//else
        if ( i < number-1 )
            fscanf(fin," ");
        node_point[i].heap = 1;
    }//for

    fclose(fin);
    return node_point;
}//ReadInput



void * AddPointType( node node_point[]){
//*****************************************
//red : original_path == NULL
//black : next_path == NULL
//white: d and else
//******************************************
    int i,white_index;
    white_index = 0;
    node *now_point;
    now_point = malloc(sizeof(now_point));
    for ( i = 0 ; i < number ; i++ ){
        if ( i == number-1 ){
            strcpy(node_point[i].type,"white");
            node_point[i].white_index = white_index;
            white_index++;
            //printf( "%d\n",i );
            //printf( "node_point[i].white_index:%d\n",node_point[i].white_index );
        }//if
        else if(node_point[i].original_path == NULL)
            strcpy(node_point[i].type,"red");
        else if ( node_point[i].next_path == NULL )
            strcpy(node_point[i].type,"black");
        else{
            strcpy(node_point[i].type,"white");
            //node_point[i].white_index = white_index;
            //white_index++;
            //printf( "%d\n",i );
            //printf( "node_point[i].white_index:%d\n",node_point[i].white_index );
        }//else
    }//for

    if ( strcmp( node_point[0].type,"white" ) == 0 ){
        node_point[0].white_index = white_index;
        white_index++;
    }//if

    now_point = node_point[0].original_path;
    while ( now_point != NULL ){
        //printf( "now_point->:%d\n",now_point->point );
        if ( strcmp( now_point->type,"white" ) == 0 ){
            now_point->white_index = white_index;
            white_index++;
        }//while

        now_point = now_point->original_path;
    }//while
}//ReadInput


void * PointRedConnectNextpath( node node_point[]){
//*****************************************
//if red connect dotted line , disconnect solid line
//******************************************
    int i;
    for ( i = 0 ; i < number ; i++ ){
        if((strcmp(node_point[i].type,"red") == 0)){
            node_point[i].original_path = node_point[i].next_path;
            node_point[i].next_path = NULL;
        }//if
    }//for
}//PointRedConnectNextpath

int * IsFinishOddEven( node node_point[]){
//*****************************************
//determine IsFinishOddEven ,if Finish  return 1 else return 0
//******************************************
    int i;
    for ( i = 0 ; i < number ; i++ ){
        if ( node_point[i].solution_path == NULL )
            continue;
        if(node_point[i].original_path != node_point[i].solution_path)
            return 0;
    }//for

    return 1;//true
}//PointRedConnectNextpath

int * IsFinishRed( node node_point[]){
//*****************************************
//determine IsFinishhRed ,if Finish  return 1 else return 0
//******************************************
    int i;
    for ( i = 0 ; i < number ; i++ ){
        if ( (strcmp( node_point[i].type,"red" ) == 0))
            return 1; //true
    }//for

    return 0; //false
}//PointRedConnectNextpath


int * IsFinishBlack( node node_point[]){
//*****************************************
//determine IsFinishBlack ,if Finish  return 1 else return 0
//******************************************
    int i;
    for ( i = 0 ; i < number ; i++ ){
        if ( (strcmp( node_point[i].type,"black" ) == 0))
            return 1; //true
    }//for

    return 0; //false
}//PointRedConnectNextpath






void * Odd_Shortcut_Phase_Mnay( node node_point[],update_infor up_info[]){
//*****************************************
//1.find white and record the point number and  distance
//2.check update_point
//    (1)select farthest distance white_point  , if there are more than one , the smallest_point_number priority.
//    (2)check no_conflict_white_point update together
//    (3)return the update numbers
//******************************************

    //single update
    node *now_point;
    now_point = malloc(sizeof(now_point));
    int i,j,k;
    int array_i = 0,distance_max = 0,update_point = 0,proposol_point_white_index_index = 0;
    int up_i = 0 ;
    int distance[1000] = {0};
    int start_point[1000] = {0};
    int ori_pheap[1000] = {0};
    int next_pheap[1000] = {0};
    int white_in[1000] = {0};
    int proposol_point_white_index[1000] = {0};

//1.find white and record the point number and  distance
    for ( i = 0 ; i < number ; i++ ){
        if ( strcmp( node_point[i].type,"white" ) == 0 ){
            //printf( "i:%d\n",i );
            //printf("node_point[i].point: %d\n ",node_point[i].point);
            //next_path pass
            if ( i == number-1 )
                continue;

            //printf( "it is not final point.\n" );
            if ( node_point[i].original_path->point ==  node_point[i].solution_path->point )
                continue;
            now_point = node_point[i].next_path;
            if ( now_point == NULL )
                continue;

            //printf( "%s",now_point -> type );
            for ( j = 0 ; j < number ; j++ ){
                //printf("now_point->point: %d\n",now_point->point);
                if ( strcmp(now_point->type,"white" ) == 0  ){
                    //printf("strcmp(now_point->type,white ) == 0 point: %d\n",now_point->next_path->point);
                    start_point[array_i] = i;
                    distance[array_i] = now_point->white_index - node_point[i].white_index;
                    white_in[array_i] = node_point[i].white_index;
                    ori_pheap[array_i] = node_point[i].heap;
                    next_pheap[array_i] = now_point->heap;
/*
                    printf(  "start_point[array_i]:%d\n",start_point[array_i]);
                    printf(  "distance[array_i]:%d\n",distance[array_i]);
                    printf( "white_in[array_i]:%d\n",white_in[array_i]);
                    printf( "ori_pheap[array_i]:%d\n",ori_pheap[array_i]);
                    printf( "next_pheap[array_i]:%d\n",next_pheap[array_i] );
                    proposol_point_white_index[array_i] = now_point->white_index;
*/
                    array_i++;
                    //printf( "array_i:%d\n",array_i );
                    break;
                }//if
                else{
                    now_point = now_point -> original_path;
                }//else
            }//for
        }//if
    }//for

    //printf( "array_i:%d\n",array_i );
    //find distance_max
    //printf( "distance[array_i]:");

//2.check update_point
//    (1)select farthest distance white_point  , if there are more than one , the smallest_point_number priority.

    //printf( "distance[0]:%d\n",distance[0] );

    //printf( "array_i:%d\n",array_i );
    for ( i = 0 ; i < array_i ; i++ ){
        //printf( "%d ",distance[i] );
        if ( i == 0 )
            distance_max = distance[0];
        if ( distance[i] > distance_max )
            distance_max = distance[i] ;
    }//for



//2.check update_point
//    (2)check no_conflict_white_point update together

    for ( i = 0 ; i < array_i ; i++ ){
        //printf( "start_point[i]:%d\n",start_point[i] );
        //printf( "distance[i]:%d\n",distance[i] );
        if ( distance[i] == distance_max ){
            update_point = start_point[i];
            proposol_point_white_index_index = i;
            up_info[up_i].update_point = update_point; // insert first update point
            up_info[up_i].distance_max = distance_max;
            up_info[up_i].white_index= node_point[update_point].white_index;
            //if heap is same = 1 , else = 0
            if ( ori_pheap[up_i] == next_pheap[up_i]  )
                up_info[up_i].heap_same = 1;
            else
                up_info[up_i].heap_same = 0;
            //printf( "distance_max:%d\n",distance_max );
            up_i++;
            break;
        }//if
    }//for

    //printf( "distance[0]:%d\n",distance[0] );
    bool confi = false ;

//2.check update_point
//    (3)return the update numbers

//isconflict
//another point >= update point + distance && another point + distance > update point + distance
//another point < update point && another point + distance <= update point

// if equal first pass
    //printf( "array_i:%d\n",array_i );
    for ( k = distance_max; k > 0 ; k--  ){ //距離下去找
        //printf( "k:%d\n",k );
        for ( i = 0 ; i < array_i ; i++ ){ //找每個點
            //printf( "i:%d\n",i );
            if ( distance[i] != k )
                continue;
            for ( j = 0;j < up_i  ;j++ ){ //找衝突
                if ( start_point[i] == up_info[j].update_point ){ //等於就跳過
                    confi = true;
                    break ;
                }//if

                if ( ori_pheap[i] != next_pheap[i] )
                    confi = false;
                else if ( (distance[i] < 0) //距離為負
                    || (((node_point[start_point[i]].white_index < node_point[up_info[j].update_point].white_index))
                        &&(node_point[start_point[i]].white_index  + distance[i]) > node_point[up_info[j].update_point].white_index)  // 左邊進到中間
                    || ((node_point[start_point[i]].white_index >= node_point[up_info[j].update_point].white_index) // 中間不含最右的點
                        && (node_point[start_point[i]].white_index < node_point[up_info[j].update_point].white_index +up_info[j].distance_max ))){
                    confi = true;
                    //printf( "start_point[i]:%d is confi\n",start_point[i] );
                    //printf( "node_point[start_point[i]].white_index  + distance[i]  is confi:%d\n",node_point[start_point[i]].white_index  + distance[i] );
                }//if
                //printf( "start_point[i]:%d is not confi\n",start_point[i] );
                //printf( "node_point[start_point[i]].white_index  + distance[i]  is not confi:%d\n",node_point[start_point[i]].white_index  + distance[i] );
            }//for

            if (confi == true){
                confi = false;
                continue ;
            }//if
            else{//confi == false
                /*
                printf( "i:%d\n",i );
                printf( "start_point[i]:%d\n",start_point[i] );
                printf( "distance[i]:%d\n",distance[i]);
                printf( "white_in[i]:%d\n",white_in[i] );
                printf( "up_info[i].distance_max:%d\n",up_info[i].distance_max );
                printf( "white_index:%d\n",node_point[up_info[j].update_point].white_index );
                printf( "distance_max:%d\n",up_info[j].distance_max );
                */

                up_info[up_i].update_point = start_point[i];
                up_info[up_i].distance_max = distance[i];
                up_info[up_i].white_index = white_in[i];
                if ( ori_pheap[up_i] == next_pheap[up_i]  ){
                    up_info[up_i].heap_same = 1;
                    //printf("up_info[up_i].heap_same:%d\n",up_info[up_i].heap_same);
                }//if
                else
                    up_info[up_i].heap_same = 0;
            //printf( "distance_max:%d\n",distance_max );
                up_i++;
               // printf("up_i:%d\n",up_i);
                confi = true;
            }//else
        }//for
    }//for

    /*
    for ( i = 0 ; i < up_i ; i++ ){
        printf( "i:%d\n",i );
        printf( "up_info[i].update_point:%d\n",up_info[i].update_point );
        printf( "up_info[i].distance_max:%d\n",up_info[i].distance_max );
    }//for
    */


    //printf( "up_i:%d\n",up_i );
    //update
    //1. point merge
    //2.original_path = next_path
    //3.next_path = NULL
    //printf( "up_i:%d\n",up_i );

    int max_heap = 0;
    for ( i = 0 ; i < up_i ; i++ ){
        //printf( "update point :%d\n",node_point[up_info[i].update_point].point );
        //printf( "after update:%d\n",node_point[up_info[i].update_point].solution_path->point);
        now_point = node_point[up_info[i].update_point].original_path;
        //printf( "i:%d\n",i );
        if ( (up_info[i].heap_same == 1) &&(up_info[i].distance_max > 1)   ) {
            for (  ;  now_point->white_index > 0 && now_point->white_index <= node_point[up_info[i].update_point].white_index + up_info[i].distance_max  ; ){
                //printf( "test\n" );
                if ( now_point->white_index < node_point[up_info[i].update_point].white_index + up_info[i].distance_max ){
                    now_point -> heap = 2;
                    now_point = now_point -> original_path;
                }//if
                else{
                    //printf( "now_point ->white_index:%d\n",now_point ->white_index );
                    max_heap = now_point -> heap;
                    break;
                    //now_point = now_point -> original_path;
                }//else
            }//for
        }//if
        node_point[up_info[i].update_point].heap = max_heap;
        node_point[up_info[i].update_point].white_index = node_point[up_info[i].update_point].white_index + up_info[i].distance_max;
        node_point[up_info[i].update_point].original_path = node_point[up_info[i].update_point].solution_path;
        node_point[up_info[i].update_point].next_path = NULL;
    }//for

}//Odd_Shortcut_phase


void * Even_Prune_Phase_Many( node node_point[],update_infor up_info[]){
//*****************************************
//1.read update_point and distance
//2.update all nodes in the middle
//******************************************
    int i,j,k;
    int array_i = 0;
    int num_of_up = 0 ;
    int ori_white_index = 0 ;
    node *now_point;
    now_point = malloc(sizeof(now_point));
    /*
    for ( i = 0 ; i < 2 ; i++ ){
        printf( "i:%d\n",i );
        printf( "up_info[i].update_point:%d\n",up_info[i].update_point );
        printf( "up_info[i].distance_max:%d\n",up_info[i].distance_max );
    }//for
    */

//1.read update_point and distance
//2.update all nodes in the middle
    for ( array_i = 0 ;array_i <number ;array_i++  ){
        //num_of_up = 0 ;
        //printf( "array_i:%d\n",array_i );
        //printf( "up_info[array_i].white_index:%d\n",up_info[array_i].white_index );
        //printf( "up_info[array_i].distance_max:%d\n",up_info[array_i].distance_max );
        //printf( "up_info[array_i].update_point:%d\n",up_info[array_i].update_point );
        if (  up_info[array_i].distance_max == 0  )
            break;
        for ( i = 0 ; i < number-1 ;i++ ){
            if ( node_point[i].original_path == node_point[i].solution_path )
                continue;
            //找下一個white  若遇到red繼續找
            if ( (strcmp( node_point[i].type,"white" ) != 0) )
                continue;

            now_point = node_point[i].next_path;
            while ( (strcmp( now_point -> type,"white" ) != 0 )){
                //printf( "now_point:%d\n",now_point->point );
                //printf( "now_point->original_path->type:%s\n",now_point->original_path->type );
                now_point = now_point->original_path;
            }//while
                //printf( "now_point:%d\n",now_point->point );
                //printf( "now_point->original_path->type:%s\n",now_point->original_path->type );
            if ( (strcmp( node_point[i].type,"white" ) == 0)
                &&( node_point[i].white_index > up_info[array_i].white_index)
                && ( node_point[i].white_index < up_info[array_i].white_index + up_info[array_i].distance_max)){
                //printf( "node_point[i].point:%d\n",node_point[i].point );

                //要更新的點比下一個大
                if ( node_point[i].white_index > now_point->white_index ){
                    now_point->white_index = node_point[i].white_index ;
                    now_point->heap = node_point[i].heap;
                }//if
                else{
                    ori_white_index = node_point[i].white_index;
                    node_point[i].white_index = now_point->white_index ;
                    node_point[i].heap = now_point->heap;
                    for ( k = 0 ; k < number-1 ;k++  ) {
                        if ( node_point[j].white_index == ori_white_index )
                            node_point[j].white_index = node_point[i].white_index;

                    }//for
                }//else

                node_point[i].original_path = node_point[i].next_path;
                node_point[i].next_path = NULL;
            }//if
        }//for
    }//for

            //if ( i == up_info[array_i].update_point ) {
        /*
        for ( j = up_info[array_i].update_point+1  ; j < number-1 ; j++ ){
            //update update_point < white point < white_index + distance_max

            if ( num_of_up+1 >= up_info[array_i].distance_max)
                break;
           // printf( "node_point[j].point is proposal.:%d\n",node_point[j].point );
            if ( (strcmp( node_point[j].type,"white" ) == 0)) {
                if ( node_point[j].original_path->point ==  node_point[j].solution_path->point )
                    continue;
                else{
                  //  printf( "node_point[j].point is updated.:%d\n",node_point[j].point);

                    num_of_up++;
                }//esle
            }//if
        }//for
        */
            //}//if

}//Even_Prune_Phase

void * PointBlackDisconnectNextpath( node node_point[]){
//*****************************************
//final round : if black disconnect solid line
//******************************************
    int i;
    for ( i = 0 ; i < number ; i++ ){
        if(strcmp(node_point[i].type,"black") == 0){
            node_point[i].original_path = NULL;
        }//if
    }//for
}//PointBlackDisconnectNextpath


//*****************************************
//below is Debug Code
//******************************************

void Print_Node_Point( node node_point[],int number ){
    int i =0;
    //printf( "number:%d\n",number );
    for (i=0;i<number;i++)
    {
        if ( node_point[i].original_path == NULL )
            printf( "-1" );
        else
            printf( "%d",node_point[i].original_path->point );

        if ( i<number-1 )
            printf(" ");
        else
            printf( "\n" );
    }//for
}//Print_Node_Point

void Debug_Print_Node_Point( node node_point[],int number ){
    int i =0;
    //printf( "number:%d\n",number );
    for (i=0;i<number;i++)
    {
        printf( "point:%d ",node_point[i].point );
        printf( "type:%s ",node_point[i].type );
        printf( "white_index:%d ",node_point[i].white_index );
        printf( "heap:%d ",node_point[i].heap );
        if ( node_point[i].original_path == NULL )
            printf( "original_path:-1 " );
        else
            printf( "original_path:%d ",node_point[i].original_path->point );

        if ( node_point[i].solution_path == NULL  )
            printf( "solution_path:-1 " );
        else
            printf( "solution_path:%d ",node_point[i].solution_path->point );

        if ( node_point[i].next_path == NULL  )
            printf( "next_path:-1\n" );
        else
            printf( "next_path:%d\n",node_point[i].next_path->point );
    }//for
}//Debug_Print_Node_Point()


<file_sep>/HW3/CODE/406410114_DS_HW3_segment_rounting.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

#define V 100
typedef struct link_input{
	int linkID;
	int firstNodeID;
	int secondNodeID; // sorting
	double linkCapacity;
} link_input;

typedef struct flow_input{
	int flowID;
	int sourceID;
	int destinationID; // sorting
	double flowSize;
} flow_input;

typedef struct node{
	int point;
	double weight;
	double load; // sorting
	double linkCapacity;
	struct node *next;
} node;






void dijkstra(double graph[V][V], int src);
void ReadInput();
void Debug_node_printf();
void Debug_flow_printf();
void Debug_node_printf();
void create_wei_graph( node node_info[] );
int minDistance(int dist[], bool sptSet[]);
int printSolution(int dist[]);
bool capacity_determine( node node_info[], double capacity );
void update_weight( node node_info[],double graph[V][V] );
void seg_select_path( int src,int des );
void segment_rounting();

int node_num = 0,link_num =0,flow_num =0,n,sou_des_path[V][V],sdp_i=0;
int seg_tb[100][100][100];
double wei_graph[100][100];
link_input link_info[10000];
flow_input flow_path[10000];
node node_info[1000] = { 0,0,0,0,NULL };


//===========================================方法如下=====================================//
//1.Read input後產生node_info
//2.利用 create_wei_graph  建立出graph
//3.呼叫 dijkstra 計算shorest path
//4.dijkstra呼叫segment_rounting  建立出  segment_table[source][destination][path]
//5.輸入flow 運用seg_select_path  選擇最佳路徑
//6.capacity_determine  判斷是否最佳路徑上還有capacity  回傳true or false
//6.1若為false 則continue
//6.2若為true 則新增path  計算flow_num  throughput  並且更新權重
//7.不斷重複 4~6  直到輸入flow結束


int main() {
    int i,j,k;
    int throughput=0;
    int accept_flow=0;
    bool is_cap;
    ReadInput();
    for ( i = 0;i<node_num;i++ ){
        for ( j = 0;j<node_num;j++ ){
            sou_des_path[i][j] = -1;
            for ( k =0 ; k <node_num;k++ ){
                seg_tb[i][j][k] =-1 ;
            }//for
        }//for
    }//for

    //generate graph
    create_wei_graph( node_info );
    //create segment table
    for (i =0 ; i < node_num ; i++){
        dijkstra(wei_graph, i);
    }//for

    /*
    for ( i = 0;i<node_num;i++ ){
        for ( j = 0;j<node_num;j++ ){
            for ( k =0 ; k <node_num;k++ ){
                if ( seg_tb[i][j][k] !=-1 )
                    printf( "seg_tb[%d][%d][%d]:%d\n",i,j,k,seg_tb[i][j][k] );
            }//for
        }//for
    }//for
    */

     for (i =0 ; i < flow_num ; i++){
        create_wei_graph( node_info );
        if ( flow_path[i].sourceID < node_num &&flow_path[i].destinationID  < node_num ){
            seg_select_path(flow_path[i].sourceID,flow_path[i].destinationID );
            is_cap = capacity_determine( node_info, flow_path[i].flowSize );
            if (is_cap == true){
                accept_flow++;
                throughput = throughput + flow_path[i].flowSize;
            }//if
        }//if


     }//for


    printf( "%d %d\n",accept_flow,throughput );
    for ( i = 0; i<sdp_i;i++ ){
        printf( "%d ",i );
        for( j= 0 ;j<node_num ;j++){
            if ( sou_des_path[i][j] == -1 )
                continue;
            else{
                printf( "%d ",sou_des_path[i][j] );
            }//else
        }//for
        printf( "\n" );
    }//for





    //Debug_link_printf();
    //Debug_flow_printf();
    //Debug_node_printf();

    return 0;
}//main



void ReadInput(){
//*****************************************

//******************************************
    //int input_number = 0;
    int input = 0;
    double d_input ;

//determine rule
    int i=0;
//file input rule

    //FILE *fin;
	//fin=fopen(filename,"r");
    scanf("%d",&node_num);
    //printf( "node_num:%d\n",node_num );
    scanf("%d",&link_num);
    //printf( "node_num:%d\n",node_num );

    for (i=0;i<link_num;i++)
    {
        scanf("%d",&input);
        link_info[i].linkID = input ;
        scanf("%d",&input);
        link_info[i].firstNodeID = input ;
        scanf("%d",&input);
        link_info[i].secondNodeID = input ;
        scanf("%lf",&d_input);
        link_info[i].linkCapacity = d_input ;
    }//for

    scanf("%d",&flow_num);
    //printf( "flow_num:%d\n",flow_num );

    for (i=0;i<flow_num;i++)
    {
        scanf("%d",&input);
        flow_path[i].flowID = input ;
        scanf("%d",&input);
        flow_path[i].sourceID = input ;
        scanf("%d",&input);
        flow_path[i].destinationID = input ;
        scanf("%lf",&d_input);
        flow_path[i].flowSize = d_input ;
    }//for


    //int node_index = -1 ;
    //int max_finode_id =  link_info[node_num-1].firstNodeID ;
    node *now_ptr = (node *) malloc(sizeof(node));
    for ( i=0;i<node_num;i++ ){
        now_ptr = &node_info[node_num];
        now_ptr->next = NULL;
    }//for

    //create Adjacency Lists  use pointer array
    for ( i=0;i<link_num;i++ ){
        //printf( "-----------------------round--------------------------\n" );
        //printf( "link_info[i].firstNodeID :%d\n",link_info[i].firstNodeID );
        //printf( "node_index :%d\n ",node_index  );
        //first node
        now_ptr = &node_info[link_info[i].firstNodeID];
        node *new_ptr = (node *) malloc(sizeof(node));
        while ( now_ptr->next != NULL )
            now_ptr = now_ptr->next;

        new_ptr->point = link_info[i].secondNodeID;
        //printf( "new_ptr->point:%d\n",new_ptr->point );
        new_ptr->linkCapacity = link_info[i].linkCapacity;
        new_ptr->load = 0;
        new_ptr->weight = (new_ptr->load)/(new_ptr->linkCapacity - new_ptr->load);
        //printf( "new_ptr->linkCapacity:%d\n",new_ptr->linkCapacity );
        now_ptr->next = new_ptr;
        now_ptr = now_ptr->next;
        now_ptr->next = NULL;

        //second node
        now_ptr = &node_info[link_info[i].secondNodeID];
        node *new_ptr2 = (node *) malloc(sizeof(node));
        while ( now_ptr->next != NULL )
            now_ptr = now_ptr->next;

        new_ptr2->point = link_info[i].firstNodeID;
        //printf( "new_ptr2->point:%d\n",new_ptr2->point );
        new_ptr2->linkCapacity = link_info[i].linkCapacity;
        new_ptr2->load = 0;
        new_ptr2->weight = (new_ptr2->load)/(new_ptr2->linkCapacity - new_ptr2->load);
        //printf( "new_ptr2->linkCapacity:%d\n",new_ptr2->linkCapacity );
        now_ptr->next = new_ptr2;
        now_ptr = now_ptr->next;
        now_ptr->next = NULL;
    }//for

}//ReadInput

void create_wei_graph( node node_info[] ){
    int i,j;

    for ( i=0;i<node_num;i++ ){
        for ( j=0;j<node_num;j++ ){
            //wei_graph[i][j]=  -1.0;
            wei_graph[i][j]=  0;
        }//for
    }//for



    for ( i=0;i<node_num;i++ ){
        for ( j=0;j<node_num;j++ ){
            node *now_ptr = (node *) malloc(sizeof(node));
            now_ptr = &node_info[i];
            while ( now_ptr->next != NULL ){
                //wei_graph[i][now_ptr->next->point] = now_ptr->next->weight;
                wei_graph[i][now_ptr->next->point] = 1 + now_ptr->next->weight;
                now_ptr = now_ptr->next;
            }//wile
        }//for
    }//for

    /*
    printf( "wei_graph\n" );
    for ( i=0;i<node_num;i++ ){
        for ( j=0;j<node_num;j++ ){
            printf( "%lf ",wei_graph[i][j] );
        }//for

        printf( "\n" );
    }//for
    */


}//shorest_path



int minDistance(int dist[], bool sptSet[])
{
    // Initialize min value
    int min = INT_MAX, min_index;  //

    for (int v = 0; v < node_num; v++)
        if (sptSet[v] == false && dist[v] <= min){

            min = dist[v], min_index = v;  //  距離  並且回傳index
            //printf( " min_index:%d\n", min_index );
        }//if


    return min_index;
}

int printSolution(int dist[])
{
    printf("Vertex \t\t Distance from Source\n");
    for (int i = 0; i < node_num; i++)
        printf("%d \t\t %d\n", i, dist[i]);
}

void dijkstra(double graph[V][V], int src) // shortest path
{
    int path[V],path_i=0,sou_des_trace[V][V],sdt_i = 0;
    int dist[V];
    // distance from src to i

    for ( int i = 0 ;i<node_num;i++){
        for(int j= 0 ;j<node_num ;j++)
            sou_des_trace[i][j] = -1;
    }//for


    bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest
    // path tree or shortest distance from src to i is finalized

    // Initialize all distances as INFINITE and stpSet[] as false
    for (int i = 0; i < node_num; i++)
        dist[i] = INT_MAX, sptSet[i] = false;   //所有的距離都最大  且還沒選過

    // Distance of source vertex from itself is always 0
    dist[src] = 0;  //source點

    // Find shortest path for all vertices
    for (int count = 0; count < node_num - 1; count++) {
        // Pick the minimum distance vertex from the set of vertices not
        // yet processed. u is always equal to src in the first iteration.
        int u = minDistance(dist, sptSet);

        // Mark the picked vertex as processed
        sptSet[u] = true;   //改成true
        //path[path_i] = u;  //走過路徑
        //path_i++;

        // Update dist value of the adjacent vertices of the picked vertex.
        for (int v = 0; v < node_num; v++){
            //sdt_i=0;
            // Update dist[v] only if is not in sptSet, there is an edge from
            // u to v, and total weight of path from src to  v through u is
            // smaller than current value of dist[v]
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v]){  //假設是false 並且graph不是0  dist有值  可以到
                dist[v] = dist[u] + graph[u][v];  //
                //sou_des_trace[v][sdt_i] = u;
                //printf( "sou_des_trace[%d][sdt_i]:%d\n",v,sou_des_trace[v][sdt_i] );
                //sdt_i++;
            }//if
        }//for
    }//for






    // print the constructed distance array
    //printSolution(dist);
    segment_rounting( dist,graph,src );
}//dijkstra

//===================================segment_rounting_table=======================================//
void segment_rounting( int dist[],double graph[V][V],int src ){
    int i,j,k,m,l;
    int now_hop,max_hop=0;
    bool min_idx = true; //找最小index
    for ( i =0 ; i < node_num;i++ ){
        if ( dist[i]>max_hop )
            max_hop = dist[i];
    }//for

    //printf( "max_hop:%d\n",max_hop );
    // hop
    for ( l = 0; l <= max_hop;l++ ){
        //printf( "l:%d\n",l );
        for ( i = 0;i<node_num;i++ ){
            //從最小hop開始做到max_hop
            if ( dist[i] != l  )
                continue;
            //printf( "i:%d\n",i );
            if ( dist[i] == 0 )  // hop = 0
                seg_tb[src][i][0] = src;
            else if ( dist[i] == 1 ){ // hop = 1
                seg_tb[src][i][0] = src;
                seg_tb[src][i][1] = i;
            }//else if


            // hop >2
            else {
                for ( j = 0;j<node_num;j++ ){
                    //printf( "j:%d\n",j );
                    if ( dist[j] == dist[i]-1 ){  //使用hop小的去擴散
                        min_idx = false;
                        for ( m = 0;m<dist[i]-1 ;m++ ){
                            if ( seg_tb[src][i][m] > seg_tb[src][j][m] ) {  //若有更小的min_idx  就去找  否則不做
                                //printf( "seg_tb[src][i][m]:%d\n",seg_tb[src][i][m] );
                                //printf( "seg_tb[src][j][m]:%d\n",seg_tb[src][j][m] );
                                min_idx = true;
                                break;
                            }//if

                            else if ( seg_tb[src][i][m] < seg_tb[src][j][m]  ){
                                //printf( "seg_tb[src][i][m]:%d\n",seg_tb[src][i][m] );
                                //printf( "seg_tb[src][j][m]:%d\n",seg_tb[src][j][m] );
                                min_idx = false;
                                break;
                            }//else if
                            else
                                continue;
                        }//for

                        //printf( "min_idx:%d\n",min_idx );

                        //有更得min_index 或是第一次
                        if ( min_idx == true || seg_tb[src][i][0] == -1 ){
                            int temp_arr[100];
                            for ( k = 0;k<dist[i];k++ ){
                                temp_arr[k] = seg_tb[src][i][k];    //temp_arr暫存  若沒有找到救回填
                                seg_tb[src][i][k] = seg_tb[src][j][k];
                            }//for

                            //開始找  找到NULL代表沒找到  否則就是找到
                            node *now_ptr = (node *) malloc(sizeof(node));
                            now_ptr = &node_info[j];
                            while ( now_ptr->next != NULL && now_ptr->next->point != i )
                                now_ptr = now_ptr->next;


                            //沒找到  還原
                            if ( now_ptr->next == NULL ){
                                for ( k = 0;k<dist[i];k++ )
                                    seg_tb[src][i][k] = temp_arr[k];
                                continue;
                            }//if
                            //找到 複寫
                            else if ( now_ptr->next->point == i ){
                                seg_tb[src][i][l] = i;
                                continue;
                            }//else
                        }//if
                    }//if
                }//for

            }//else




        }//for
    }//for

    /*
    for ( i = 0;i<node_num;i++ ){
        for ( j = 0;j<node_num;j++ ){
            for ( k =0 ; k <node_num;k++ ){
                if ( seg_tb[i][j][k] !=-1 )
                printf( "seg_tb[%d][%d][%d]:%d\n",i,j,k,seg_tb[i][j][k] );
            }//for
        }//for
    }//for
    */

}

//===================================seg_select_path=======================================//
void seg_select_path( int src,int des ){
    //computing weight
    int i,j,k,m,l;
    int hop_num =-1,mid = -1,hop_temp = 0;  //mid為選中中間的的點
    double wei_num = -1,wei_temp = 0;



    for ( i = 0; i < node_num ; i++ ){
        wei_temp = 0;
        hop_temp = 0;
        //printf( "i:%d\n",i );

        //計算到source-mid
        for ( j = 0; j<node_num;j++ ){
            //printf( "j:%d\n",j );
            //找到最後一個
            if ( seg_tb[src][i][j+1] == -1 ){
                hop_temp++;
                break;
            }//if


            //source ->i
            wei_temp = wei_temp + wei_graph[seg_tb[src][i][j]][seg_tb[src][i][j+1]]-1;
            hop_temp++;
        }//for

        //計算到mid-destination
        for ( j = 0; j<node_num;j++ ){
            if ( seg_tb[i][des][j+1] == -1 ){
                hop_temp++;
                break;
            }//if

            //i->des
            wei_temp = wei_temp + wei_graph[ seg_tb[i][des][j]][ seg_tb[i][des][j+1]]-1;
            hop_temp++;
        }//for

        //printf( "wei_temp:%d\n",wei_temp );
        //printf( "hop_temp:%d\n",hop_temp );
        //printf( "mid:%d\n",mid );
        //第一次直接複寫
        if ( wei_num == -1 ){
            wei_num = wei_temp;
            hop_num = hop_temp;
            mid = i;
            //printf( "wei_num:%d\n",wei_num );
            //printf( "hop_num:%d\n",hop_num );
            //printf( "mid:%d\n",mid );
        }//if

        // 取wei小
        else if ( wei_num > wei_temp ){
            wei_num = wei_temp;
            hop_num = hop_temp;
            mid = i;
            //printf( "wei_num:%d\n",wei_num );
            //printf( "hop_num:%d\n",hop_num );
            //printf( "mid:%d\n",mid );
        }//else if

        // 相等  取hop小 因為從小開始找故一定min_index
        else if ( wei_num == wei_temp ){
            if ( hop_num > hop_temp ){
                hop_num = hop_temp;
                mid = i;
                //printf( "wei_num:%d\n",wei_num );
                //printf( "hop_num:%d\n",hop_num );
                //printf( "mid:%d\n",mid );
            }//if
        }//else if
    }//for

    //新增路徑
    int mid_index = 0;
    for ( i = 0; i < node_num ; i++ ){
        if ( seg_tb[src][mid][i] != -1 ){
            sou_des_path[sdp_i][mid_index++] = seg_tb[src][mid][i];
        }//if
    }//for
    mid_index--; //扣掉中間重複的
    for ( i = 0; i < node_num ; i++ ){
        if ( seg_tb[mid][des][i] != -1 ){
            sou_des_path[sdp_i][mid_index++] = seg_tb[mid][des][i];

        }//if
    }//for

    sdp_i++;
    /*
    printf( "sou_des_path:\n" );
    for ( i = 0; i < node_num ; i++ ){
        if ( sou_des_path[sdp_i-1][i] != -1 ){
            printf( "%d ",sou_des_path[sdp_i-1][i] );
        }//if
    }//for
    printf( "\n" );
    */

}//seg_select_path



bool capacity_determine( node node_info[],double capacity ){
    bool rule = true;
    int i,j;
    /*
    for(i= 0 ;i < node_num ;i++){
        if ( sou_des_path[sdp_i-1][i] == -1 )
            continue;
        else
            printf( "sou_des_path[sdp_i][%d]:%d\n",i,sou_des_path[sdp_i-1][i] );
    }//for
    */

    //printf( "sou_des_path[sdp_i-1][0]:%d\n",sou_des_path[sdp_i-1][0] );
    if ( sou_des_path[sdp_i-1][1] == -1 ){
        rule = false;

        for(int i= 0 ;i<node_num ;i++)
            sou_des_path[sdp_i-1][i] = -1;
        sdp_i--;
        return rule;
    }//IF


    for(i= 0 ;i < node_num ;i++){
        if ( sou_des_path[sdp_i-1][i] == -1 )
            continue;
        else{
            node *now_ptr = (node *) malloc(sizeof(node));
            now_ptr = &node_info[sou_des_path[sdp_i-1][i]];
            //找到要確認的cap

            while ( now_ptr->next != NULL && now_ptr->next->point != sou_des_path[sdp_i-1][i+1] )
                now_ptr= now_ptr->next;

            //若爆掉則reject  刪除此路徑

            if ( now_ptr->next != NULL && capacity > now_ptr->next->linkCapacity ){
                //printf( "capacity:%lf\n",capacity );
                //printf( "now_ptr->next->linkCapacity:%lf\n", now_ptr->next->linkCapacity );
                //printf( "now_ptr->point:%lf\n",now_ptr->point );
                //printf( "now_ptr->next->point:%lf\n",now_ptr->next->point );
                rule = false;
                for(int i= 0 ;i<node_num ;i++)
                    sou_des_path[sdp_i-1][i] = -1;
                sdp_i--;
                return rule;
            }//if
        }//else
    }//for


    //printf( "sdp_i:%d\n",sdp_i );



    int update_link[100],upli_i=0;


    if ( rule == true ){
        //printf( "rule is true.\n" );
        for(i= 0 ;i < node_num ;i++){
            if ( sou_des_path[sdp_i-1][i] == -1 || sou_des_path[sdp_i-1][i+1] == -1 ){
                //printf( "sou_des_path[sdp_i-1][%d]:%d\n",i,sou_des_path[sdp_i-1][i] );
                //printf( "sou_des_path[sdp_i-1][%d]:%d\n",i+1,sou_des_path[sdp_i-1][i+1] );
                continue;
            }//if

            for( j = 0 ; j< link_num ;j++ ){

                if ( (link_info[j].firstNodeID == sou_des_path[sdp_i-1][i+1] && link_info[j].secondNodeID == sou_des_path[sdp_i-1][i])
                    ||(link_info[j].secondNodeID == sou_des_path[sdp_i-1][i+1] && link_info[j].firstNodeID == sou_des_path[sdp_i-1][i]) ){
                    //printf( "link_info[j].firstNodeID:%d\n",link_info[j].firstNodeID );
                    //printf( "sou_des_path[sdp_i][i+1]:%d\n",sou_des_path[sdp_i-1][i+1] );
                    //printf( "link_info[j].secondNodeID:%d\n",link_info[j].secondNodeID );
                    //printf( "sou_des_path[sdp_i][i]:%d\n",sou_des_path[sdp_i-1][i] );
                    if ( link_info[j].linkCapacity - capacity >= 0.0 ){
                        link_info[j].linkCapacity = link_info[j].linkCapacity - capacity;
                        update_link[upli_i] = j;
                        upli_i++;
                    }//if
                    else{
                        rule = false;
                        for(int i= 0 ;i<node_num ;i++)
                            sou_des_path[sdp_i-1][i] = -1;
                        sdp_i--;
                        return rule;
                    }//else
                }//if
            }//for
        }//for

        //printf(  "upli_i:%d\n",upli_i );

        //printf( "test1\n" );
        for ( i = 0;i <upli_i;i++ ){
            node *now_ptr = (node *) malloc(sizeof(node));
            now_ptr = &node_info[link_info[update_link[i]].firstNodeID];
            //printf( "link_info[update_link[i]].firstNodeID:%d\n",link_info[update_link[i]].firstNodeID );
            now_ptr = now_ptr->next;
            while (now_ptr->point != link_info[update_link[i]].secondNodeID )
                now_ptr = now_ptr->next;
            //printf( "now_ptr->point:%d\n",now_ptr->point );

            now_ptr->load = now_ptr->load + capacity;
            if ( (now_ptr->linkCapacity - now_ptr->load) ==0 )
                now_ptr->weight = INT_MAX;
            else
                now_ptr->weight = (now_ptr->load)/(now_ptr->linkCapacity - now_ptr->load);

            now_ptr = &node_info[link_info[update_link[i]].secondNodeID];
            //printf( "link_info[update_link[i]].secondNodeID:%d\n",link_info[update_link[i]].secondNodeID );
            now_ptr = now_ptr->next;
            while (now_ptr->point != link_info[update_link[i]].firstNodeID ){
                now_ptr = now_ptr->next;
            }//while
            //printf( "now_ptr->point:%d\n",now_ptr->point );
            //printf( "capacity:%lf\n",capacity );
            //printf( "now_ptr->load:%lf\n",now_ptr->load );
            //printf( "now_ptr->load + capacity:%lf\n",now_ptr->load + capacity );
            now_ptr->load = now_ptr->load + capacity;
            if ( (now_ptr->linkCapacity - now_ptr->load) ==0 )
                now_ptr->weight = INT_MAX;
            else
                now_ptr->weight = (now_ptr->load)/(now_ptr->linkCapacity - now_ptr->load);
        }//for

    }//if



    return rule;


}//capacity_determine


void Debug_link_printf(){
    printf( "node_num:%d\n",node_num );
    printf( "link_num:%d\n",link_num );
    printf( "Debug_node_printf:\n" );
    printf( "linkID firstNodeID secondNodeID linkCapacity\n" );
    for (int i=0;i<link_num;i++)
    {
        printf("%d ",link_info[i].linkID);
        printf("%d ",link_info[i].firstNodeID);
        printf("%d ",link_info[i].secondNodeID);
        printf("%lf\n",link_info[i].linkCapacity);
    }//for
}//Debug_node_printf


void Debug_flow_printf(){
    printf( "flow_num:%d\n",flow_num );
    printf( "Debug_flow_printf:\n" );
    printf( "flowID sourceID destinationID flowSize\n" );
    for (int i=0;i<flow_num;i++)
    {
        printf("%d ",flow_path[i].flowID);
        printf("%d ",flow_path[i].sourceID);
        printf("%d ",flow_path[i].destinationID);
        printf("%lf\n",flow_path[i].flowSize);
    }//for
}//Debug_node_printf




void Debug_node_printf(){
    printf( "node_num:%d\n",node_num );
    printf( "Debug_node_printf:\n" );

    node *now_ptr = (node *) malloc(sizeof(node));
    int max_finode_id =  link_info[node_num-1].firstNodeID ;
    for (int i=0;i< node_num;i++){
        now_ptr = &node_info[i];
        printf( "it is node [%d]\n",i);
        while  ( now_ptr->next != NULL ){
            now_ptr = now_ptr->next;
            printf("point:%d ",now_ptr->point);
            printf("linkCapacity:%lf ",now_ptr->linkCapacity);
            printf("load:%lf ",now_ptr->load);
            printf("weight:%lf \n",now_ptr->weight);
        }//if
    }//for
}//Debug_node_printf

<file_sep>/HW1/Minimize_the_table_size_1.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_LINE 1024
#define bool int
#define false 0
#define true 1


main()
{
    int rule_number = 0;
    int point_number = 0;
    char rule_point1[ 1024 ];
    char rule_point2[ 1024 ];
    char rule_port[ 1024 ];
    char input_point1[ 1024 ];
    char input_point2[ 1024 ];
    char star[1] = "*";
    bool isfind_port = true;

    FILE *fpr;
    fpr=fopen("input.txt","r");
    fscanf(fpr,"%d\n",&rule_number);
    for (int i=0;i<rule_number;i++)
    {

        fscanf(fpr,"%c ",&rule_point1[i]);
        fscanf(fpr,"%c ",&rule_point2[i]);
        fscanf(fpr,"%c\n",&rule_port[i]);

    }//for




    fscanf(fpr,"%d\n",&point_number);
    for (int i=0;i<point_number;i++)
    {

        fscanf(fpr,"%c ",&input_point1[i]);
        fscanf(fpr,"%c\n",&input_point2[i]);

    }//for

    fclose(fpr);

//output file

    FILE *fout;
    fout = fopen( "output.txt","w" );
    for (int i=0;i<point_number;i++){
        fprintf( fout,"%c ",input_point1[i] );
        fprintf( fout, "%c ",input_point2[i] );
        for (int j=0;j<rule_number;j++){
            //printf( "rule_point1[j]:%c",rule_point1[j] );
            //printf( "rule_point2[j]:%c",rule_point2[j] );
            if ( (input_point1[i] == rule_point1[j]) && (input_point2[i] == rule_point2[j] ) ) {
                fprintf( fout, "%c",rule_port[j] );
                isfind_port = true;
                break;
            }//if
            else if( (rule_point1[j] == star[0]) &&(input_point2[i] == rule_point2[j] ) ){
                fprintf( fout, "%c",rule_port[j] );
                isfind_port = true;
                break;
            }//else if
            else if( (input_point1[i] == rule_point1[j] ) && (rule_point2[j] == star[0]) ){
                fprintf( fout, "%c",rule_port[j] );
                isfind_port = true;
                break;
            }//else if
            else{
                isfind_port = false;
            }//else
        }//for
        if ( isfind_port == false ){
            fprintf( fout,  "drop" );
            isfind_port = true ;
        }//if
        fprintf( fout, "\n" );

    }//for
    fclose(fout);

    /*
    printf("%d\n",rule_number);

    for (int i=0;i<rule_number;i++)
    {
        printf("%c ",rule_point1[i]);
        printf("%c ",rule_point2[i]);
        printf("%c\n",rule_port[i]);
    }//for



    printf("%d\n",point_number);
    for (int i=0;i<point_number;i++)
    {
        printf("%c ",input_point1[i]);
        printf("%c\n",input_point2[i]);

    }//for
    */




}
