<commit_before>// (C) 2014 <NAME>

#pragma once

#include <algorithm>
#include <stack>
#include <vector>

#include <boost/graph/adjacency_list.hpp>

#include "range.hpp"

namespace detail {

  unsigned typedef node;
  std::pair<node, node> typedef edge;

  template <class Graph>
  void visit(Graph& G, Graph& T, node v,
    node& next_rank, std::vector<unsigned>& rank,
    std::vector<unsigned>& deg, std::stack<edge>& edges) {

    rank[v] = next_rank++;

    node w = -1, x, y;
    unsigned min_deg = UINT_MAX;

    for(auto u : range(adjacent_vertices(v, G))) {
      --deg[u];

      if(rank[u] == 0 && deg[u] < min_deg) {
        w = u;
        min_deg = deg[u];
      }
    }

    if(min_deg == UINT_MAX) {
      while(!edges.empty() && rank[edges.top().second] != 0)
        edges.pop();
      if(edges.empty())
        return;
      std::tie(x, y) = edges.top();
    } else std::tie(x, y) = edge(v, w);

    add_edge(x, y, T);

    for(auto u : range(adjacent_vertices(x, G)))
      if(u != y && rank[u] == 0)
        edges.emplace(x, u);

    visit(G, T, y, next_rank, rank, deg, edges);
  }

}

template <class Graph>
Graph rdfs_tree(Graph& G) {
  unsigned n = num_vertices(G);
  Graph T(n);
  unsigned next_rank = 1;
  std::vector<unsigned> rank(n, 0), deg(n, 0);
  std::stack<detail::edge> edges;

  for(auto v : range(vertices(G)))
    deg[v] = degree(v, G);

  detail::visit(G, T, 0, next_rank, rank, deg, edges);

  return T;
}

template <class Graph>
Graph rdfs_sort_tree(Graph const & G) {
  typedef std::pair<int, int> edge;
  std::vector<unsigned> deg(num_vertices(G));
  std::vector<bool> V(num_vertices(G));
  std::stack<edge> Q;
  Graph T(num_vertices(G));
  int parent, v = 0;
  Q.emplace(-1, v);
  for(auto v : range(vertices(G))) deg[v] = degree(v, G);
  while(!Q.empty()) {
    std::tie(parent, v) = Q.top();
    Q.pop();
    if(!V[v]) {
      V[v] = true;
      if(parent >= 0) add_edge(parent, v, T);
      std::vector<unsigned> neighbors;
      for(auto w : range(adjacent_vertices(v, G))) if(!V[w]) {
        --deg[w];
        neighbors.push_back(w);
      }<commit_msg>remove unused rank array<commit_after>// (C) 2014 <NAME>

#pragma once

#include <algorithm>
#include <stack>
#include <vector>

#include <boost/graph/adjacency_list.hpp>

#include "range.hpp"

namespace detail {

  unsigned typedef node;
  std::pair<node, node> typedef edge;

  template <class Graph>
  void visit(Graph& G, Graph& T, node v, std::vector<bool>& visited,
    std::vector<unsigned>& deg, std::stack<edge>& edges) {

    visited[v] = true;

    node w = -1, x, y;
    unsigned min_deg = UINT_MAX;

    for(auto u : range(adjacent_vertices(v, G))) {
      --deg[u];

      if(!visited[u] && deg[u] < min_deg) {
        w = u;
        min_deg = deg[u];
      }
    }

    if(min_deg == UINT_MAX) {
      while(!edges.empty() && !visited[edges.top().second])
        edges.pop();
      if(edges.empty())
        return;
      std::tie(x, y) = edges.top();
    } else std::tie(x, y) = edge(v, w);

    add_edge(x, y, T);

    for(auto u : range(adjacent_vertices(x, G)))
      if(u != y && !visited[u])
        edges.emplace(x, u);

    visit(G, T, y, visited, deg, edges);
  }

}

template <class Graph>
Graph rdfs_tree(Graph& G) {
  unsigned n = num_vertices(G);
  Graph T(n);
  std::vector<bool> visited(n, 0);
  std::vector<unsigned> deg(n, 0);
  std::stack<detail::edge> edges;

  for(auto v : range(vertices(G)))
    deg[v] = degree(v, G);

  detail::visit(G, T, 0, visited, deg, edges);

  return T;
}

template <class Graph>
Graph rdfs_sort_tree(Graph const & G) {
  typedef std::pair<int, int> edge;
  std::vector<unsigned> deg(num_vertices(G));
  std::vector<bool> V(num_vertices(G));
  std::stack<edge> Q;
  Graph T(num_vertices(G));
  int parent, v = 0;
  Q.emplace(-1, v);
  for(auto v : range(vertices(G))) deg[v] = degree(v, G);
  while(!Q.empty()) {
    std::tie(parent, v) = Q.top();
    Q.pop();
    if(!V[v]) {
      V[v] = true;
      if(parent >= 0) add_edge(parent, v, T);
      std::vector<unsigned> neighbors;
      for(auto w : range(adjacent_vertices(v, G))) if(!V[w]) {
        --deg[w];
        neighbors.push_back(w);
      }
{'fraction_non_alphanumeric': 0.1888648908087353, 'fraction_numerical': 0.006239500839932805, 'mean_word_length': 3.0742913000977516, 'pattern_counts': {'":': 0, '<': 44, '<?xml version=': 0, '>': 44, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '601515', 'n_tokens_mistral': 1666, 'n_tokens_neox': 1609, 'n_words': 376}