graph.cpp

粗糙集应用软件

	return degree;

}

//-------------------------------------------------------------------
// Method........: GetInDegreeByValue
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

int
Graph::GetInDegreeByValue(int value) const {
	return GetInDegreeByIndex(GetNodeIndex(value));
}

//-------------------------------------------------------------------
// Method........: GetOutDegreeByIndex
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

int
Graph::GetOutDegreeByIndex(int index) const {

	int no_nodes = GetNoNodes();

	// Sanity check.
	if (index < 0 || index >= no_nodes)
		return 0;

	int to, degree = 0;

	// Compute out-degree.
	for (to = 0; to < no_nodes; to++) {
		if (GetEdgeByIndex(index, to))
			degree++;
	}

	return degree;

}

//-------------------------------------------------------------------
// Method........: GetOutDegreeByValue
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

int
Graph::GetOutDegreeByValue(int value) const {
	return GetOutDegreeByIndex(GetNodeIndex(value));
}

//-------------------------------------------------------------------
// Edge methods.
//===================================================================

//-------------------------------------------------------------------
// Method........: GetNoEdges
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

int
Graph::GetNoEdges() const {

	int i, j, no_nodes = GetNoNodes(), no_edges = 0;

	for (i = 0; i < no_nodes; i++) {
		for (j = 0; j < no_nodes; j++) {
			if (GetEdgeByIndex(i, j))
				no_edges++;
		}
	}

	return no_edges;

}

//-------------------------------------------------------------------
// Method........: MakeAdjacencyMatrix
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::MakeAdjacencyMatrix() {

	// Resize current matrix.
	matrix_.erase(matrix_.begin(), matrix_.end());

	int i, dimension = map_.size();

	// Avoid spurious allocations.
	matrix_.reserve(dimension);

	Bits bits(dimension, false);

	// Build matrix.
	for (i = 0; i < dimension; i++)
		matrix_.push_back(bits);

	return true;

}

//-------------------------------------------------------------------
// Method........: GetEdgeByIndex
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::GetEdgeByIndex(int index_from, int index_to) const {

#ifdef _DEBUG
	if (index_from < 0 || index_from >= matrix_.size()) {
		Message::Error("Illegal source node index (" + String::Format(index_from) + ") passed to graph " + GetName() + ".");
		return false;
	}

	if (index_to < 0 || index_to >= matrix_[index_from].GetSize()) {
		Message::Error("Illegal destination node index (" + String::Format(index_to) + ") passed to graph " + GetName() + ".");
		return false;
	}
#endif

	return matrix_[index_from][index_to];

}

//-------------------------------------------------------------------
// Method........: SetEdgeByIndex
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::SetEdgeByIndex(int index_from, int index_to, bool flag) {

#ifdef _DEBUG
	if (index_from < 0 || index_from >= matrix_.size()) {
		Message::Error("Illegal source node index (" + String::Format(index_from) + ") passed to graph " + GetName() + ".");
		return false;
	}

	if (index_to < 0 || index_to >= matrix_[index_from].GetSize()) {
		Message::Error("Illegal destination node index (" + String::Format(index_to) + ") passed to graph " + GetName() + ".");
		return false;
	}
#endif

	// Update matrix.
	matrix_[index_from][index_to] = flag;

	return true;

}

//-------------------------------------------------------------------
// Method........: GetEdgeByValue
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::GetEdgeByValue(int value_from, int value_to) const {

	int index_from = GetNodeIndex(value_from);

	if (value_from == value_to)
		return GetEdgeByIndex(index_from, index_from);
	else
		return GetEdgeByIndex(index_from, GetNodeIndex(value_to));

}

//-------------------------------------------------------------------
// Method........: SetEdgeByValue
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::SetEdgeByValue(int value_from, int value_to, bool flag) {

	int index_from = GetNodeIndex(value_from);

	if (value_from == value_to)
		return SetEdgeByIndex(index_from, index_from, flag);
	else
		return SetEdgeByIndex(index_from, GetNodeIndex(value_to), flag);

}

//-------------------------------------------------------------------
// Method........: MakeReflexive
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Adds a "loop edge" to each vertex.
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::MakeReflexive() {

	int i;

	for (i = GetNoNodes() - 1; i >= 0; i--)
		SetEdgeByIndex(i, i, true);

	return true;

}

//-------------------------------------------------------------------
// Method........: MakeSymmetric
// Author........: Aleksander 豩rn
// Date..........:
// Description...: For each directed edge, adds an edge in the other
//                 direction.
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::MakeSymmetric() {

	int i, j, no_nodes = GetNoNodes();

	for (i = 1; i < no_nodes; i++) {
		for (j = 0; j < i; j++) {
			if (GetEdgeByIndex(i, j))
				SetEdgeByIndex(j, i, true);
			else if (GetEdgeByIndex(j, i))
				SetEdgeByIndex(i, j, true);
		}
	}

	return true;

}

//-------------------------------------------------------------------
// Method........: MakeTransitive
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Computes the transitive closure.
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::MakeTransitive() {
	return Warshall();
}

//-------------------------------------------------------------------
// Method........: MakeComplement
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Inverts the adjacency matrix.
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::MakeComplement() {

	int i;

	for (i = 0; i < matrix_.size(); i++)
		matrix_[i].Invert();

	return true;

}

//-------------------------------------------------------------------
// Method........: MakeDistance
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Looks up the value at each node. Adds an edge
//                 between two nodes if their values are "close
//                 enough". Existing edges are left alone.
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::MakeDistance(int radius) {

	int i, j, no_nodes = GetNoNodes();

	for (i = 1; i < no_nodes; i++) {

		// Get value at node i.
		int value_i = GetNodeValue(i);

		// Skip it if it's the magic "missing value" node.
		if (value_i == Undefined::Integer())
			continue;

		for (j = 0; j <= i; j++) {

			// Get value at node j.
			int value_j  = GetNodeValue(j);

			// Skip it if it's the magic "missing value" node.
			if (value_j == Undefined::Integer())
				continue;

			// Compute absolute distance.
			int distance = value_i - value_j;
			if (distance < 0)
				distance = -distance;

			// Add an (i, j) edge if the distance is small enough.
			if (distance <= radius) {
				SetEdgeByIndex(i, j, true);
				SetEdgeByIndex(j, i, true);
			}

		}
	}

	return true;

}

//-------------------------------------------------------------------
// Misc. algorithms.
//===================================================================

//-------------------------------------------------------------------
// Method........: Warshall
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Transitive closure by Warshall's algorithm.
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::Warshall() {

	int i, j, k, no_nodes = GetNoNodes();

  for (k = 0; k < no_nodes; k++) {
    for (i = 0; i < no_nodes; i++) {
      for (j = 0; j < no_nodes; j++) {
        if (!GetEdgeByIndex(i, j))
					SetEdgeByIndex(i, j, GetEdgeByIndex(i, k) && GetEdgeByIndex(k, j));
			}
		}
	}

	return true;

}

//-------------------------------------------------------------------
// Method........: Dijkstra
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Returns (in-place) the length of the shortest path
//                 from one node to every other node, computed by
//                 Dijkstra's algorithm.
//
// Comments......: Current implementation uses unit costs/distances.
//                 Could take advantage of symmetry, if present.
// Revisions.....:
//===================================================================

bool
Graph::Dijkstra(int index, SPVector &distances) const {

	int i, j, k, no_nodes = GetNoNodes();

	// Sanity check.
	if (index < 0 || index >= no_nodes)
		return false;

	// Define a value for "infinite distance".
	const SPDistance d_infinite = Undefined::Integer();

	// Resize and initialize SP vector.
	distances.erase(distances.begin(), distances.end());
	distances.reserve(no_nodes);

	for (i = 0; i < no_nodes; i++) {
		distances.push_back(d_infinite);
		if (GetEdgeByIndex(index, i))
			distances[i] = 1;
	}

	distances[index] = 0;

	// Initialize working structures.
	Vector(int) S; S.reserve(no_nodes);
	Vector(int) R; R.reserve(no_nodes);

	for (i = 0; i < no_nodes; i++) {
		if (i == index)
			S.push_back(i);
		else
			R.push_back(i);
	}

	// Do greedy algorithm.
	while (!R.empty()) {

		SPDistance d_minimum = d_infinite;

		// Choose a vertex k in R such that d(k) is a minimum.
		for (j = R.size() - 1; j >= 0; j--) {
			SPDistance d_current = distances[R[j]];
			if (d_current == d_infinite)
				continue;
			if (d_minimum == d_infinite) {
				i = j;
				k = R[j];
				d_minimum = d_current;
			}
			else {
				if (d_current < d_minimum) {
					i = j;
					k = R[j];
					d_minimum = d_current;
				}
			}
		}

		if (d_minimum == d_infinite)
			return true;

		// Move k to S from R.
		S.push_back(k);
		R[i] = R[R.size() - 1];
		R.pop_back();

		// Update d for each vertex in R.
		for (j = R.size() - 1; j >= 0; j--) {
			i = R[j];
			SPDistance d_old = distances[i];
			SPDistance d_new = (GetEdgeByIndex(k, i)) ? (d_minimum + 1) : (d_infinite);
			if (d_new == d_infinite)
				continue;
			if ((d_old == d_infinite) || (d_new < d_old))
				distances[i] = d_new;
		}

	}

	return true;

}

//-------------------------------------------------------------------
// Method........: Floyd
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Returns (in-place) the all-pairs shortest paths
//                 (APSP) matrix, computed using Floyd's algorithm.
//
// Comments......: Current implementation uses unit costs/distances.
//                 Could take advantage of symmetry, if present.
// Revisions.....:
//===================================================================

bool
Graph::Floyd(APSPMatrix &distances) const {

	int i, j, k, no_nodes = GetNoNodes();

	// Define a value for "infinite distance".
	const SPDistance d_infinite = Undefined::Integer();

	// Resize and initialize APSP matrix.
	distances.erase(distances.begin(), distances.end());
	distances.reserve(no_nodes);

	for (i = 0; i < no_nodes; i++) {
		distances.push_back(SPVector());
		distances[i].reserve(no_nodes);
		for (j = 0; j < no_nodes; j++) {
			if (GetEdgeByIndex(i, j))
				distances[i].push_back(1);
			else
				distances[i].push_back(d_infinite);
		}
		distances[i][i] = 0;
	}

	// Compute APSPs.
  for (k = 0; k < no_nodes; k++) {
    for (i = 0; i < no_nodes; i++) {
			if (distances[i][k] == d_infinite)
				continue;
      for (j = 0; j < no_nodes; j++) {
				if (distances[k][j] == d_infinite)
					continue;
				SPDistance d_old = distances[i][j];
				SPDistance d_new = distances[i][k] + distances[k][j];
				if ((d_old == d_infinite) || (d_new < d_old))
					distances[i][j] = d_new;
			}
		}
	}

	return true;

}