graph.cpp

粗糙集应用软件

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

#include <stdafx.h> // Precompiled headers.
#include <copyright.h>

#include <kernel/structures/graph.h>
#include <kernel/structures/decisiontable.h>

#include <kernel/utilities/iokit.h>
#include <kernel/utilities/mathkit.h>

#include <kernel/system/fstream.h>

//-------------------------------------------------------------------
// Static helpers (file scope).
//===================================================================

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

static int
StaticGetValue(const String &text, const DecisionTable *table, int attribute, bool masked) {

	if (text == Undefined::String())
		return Undefined::Integer();

	if (table == NULL)
		return text.IsInteger() ? text.GetInteger() : Undefined::Integer();
	else {
		int value = table->GetDictionaryEntry(attribute, text, masked);
		if (value == Undefined::Integer()) {
			if (text.IsInteger())
				value = table->SuggestDictionaryEntry(attribute, text, masked);
		}
		return value;
	}

}

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

static String
StaticGetText(int value, const DecisionTable *table, int attribute, bool masked) {

	if (value == Undefined::Integer())
		return Undefined::String();

	if (table == NULL) {
		return String::Format(value);
	}
	else {
		String text = table->GetDictionaryEntry(attribute, value, masked);
		if (text == Undefined::String())
			text = String::Format(value);
		return text;
	}

}

//-------------------------------------------------------------------
// Methods for class Graph.
//===================================================================

//-------------------------------------------------------------------
// Constructors/destructor.
//===================================================================

//-------------------------------------------------------------------
// Method........: Constructor
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Copy constructor
// Comments......:
// Revisions.....:
//===================================================================

Graph::Graph(const Graph &in) : Structure(in) {
	name_      = in.name_;
	attribute_ = in.attribute_;
	map_       = in.map_;
	matrix_    = in.matrix_;
}

//-------------------------------------------------------------------
// Method........: Constructor
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Empty constructor
// Comments......:
// Revisions.....:
//===================================================================

Graph::Graph() {
	name_      = Undefined::String();
	attribute_ = Undefined::Integer();
}

//-------------------------------------------------------------------
// Method........: Constructor
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Initializes graph with file contents.
// Comments......:
// Revisions.....:
//===================================================================

Graph::Graph(const String &filename, const DecisionTable *table, bool masked) {

	ifstream stream;

	if (!IOKit::Open(stream, filename)) {
		Message::Error("Unable to open " + filename + ".");
	}
	else {
		if (!Load(stream, table, masked))
			Clear();
	}

	IOKit::Close(stream);

}

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

Graph::~Graph() {
}

//-------------------------------------------------------------------
// Methods inherited from Identifier.
//===================================================================

IMPLEMENTIDMETHODS(Graph, GRAPH, Structure)

//-------------------------------------------------------------------
// Methods inherited from Persistent.
//===================================================================

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

bool
Graph::Load(ifstream &stream) {
	return Load(stream, NULL, true);
}

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

bool
Graph::Save(ofstream &stream) const {
	return Save(stream, NULL, true);
}

//-------------------------------------------------------------------
// Methods inherited from Structure.
//===================================================================

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

Structure *
Graph::Duplicate() const {
  return new Graph(*this);
}

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

void
Graph::Clear() {
	name_ = Undefined::String();
	attribute_ = Undefined::Integer();
	map_.erase(map_.begin(), map_.end());
	matrix_.erase(matrix_.begin(), matrix_.end());
}

//-------------------------------------------------------------------
// New methods.
//===================================================================

//-------------------------------------------------------------------
// Graph identification methods.
//===================================================================

//-------------------------------------------------------------------
// Method........: GetName/SetName
// Author........: Aleksander 豩rn
// Date..........:
// Description...: The name of the graph. If the domain of the graph
//                 is the value set of an attribute in a decision
//                 table, the graph name is typically equal to the
//                 attribute name.
// Comments......:
// Revisions.....:
//===================================================================

const String &
Graph::GetName() const {
	return name_;
}

bool
Graph::SetName(const String &name) {
	name_ = name;
	return true;
}

//-------------------------------------------------------------------
// Method........: GetAttribute/SetAttribute
// Author........: Aleksander 豩rn
// Date..........:
// Description...: If the domain of the graph is the value set of an
//                 attribute in a decision table, this denotes the
//                 index of the attribute in the table.
// Comments......:
// Revisions.....:
//===================================================================

int
Graph::GetAttribute() const {
	return attribute_;
}

bool
Graph::SetAttribute(int attribute) {
	attribute_ = attribute;
	return true;
}

//-------------------------------------------------------------------
// Querying methods.
//===================================================================

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

bool
Graph::IsReflexive() const {

	int i;

	for (i = GetNoNodes() - 1; i >= 0; i--) {
		if (!GetEdgeByIndex(i, i))
			return false;
	}

	return true;

}

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

bool
Graph::IsSymmetric() const {

	int i, j, no_nodes = GetNoNodes();

	for (i = 1; i < no_nodes; i++) {
		for (j = 0; j < i; j++) {
			if (GetEdgeByIndex(i, j) != GetEdgeByIndex(j, i))
				return false;
		}
	}

	return true;

}

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

bool
Graph::IsTransitive() const {

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

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

	return true;

}

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

bool
Graph::IsAntiReflexive() const {

	int i;

	for (i = GetNoNodes() - 1; i >= 0; i--) {
		if (GetEdgeByIndex(i, i))
			return false;
	}

	return true;

}

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

bool
Graph::IsAntiSymmetric() const {

	int i, j, no_nodes = GetNoNodes();

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

	return true;

}

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

bool
Graph::IsAntiTransitive() const {
	Message::Error("Graph::IsAntiTransitive() not implemented.");
	return false;
}

//-------------------------------------------------------------------
// Persistence methods.
//===================================================================

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

bool
Graph::Load(const String &filename, const DecisionTable *table, bool masked) {

	ifstream stream;

	if (!IOKit::Open(stream, filename))
		return false;

	return Load(stream, table, masked);

}

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

bool
Graph::Save(const String &filename, const DecisionTable *table, bool masked) const {

	ofstream stream;

	if (!IOKit::Open(stream, filename))
		return false;

	return Save(stream, table, masked);

}

//-------------------------------------------------------------------
// Method........: Load
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Parses the text file and constructs the graph.
// Comments......:
// Revisions.....:
//===================================================================

bool
Graph::Load(ifstream &stream, const DecisionTable *table, bool masked) {

	// Clear current contents.
	Clear();

	String name;
	int    attribute;

	// Parse header.
	if (!ParseHeader(stream, "begin", table, masked, name, attribute))
		return false;

	SetName(name);
	SetAttribute(attribute);

	// Parse nodes/vertices/domain.
	if (!ParseNodes(stream, "nodes", table, masked, attribute))
		return false;

	// Parse edges.
	if (!ParseEdges(stream, "end", table, masked, attribute))
		return false;

	return true;

}

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

bool
Graph::Save(ofstream &stream, const DecisionTable *table, bool masked) const {

	const String &keyword_header_prefix = "begin ";
	const String &keyword_domain_prefix = "nodes ";
	const String &keyword_footer_prefix = "end ";
	const String &keyword_directed      = " -> ";
	const String &keyword_undirected    = " -- ";
	const String &keyword_expansion     = "*";
	const String &keyword_indent        = "\t";

	// Sanity check.
	if (GetAttribute() < 0 || (table != NULL && GetAttribute() >= table->GetNoAttributes(masked))) {
		Message::Error("Attribute index is negative or does not match table.");
		return false;
	}

	int i, j, no_nodes = GetNoNodes();

	// Save header.
	stream << keyword_header_prefix << GetName() << endl;

	// Save nodes/domain.
	stream << keyword_indent << keyword_domain_prefix;
	/*
	if (table != NULL && no_nodes == table->GetNoObjects(masked)) {
		stream << keyword_expansion << endl;
	}
	else {