bool vertex_separator_flow_solver::construct_flow_pb( const PartitionConfig & config, 
                                                      graph_access & G, 
                                                      PartitionID & lhs, 
                                                      PartitionID & rhs, 
                                                      std::vector<NodeID> & lhs_nodes,
                                                      std::vector<NodeID> & rhs_nodes,
                                                      std::vector<NodeID> & new_to_old_ids,              
                                                      long *n_ad, 
                                                      long* m_ad, 
                                                      node** nodes_ad, 
                                                      arc** arcs_ad, 
                                                      long ** cap_ad,
                                                      node** source_ad, 
                                                      node** sink_ad, 
                                                      long* node_min_ad,
                                                      EdgeID & no_edges_in_flow_graph) { 
        
        //very dirty for loading variables :). some time this should all be refactored. for now we can focus on the important stuff.
        #include "../refinement/quotient_graph_refinement/flow_refinement/flow_solving_kernel/convert_ds_variables.h"

        //building up the graph as in parse.h of hi_pr code
        //first we have to count the number of edges 
        // s to lhs + rhs to t + lhs to rhs 
        unsigned no_edges = 0;
        for( unsigned i = 0; i < lhs_nodes.size(); i++) {
                NodeID node = lhs_nodes[i];
                forall_out_edges(G, e, node) {
                        NodeID target = G.getEdgeTarget(e);
                        if(rhs == G.getPartitionIndex(target)) {
                                ++no_edges;
                        }
                } endfor
        }

void mis_permutation::construct(graph_access & G) {
    inconsistencies = 0;
    solution_size = 0;
    free_size = 0;
    total_size = G.number_of_nodes();
    nodes.clear();
    tightness.clear();
    position.clear();
    nodes.resize(total_size);
    tightness.resize(total_size);
    position.resize(total_size);
    onetight_all.init(G.number_of_nodes());

    // Insert solution nodes
    forall_nodes(G, n) {
        nodes[n] = n;
        position[n] = n;
        unsigned int index = G.getPartitionIndex(n);
        // Maybe implement tightness calculations here
        if (index == 1) {
            move_to_solution(n, G);
        } else {
            int tight = calculate_tightness(n, G);
            tightness[n] = tight;
            if (tight == 0) move_to_free(n, G);
            else move_to_non_free(n, G);
            if (tight == 1) onetight_all.insert(n);
        }
    } endfor

void population_mis::set_mis_for_individuum(MISConfig & config, graph_access & G, individuum_mis & ind, bool secondary) {
    G.resizeSecondPartitionIndex(G.number_of_nodes());
    forall_nodes(G, node) {
        if (!secondary) G.setPartitionIndex(node, ind.solution[node]);
        else G.setSecondPartitionIndex(node, ind.solution[node]);
    } endfor
}

void kway_graph_refinement_core::move_node_back(PartitionConfig & config, 
                graph_access & G, 
                NodeID & node,
                PartitionID & to, 
                vertex_moved_hashtable & moved_idx, 
                refinement_pq * queue, 
                complete_boundary & boundary) {

        PartitionID from = G.getPartitionIndex(node);
        G.setPartitionIndex(node, to);        

        boundary_pair pair;
        pair.k   = config.k;
        pair.lhs = from;
        pair.rhs = to;

        //update all boundaries
        boundary.postMovedBoundaryNodeUpdates(node, &pair, true, true);

        NodeWeight this_nodes_weight = G.getNodeWeight(node);
        boundary.setBlockNoNodes(from, boundary.getBlockNoNodes(from)-1);
        boundary.setBlockNoNodes(to,   boundary.getBlockNoNodes(to)+1);
        boundary.setBlockWeight( from, boundary.getBlockWeight(from)-this_nodes_weight);
        boundary.setBlockWeight( to,   boundary.getBlockWeight(to)+this_nodes_weight);
}

void cycle_search::find_random_cycle(graph_access & G, std::vector<NodeID> & cycle) {
	//first perform a bfs starting from a random node and build the parent array
        std::deque<NodeID>* bfsqueue = new std::deque<NodeID>;
	NodeID v = random_functions::nextInt(0, G.number_of_nodes()-1);
	bfsqueue->push_back(v); 

	std::vector<bool>   touched(G.number_of_nodes(),false);
	std::vector<bool>   is_leaf(G.number_of_nodes(),false);
	std::vector<NodeID> parent(G.number_of_nodes(),0);
	std::vector<NodeID> leafes;
	touched[v] = true;
	parent[v]  = v;

	while(!bfsqueue->empty()) {
		NodeID source = bfsqueue->front();
		bfsqueue->pop_front();

		bool is_leaf = true;
		forall_out_edges(G, e, source) {
			NodeID target = G.getEdgeTarget(e);
			if(!touched[target]) {
				is_leaf         = false;
				touched[target] = true; 
				parent[target]  = source;
				bfsqueue->push_back(target);
			}
		} endfor

		if(is_leaf) 
			leafes.push_back(source);

	}

void fast_construct_mapping::construct_initial_mapping_bottomup_internal( PartitionConfig & config, graph_access & C, matrix & D, int idx,  std::vector< NodeID > & perm_rank) {

        PartitionID num_parts = C.number_of_nodes()/config.group_sizes[idx];
        partition_C_perfectly_balanced( config, C, num_parts);

        if( idx ==(int)(config.group_sizes.size() - 1) ) {
                // build initial offsets 
                int nodes_per_block = m_tmp_num_nodes / config.group_sizes[idx];
                perm_rank[0] = 0;
                for( unsigned int block = 1; block < perm_rank.size(); block++) {
                        perm_rank[block] = perm_rank[block-1]+nodes_per_block;
                }
        } else {
                //contract partitioned graph
                graph_access Q; complete_boundary bnd(&C);
                bnd.build();
                bnd.getUnderlyingQuotientGraph(Q);
               
                std::vector< NodeID > rec_ranks( num_parts, 0);
                construct_initial_mapping_bottomup_internal( config, Q, D, idx+1, rec_ranks);

                //recompute offsets 
                forall_nodes(C, node) {
                        PartitionID block = C.getPartitionIndex(node);
                        perm_rank[node]   = rec_ranks[block];
                        rec_ranks[block] += C.getNodeWeight(node);
                } endfor
        }

void kway_graph_refinement::setup_start_nodes(PartitionConfig & config, graph_access & G, complete_boundary & boundary,  boundary_starting_nodes & start_nodes) {
        QuotientGraphEdges quotient_graph_edges;
        boundary.getQuotientGraphEdges(quotient_graph_edges);

        unordered_map<NodeID, bool> allready_contained;

        for( unsigned i = 0; i < quotient_graph_edges.size(); i++) {
                boundary_pair & ret_value = quotient_graph_edges[i];
                PartitionID lhs           = ret_value.lhs;
                PartitionID rhs           = ret_value.rhs;

                PartialBoundary & partial_boundary_lhs = boundary.getDirectedBoundary(lhs, lhs, rhs);
                forall_boundary_nodes(partial_boundary_lhs, cur_bnd_node) {
                        ASSERT_EQ(G.getPartitionIndex(cur_bnd_node), lhs);
                        if(allready_contained.find(cur_bnd_node) == allready_contained.end() ) { 
                                start_nodes.push_back(cur_bnd_node);
                                allready_contained[cur_bnd_node] = true;
                        }
                } endfor

                PartialBoundary & partial_boundary_rhs = boundary.getDirectedBoundary(rhs, lhs, rhs);
                forall_boundary_nodes(partial_boundary_rhs, cur_bnd_node) {
                        ASSERT_EQ(G.getPartitionIndex(cur_bnd_node), rhs);
                        if(allready_contained.find(cur_bnd_node) == allready_contained.end()) { 
                                start_nodes.push_back(cur_bnd_node);
                                allready_contained[cur_bnd_node] = true;
                        }
                } endfor

EdgeWeight tabu_search::perform_refinement(PartitionConfig & config, graph_access & G, complete_boundary & boundary) {
        quality_metrics qm;
        EdgeWeight input_cut = qm.edge_cut(G);
        EdgeWeight cur_cut   = input_cut;
        EdgeWeight best_cut  = input_cut;
        std::vector< PartitionID > bestmap(G.number_of_nodes(), 0);
        forall_nodes(G, node) {
                bestmap[node] = G.getPartitionIndex(node);
        } endfor

int mis_permutation::calculate_tightness(NodeID node, graph_access & G) {
    int tightness = 0;
    forall_out_edges(G, edge, node) {
        NodeID target = G.getEdgeTarget(edge);
        bool target_index = G.getPartitionIndex(target);
        if (target_index == 1) {
            tightness++;
        }
    } endfor

int graph_io::writeGraphWeighted(graph_access & G, std::string filename) {
        std::ofstream f(filename.c_str());
        f << G.number_of_nodes() <<  " " <<  G.number_of_edges()/2 <<  " 11" <<  std::endl;

        forall_nodes(G, node) {
                f <<  G.getNodeWeight(node) ;
                forall_out_edges(G, e, node) {
                        f << " " <<   (G.getEdgeTarget(e)+1) <<  " " <<  G.getEdgeWeight(e) ;
                } endfor 

void separator_pool::init(MISConfig & config, graph_access & G) {
    xadj = G.UNSAFE_metis_style_xadj_array();
    adjncy = G.UNSAFE_metis_style_adjncy_array();
    separators_size = config.number_of_separators; 
    partitions_size = config.number_of_partitions; 
    k_separators_size = config.use_multiway_vc ? 0 : config.number_of_k_separators;
    k_partitions_size = config.use_multiway_vc ? config.number_of_k_partitions : 0;
    if (config.use_multiway_vc) scores.resize(config.multiway_blocks*config.population_size*config.number_of_k_partitions);
    else scores.resize(config.multiway_blocks*config.population_size*config.number_of_k_separators);
    clear_scores(config);
}

EdgeWeight quality_metrics::edge_cut(graph_access & G) {
        EdgeWeight edgeCut = 0;
        forall_nodes(G, n) { 
                PartitionID partitionIDSource = G.getPartitionIndex(n);
                forall_out_edges(G, e, n) {
                        NodeID targetNode = G.getEdgeTarget(e);
                        PartitionID partitionIDTarget = G.getPartitionIndex(targetNode);

                        if (partitionIDSource != partitionIDTarget) {
                                edgeCut += G.getEdgeWeight(e);
                        }
                } endfor 

void topological_sort::sort( graph_access & G, std::vector<NodeID> & sorted_sequence) {
        std::vector<int> dfsnum(G.number_of_nodes(), -1);
        int dfscount = 0;

        std::vector<NodeID> nodes(G.number_of_nodes());
        random_functions::permutate_vector_good(nodes, true);

        forall_nodes(G, node) {
                NodeID curNode = nodes[node];
                if(dfsnum[curNode] == -1) {
                        sort_dfs(curNode, G, dfsnum, dfscount, sorted_sequence); 
                }
        } endfor

bool augmented_Qgraph_fabric::build_augmented_quotient_graph( PartitionConfig & config, 
                                                              graph_access & G, 
                                                              complete_boundary & boundary, 
                                                              augmented_Qgraph & aqg, 
                                                              unsigned & s, bool rebalance, bool plus) {

        graph_access G_bar;
        boundary.getUnderlyingQuotientGraph(G_bar); 
        if(m_eligible.size() != G.number_of_nodes()) {
                m_eligible.resize(G.number_of_nodes());
                forall_nodes(G, node) {
                        m_eligible[node] = true;
                } endfor
        } else {

int wcycle_partitioner::perform_partitioning(const PartitionConfig & config, graph_access & G) {
        PartitionConfig  cfg = config; 

        if(config.stop_rule == STOP_RULE_SIMPLE) {
                m_coarsening_stop_rule = new simple_stop_rule(cfg, G.number_of_nodes());
        } else {
                m_coarsening_stop_rule = new multiple_k_stop_rule(cfg, G.number_of_nodes());
        }

        int improvement = (int) perform_partitioning_recursive(cfg, G, NULL); 
        delete m_coarsening_stop_rule;

        return improvement;
}

void greedy_mis::initial_partition(const unsigned int seed, graph_access & G) {
    random_functions::setSeed(seed);
    NodePermutationMap permutation;
    generate_permutation(G, permutation);

    bucket_array *buckets = new bucket_array(G.number_of_nodes());
    G.set_partition_count(2);

    // Initialize the priority queue
    forall_nodes (G, n) {
        NodeID node = permutation[n];
        EdgeWeight node_degree = G.getNodeDegree(node);
        buckets->increment(node, node_degree);
        G.setPartitionIndex(node, 0);
    } endfor

EdgeWeight parallel_mh_async::collect_best_partitioning(graph_access & G) {
        //perform partitioning locally
	EdgeWeight min_objective = 0;
        m_island->apply_fittest(G, min_objective);

        int best_local_objective  = min_objective;
        int best_global_objective = 0; 

        PartitionID* best_local_map = new PartitionID[G.number_of_nodes()];
	std::vector< NodeWeight > block_sizes(G.get_partition_count(),0);

        forall_nodes(G, node) {
                best_local_map[node] = G.getPartitionIndex(node);
		block_sizes[G.getPartitionIndex(node)]++;
        } endfor

void bipartition::initial_partition( const PartitionConfig & config, 
                                     const unsigned int seed, 
                                     graph_access & G, 
                                     int* partition_map) {

        timer t;
        t.restart();
        unsigned iterations = config.bipartition_tries;
        EdgeWeight best_cut = std::numeric_limits<EdgeWeight>::max();
        int best_load       = std::numeric_limits<int>::max();

        for( unsigned i = 0; i < iterations; i++) {
                if(config.bipartition_algorithm == BIPARTITION_BFS)  {
                        grow_regions_bfs(config, G);
                } else if( config.bipartition_algorithm == BIPARTITION_FM) {
                        grow_regions_fm(config, G);
                } 

                G.set_partition_count(2);

                post_fm(config, G);

                quality_metrics qm;
                EdgeWeight curcut = qm.edge_cut(G); 

                int lhs_block_weight = 0;
                int rhs_block_weight = 0;

                forall_nodes(G, node) {
                        if(G.getPartitionIndex(node) == 0) {
                                lhs_block_weight += G.getNodeWeight(node);
                        } else {
                                rhs_block_weight += G.getNodeWeight(node);
                        }
                } endfor

                int lhs_overload = std::max(lhs_block_weight - config.target_weights[0],0);
                int rhs_overload = std::max(rhs_block_weight - config.target_weights[1],0);

                if(curcut < best_cut || (curcut == best_cut && lhs_overload + rhs_block_weight < best_load) ) {
                        //store it
                        best_cut  = curcut;
                        best_load = lhs_overload + rhs_overload;

                        forall_nodes(G, n) {
                                partition_map[n] =  G.getPartitionIndex(n);
                        } endfor
                } 

void two_way_fm::init_queue_with_boundary(const PartitionConfig & config,
                                          graph_access & G,
                                          std::vector<NodeID> & bnd_nodes,
                                          refinement_pq * queue,                     
                                          PartitionID partition_of_boundary, 
                                          PartitionID other) {

        if(config.permutation_during_refinement == PERMUTATION_QUALITY_FAST) {
                random_functions::permutate_vector_fast(bnd_nodes, false);
        } else if(config.permutation_during_refinement == PERMUTATION_QUALITY_GOOD) {
                random_functions::permutate_vector_good(bnd_nodes, false);
        }


        for( unsigned int i = 0, end = bnd_nodes.size(); i < end; i++) {
                NodeID cur_bnd_node = bnd_nodes[i];
                //compute gain
                EdgeWeight int_degree = 0;
                EdgeWeight ext_degree = 0;

                int_ext_degree(G, cur_bnd_node, partition_of_boundary, other, int_degree, ext_degree);

                Gain gain = ext_degree - int_degree;
                queue->insert(cur_bnd_node, gain);
                ASSERT_TRUE(ext_degree > 0);
                ASSERT_EQ(partition_of_boundary, G.getPartitionIndex(cur_bnd_node));
        }
}

void initial_partition_bipartition::initial_partition( const PartitionConfig & config, 
                                                       const unsigned int seed,  
                                                       graph_access & G, int* partition_map) {
        graph_partitioner gp;
        PartitionConfig rec_config                  = config;
        rec_config.initial_partitioning_type        = INITIAL_PARTITIONING_BIPARTITION;
        rec_config.initial_partitioning_repetitions = 0;
        rec_config.global_cycle_iterations          = 1;
        rec_config.use_wcycles                      = false;
        rec_config.use_fullmultigrid                = false;
        rec_config.fm_search_limit                  = config.bipartition_post_ml_limits;
        rec_config.matching_type                    = MATCHING_GPA;
        //rec_config.matching_type                    = CLUSTER_COARSENING;
        rec_config.permutation_quality              = PERMUTATION_QUALITY_GOOD;

        rec_config.initial_partitioning             = true;

        std::streambuf* backup = std::cout.rdbuf();
        std::ofstream ofs;
        ofs.open("/dev/null");
        std::cout.rdbuf(ofs.rdbuf()); 

        gp.perform_recursive_partitioning(rec_config, G); 

        ofs.close();
        std::cout.rdbuf(backup);

        forall_nodes(G, n) {
                partition_map[n] =  G.getPartitionIndex(n);
        } endfor