graph.cc

C语言前端编译器,yacc/lex编写,可自行修改代码.

// Copyright 2000 by Robert Dick.
// All rights reserved.

#include "Graph.h"

#include <functional>
#include <algorithm>
#include <typeinfo>
#include <iostream>

/*###########################################################################*/
RawGraph &
RawGraph::operator=(const self & a) {
	vertex_ = a.vertex_;
	edge_ = a.edge_;
	return *this;
}


/*===========================================================================*/
RawGraph::vertex_index RawGraph::add_vertex() {
	vertex_type new_vertex;
	vertex_.push_back(new_vertex);

	RDEBUG(self_check());
	return vertex_.size() - 1;
}

/*===========================================================================*/
RawGraph::edge_index RawGraph::
add_edge(const vertex_index from, const vertex_index to) {
	edge_.push_back(edge_type(from, to));

	edge_index e = edge_.size() - 1;
	vertex(to)->in_.push_back(e);
	vertex(from)->out_.push_back(e);

	RDEBUG(self_check());
	return e;
}

/*===========================================================================*/
void RawGraph::erase_vertex(const vertex_index i) {
// Erase all of the connected edges.
	vertex_iterator v = vertex(i);

	while (! v->in_.empty()) {
		erase_edge(v->in_.back());
	}

	while (! v->out_.empty()) {
		erase_edge(v->out_.back());
	}

// Erase the vertex.
	vertex_.erase(v);

// Fix all of the other vertex indices.
	MAP(x, edge_.size()) {
		vertex_index & to = edge_[x].to_;
		vertex_index & from = edge_[x].from_;

		if (to > i) {
			--to;
		}

		if (from > i) {
			--from;
		}
	}
	RDEBUG(self_check());
}

/*===========================================================================*/
void RawGraph::erase_edge(const edge_index i) {
// Fix connected vertices.
	vertex_type & parent = *vertex(edge(i)->from());
	vertex_type & child = *vertex(edge(i)->to());

	edge_index * parent_edge = find(parent.out_.begin(), parent.out_.end(), i);
	edge_index * child_edge = find(child.in_.begin(), child.in_.end(), i);

	parent.out_.erase(parent_edge);
	child.in_.erase(child_edge);

// Erase the edge.
	edge_.erase(edge(i));

// Fix all the other edge indices.
	MAP(x, vertex_.size()) {
		RVector<edge_index> & out = vertex_[x].out_;
		MAP(y, out.size()) {
			RASSERT(out[y] != i);
			if (out[y] > i) {
				--out[y];
			}
		}

		RVector<edge_index> & in = vertex_[x].in_;
		MAP(y, in.size()) {
			RASSERT(in[y] != i);
			if (in[y] > i) {
				--in[y];
			}
		}
	}
	RDEBUG(self_check());
}

/*===========================================================================*/
void RawGraph::pack_memory() {
	RVector<vertex_type> v(vertex_);
	RVector<edge_type> e(edge_);
	vertex_.rswap(v);
	edge_.rswap(e);
}

/*===========================================================================*/
void RawGraph::clear() {
	vertex_.clear();
	edge_.clear();
	RDEBUG(self_check());
}

/*===========================================================================*/
void RawGraph::rswap(RawGraph & rg) {
	vertex_.rswap(rg.vertex_);
	edge_.rswap(rg.edge_);
	RDEBUG(self_check());
	RDEBUG(rg.self_check());
}

/*===========================================================================*/
void RawGraph::print_to(ostream & os) const {
	MAP(x, vertex_.size()) {
		os << "vertex " << x;
		vertex_[x].print_to(os);
		os << "\n";
	}

	MAP(x, edge_.size()) {
		os << "edge " << x;
		edge_[x].print_to(os);
		os << "\n";
	}
}

/*===========================================================================*/
bool RawGraph::cyclic() const {
	MAP(start, vertex_.size()) {
		RVector<big_bool> visited(vertex_.size(), false);
		if (cyclic_recurse(visited, start, start))
			return true;
	}
	return false;
}

/*===========================================================================*/
bool RawGraph::
connected(const vertex_index start, bool reverse_i) const {
	RVector<vertex_index> vec = dfs(start, reverse_i);
	return vec.size() == vertex_.size();
}

/*===========================================================================*/
bool RawGraph::
nodes_linked (vertex_index a, vertex_index b) const {
	MAP (x, vertex(a)->size_out()) {
		if (edge(vertex(a)->out(x))->to() == b) {
			return true;
		}
	}
	MAP (x, vertex(b)->size_out()) {
		if (edge(vertex(b)->out(x))->to() == a) {
			return true;
		}
	}
	return false;
}

/*===========================================================================*/
const RVector<RawGraph::vertex_index> RawGraph::
dfs(const vertex_index start, bool reverse_i) const {
	RVector<vertex_index> vec;
	RVector<big_bool> visited(vertex_.size(), false);
	dfs_recurse(vec, visited, start, reverse_i);
	return vec;
}

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

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

	return vec;
}

/*===========================================================================*/
const RVector<RawGraph::vertex_index>
RawGraph::bfs(const vertex_index start, bool reverse_i) const {
	RVector<vertex_index> vec;
	RVector<big_bool> visited(vertex_.size(), false);
	bfs_recurse(vec, visited, start, reverse_i);
	return vec;
}

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

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

	return vec;
}

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

// For now, allow only source or sink start nodes.
	RASSERT(reverse_i && ! vertex_[start].size_out() ||
		! reverse_i && ! vertex_[start].size_in());

// Figure out which nodes can be reached.
	dfs_recurse(vec, visited, start, 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());

	top_sort_recurse(vec, visited, start, reverse_i);
	return vec;
}

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

// Figure out which nodes can be reached.
	MAP(x, start.size()) {
// For now, allow only source or sink start nodes.
		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);
	outward_crawl_recurse(vec, visited, start);
	return vec;
}

/*===========================================================================*/
const RVector<int>
RawGraph::max_depth(const vertex_index start, bool reverse_i) const {
// Warning: This method has not been well-tested.
Rabort();

	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());