void parallel_dc(graph_t& g, unsigned threadnum, gBenchPerf_multi & perf, int perf_group)
{
    uint64_t chunk = (unsigned)ceil(g.num_vertices()/(double)threadnum);
    #pragma omp parallel num_threads(threadnum)
    {
        unsigned tid = omp_get_thread_num();

        perf.open(tid, perf_group);
        perf.start(tid, perf_group); 
       
        unsigned start = tid*chunk;
        unsigned end = start + chunk;
        if (end > g.num_vertices()) end = g.num_vertices();

        for (unsigned vid=start;vid<end;vid++)
        {
            vertex_iterator vit = g.find_vertex(vid);
            // out degree
            vit->property().outdegree = vit->edges_size();

            // in degree
            edge_iterator eit;
            for (eit=vit->edges_begin(); eit!=vit->edges_end(); eit++) 
            {
                vertex_iterator targ = g.find_vertex(eit->target());
                __sync_fetch_and_add(&(targ->property().indegree), 1);
            }

        }
        perf.stop(tid, perf_group);
    }
}

void randomgraph_construction(graph_t &g, size_t vertex_num, size_t edge_num, gBenchPerf_event & perf, int perf_group)
{
    vector<pair<size_t,size_t> > edges;
    for (size_t i=0;i<edge_num;i++) 
    {
        edges.push_back(make_pair(rand()%vertex_num, rand()%vertex_num));
    }
    perf.open(perf_group);
    perf.start(perf_group);
    for (size_t i=0;i<vertex_num;i++) 
    {
        vertex_iterator vit = g.add_vertex();
        vit->set_property(vertex_property(i));
    }
#ifdef SIM
    SIM_BEGIN(true);
#endif 
    for (size_t i=0;i<edge_num;i++) 
    {
        edge_iterator eit;
        g.add_edge(edges[i].first, edges[i].second, eit);
#ifndef SIM
        eit->set_property(edge_property(i));
#endif
    }
#ifdef SIM
    SIM_END(true);
#endif 
    perf.stop(perf_group);
}

//==============================================================//
void dc(graph_t& g, gBenchPerf_event & perf, int perf_group) 
{
    perf.open(perf_group);
    perf.start(perf_group);
#ifdef SIM
    SIM_BEGIN(true);
#endif
    vertex_iterator vit;
    for (vit=g.vertices_begin(); vit!=g.vertices_end(); vit++) 
    {
        // out degree
        vit->property().outdegree = vit->edges_size();

        // in degree
        edge_iterator eit;
        for (eit=vit->edges_begin(); eit!=vit->edges_end(); eit++) 
        {
            vertex_iterator targ = g.find_vertex(eit->target());
            (targ->property().indegree)++;
        }
    }
#ifdef SIM
    SIM_END(true);
#endif
    perf.stop(perf_group);
}// end dc

void degree_analyze(graph_t& g, 
                    uint64_t& indegree_max, uint64_t& indegree_min,
                    uint64_t& outdegree_max, uint64_t& outdegree_min)
{
    vertex_iterator vit;
    indegree_max=outdegree_max=0;
    indegree_min=outdegree_min=numeric_limits<uint64_t>::max();


    for (vit=g.vertices_begin(); vit!=g.vertices_end(); vit++) 
    {
        if (indegree_max < vit->property().indegree)
            indegree_max = vit->property().indegree;

        if (outdegree_max < vit->property().outdegree)
            outdegree_max = vit->property().outdegree;

        if (indegree_min > vit->property().indegree)
            indegree_min = vit->property().indegree;

        if (outdegree_min > vit->property().outdegree)
            outdegree_min = vit->property().outdegree;
    }

    return;
}

    // ヒントを与えた上でgreedy探索を行う
    // graph: 元となったグラフ構造
    // parent_nodes, child_nodes: parent_nodesに含まれるnodeからchild_nodeに含まれるnodeにしか辺を張らない
    double learn_with_hint(graph_t& graph, std::vector<vertex_type> parent_nodes, std::vector<vertex_type> child_nodes)
    {
        // 子ノードの出現順序をランダムに
        std::shuffle(std::begin(child_nodes), std::end(child_nodes), engine_);

        // 最高評価値を保存しておく
        sampling_.make_cpt(graph);
        double eval_now = eval_(graph);

        // 親候補と子候補を全部回して様子見る
        for(auto const& child : child_nodes)
        {
            // 親ノードの出現順序をランダムに
            std::shuffle(std::begin(parent_nodes), std::end(parent_nodes), engine_);

            for(auto const& parent : parent_nodes)
            {
                if(auto edge = graph.add_edge(parent, child))
                {
                    // 辺が張れたならば，評価をする
                    sampling_.make_cpt(graph);
                    auto const eval_next = eval_(graph);

                    if(eval_next < eval_now)
                        // 良くなってるscore
                        eval_now = eval_next;
                    else
                        // 変わらない or 悪い -> 元に戻す
                        graph.erase_edge(edge);
                }
            }
        }

        return eval_now;
    }

void output(graph_t& g)
{
    cout<<"Results: \n";
    vertex_iterator vit;
    for (vit=g.vertices_begin(); vit!=g.vertices_end(); vit++)
    {
        cout<<"== vertex "<<vit->id()<<": edge#-"<<vit->edges_size()<<"\n";
    }
}

void reset_graph(graph_t & g)
{
    vertex_iterator vit;
    for (vit=g.vertices_begin(); vit!=g.vertices_end(); vit++)
    {
        vit->property().indegree = 0;
        vit->property().outdegree = 0;
    }
}

//==============================================================//
void output(graph_t& g)
{
    cout<<"Betweenness Centrality Results: \n";
    vertex_iterator vit;
    for (vit=g.vertices_begin(); vit!=g.vertices_end(); vit++)
    {
        cout<<"== vertex "<<vit->id()<<": "<<vit->property().BC<<"\n";
    }
}

void reset_graph(graph_t & g)
{
    vertex_iterator vit;
    for (vit=g.vertices_begin(); vit!=g.vertices_end(); vit++)
    {
        vit->property().root = vit->id();
    }

}

void output(graph_t& g)
{
    cout<<"WCC Results: \n";
    vertex_iterator vit;
    for (vit=g.vertices_begin(); vit!=g.vertices_end(); vit++)
    {
        cout << vit->id() << " " << vit->property().root << "\n";
    }
}

void graph_update(graph_t &g, vector<uint64_t> IDs)
{
    for (size_t i=0;i<IDs.size();i++) 
    {
        if (g.num_vertices()==0) break;

        g.delete_vertex(IDs[i]);
    }
    
}

void output(graph_t& g) 
{
    cout<<"Degree Centrality Results: \n";
    vertex_iterator vit;
    for (vit=g.vertices_begin(); vit!=g.vertices_end(); vit++)
    {
        cout<<"== vertex "<<vit->id()<<": in-"<<vit->property().indegree
            <<" out-"<<vit->property().outdegree<<"\n";
    }
}

void reset_graph(graph_t & g)
{
    vertex_iterator vit;
    for (vit=g.vertices_begin(); vit!=g.vertices_end(); vit++)
    {
        vit->property().degree = 0;
        vit->property().removed = false;
    }

}

void prepareGraphIncrementaly(graph_t &graph)
{
  obj_t obj;
  P::Pose p;
  P::InformMatrix inform;
  graph.addNode(node_t(p, obj));
  for (size_t i = 0; i < 19; ++i) {
    graph.addNode(node_t(p, obj));
    graph.addEdge(edge_t(&graph.getNode(i), &graph.getNode(i + 1), p, inform));
  }
}

void parallel_init(graph_t& g, unsigned threadnum,
                   vector<vector<uint64_t> >& global_input_tasks)
{
    global_input_tasks.resize(threadnum);
    for (vertex_iterator vit=g.vertices_begin(); vit!=g.vertices_end(); vit++)
    {
        vit->property().root = vit->id();
        global_input_tasks[vertex_distributor(vit->id(), threadnum)].push_back(vit->id());

    }
}

void delete_edge(graph_t& g, uint32_t u, uint32_t v) {
  auto it = g.find(u);
  
  // u does not exist
  if (it == g.end()) {
    return;
  }

  vector<uint32_t>& neighbors = it->second;
  neighbors.erase(remove_if(neighbors.begin(), neighbors.end(),
                            [v](uint32_t n) {return n == v;}),
                  neighbors.end());
}

size_t kcore(graph_t& g, size_t k, gBenchPerf_event & perf, int perf_group) 
{
    size_t remove_cnt=0;

    queue<vertex_iterator> process_q;

    // initialize
    for (vertex_iterator vit=g.vertices_begin(); vit!=g.vertices_end(); vit++) 
    {
        size_t degree = vit->edges_size();
        vit->property().degree = degree;

        if (degree < k) 
        {
            process_q.push(vit);
            vit->property().removed = true;
            remove_cnt++;
        }
    }
    
    perf.open(perf_group);
    perf.start(perf_group);

    // remove vertices iteratively 
    while (!process_q.empty()) 
    {

        vertex_iterator vit = process_q.front();
        process_q.pop();

        for (edge_iterator eit=vit->edges_begin(); eit!=vit->edges_end(); eit++) 
        {
            size_t targ = eit->target();
            vertex_iterator targ_vit = g.find_vertex(targ);
            if (targ_vit->property().removed==false)
            {
                targ_vit->property().degree--;
                if (targ_vit->property().degree < k) 
                {
                    targ_vit->property().removed = true;
                    process_q.push(targ_vit);
                    remove_cnt++;
                }
            }
        }

    }

    perf.stop(perf_group);
    return remove_cnt;
}  // end kcore

//==============================================================//
void output(graph_t& g)
{
    cout<<"kCore Results: \n";
    vertex_iterator vit;
    for (vit=g.vertices_begin(); vit!=g.vertices_end(); vit++)
    {
        cout<<"== vertex "<<vit->id()<<": degree-"<<vit->property().degree
            <<" removed-";
        if (vit->property().removed) 
            cout<<"true\n";
        else
            cout<<"false\n";
    }
}

size_t biconnected_components(graph_t& g, vector<graph_t*>& bicomponents) {
	map< edge_descriptor_t, unsigned > bicomponent_edges;
	vector<vertex_discripter_t> articulation_points;
	articulation_points.reserve(num_vertices(g));

	int n = biconnected_components(g,
			make_assoc_property_map(bicomponent_edges),
			back_inserter(articulation_points) ).first;
	int o = bicomponents.size();
	for (int i=0; i<n; i++)
		bicomponents.push_back( &(g.create_subgraph()) );
	graph_traits<graph_t>::edge_iterator e, e_end;
	for (tie(e, e_end) = edges(g); e != e_end; ++e) {
		add_vertex_once( source(*e,g), *bicomponents[o+bicomponent_edges[*e]] );
		add_vertex_once( target(*e,g), *bicomponents[o+bicomponent_edges[*e]] );
	}
	// cout << "Graph #" << ... << " : " << get(graph_name, g);
	// cout << " |V|=" << num_vertices(g) << endl;
	// cout << " |Component|=" << bicomponents.size() << endl;

	vector<vertex_discripter_t>::iterator v,v_end;
	cout << "Art.pts.\tComponents\n";
	// cout << articulation_points.size() << endl;
	for (v=articulation_points.begin(), v_end=articulation_points.end();
			v != v_end; v++) {
		cout << get(&vertex_properties::id, g, *v) << "\t\t";
		for (int i=0; i<n; i++)
			if ((bicomponents[o+i]->find_vertex(*v)).second)
				cout << ' ' << o+i << ' ';
		cout << endl;
	}
	return n;
}

dists_t dijkstra_shortest_path(graph_t g, vert_t s) {
    set<pair<dist_t, vert_t> > q; // implicit ordering by distance
    
    // ps_t ps(g.size(), -1);
    
    dists_t dists(g.size(), dist_infty);
    dists[s] = 0;
    
    q.insert(make_pair(dists[s], s));
    while( !q.empty() ) {
        dist_t dist = q.begin()->first;
        vert_t v = q.begin()->second;
        q.erase( q.begin() ); // pop first
        
        for(int i=0; i<g[v].size(); i++) {
            vert_t t = g[v][i].to;
            dist_t d_with = dist + g[v][i].len;
            
            if( d_with < dists[t] ) { // relax
                q.erase( make_pair(dists[t], t) );
                q.insert( make_pair(d_with, t) );
                dists[t] = d_with;
                // ps[t] = v;
            }
        }
    }
    
    return dists;
}