XOR回廊のジェネレータ

XOR回廊で使ったジェネレータ。前半部分はgithubにも置きました。自由に使ってください。

// Please use ulimit -s unlimited
// Because this program occures stack over flow at SetWeightDfs

#include <assert.h>
#include "../../common/testlib.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

//=================================================================
// Parameter & Variance
//=================================================================
typedef ll Weight;
const bool UNIDIRECT = false;
const bool EXIST_WEIGHT = true;
const bool EXIST_TWICE_EDGE = false;
const int ORIGIN = 0; // if 0 is zero origin, 1 is one origin
const int VERTEX_MAX = 100000;
const Weight NOP_VALUE = 0xdeadbeaf;
vector<int> mapto; // updated by Rename
double P; // used by SkewTree

//=================================================================
// Base
//=================================================================
struct Edge {
  int src;
  int dest;
  Weight weight;
  Edge() {;}
  Edge(int src, int dest, Weight weight) : src(src), dest(dest), weight(weight) {;}
  bool operator<(const Edge &rhs) const {
    if (weight != rhs.weight) { return weight > rhs.weight; }
    if (src != rhs.src) { return src < rhs.src; }
    return dest < rhs.dest;
  }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void PrintMatrix(const Matrix &matrix) {
  for (int y = 0; y < (int)matrix.size(); y++) {
    for (int x = 0; x < (int)matrix[y].size(); x++) {
      printf("%lld ", matrix[y][x]);
    }
    puts("");
  }
}

void AddEdge(Graph &g, int f, int t, Weight w) {
  if (UNIDIRECT) {
    g[f].push_back(Edge(f, t, w));
  } else {
    g[f].push_back(Edge(f, t, w));
    g[t].push_back(Edge(t, f, w));
  }
}
//=================================================================
// Converter
//=================================================================
Graph EdgesToGraph(const Edges &edges, int n) {
  Graph g(n);
  FORIT(it, edges) {
    int f = it->src;
    int t = it->dest;
    Weight w = it->weight;
    AddEdge(g, f, t, w);
  }
  return g;
}

Edges GraphToEdges(const Graph &g) {
  const int n = g.size();
  Edges edges;
  REP(from, n) {
    FORIT(it, g[from]) {
      int to = it->dest;
      if (!UNIDIRECT && to < from) { continue; }
      edges.push_back(*it);
    }
  }
  return edges;
}

Matrix GraphToMatrix(const Graph &g) {
  const int n = g.size();
  Matrix ret(n, Array(n, NOP_VALUE));
  REP(i, n) {
    FORIT(it, g[i]) {
      ret[it->src][it->dest] = it->weight;
    }
  }
  return ret;
}

Graph MatrixToGraph(const Matrix &matrix) {
  const int n = matrix.size();
  Graph g(n);
  REP(y, n) REP(x, n) {
    if (matrix[y][x] != NOP_VALUE) {
      g[y].push_back(Edge(y, x, matrix[y][x]));
    }
  }
  return g;
}

//=================================================================
// Utility
//=================================================================
struct UnionFind {
  vector<int> parent;
  UnionFind() : parent(VERTEX_MAX, -1) {;}
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) { return false; }
    if (parent[y] < parent[x]) { swap(x, y); }
    parent[x] += parent[y];
    parent[y] = x;
    return true;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); }
};

inline ll MaxEdge(int n) {
  if (n != 0 && EXIST_TWICE_EDGE) { return 1 << 30; }
  ll ret = (ll)n * (n - 1) / 2;
  if (UNIDIRECT) { ret *= 2; }
  return ret;
}

int CountEdge(const Graph &g) {
  const int n = g.size();
  int m = 0;
  REP(i, n) { m += g[i].size(); }
  assert(UNIDIRECT || m % 2 == 0);
  if (!UNIDIRECT) { m /= 2; }
  return m;
}

Graph Merge(const vector<Graph> &gs) {
  int n = 0;
  int m = gs.size();
  REP(i, m) { n += gs[i].size(); }
  Graph retG(n);
  int offset = 0;
  REP(i, m) {
    int ln = gs[i].size();
    REP(from, ln) {
      FORIT(it, gs[i][from]) {
        int to = it->dest;
        Weight w = it->weight;
        retG[offset + from].push_back(Edge(offset + from, offset + to, w));
      }
    }
    offset += ln;
  }
  return retG;
}

Graph Merge(const Graph &l, const Graph &r) {
  vector<Graph> gs;
  gs.push_back(l);
  gs.push_back(r);
  return Merge(gs);
}

Graph SetRandomWeight(const Graph &g, Weight low, Weight high) {
  if (low > high) { swap(low, high); }
  Edges es = GraphToEdges(g);
  FORIT(it, es) {
    if (high - low == 0) {
      it->weight = 0;
    } else {
      it->weight = rnd.next(low, high);
    }
  }
  return EdgesToGraph(es, g.size());
}

bool Connected(const Graph &g) {
  const int n = g.size();
  UnionFind ufind;
  int cnt = 1;
  REP(from, n) {
    FORIT(it, g[from]) {
      int to = it->dest;
      if (ufind.unionSet(from, to)) {
        cnt++;
        if (cnt == n) { return true; }
      }
    }
  }
  return cnt == n;
}

bool TwiceEdge(const Graph &g) {
  const int n = g.size();
  set<pair<int, int> > open;
  REP(f, n) {
    FORIT(it, g[f]) {
      int t = it->dest;
      if (open.count(make_pair(f, t))) { return true; }
      open.insert(make_pair(f, t));
    }
  }
  return false;
}

Graph Rename(const Graph &g) {
  const int n = g.size();
  mapto = vector<int>(n);
  REP(i, n) { mapto[i] = i; }
  shuffle(mapto.begin(), mapto.end());

  Graph retG(n);
  REP(i, n) {
    int from = mapto[i];
    FORIT(it, g[i]) {
      int to = mapto[it->dest];
      retG[from].push_back(Edge(from, to, it->weight));
    }
  }
  return retG;
}

// Output Format is
// n m
// f1 t1 w1
// ...
// fm tm wm
Graph OutputGraph(FILE *fp, Graph g, int q, bool renameVertex = true, bool shuffleEdge = true) {
  const int n = g.size();
  const int m = CountEdge(g);;
  //int q = max(100, n);
  assert(fp != NULL);
  assert(g.size() != 0);
  if (renameVertex) { g = Rename(g); }
  else {
    mapto = vector<int>(n);
    REP(i, n) { mapto[i] = i; }
  }
  fprintf(fp, "%d %d %d\n", n, m, q);
  Edges edges = GraphToEdges(g);
  if (shuffleEdge) {
    shuffle(edges.begin(), edges.end());
  }
  FORIT(it, edges) {
    if (!UNIDIRECT && shuffleEdge && rnd.next(0, 1)) {
      swap(it->src, it->dest);
    }
    if (EXIST_WEIGHT) {
      fprintf(fp, "%d %d %lld\n", it->src + ORIGIN, it->dest + ORIGIN, it->weight);
    } else {
      fprintf(fp, "%d %d\n", it->src + ORIGIN, it->dest + ORIGIN);
    }
  }
  return g;
}

//=================================================================
// Graph Generator
//=================================================================
Graph NoEdgeGraph(int n) {
  return Graph(n);
}

Graph LineGraph(int n) {
  Graph g(n);
  REP(i, n - 1) {
    AddEdge(g, i, i + 1, 0);
  }
  return g;
}

Graph RingGraph(int n) {
  assert(n > 2);
  Graph g(n);
  REP(i, n) {
    AddEdge(g, i, (i + 1) % n, 0);
  }
  return g;
}

Graph StarGraph(int n) {
  Graph g(n);
  FOR(i, 1, n) {
    AddEdge(g, 0, i, 0);
  }
  return g;
}

Graph CompleteGraph(int n) {
  Graph g(n);
  REP(i, n) {
    REP(j, i) {
      AddEdge(g, i, j, 0);
      if (UNIDIRECT) {
        AddEdge(g, j, i, 0);
      }
    }
  }
  return g;
}

Graph BinaryTree(int n) {
  Graph g(n);
  REP(i, n) {
    int f = i;
    int t1 = i * 2 + 1;
    int t2 = i * 2 + 2;
    if (t1 < n) { AddEdge(g, f, t1, 0); }
    if (t2 < n) { AddEdge(g, f, t2, 0); }
  }
  return g;
}

// maybe slow
Graph RandomTree(int n) {
  UnionFind ufind;
  Graph g(n);
  REP(i, n - 1) {
    int f = rnd.next(n);
    int t = rnd.next(n);
    if (!ufind.unionSet(f, t)) {
      i--;
      continue;
    }
    AddEdge(g, f, t, 0);
  }
  return g;
}

// if rnd.next(1.0) < p, vertex i is connected by vertex i - 1
// else vertex i is connected by vertex [0, i - 1] with uniform distribution
// p = 0.0 then diameter is large
// p = 1.0 then there exist large degree vertex
Graph SkewTree(int n) {
  Graph g(n);
  FOR(t, 1, n) {
    int f = t - 1;
    if (rnd.next(1.0) < P) {
      f = rnd.next(t);
    }
    AddEdge(g, f, t, 0);
  }
  return g;
}

Graph RandomGraph(int n, int m) {
  assert(m <= MaxEdge(n));
  set<pair<int, int> > used;
  Graph g(n);
  REP(i, m) {
    int f = rnd.next(n);
    int t = rnd.next(n);
    if (f == t ||
        (!EXIST_TWICE_EDGE && used.count(make_pair(f, t)))) {
      i--;
      continue;
    }
    AddEdge(g, f, t, 0);
    used.insert(make_pair(f, t));
    if (!UNIDIRECT) {
      used.insert(make_pair(t, f));
    }
  }
  return g;
}

Graph EraseEdge(const Graph &g, int m) {
  const int n = g.size();
  assert(m <= CountEdge(g));
  Edges edges = GraphToEdges(g);
  shuffle(edges.begin(), edges.end());
  edges.resize(m);
  return EdgesToGraph(edges, n);
}

Graph AddRandomEdge(Graph g, int m) {
  const int n = g.size();
  assert(EXIST_TWICE_EDGE || m <= MaxEdge(n));
  set<pair<int, int> > used;
  REP(from, n) {
    FORIT(it, g[from]) {
      int to = it->dest;
      used.insert(make_pair(from, to));
      if (!UNIDIRECT) {
        used.insert(make_pair(to, from));
      }
    }
  }
  int cnt = CountEdge(g);
  while (cnt < m) {
    int f = rnd.next(n);
    int t = rnd.next(n);
    if (f == t ||
        (!EXIST_TWICE_EDGE && used.count(make_pair(f, t)))) { continue; }
    AddEdge(g, f, t, 0);
    used.insert(make_pair(f, t));
    if (!UNIDIRECT) {
      used.insert(make_pair(t, f));
    }
    cnt++;
  }
  return g;
}

Graph ConnectedRandomGraph(int n, int m) {
  assert(n - 1 <= m && m <= MaxEdge(n));
  Graph g = RandomTree(n);
  return AddRandomEdge(g, m);
}

// No Checked
// O(m * n^0.5) if use Dinic
// it may have k vertex less than n
Graph DestroyDinicGraph(int n) {
  Matrix m(n, Array(n, 0));
  vector<int> level(n, -1);
  Edges target;
  Graph g(2);
  int cnt = 2;
  int last = 0;
  FOR(i, 1, n) {
    if (cnt + i > n) { break; }
    Graph ng = CompleteGraph(i);
    //Graph ng = NoEdge(i);
    g = Merge(g, ng);
    AddEdge(g, cnt, 1, 0);
    REP(j, i) {
      REP(k, i - 1) {
        AddEdge(g, cnt + j, cnt - 1 - k, 0);
      }
    }
    last = i;
    cnt += i;
  }
  REP(i, last) {
    AddEdge(g, 0, cnt - 1 - i, 0);
  }
  return g;
}

// library is end
//*****************************************************************

//=================================================================
// SetBaseVectorWeight
//=================================================================
bool Push(ll v, vector<ll> &base) {
  int first = -1;
  for (int i = 60; i >= 0; i--) {
    if (v & (1LL << i)) {
      v ^= base[i];
      if (v & (1LL << i)) { first = max(first, i); }
    }
  }
  assert(first != -1 || v == 0);
  if (first != -1) { base[first] = v; return true; }
  return false;
}

// be careful about Stack Over flow
int visit[100010];
ll dist[100010];
void SetWeightDfs(Graph &g, int from, int parent, ll cost, vector<ll> &candidate) {
  visit[from] = 1;
  dist[from] = cost;
  FORIT(it, g[from]) {
    int to = it->dest;
    if (to == parent) { it->weight = -1; continue; }
    if (visit[to] == 2) {
      it->weight = -1;
      continue;
    } else if (visit[to] == 1) {
      ll v = dist[from] ^ dist[to];
      FORIT(it2, candidate) {
        if (rnd.next(0.0, 1.0) < 0.5) { v ^= *it2; }
      }
      it->weight = v;
      continue;
    } else {
      it->weight = rnd.next(0LL, (1LL << 60) - 1);
    }
    SetWeightDfs(g, to, from, cost ^ it->weight, candidate);
  }
  visit[from] = 2;
}
Graph SetBaseVectorWeight(Graph g) {
  assert(Connected(g));
  const int n = g.size();
  int cnts[8] = { 0, 1, rnd.next(2, 8), rnd.next(9, 20), rnd.next(21, 40), rnd.next(41, 57), 58, 59 };
  int baseCnt = cnts[rnd.next(0, 7)];
  vector<ll> candidate;
  if (baseCnt == 0) { candidate.push_back(0); }
  else {
    vector<ll> base(70, 0);
    REP(i, baseCnt) {
      ll v = rnd.next(0LL, (1LL << 60) - 1);
      if (!Push(v, base)) { i--; continue; }
      candidate.push_back(v);
    }
  }
  MEMSET(visit, 0);
  MEMSET(dist, 0);
  SetWeightDfs(g, 0, 0, 0, candidate);
  map<pair<int, int>, ll> ws;
  REP(f, n) {
    FORIT(it, g[f]) {
      int t = it->dest;
      if (it->weight != -1) {
        ws[make_pair(f, t)] = it->weight;
        ws[make_pair(t, f)] = it->weight;
      }
    }
  }
  REP(f, n) {
    FORIT(it, g[f]) {
      int t = it->dest;
      if (it->weight == -1) {
        it->weight = ws[make_pair(f, t)];
      }
    }
  }
  return g;
}

//=================================================================
// Util2
//=================================================================
const int MAX_QUERY = 100000;
void Output(int number, string name, int index, const Graph &g, const vector<pair<int, int> > query) {
  assert(Connected(g));
  char filename[1000];
  const int n = g.size();
  const int m = CountEdge(g);
  snprintf(filename, 999, "%1d_%02d_%s_%02d_%06d_%06d.in", m <= 20 ? 0 : 1, number, name.c_str(), index, n, m);
  FILE *fp = fopen(filename, "w");
  assert(fp != NULL);
  OutputGraph(fp, g, query.size());
  FORIT(it, query) {
    fprintf(fp, "%d %d\n", mapto[it->first], mapto[it->second]);
  }
  fclose(fp);
}

vector<pair<int, int> > RandomQuery(int n, bool full = false) {
  int q = max(100, n);
  if (full) { q = MAX_QUERY; }
  vector<pair<int, int> > ret;
  REP(i, q) {
    ret.push_back(make_pair(rnd.next(n), rnd.next(n)));
  }
  return ret;
}


//=================================================================
// Main Generator
//=================================================================
void PerfectRandom(int n, int index) {
  Graph g = ConnectedRandomGraph(n, rnd.next(n - 1LL, min(MaxEdge(n), 200000LL)));
  g = SetRandomWeight(g, 0, rnd.next(0LL, (1LL << 16) - 1));
  Output(10, "PerfectRandom", index, g, RandomQuery(n));
}

void Tree(int n, int index) {
  P = rnd.next(0.0, 1.0);
  typedef Graph TreeGenerator(int n);
  TreeGenerator *gens[5] = { LineGraph, StarGraph, BinaryTree, RandomTree, SkewTree };
  string strs[5] = { "Line", "Star", "BinaryTree", "RandomTree", "SkewTree" };
  int r = rnd.next(0, 4);
  Graph g = gens[r](n);
  g = SetRandomWeight(g, 0, (1LL << 60) - 1);
  Output(20 + r, strs[r], index, g, RandomQuery(n));
}
void Ring(int n, int index) {
  Graph g = RingGraph(n);
  g = SetBaseVectorWeight(g);
  Output(25, "Ring", index, g, RandomQuery(n));
}
void Complete(int n, int index) {
  assert(MaxEdge(n) <= 200000);
  Graph g = CompleteGraph(n);
  g = SetBaseVectorWeight(g);
  Output(26, "Complete", index, g, RandomQuery(n));
}
void Random(int n, int index) {
  Graph g = ConnectedRandomGraph(n, rnd.next(n - 1LL, min(MaxEdge(n), 200000LL)));
  g = SetBaseVectorWeight(g);
  Output(27, "Random", index, g, RandomQuery(n));
}

void Island(int n, int index) {
  int cnt[4] = { rnd.next(2, 5), rnd.next(6, 100), rnd.next(101, 1000) };
  int d = 20000;
  if (n == 1) { d = 1; }
  else if (n < 5) { d = 2; }
  while (d > n) {
    d = cnt[rnd.next(0, 4)];
  }
  set<int> ds;
  ds.insert(n);
  REP(i, d - 1) {
    int r = rnd.next(n) + 1;
    if (ds.count(r)) { i--; continue; }
    ds.insert(r);
  }
  vector<Graph> gs;
  int prev = 0;
  FORIT(it, ds) {
    P = rnd.next(0.0, 1.0);
    int ln = *it - prev;
    int r = rnd.next(8);
    Graph g(ln);
    if (ln != 1) {
      if (r == 7) {
        while (!Connected(g)) {
          g = ConnectedRandomGraph(ln, rnd.next(ln - 1LL, min(MaxEdge(ln), max(ln - 1LL, 20000LL))));
        }
      } else {
        typedef Graph GraphGenerator(int n);
        GraphGenerator *gens[7] = { LineGraph, StarGraph, BinaryTree, RandomTree, SkewTree, RingGraph, CompleteGraph };
        if (MaxEdge(ln) > 10000 && r == 6) { r = 5; }
        if (ln == 2 && r == 5) { r = 0; }
        g = gens[r](ln);
      }
    }
    //OutputGraph(stderr, g, false, false);
    gs.push_back(g);
    prev = *it;
  }
  Graph g = Merge(gs);
  gs.clear();
  assert((int)g.size() == n);
  while (!Connected(g) || CountEdge(g) > 200000) {
    g = EraseEdge(g, min(CountEdge(g), 150000));
    UnionFind ufind;
    int cnt = 1;
    REP(i, n) {
      FORIT(it, g[i]) {
        if (ufind.unionSet(i, it->dest)) { cnt++; }
      }
    }
    while (cnt != n) {
      int f = rnd.next(n);
      int t = rnd.next(n);
      if (!ufind.unionSet(f, t)) { continue; }
      AddEdge(g, f, t, 0);
      cnt++;
    }
  }
  g = SetBaseVectorWeight(g);
  Output(30, "Island", index, g, RandomQuery(n));
}

void SmallCorner() {
  int m = 20;
  {
    Graph g = ConnectedRandomGraph(10, m);
    g = SetBaseVectorWeight(g);
    vector<pair<int, int> > query = RandomQuery(g.size(), true);
    Output(40, "Corner", 0, g, query);
  }
  {
    Graph g = LineGraph(21);
    g = SetBaseVectorWeight(g);
    vector<pair<int, int> > query = RandomQuery(g.size(), true);
    Output(40, "Corner", 1, g, query);
  }
}

//=================================================================
// main
//=================================================================
int main(int argc, char* argv[]) {
  registerGen(argc, argv);

  SmallCorner();
  Ring(3, 0);
  Ring(20, 1);
  Ring(1000, 2);
  Ring(100000, 3);

  Complete(4, 0);
  Complete(5, 1);
  Complete(67, 2);
  Complete(500, 3);

  int index = 0;
  REP(iter, 4) {
    PerfectRandom(2 + iter * 3 + rnd.next(0, 2), index);
    Tree(2 + iter * 3 + rnd.next(0, 2), index);
    Random(2 + iter * 3 + rnd.next(0, 2), index);
    Island(2 + iter * 3 + rnd.next(0, 2), index);
    index++;
  }

  REP(iter, 2) {
    PerfectRandom(rnd.next(10, 100), index);
    Tree(rnd.next(10, 100), index);
    Random(rnd.next(10, 100), index);
    Island(rnd.next(10, 100), index);
    index++;
  }
  REP(iter, 2) {
    PerfectRandom(rnd.next(100, 1000), index);
    Tree(rnd.next(100, 1000), index);
    Random(rnd.next(100, 1000), index);
    Island(rnd.next(100, 1000), index);
    index++;
  }
  REP(iter, 2) {
    PerfectRandom(rnd.next(1000, 10000), index);
    Tree(rnd.next(1000, 10000), index);
    Random(rnd.next(1000, 10000), index);
    Island(rnd.next(1000, 10000), index);
    index++;
  }
  REP(iter, 2) {
    PerfectRandom(rnd.next(10000, 100000), index);
    Tree(rnd.next(10000, 100000), index);
    Random(rnd.next(10000, 100000), index);
    Island(rnd.next(10000, 100000), index);
    index++;
  }
  REP(iter, 3) {
    Island(rnd.next(99990, 100000), index);
    index++;
  }
}