indiscernibilitygraph.cpp

粗糙集应用软件

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

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

#include <kernel/structures/indiscernibilitygraph.h>
#include <kernel/structures/discernibilitymatrix.h>
#include <kernel/structures/decisiontable.h>
#include <kernel/structures/generalizeddecision.h>

#include <kernel/utilities/partitionkit.h>
#include <kernel/utilities/discerner.h>
#include <kernel/utilities/creator.h>

#include <kernel/basic/map.h>

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

//-------------------------------------------------------------------
// Method........: StaticVerifyNames
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Verifies validity of index (unmasked) of attribute
//                 that specifies node names.
//
//                 Also checks that attribute is valid for unique
//                 object naming (with a masked table).
// Comments......:
// Revisions.....:
//===================================================================

static bool
StaticVerifyNames(int index, const DecisionTable &table) {

	if (index == Undefined::Integer())
		return true;

	// Verify range.
	if (index < 0 || index >= table.GetNoAttributes(false))
		return false;

	Vector(int) values, cardinalities;

	// Get value set.
	if (!table.GetValueSet(values, cardinalities, index, false))
		return false;

	// Verify "1-1"-ness with the masked table.
	if (values.size() != table.GetNoObjects(true))
		return false;

	return true;

}

//-------------------------------------------------------------------
// Methods for class IndiscernibilityGraph.
//===================================================================

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

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

IndiscernibilityGraph::IndiscernibilityGraph(const IndiscernibilityGraph &in) : Graph(in) {
}

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

IndiscernibilityGraph::IndiscernibilityGraph() {
}

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

IndiscernibilityGraph::~IndiscernibilityGraph() {
}

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

IMPLEMENTIDMETHODS(IndiscernibilityGraph, INDISCERNIBILITYGRAPH, Graph)

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

//-------------------------------------------------------------------
// Method........: AreIndiscernible
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Given objects x and y (or more precisely, object
//                 indices i and j) and the discernibility matrix M,
//                 returns true iff x and y are indiscernible.
//
//                 Default implementation returns true iff M(x, y)
//                 contains less than k elements. Can be overloaded to
//                 provide other behaviours.
//
// Comments......: Called from the Create method. The AddEdges1 and
//                 AddEdges2 methods should be generalized to allow
//                 similar flexibility through a related AreIndiscernible
//                 method.
//
// Revisions.....:
//===================================================================

bool
IndiscernibilityGraph::AreIndiscernible(int i, int j, const DiscernibilityMatrix &matrix, int cardinality) const {

	if (matrix.IsEmpty(i, j))
		return true;

	// Assuming that only non-empty entries are stored in the matrix.
	if (cardinality == 0)
		return false;

	return (matrix.GetEntry(i, j)->Count(true) <= cardinality);

}

//-------------------------------------------------------------------
// Method........: AreIndiscernible
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Given objects x and y (or more precisely, object
//                 indices i and j) and the decision table to which they
//                 belong, returns true iff x and y are indiscernible.
//
//                 Can be overloaded to provide other behaviours, e.g.,
//                 Euclidian or Mahalonobis distance.
//
// Comments......: Called from the AddEdges1 method.
// Revisions.....:
//===================================================================

bool
IndiscernibilityGraph::AreIndiscernible(int i, int j, const DecisionTable &table, bool masked, const Discerner &discerner, bool all, int cardinality) const {
	return AreIndiscernible(i, j, table, masked, discerner, all, cardinality, table.GetNoAttributes(masked));
}

bool
IndiscernibilityGraph::AreIndiscernible(int i, int j, const DecisionTable &table, bool masked, const Discerner &discerner, bool all, int cardinality, int no_attributes) const {

	int k, count = 0;

	// Are objects (i, j) indiscernible?
	for (k = 0; k < no_attributes; k++) {
		if (all || table.IsCondition(k, masked)) {
			int value_i = table.GetEntry(i, k, masked);
			int value_j = table.GetEntry(j, k, masked);
			if (discerner.Discerns(k, value_i, value_j)) {
				count++;
				if (count > cardinality)
					return false;
			}
		}
	}

	return true;

}

//-------------------------------------------------------------------
// Method........: Create
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Constructs a graph (V, E).
//
//                 V: The set of nodes. One node per object in the
//                    discernibility matrix.
//                 E: The set of edges. Typically, an edge is present
//                    between node i and node j iff entry (i, j) in
//                    the matrix is empty.
//
// Comments......:
// Revisions.....:
//===================================================================

bool
IndiscernibilityGraph::Create(const DiscernibilityMatrix &matrix, int cardinality) {

	// Delete current graph contents.
	Clear();

	int i, j, no_objects = matrix.GetDimension();

	// Initialize node set.
	for (i = 0; i < no_objects; i++) {
		if (!AddNode(i))
			return false;
	}

	// Create edge matrix.
	if (!MakeAdjacencyMatrix())
		return false;

	// Add an undirected edge between two objects if the objects are indiscernible.
	// Assume a symmetric matrix.
	for (i = 0; i < no_objects; i++) {
		for (j = 0; j <= i; j++) {
			if (AreIndiscernible(i, j, matrix, cardinality)) {
				if (!SetEdgeByIndex(i, j, true) || !SetEdgeByValue(j, i, true))
					return false;
			}
		}
	}

	return true;

}

//-------------------------------------------------------------------
// Method........: Create
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Constructs a graph (V, E).
//
//                 V: The set of nodes. One node per object in the
//                    table.
//                 E: The set of edges. An edge is present between
//                    node i and node j iff objects i and j are
//                    indiscernible.
//
//                 table:
//                    The decision table to work on.
//                 masked:
//                    Work on a masked table?
//                 discerner:
//                    Defines the discernibility predicate.
//                 all:       (default true)
//                    For discernibility, consider all attributes
//                    (i.e., both condition and decision attributes)
//                    or condition attributes only?
//                 names:     (default Undefined::Integer())
//                    The index (unmasked) of a 1-1 attribute in the
//                    table that defines node names. If Undefined,
//                    no names are used.
//                 decisions: (default NULL)
//                    If supplied, returned in-place. In effect
//                    defines the generalized decision values for
//                    each object, since it compiles the decision
//                    values of all indiscernible objects, i.e.,
//                    neighbouring nodes.
//
// Comments......: The table can be masked to change the attribute
//                 subset under consideration.
//
//                 Creation of graph can be done quicker if we know
//                 that the indiscernibility relation is an
//                 equivalence relation. Hence, a specialized
//                 implementation is provided if the discernibility
//                 predicate does not use a IDG. Then, strict inequality
//                 assumed used.
//
//                 Can be optimized by only considering one
//                 representative from each equivalence class.
//
// Revisions.....:
//===================================================================

bool
IndiscernibilityGraph::Create(const DecisionTable &table, bool masked, const Discerner &discerner, bool all, int cardinality, int names, GeneralizedDecision::Handles *decisions) {

	// Delete current graph contents.
	Clear();

	int no_objects    = table.GetNoObjects(masked);
	int no_attributes = table.GetNoAttributes(masked);

	// Current implementation is not perfect...
	if (table.GetNoObjects(true) != table.GetNoObjects(false)) {
		Message::Error("Current implementation does not handle masked objects.");
		return false;
	}

	// Verify validity of name attribute.
	if (!StaticVerifyNames(names, table)) {
		Message::Error("Name attribute not accepted. Does it assign unique names?");
		return false;
	}

	int i;

	// Initialize node set.
	for (i = 0; i < no_objects; i++) {
		int name = (names == Undefined::Integer()) ? i : table.GetEntry(i, names, false);
		if (!AddNode(name))
			return false;
	}

	// Create edge matrix.
	if (!MakeAdjacencyMatrix())
		return false;

	// Add edges.
	if (discerner.HasIDGs() || (cardinality > 0)) {
		if (!AddEdges1(table, masked, discerner, all, cardinality, names, decisions))
			return false;
	}
	else {
		if (!AddEdges2(table, masked, all, names, decisions))
			return false;
	}

	// Set index of attribute graph node values refer to (if any).
	SetAttribute(names);

	return true;

}

//-------------------------------------------------------------------
// Method........: AddEdges1
// Author........: Aleksander 豩rn
// Date..........:
// Description...: Helper, called from Create. Adds edges to graph.
//                 General O(n^2) implementation.
//
// Comments......: Future optimization: Compute equivalence classes
//                 and consider representatives in the computations.
//
// Revisions.....: 990717 A