sparse_learn/c/head_tail_proj.c
bool dfs_tour(
        const EdgePair *edges, int n, Array *tree_nodes, Array *tree_edges,
        Array *tour_nodes, Array *tour_edges) {
    /**
     * This method is to find a euler tour given a tree. This method is
     * proposed in the following paper:
     *  Authors : Edmonds, Jack, and Ellis L. Johnson.
     *  Title : Matching, Euler tours and the Chinese postman
     *  Journal: Mathematical programming 5.1 (1973): 88-124.
     */
    //Make sure the tree has at least two nodes.
    if (tree_nodes->size <= 1) {
        printf("error: The input tree has at least two nodes.");
        exit(0);
    }
    typedef struct {
        int first;
        int second;
        bool third;
    } Tuple;
    typedef struct {
        Tuple *array;
        size_t size;
    } Nei;
    int i, *nei_size = calloc((size_t) n, sizeof(int));
    for (i = 0; i < tree_edges->size; i++) {
        nei_size[edges[tree_edges->array[i]].first]++;
        nei_size[edges[tree_edges->array[i]].second]++;
    }
    Nei *adj = malloc(sizeof(Nei) * n);
    for (i = 0; i < n; i++) {
        adj[i].size = 0;
        adj[i].array = malloc(sizeof(Tuple) * nei_size[i]);
    }
    for (i = 0; i < tree_edges->size; i++) {
        // each tuple is: (indexed node, edge_index, is_visited)
        int uu = edges[tree_edges->array[i]].first;
        int vv = edges[tree_edges->array[i]].second;
        Tuple nei_v, nei_u;
        nei_v.second = tree_edges->array[i];
        nei_u.second = tree_edges->array[i];
        nei_v.first = vv, nei_v.third = false;
        nei_u.first = uu, nei_u.third = false;
        adj[uu].array[adj[uu].size++] = nei_v;  // edge u --> v
        adj[vv].array[adj[vv].size++] = nei_u;  // edge v --> u
    }
    // The first element as tour's root.
    int start_node = tree_nodes->array[0];
    bool *visited = calloc((size_t) n, sizeof(bool));
    tour_nodes->array[tour_nodes->size++] = start_node;
    while (true) {
        bool flag_1 = false;
        visited[start_node] = true;
        // iterate the adj of each node. in this loop, we check if
        // there exists any its neighbor which has not been visited.
        for (i = 0; i < (int) adj[start_node].size; i++) {
            int next_node = adj[start_node].array[i].first;
            int edge_index = adj[start_node].array[i].second;
            if (!visited[next_node]) { // first time to visit this node.
                visited[next_node] = true; // mark it as visited.
                tour_nodes->array[tour_nodes->size++] = next_node;
                tour_edges->array[tour_edges->size++] = edge_index;
                adj[start_node].array[i].third = true; // mark it as labeled.
                start_node = next_node;
                flag_1 = true;
                break;
            }
        }
        // all neighbors are visited. Then we check if
        // there exists adj which is false nodes.
        if (!flag_1) {
            bool flag_2 = false;
            for (i = 0; i < (int) adj[start_node].size; i++) {
                int next_node = adj[start_node].array[i].first;
                int edge_index = adj[start_node].array[i].second;
                bool is_visited = adj[start_node].array[i].third;
                // there exists a neighbor. has false node
                if (!is_visited) {
                    adj[start_node].array[i].third = true;
                    tour_nodes->array[tour_nodes->size++] = next_node;
                    tour_edges->array[tour_edges->size++] = edge_index;
                    start_node = next_node;
                    flag_2 = true;
                    break;
                }
            }
            // all nodes are visited and there is no false nodes.
            if (!flag_2) {
                break;
            }
        }
    }
    free(visited);
    for (i = 0; i < n; i++) { free(adj[i].array); }
    free(adj);
    free(nei_size);
    return true;
}
// deep first search for finding a tour.
deep first search for finding a tour.
deep first search for finding a tour .
bool dfs_tour(
        const EdgePair *edges, int n, Array *tree_nodes, Array *tree_edges,
        Array *tour_nodes, Array *tour_edges) {
    if (tree_nodes->size <= 1) {
        printf("error: The input tree has at least two nodes.");
        exit(0);
    }
    typedef struct {
        int first;
        int second;
        bool third;
    } Tuple;
    typedef struct {
        Tuple *array;
        size_t size;
    } Nei;
    int i, *nei_size = calloc((size_t) n, sizeof(int));
    for (i = 0; i < tree_edges->size; i++) {
        nei_size[edges[tree_edges->array[i]].first]++;
        nei_size[edges[tree_edges->array[i]].second]++;
    }
    Nei *adj = malloc(sizeof(Nei) * n);
    for (i = 0; i < n; i++) {
        adj[i].size = 0;
        adj[i].array = malloc(sizeof(Tuple) * nei_size[i]);
    }
    for (i = 0; i < tree_edges->size; i++) {
        int uu = edges[tree_edges->array[i]].first;
        int vv = edges[tree_edges->array[i]].second;
        Tuple nei_v, nei_u;
        nei_v.second = tree_edges->array[i];
        nei_u.second = tree_edges->array[i];
        nei_v.first = vv, nei_v.third = false;
        nei_u.first = uu, nei_u.third = false;
        adj[uu].array[adj[uu].size++] = nei_v;  
        adj[vv].array[adj[vv].size++] = nei_u;  
    }
    int start_node = tree_nodes->array[0];
    bool *visited = calloc((size_t) n, sizeof(bool));
    tour_nodes->array[tour_nodes->size++] = start_node;
    while (true) {
        bool flag_1 = false;
        visited[start_node] = true;
        for (i = 0; i < (int) adj[start_node].size; i++) {
            int next_node = adj[start_node].array[i].first;
            int edge_index = adj[start_node].array[i].second;
            if (!visited[next_node]) { 
                visited[next_node] = true; 
                tour_nodes->array[tour_nodes->size++] = next_node;
                tour_edges->array[tour_edges->size++] = edge_index;
                adj[start_node].array[i].third = true; 
                start_node = next_node;
                flag_1 = true;
                break;
            }
        }
        if (!flag_1) {
            bool flag_2 = false;
            for (i = 0; i < (int) adj[start_node].size; i++) {
                int next_node = adj[start_node].array[i].first;
                int edge_index = adj[start_node].array[i].second;
                bool is_visited = adj[start_node].array[i].third;
                if (!is_visited) {
                    adj[start_node].array[i].third = true;
                    tour_nodes->array[tour_nodes->size++] = next_node;
                    tour_edges->array[tour_edges->size++] = edge_index;
                    start_node = next_node;
                    flag_2 = true;
                    break;
                }
            }
            if (!flag_2) {
                break;
            }
        }
    }
    free(visited);
    for (i = 0; i < n; i++) { free(adj[i].array); }
    free(adj);
    free(nei_size);
    return true;
}
bool dfs_tour ( const EdgePair * edges , int n , Array * tree_nodes , Array * tree_edges , Array * tour_nodes , Array * tour_edges ) { if ( tree_nodes -> size <= 1 ) { printf ( " " ) ; exit ( 0 ) ; } typedef struct { int first ; int second ; bool third ; } Tuple ; typedef struct { Tuple * array ; size_t size ; } Nei ; int i , * nei_size = calloc ( ( size_t ) n , sizeof ( int ) ) ; for ( i = 0 ; i < tree_edges -> size ; i ++ ) { nei_size [ edges [ tree_edges -> array [ i ] ] . first ] ++ ; nei_size [ edges [ tree_edges -> array [ i ] ] . second ] ++ ; } Nei * adj = malloc ( sizeof ( Nei ) * n ) ; for ( i = 0 ; i < n ; i ++ ) { adj [ i ] . size = 0 ; adj [ i ] . array = malloc ( sizeof ( Tuple ) * nei_size [ i ] ) ; } for ( i = 0 ; i < tree_edges -> size ; i ++ ) { int uu = edges [ tree_edges -> array [ i ] ] . first ; int vv = edges [ tree_edges -> array [ i ] ] . second ; Tuple nei_v , nei_u ; nei_v . second = tree_edges -> array [ i ] ; nei_u . second = tree_edges -> array [ i ] ; nei_v . first = vv , nei_v . third = false ; nei_u . first = uu , nei_u . third = false ; adj [ uu ] . array [ adj [ uu ] . size ++ ] = nei_v ; adj [ vv ] . array [ adj [ vv ] . size ++ ] = nei_u ; } int start_node = tree_nodes -> array [ 0 ] ; bool * visited = calloc ( ( size_t ) n , sizeof ( bool ) ) ; tour_nodes -> array [ tour_nodes -> size ++ ] = start_node ; while ( true ) { bool flag_1 = false ; visited [ start_node ] = true ; for ( i = 0 ; i < ( int ) adj [ start_node ] . size ; i ++ ) { int next_node = adj [ start_node ] . array [ i ] . first ; int edge_index = adj [ start_node ] . array [ i ] . second ; if ( ! visited [ next_node ] ) { visited [ next_node ] = true ; tour_nodes -> array [ tour_nodes -> size ++ ] = next_node ; tour_edges -> array [ tour_edges -> size ++ ] = edge_index ; adj [ start_node ] . array [ i ] . third = true ; start_node = next_node ; flag_1 = true ; break ; } } if ( ! flag_1 ) { bool flag_2 = false ; for ( i = 0 ; i < ( int ) adj [ start_node ] . size ; i ++ ) { int next_node = adj [ start_node ] . array [ i ] . first ; int edge_index = adj [ start_node ] . array [ i ] . second ; bool is_visited = adj [ start_node ] . array [ i ] . third ; if ( ! is_visited ) { adj [ start_node ] . array [ i ] . third = true ; tour_nodes -> array [ tour_nodes -> size ++ ] = next_node ; tour_edges -> array [ tour_edges -> size ++ ] = edge_index ; start_node = next_node ; flag_2 = true ; break ; } } if ( ! flag_2 ) { break ; } } } free ( visited ) ; for ( i = 0 ; i < n ; i ++ ) { free ( adj [ i ] . array ) ; } free ( adj ) ; free ( nei_size ) ; return true ; }
deep first search for finding a tour.
deep first search for finding a tour .
/**
     * This method is to find a euler tour given a tree. This method is
     * proposed in the following paper:
     *  Authors : Edmonds, Jack, and Ellis L. Johnson.
     *  Title : Matching, Euler tours and the Chinese postman
     *  Journal: Mathematical programming 5.1 (1973): 88-124.
     */ //Make sure the tree has at least two nodes. // each tuple is: (indexed node, edge_index, is_visited) // edge u --> v // edge v --> u // The first element as tour's root. // iterate the adj of each node. in this loop, we check if // there exists any its neighbor which has not been visited. // first time to visit this node. // mark it as visited. // mark it as labeled. // all neighbors are visited. Then we check if // there exists adj which is false nodes. // there exists a neighbor. has false node // all nodes are visited and there is no false nodes.