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++; } }