graph.cpp

粗糙集应用软件

	*/
		for (i = 0; i < no_nodes; i++)
			stream << StaticGetText(GetNodeValue(i), table, GetAttribute(), masked) << " ";
	/*
	}
	*/
	stream << endl;

	// Save edges/matrix.
	for (i = 0; i < no_nodes; i++) {
		String text1 = StaticGetText(GetNodeValue(i), table, GetAttribute(), masked);
		for (j = 0; j < no_nodes; j++) {
			if (GetEdgeByIndex(i, j)) {   // Only save existing edges.
				String text2 = StaticGetText(GetNodeValue(j), table, GetAttribute(), masked);
				if (GetEdgeByIndex(j, i)) { // Bidirectional edge
					if (i <= j) {             // Avoid writing out duplicates.
						if (i != j)
							stream << keyword_indent << text1 << keyword_undirected << text2 << endl;
						else                    // Format as a unidirectional edge.
							stream << keyword_indent << text1 << keyword_directed << text2 << endl;
					}
				}
				else {                      // Unidirectional edge
					stream << keyword_indent << text1 << keyword_directed << text2 << endl;
				}
			}
		}
	}

	// Save dimensional information.
	stream << keyword_indent << "% |nodes| = " << no_nodes << endl;
	stream << keyword_indent << "% |edges| = " << GetNoEdges() << endl;

	const int max_no_nodes_for_transitivity_check = 100;

	// Compute properties.
	bool is_reflexive     = IsReflexive();
	bool is_symmetric     = IsSymmetric();
	bool is_antisymmetric = IsAntiSymmetric();
	bool is_transitive    = (no_nodes > max_no_nodes_for_transitivity_check) ? false : IsTransitive();

	// Save general property information.
	if (is_reflexive)
		stream << keyword_indent << "% reflexive" << endl;
	if (is_symmetric)
		stream << keyword_indent << "% symmetric" << endl;
	if (is_antisymmetric)
		stream << keyword_indent << "% antisymmetric" << endl;
	if (is_transitive)
		stream << keyword_indent << "% transitive" << endl;
	if (no_nodes > max_no_nodes_for_transitivity_check)
		stream << keyword_indent << "% transitivity too time-consuming to check" << endl;

	bool is_tolerance   = is_reflexive && is_symmetric;
	bool is_equivalence = is_reflexive && is_symmetric && is_transitive;
	bool is_partial     = is_reflexive && is_antisymmetric && is_transitive;

	if (is_tolerance && !is_equivalence)
		stream << keyword_indent << "% => tolerance relation" << endl;
	if (is_equivalence)
		stream << keyword_indent << "% => equivalence relation" << endl;
	if (is_partial)
		stream << keyword_indent << "% => partial order" << endl;

	// Save degree information.
	if (is_symmetric) {
		for (i = 0; i < no_nodes; i++) {
			String text = StaticGetText(GetNodeValue(i), table, GetAttribute(), masked);
			stream << keyword_indent << "% deg(" << text << ") = " << GetInDegreeByIndex(i) << endl;
		}
	}
	else {
		for (i = 0; i < no_nodes; i++) {
			String text = StaticGetText(GetNodeValue(i), table, GetAttribute(), masked);
			stream << keyword_indent << "% deg(in , " << text << ") = " << GetInDegreeByIndex(i) << endl;
			stream << keyword_indent << "% deg(out, " << text << ") = " << GetOutDegreeByIndex(i) << endl;
		}
	}

	// Save footer.
	stream << keyword_footer_prefix << GetName() << endl;

	return true;

}

//-------------------------------------------------------------------
// Method........: ParseHeader
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Reads and parses header.
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::ParseHeader(ifstream &stream, const String &prefix, const DecisionTable *table, bool masked, String &name, int &attribute) {

	// Load header line.
	if (!IOKit::LoadLine(stream, name))
		return false;

	// Verify and parse header line.
	if (!name.StartsWith(prefix)) {
		Message::Error("Header line not found, should start with " + prefix + ".");
		return false;
	}

	name.Delete(prefix);
	name.Trim(" \t");

	if (table == NULL && !name.IsInteger()) {
		Message::Error("Could not parse name.");
		return false;
	}

	attribute = (table == NULL) ? name.GetInteger() : table->GetAttributeIndex(name, true, masked);

	if (table != NULL && attribute == Undefined::Integer()) {
		Message::Error("Could not translate \"" + name + "\" to an attribute index.");
		return false;
	}

	return true;

}

//-------------------------------------------------------------------
// Method........: ParseNodes
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Reads and parses node/vertex/domain specification.
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::ParseNodes(ifstream &stream, const String &prefix, const DecisionTable *table, bool masked, int attribute) {

	const String &keyword_expansion = "*";

	String domain;

	// Load domain line.
	if (!IOKit::LoadLine(stream, domain))
		return false;

	// Verify and parse domain line.
	if (!domain.StartsWith(prefix)) {
		Message::Error("Line starting with " + prefix + " expected.");
		return false;
	}

	domain.Delete(prefix);
	domain.Trim(" \t");

	String name;

	int i;

	// Build node/vertex/domain index map.
	while (domain.GetToken(name)) {

		// Set/range of integers?
		if (name.Contains("..")) {
			String from = name.Before("..");
			String to = name.After("..");
			if (!from.IsInteger() || !to.IsInteger()) {
				Message::Error("Could not parse integer set specification \"" + name + "\".");
				continue;
			}
			int lower = from.GetInteger();
			int upper = to.GetInteger();
			for (i = lower; i <= upper; i++) {
				if (!AddNode(i)) {
					// ...
					break;
				}
			}
		}

		// Expansion?
		else if (name == keyword_expansion) {
			if (table == NULL) {
				Message::Error("Domain expansion without table not implemented.");
				continue;
			}
			int no_objects    = table->GetNoObjects(masked);
			int no_attributes = table->GetNoAttributes(masked);
			if (attribute < 0 || attribute >= no_attributes) {
				Message::Error("Name of graph (" + GetName() + ") translates to an illegal attribute index.");
				continue;
			}
			for (i = 0; i < no_objects; i++) {
				if (!AddNode(table->GetEntry(i, attribute, masked))) {
					// ...
					break;
				}
			}
		}

		// Proper name?
		else {
			if (!AddNode(StaticGetValue(name, table, attribute, masked))) {
				// ...
			}
		}

	}

	// Build edge representation.
	return MakeAdjacencyMatrix();

}

//-------------------------------------------------------------------
// Method........: ParseEdges
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Reads and parses edges/commands.
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::ParseEdges(ifstream &stream, const String &footer, const DecisionTable *table, bool masked, int attribute) {

	String line;

	// Continue until footer is encountered or to EOF.
	while (true) {

		// Load next command/edge specification.
		if (!IOKit::LoadLine(stream, line))
			return false;

		// Are all lines read?
		if (line.StartsWith(footer)) {
			String copy(line);
			copy.Delete(footer);
			copy.Trim(" \t");
			if (copy == GetName())
				return true;
		}

		// Parse edge/command.
		if (!ParseEdge(line, table, masked, attribute))
			return false;

	}

	// Programmer's paranoia.
	return false;

}

//-------------------------------------------------------------------
// Method........: ParseEdge
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Parses edge/command.
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::ParseEdge(const String &entry, const DecisionTable *table, bool masked, int attribute) {

	const String &keyword_reflexive   = "make-reflexive";
	const String &keyword_symmetric   = "make-symmetric";
	const String &keyword_transitive  = "make-transitive";
	const String &keyword_distance    = "make-distance";
	const String &keyword_complement  = "make-complement";
	const String &keyword_directed    = "->";
	const String &keyword_undirected  = "--";
	const String &keyword_expansion   = "*";

	// Reflexivity command?
	if (entry == keyword_reflexive) {
		return MakeReflexive();
	}

	// Symmetry command?
	else if (entry == keyword_symmetric) {
		return MakeSymmetric();
	}

	// Transitivity command?
	else if (entry == keyword_transitive) {
		return MakeTransitive();
	}

	// Inversion command?
	else if (entry == keyword_complement) {
		return MakeComplement();
	}

	// Distance command?
	else if (entry.StartsWith(keyword_distance)) {
		String radius_string = entry.After(keyword_distance);
		radius_string.Trim(" \t");
		if (!radius_string.IsFloat() || (table == NULL && !radius_string.IsInteger())) {
			Message::Error("Illegal radius supplied.");
			return false;
		}
		if (table == NULL)
			return MakeDistance(radius_string.GetInteger());
		float radius_float = radius_string.GetFloat();
		int radius_integer = MathKit::Round(radius_float * MathKit::Power(10, table->GetAttributeScalingExponent(attribute, masked)));
		return MakeDistance(radius_integer);
	}

	// Edge entry?
	else if (entry.Contains(keyword_directed) || entry.Contains(keyword_undirected)) {

		// Directed or undirected edge?
		bool is_undirected = entry.Contains(keyword_undirected);

		// Split.
		String text_l = entry.Before(is_undirected ? keyword_undirected : keyword_directed);
		String text_r = entry.After(is_undirected ? keyword_undirected : keyword_directed);

		text_l.Trim(" \t");
		text_r.Trim(" \t");

		// Expand?
		if (text_l == keyword_expansion || text_r == keyword_expansion)
			return ParseExpansion(text_l, text_r, is_undirected ? keyword_undirected : keyword_directed, table, masked, attribute);

		// Lookup node/domain values.
		int value_l = StaticGetValue(text_l, table, attribute, masked);
		int value_r = StaticGetValue(text_r, table, attribute, masked);

		if (value_l == Undefined::Integer() && text_l != Undefined::String()) {
			Message::Error("Failed to look up " + text_l + " in domain map.");
			return false;
		}

		if (value_r == Undefined::Integer() && text_r != Undefined::String()) {
			Message::Error("Failed to look up " + text_r + " in domain map.");
			return false;
		}

		// Lookup matrix indices.
		int index_l = GetNodeIndex(value_l);
		int index_r = GetNodeIndex(value_r);

		if (index_l == Undefined::Integer()) {
			Message::Error("Failed to look up matrix index for " + text_l + ".");
			return false;
		}

		if (index_r == Undefined::Integer()) {
			Message::Error("Failed to look up matrix index for " + text_r + ".");
			return false;
		}

		// Update matrix.
		if (is_undirected)
			return SetEdgeByIndex(index_l, index_r, true) && SetEdgeByIndex(index_r, index_l, true);
		else
			return SetEdgeByIndex(index_l, index_r, true);

	}

	// Unrecognized entry.
	Message::Error("Could not parse entry \"" + entry + "\".");

	return false;

}

//-------------------------------------------------------------------
// Method........: ParseExpansion
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Expands and calls ParseEdge.
// Comments......: Called from ParseEdge.
// Revisions.....:
//===================================================================

bool
Graph::ParseExpansion(const String &lhs, const String &rhs, const String &connective, const DecisionTable *table, bool masked, int attribute) {

	const String &keyword_expansion = "*";

	String expansion;

	int i, no_nodes = GetNoNodes();

	// Expand and parse LHS.
	if (lhs == keyword_expansion) {
		for (i = no_nodes - 1; i >= 0; i--) {
			expansion = StaticGetText(GetNodeValue(i), table, attribute, masked) + connective + rhs;
			if (!ParseEdge(expansion, table, masked, attribute))
				return false;
		}
	}

	// Expand and parse RHS.
	if (rhs == keyword_expansion) {
		for (i = no_nodes - 1; i >= 0; i--) {
			expansion = lhs + connective + StaticGetText(GetNodeValue(i), table, attribute, masked);
			if (!ParseEdge(expansion, table, masked, attribute))
				return false;
		}
	}

	return true;

}

//-------------------------------------------------------------------
// Node/domain methods.
//===================================================================

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

int
Graph::GetNoNodes() const {

#ifdef _DEBUG
	if (map_.size() != matrix_.size())
		Message::Error("Size mismatch between map and matrix!");
#endif

	return map_.size();

}

//-------------------------------------------------------------------
// Method........: AddNode
// Author........: Aleksander 豩rn
// Date..........:
// Description...:
// Comments......: Adjacency matrix does not get updated.
// Revisions.....:
//===================================================================

bool
Graph::AddNode(int value) {

	// Is value already a domain member?
	// This should be a const_iterator, but VC++ 6.0 won't let me...
	Map(int, int)::iterator iterator = map_.find(value);

	if (!(iterator == map_.end()))
		return true;

	// Get a free index.
	int index = map_.size();

	// Add to domain.
	map_.insert(Pair(const int, int)(value, index));

	return true;

}

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

int
Graph::GetNodeIndex(int value) const {

	Map(int, int)::const_iterator iterator = map_.find(value);

#ifdef _DEBUG
	if (!(iterator == map_.end())) {
		return (*iterator).second;
	}
	else {
		Message::Error("Graph " + GetName() + " does not recognize node value " + String::Format(value) + ".");
		return Undefined::Integer();
	}
#else
	return (*iterator).second;
#endif

}

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

int
Graph::GetNodeValue(int index) const {

	Map(int, int)::const_iterator iterator = map_.begin();

	while (!(iterator == map_.end())) {
		if ((*iterator).second == index)
			return (*iterator).first;
		iterator++;
	}

	return Undefined::Integer();

}

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

int
Graph::GetInDegreeByIndex(int index) const {

	int no_nodes = GetNoNodes();

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

	int from, degree = 0;

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