Created
January 30, 2012 20:06
-
-
Save IlyaKornakov/1706363 to your computer and use it in GitHub Desktop.
Tarjan Subtree Decomposition
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#ifndef GRAPH_H_ | |
#define GRAPH_H_ | |
#include <algorithm> | |
#include <cstdio> | |
#include <string> | |
#include <stdexcept> | |
namespace sp { | |
class Graph { | |
public: | |
struct Arc { | |
int head; | |
int weight; | |
}; | |
Graph() { | |
arcs = 0; | |
firstArcs = 0; | |
} | |
~Graph() { | |
if (arcs) { | |
delete[] arcs; | |
} | |
if (firstArcs) { | |
delete[] firstArcs; | |
} | |
} | |
void load(const std::string &fileName) { | |
FILE *f = fopen(fileName.c_str(), "r"); | |
if (f == NULL) { | |
throw std::runtime_error("can't open the input file"); | |
} | |
if (fscanf(f, "%d%d", &numNodes, &numArcs) != 2) { | |
throw std::runtime_error("can't read numNodes or numArcs"); | |
} | |
if (numNodes <= 0) { | |
throw std::runtime_error("numNodes <= 0"); | |
} | |
if (numArcs < 0) { | |
throw std::runtime_error("numArcs < 0"); | |
} | |
InternalArc *readArcs = new InternalArc[numArcs]; | |
for (int i = 0; i < numArcs; ++i) { | |
if (fscanf(f, "%d%d%d", &readArcs[i].tail, &readArcs[i].head, &readArcs[i].weight) != 3) { | |
throw std::runtime_error("can't read tail, head or weight"); | |
} | |
if (readArcs[i].tail < 0 || readArcs[i].tail >= numNodes) { | |
throw std::runtime_error("invalid tail"); | |
} | |
if (readArcs[i].head < 0 || readArcs[i].head >= numNodes) { | |
throw std::runtime_error("invalid head"); | |
} | |
} | |
std::sort(readArcs, readArcs + numArcs); | |
firstArcs = new Arc*[numNodes + 1]; | |
arcs = new Arc[numArcs]; | |
for (int i = 0; i < numArcs; ++i) { | |
arcs[i].head = readArcs[i].head; | |
arcs[i].weight = readArcs[i].weight; | |
} | |
int curArc = 0; | |
for (int i = 0; i < numNodes; ++i) { | |
firstArcs[i] = &arcs[curArc]; | |
while (curArc < numArcs && readArcs[curArc].tail == i) { | |
curArc++; | |
} | |
} | |
firstArcs[numNodes] = &arcs[curArc]; | |
delete[] readArcs; | |
if (fclose(f) == EOF) { | |
throw std::runtime_error("can't close the input file"); | |
} | |
} | |
inline int getNumNodes() const { | |
return numNodes; | |
} | |
inline std::pair<Arc*, Arc*> getOutgoingArcs(int node) { | |
return std::make_pair(firstArcs[node], firstArcs[node + 1]); | |
} | |
private: | |
struct InternalArc { | |
int tail; | |
int head; | |
int weight; | |
bool operator<(const InternalArc &he) const { | |
return std::make_pair(tail, head) < std::make_pair(he.tail, he.head); | |
} | |
}; | |
int numNodes; | |
int numArcs; | |
Arc *arcs; | |
Arc **firstArcs; | |
}; | |
} | |
#endif |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include "graph.h" | |
#include <cassert> | |
#include <limits> | |
#include <utility> | |
int main() { | |
sp::Graph g; | |
g.load("input.txt"); | |
int time1 = clock(); | |
int n = g.getNumNodes(); | |
long long *d = new long long[n]; | |
for (int i = 0; i < n; ++i) { | |
d[i] = std::numeric_limits<long long>::max(); | |
} | |
int *next = new int[n]; | |
int *prev = new int[n]; | |
int *degree = new int[n]; | |
int *q = new int[n + 1]; | |
int *type = new int[n]; | |
for (int i = 0; i < n; ++i) { | |
type[i] = 0; | |
} | |
int *p = new int[n]; | |
for (int i = 0; i < n; ++i) { | |
p[i] = -1; | |
} | |
int ql = 0, qr = 0; | |
d[0] = 0; | |
next[0] = prev[0] = 0; | |
degree[0] = 0; | |
q[qr++] = 0; | |
type[0] = 1; | |
int nodesScanned = 0; | |
int arcsScanned = 0; | |
int arcsRelaxed = 0; | |
int curQueueSize = 1; | |
int maxQueueSize = 1; | |
while (ql != qr) { | |
int curNode = q[ql++]; | |
if (ql == n + 1) ql = 0; | |
curQueueSize--; | |
if (type[curNode] == 0) continue; | |
nodesScanned++; | |
std::pair<sp::Graph::Arc*, sp::Graph::Arc*> its = g.getOutgoingArcs(curNode); | |
for (sp::Graph::Arc* a = its.first; a != its.second; ++a) { | |
arcsScanned++; | |
int he = a->head; | |
if (d[curNode] + a->weight >= d[he]) continue; | |
arcsRelaxed++; | |
long long delta = d[he] - d[curNode] - a->weight; | |
d[he] = d[curNode] + a->weight; | |
if (type[he] != 1) { | |
q[qr++] = he; | |
if (qr == n + 1) qr = 0; | |
curQueueSize++; | |
if (curQueueSize > maxQueueSize) { | |
maxQueueSize = curQueueSize; | |
} | |
} | |
if (type[he] != 0) { | |
int curSubtreeNode = next[he]; | |
int score = degree[he]; | |
while (score != 0) { | |
type[curSubtreeNode] = 0; | |
d[curSubtreeNode] -= delta - 1; | |
score--; | |
score += degree[curSubtreeNode]; | |
curSubtreeNode = next[curSubtreeNode]; | |
} | |
next[prev[he]] = curSubtreeNode; | |
prev[curSubtreeNode] = prev[he]; | |
if (p[he] != -1) degree[p[he]]--; | |
} | |
prev[he] = curNode; | |
next[he] = next[curNode]; | |
prev[next[he]] = he; | |
next[prev[he]] = he; | |
degree[he] = 0; | |
degree[curNode]++; | |
type[he] = 1; | |
p[he] = curNode; | |
} | |
type[curNode] = 2; | |
} | |
printf("%.3lf\n", (clock() - time1 + 0.0) / (CLOCKS_PER_SEC + 0.0)); | |
for (int i = 0; i < n; ++i) { | |
std::pair<sp::Graph::Arc*, sp::Graph::Arc*> its = g.getOutgoingArcs(i); | |
for (sp::Graph::Arc* a = its.first; a != its.second; ++a) { | |
if (a->weight + d[i] - d[a->head] < 0) { | |
throw std::runtime_error("invalid distances"); | |
} | |
if (p[a->head] == i && a->weight + d[i] - d[a->head] != 0) { | |
throw std::runtime_error("tree edge with non-zero reduced cost"); | |
} | |
} | |
} | |
for (int i = 0; i < n; ++i) { | |
if (p[i] == -1 && i) { | |
throw std::runtime_error("p[v] == null and v != s"); | |
} | |
} | |
delete[] type; | |
delete[] q; | |
delete[] d; | |
delete[] next; | |
delete[] prev; | |
delete[] degree; | |
printf("nodesScanned = %d\n", nodesScanned); | |
printf("arcsScanned = %d\n", arcsScanned); | |
printf("arcsRelaxed = %d\n", arcsRelaxed); | |
printf("maxQueueSize = %d\n", maxQueueSize); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment