graph.cc

TGFF省城程序

		RASSERT(reverse_i && ! vertex_[start[x]].size_out() ||
			! reverse_i && ! vertex_[start[x]].size_in());

		dfs_recurse(vec, visited, start[x], reverse_i);
	}

// Invert to pre-visit nodes which can't be reached.
	transform(visited.begin(), visited.end(), visited.begin(),
	  logical_not<big_bool>());
	vec.erase(vec.begin(), vec.end());

	MAP(x, start.size())
		top_sort_recurse(vec, visited, start[x], reverse_i);

	return vec;
}

/*===========================================================================*/
const RVector<RawGraph::vertex_index> RawGraph::
RawGraph::outward_crawl(const vertex_index start) const {
	RVector<vertex_index> vec;
	RVector<big_bool> visited(vertex_.size(), false);
	visited[start] = true;
	outward_crawl_recurse(vec, visited, start);
	return vec;
}

/*===========================================================================*/
const RVector<int>
RawGraph::max_depth(const vertex_index start, bool reverse_i) const {
	RVector<int> vec(vertex_.size(), -1);
	RVector<big_bool> visited(vertex_.size(), false);

// Figure out which nodes can be reached.
	RVector<vertex_index> scratch;
	dfs_recurse(scratch, visited, start, reverse_i);
	scratch.erase(scratch.begin(), scratch.end());

// Invert to pre-visit nodes which can't be reached.
	transform(visited.begin(), visited.end(), visited.begin(),
	  logical_not<big_bool>());

	vec[start] = 0;
	max_depth_recurse(vec, visited, start, reverse_i);
	return vec;
}

/*===========================================================================*/
const RVector<int>
RawGraph::max_depth(const RVector<vertex_index> & start,
bool reverse_i) const {
	RVector<int> vec(vertex_.size(), -1);
	RVector<big_bool> visited(vertex_.size(), false);

	RVector<vertex_index> scratch;

	MAP(x, start.size())
		dfs_recurse(scratch, visited, start[x], reverse_i);

	scratch.erase(scratch.begin(), scratch.end());

	transform(visited.begin(), visited.end(), visited.begin(),
	  logical_not<big_bool>());

	MAP(x, start.size()) {
		vec[start[x]] = 0;
		max_depth_recurse(vec, visited, start[x], reverse_i);
	}

	return vec;
}

/*===========================================================================*/
void RawGraph::self_check() const {
	MAP(x, vertex_.size()) {
		Rassert(vertex_offset(vertex_.begin() + x) < size_vertex());
	}

	MAP(x, edge_.size()) {
		Rassert(edge_[x].to_ < size_vertex());
		Rassert(edge_[x].from_ < size_vertex());
	}

	MAP(x, vertex_.size()) {
		MAP(y, vertex_[x].out_.size()) {
			Rassert(vertex_[x].out_[y] < size_edge());
		}

		MAP(y, vertex_[x].in_.size()) {
			Rassert(vertex_[x].in_[y] < size_edge());
		}
	}
}

/*===========================================================================*/
bool RawGraph::cyclic_recurse(RVector<big_bool> & visited,
const vertex_index start, const vertex_index branch) const {
	visited[branch] = true;
	MAP(x, vertex(branch)->out_.size()) {
		vertex_index to_vertex = edge(vertex(branch)->out_[x])->to_;

		if (to_vertex == start)
			return true;

		if (! visited[to_vertex])
			if (cyclic_recurse(visited, start, to_vertex))
				return true;
	}
	return false;
}

/*===========================================================================*/
void RawGraph::dfs_recurse(RVector<vertex_index> & vec,
RVector<big_bool> & visited, const vertex_index branch,
bool reverse_i) const {
	visited[branch] = true;
	vec.push_back(branch);

	if (reverse_i) {
		MAP(x, vertex(branch)->in_.size()) {
			vertex_index next_index = edge(vertex(branch)->in_[x])->from_;
			if (! visited[next_index]) {
				dfs_recurse(vec, visited, next_index, reverse_i);
			}
		}
	} else {
		MAP(x, vertex(branch)->out_.size()) {
			vertex_index next_index = edge(vertex(branch)->out_[x])->to_;
			if (! visited[next_index]) {
				dfs_recurse(vec, visited, next_index, reverse_i);
			}
		}
	}
}

/*===========================================================================*/
void RawGraph::bfs_recurse(RVector<vertex_index> & vec,
RVector<big_bool> & visited, const vertex_index branch,
bool reverse_i) const {
	RVector<vertex_index> stack;

	if (reverse_i) {
		MAP(x, vertex(branch)->in_.size()) {
			vertex_index next_index = edge(vertex(branch)->in_[x])->from_;

			if (! visited[next_index]){
				visited[next_index] = true;
				vec.push_back(next_index);
				stack.push_back(next_index);
			}
		}
	} else {
		MAP(x, vertex(branch)->out_.size()) {
			vertex_index next_index = edge(vertex(branch)->out_[x])->to_;

			if (! visited[next_index]){
				visited[next_index] = true;
				vec.push_back(next_index);
				stack.push_back(next_index);
			}
		}
	}

	MAP(x, stack.size()) {
		bfs_recurse(vec, visited, stack[x], reverse_i);
	}
}

/*===========================================================================*/
void RawGraph::top_sort_recurse(RVector<vertex_index> & vec,
RVector<big_bool> & visited, const vertex_index branch,
bool reverse_i) const {
// If any of the parents haven't been visited yet, stop exploring this path.
	if (reverse_i) {
		MAP(x, vertex(branch)->out_.size())
			if (! visited[edge(vertex(branch)->out_[x])->to_])
				return;
	} else {
		MAP(x, vertex(branch)->in_.size())
			if (! visited[edge(vertex(branch)->in_[x])->from_])
				return;
	}

	visited[branch] = true;
	vec.push_back(branch);

	if (reverse_i) {
		MAP(x, vertex(branch)->in_.size()) {
			vertex_index next_index = edge(vertex(branch)->in_[x])->from_;
			if (! visited[next_index])
				top_sort_recurse(vec, visited, next_index, reverse_i);
		}
	} else {
		MAP(x, vertex(branch)->out_.size()) {
			vertex_index next_index = edge(vertex(branch)->out_[x])->to_;
			if (! visited[next_index])
				top_sort_recurse(vec, visited, next_index, reverse_i);
		}
	}
}

/*===========================================================================*/
void RawGraph::outward_crawl_recurse(RVector<vertex_index> & vec,
RVector<big_bool> & visited, vertex_index branch) const {
	RVector<vertex_index> stack;

	MAP(x, vertex(branch)->in_.size()) {
		vertex_index next_index = edge(vertex(branch)->in_[x])->from_;

		if (! visited[next_index]){
			visited[next_index] = true;
			vec.push_back(next_index);
			stack.push_back(next_index);
		}
	}

	MAP(x, vertex(branch)->out_.size()) {
		vertex_index next_index = edge(vertex(branch)->out_[x])->to_;

		if (! visited[next_index]){
			visited[next_index] = true;
			vec.push_back(next_index);
			stack.push_back(next_index);
		}
	}

	MAP(x, stack.size()) {
		outward_crawl_recurse(vec, visited, stack[x]);
	}
}

/*===========================================================================*/
void RawGraph::max_depth_recurse(RVector<int> & vec,
RVector<big_bool> & visited, const vertex_index branch,
bool reverse_i) const {
// If any of the parents haven't been visited yet, stop exploring this path.
	if (reverse_i) {
		MAP(x, vertex(branch)->out_.size())
			if (! visited[edge(vertex(branch)->out_[x])->to_])
				return;
	} else {
		MAP(x, vertex(branch)->in_.size())
			if (! visited[edge(vertex(branch)->in_[x])->from_])
				return;
	}

	visited[branch] = true;

	if (reverse_i) {
		MAP(x, vertex(branch)->in_.size()) {
			vertex_index next_index = edge(vertex(branch)->in_[x])->from_;
			vec[next_index] = max(vec[next_index], vec[branch] + 1);
			if (! visited[next_index])
				max_depth_recurse(vec, visited, next_index, reverse_i);
		}
	} else {
		MAP(x, vertex(branch)->out_.size()) {
			vertex_index next_index = edge(vertex(branch)->out_[x])->to_;
			vec[next_index] = max(vec[next_index], vec[branch] + 1);
			if (! visited[next_index])
				max_depth_recurse(vec, visited, next_index, reverse_i);
		}
	}
}

/*===========================================================================*/
void RawGraph::edge_type::print_to(ostream & os) const {
	os << " from vertex " << from_ << " to vertex " << to_;
}

/*===========================================================================*/
comp_type
RawGraph::edge_type::comp(const self & et) const {
	const comp_type fr = rstd::comp(from_, et.from_);
	return fr ? fr : rstd::comp(to_, et.to_);
}

/*===========================================================================*/
void RawGraph::vertex_type::print_to(ostream & os) const {
	os << "out edges: ";
	MAP(y, out_.size()) {
		os << out_[y] << " ";
	}

	os << "in edges: ";
	MAP(y, in_.size()) {
		os << in_[y] << " ";
	}
}

/*===========================================================================*/
comp_type
RawGraph::vertex_type::comp(const self & vt) const {
	const comp_type ot = comp_cont(out_, vt.out_);
	return ot ? ot : comp_cont(in_, vt.in_);
}

/*###########################################################################*/
double
WGraph::vertex_weight(vertex_index v) const {
	return (*this)[v];
}

/*===========================================================================*/
double
WGraph::edge_weight(edge_index e) const {
	return (*this)(e);
}

/*###########################################################################*/
void Graph_test() {
	Graph<int, int> g1;
	Graph<int, int> g2;

	g1.rswap(g2);

	typedef RawGraph::vertex_index vi;
	vi v0 = g1.add_vertex(0);
	vi v1 = g1.add_vertex(1);
	vi v2 = g1.add_vertex(2);
	vi v3 = g1.add_vertex(3);

	g1.add_edge(v0, v1, 0);
	g1.add_edge(v1, v2, 1);
	g1.add_edge(v0, v3, 2);

	RVector<RawGraph::vertex_index> dl;
	dl.push_back(v3);
	dl.push_back(v2);
	dl.push_back(v1);

	for (long x = dl.size() - 1; x >= 0; --x) {
		if (g1.vertex(dl[x])->size_out()) {
			dl.erase(dl.begin() + x);
		}
	}

	cout << g1 << "\n";

	RVector<RawGraph::vertex_index> rtsrt = g1.top_sort(dl, true);
	cout << "Graph: " << rtsrt << "\n";
	RASSERT(rtsrt.size() == g1.size_vertex());
}

}