graph.cc

TGFF省城程序

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

#include "Graph.h"

#include <functional>
#include <algorithm>
#include <typeinfo>
#include <iostream>
#include "Epsilon.h"

namespace rstd {
using namespace std;

const RawGraph::vertex_index RawGraph::INVALID_VINDEX = -1;
const RawGraph::edge_index RawGraph::INVALID_EINDEX = -1;

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

/*===========================================================================*/
comp_type
RawGraph::vertex_index::comp(const vertex_index & a) const {
	return rstd::comp(index_, a.index_);
}

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

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

/*===========================================================================*/
comp_type
RawGraph::edge_index::comp(const edge_index & a) const {
	return rstd::comp(index_, a.index_);
}

/*===========================================================================*/
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;
}

/*===========================================================================*/
double
RawGraph::vertex_weight(vertex_index /* v */) const {
	return 0.0;
}

/*===========================================================================*/
double
RawGraph::edge_weight(edge_index /* e */) const {
	return 1.0;
}

/*===========================================================================*/
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) {
	RASSERT(i < size_edge());
// Fix connected vertices.
	vertex_type & parent = *vertex(edge(i)->from());
	vertex_type & child = *vertex(edge(i)->to());

	RVector<edge_index>::iterator parent_edge =
		find(parent.out_.begin(), parent.out_.end(), i);

	RVector<edge_index>::iterator 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);
	visited[start] = true;
	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()) {
		visited[start[x]] = true;
		bfs_recurse(vec, visited, start[x], reverse_i);
	}

	return vec;
}

/*===========================================================================*/
const RVector<std::pair<RawGraph::vertex_index, double> >
RawGraph::shortest_path(vertex_index start) const {
Rabort();
	RVector<vertex_index> parent;
	RVector<double> distance;

// Initialize single source

	MAP(x, vertex_.size()) {
		parent.push_back(RawGraph::INVALID_VINDEX);

		if (x == start) {
			distance.push_back(0.0);
		} else {
			distance.push_back(numeric_limits<double>::max());
		}
	}

// relax
// recursively do this until no more changes
	bool distance_changed = true;
	while (distance_changed == true) {
		distance_changed = false;
		MAP(x, edge_.size()) {
			if (distance[edge_[x].to_] > distance[edge_[x].from_] +
				edge_weight(x))
			{
				distance[edge_[x].to_] = distance[edge_[x].from_] + edge_weight(x);
				parent[edge_[x].to_] = vertex_index(edge_[x].from_);
				distance_changed = true;
			}
		}

	}

// check for negative weight
	eps_equal_to<double, 10> eq;
	MAP(x, edge_.size()) {
//#warning THIS CODE IS WRONG
		RASSERT(eq(distance[edge_[x].to_], distance[edge_[x].from_] +
			edge_weight(x)));
	}

	RVector<std::pair<vertex_index, double> > shortestpath_result;

	MAP (x, parent.size()) {
		pair<vertex_index, double> result(parent[x], distance[x]);
		shortestpath_result.push_back(result);
	}

	return shortestpath_result;
}

/*===========================================================================*/
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.