Graph representing the undirected graph used for Sloan algorithm for symmetric matrix profile reduction. More...

#include <sloangraph.h>

Collaboration diagram for oofem::SloanGraph:

Public Types
enum	SpineQualityType { Good, Best }
	Quality type definition. More...

Public Member Functions
	SloanGraph (Domain *d)
	Constructor. Creates the graph associated to given domain. More...

	~SloanGraph ()
	Destructor. More...

Domain *	giveDomain ()
	Returns associated domain. More...

void	initialize ()
	Initialize graph from domain description. More...

void	resetAll ()
	Resets the receiver state. Clears the startNode, endNode and nodeDistancesFlag values. More...

SloanGraphNode &	giveNode (int num)
	Return graph node. More...

void	findPeripheralNodes ()
	Finds the peripheral nodes (rooted in optimal start node) according to receiver quality and current weights. More...

int	computeTrueDiameter ()

int	findBestRoot ()

int	giveFullProfileSize ()

int	giveOptimalProfileSize ()
	Returns the optimal profile found. More...

double	giveOptimalProfileDensity ()
	Returns the optimal density of mesh. More...

int	computeProfileSize ()
	Assigns the New numbers by node labeling algorithm (old numbers are used when both weights are zero) and returns the profile size. More...

void	askNewOptimalNumbering (TimeStep *tStep)
	Numbers all the DOFs according to the optimal renumbering found. More...

IntArray &	giveOptimalRenumberingTable ()
	Returns the optimal reverse renumbering table. More...

void	writeRenumberingTable (FILE *file)

int	writeOptimalRenumberingTable (FILE *file)

void	setWeightDistance (int w)
	Sets weight distance to given value. More...

void	setWeightDegree (int w)
	Sets weight degree to given value. More...

void	setSpineQuality (SpineQualityType q)
	Select spine quality generation. More...

void	printParameters ()
	Prints actual parameters. More...

void	setParameters (int wdeg, int wdis)
	Sets weight degee and weight dist to given values. More...

void	tryParameters (int wdeg, int wdis)
	Generates the new nodal numbering based on given parameters. More...

Private Member Functions
int	giveNodeWithMinDegree ()
	Returns graph node number with minimal degree. More...

void	extractCandidates (std::list< int > &candidates, SloanLevelStructure &Spine)
	Extract candidates from given level structure. More...

void	initStatusAndPriority ()
	Initializes statuses and priority of nodes of receiver. More...

void	evaluateNodeDistances ()
	Evaluates the nodal distances from backSpine. The backSpine is generated if not available. More...

void	assignOldNumbers ()
	Assigns old node numbers as new ones. Used to compute the profile of existing old numbering. More...

void	assignNewNumbers ()
	Implementation of node labeling algorithm. More...

void	insertNeigborsOf (int)
	Inserts inactive neighbours of given node as preactive ones. More...

void	modifyPriorityAround (int)
	Modifies the priority around node with max priority. More...

int	findTopPriorityInQueue ()
	Finds node with highest priority in queue, removes its entry and returns its number. More...

void	numberIsolatedNodes (int &NextNumber, int &labeledNodes)
	Numbers isolated nodes (those with degree equal to 0). More...

Private Attributes
Domain *	domain
	Domain asoociated to graph. More...

std::vector< SloanGraphNode >	nodes
	List of graph nodes. More...

std::vector< DofManager * >	dmans
	List of dof managers corresponding to nodes. More...

int	startNode
	Start peripheral node. More...

int	endNode
	End peripheral node. More...

std::list< int >	queue
	Priority queue of active or preactive nodes. More...

int	WeightDistance
	Integer distance weight. More...

int	WeightDegree
	Integer degree weight. More...

SpineQualityType	SpineQuality

int	MinimalProfileSize
	Minimal profile size obtained. More...

int	OptimalWeightDegree
	Optimal degree weight. More...

int	OptimalWeightDistance
	Optimal distance weight. More...

int	nodeDistancesFlag
	Flag indicating that node distances from endNode were already computed. More...

IntArray	OptimalRenumberingTable
	Inverse renumbering table. More...

Detailed Description

Graph representing the undirected graph used for Sloan algorithm for symmetric matrix profile reduction.

The Sloan algorithm is described by following papers: Sloan, S., W: An algorithm for profile and wavefront reduction of sparse matrices, IJNME, vol. 23, 239-251, 1986 Sloan, S., W: A Fortran program for profile and wavefront reduction, IJNME, vol. 28, 2651-2679, 1989. The current implementation undergoes the description of algorithm given in second paper.

The rigid arm nodes and slave dofs are supported. A fictitious element (graph edge) connecting corresponding slave and master nodes is added to reflect the connection.

The current implementation allows to select quality. The recommended value for quality is Good, causing Sloan pseudo-peripheral node selection algorithm is used. The Best causes the level structure to be generated for all nodes and selecting the best one. However, this is extremely time consuming.

Author: Milan Jirasek; Borek Patzak

Definition at line 77 of file sloangraph.h.

Member Enumeration Documentation

enum oofem::SloanGraph::SpineQualityType

Quality type definition.

Enumerator
Good
Best

Definition at line 81 of file sloangraph.h.

Constructor & Destructor Documentation

oofem::SloanGraph::SloanGraph ( Domain * d )

Constructor. Creates the graph associated to given domain.

Definition at line 52 of file sloangraph.C.

References domain, endNode, Good, MinimalProfileSize, nodeDistancesFlag, OptimalWeightDegree, OptimalWeightDistance, SpineQuality, startNode, WeightDegree, and WeightDistance.

oofem::SloanGraph::~SloanGraph ( )

Destructor.

Definition at line 65 of file sloangraph.C.

Member Function Documentation

void oofem::SloanGraph::askNewOptimalNumbering ( TimeStep * tStep )

Numbers all the DOFs according to the optimal renumbering found.

Definition at line 542 of file sloangraph.C.

References dmans, and OptimalRenumberingTable.

Referenced by oofem::EngngModel::forceEquationNumbering().

void oofem::SloanGraph::assignNewNumbers ( )

private

Implementation of node labeling algorithm.

Definition at line 396 of file sloangraph.C.

References domain, findTopPriorityInQueue(), giveNode(), oofem::Domain::giveNumberOfDofManagers(), oofem::SloanGraphNode::giveStatus(), initStatusAndPriority(), insertNeigborsOf(), modifyPriorityAround(), nodes, numberIsolatedNodes(), OOFEM_ERROR, oofem::SloanGraphNode::Postactive, oofem::SloanGraphNode::Preactive, queue, oofem::SloanGraphNode::setNewNumber(), oofem::SloanGraphNode::setStatus(), and startNode.

Referenced by computeProfileSize().

void oofem::SloanGraph::assignOldNumbers ( )

private

Assigns old node numbers as new ones. Used to compute the profile of existing old numbering.

Definition at line 375 of file sloangraph.C.

References nodes.

Referenced by computeProfileSize().

int oofem::SloanGraph::computeProfileSize ( )

Assigns the New numbers by node labeling algorithm (old numbers are used when both weights are zero) and returns the profile size.

Definition at line 519 of file sloangraph.C.

References assignNewNumbers(), assignOldNumbers(), nodes, WeightDegree, and WeightDistance.

Referenced by tryParameters().

int oofem::SloanGraph::computeTrueDiameter ( )

Definition at line 263 of file sloangraph.C.

References findBestRoot(), and oofem::SloanLevelStructure::giveDepth().

void oofem::SloanGraph::evaluateNodeDistances ( )

private

Evaluates the nodal distances from backSpine. The backSpine is generated if not available.

Definition at line 353 of file sloangraph.C.

References endNode, oofem::SloanLevelStructure::giveDepth(), oofem::SloanLevelStructure::giveLevel(), giveNode(), nodeDistancesFlag, and oofem::SloanGraphNode::setDistance().

Referenced by initStatusAndPriority().

void oofem::SloanGraph::extractCandidates	(	std::list< int > &	candidates,
		SloanLevelStructure &	Spine
	)

private

Extract candidates from given level structure.

The list of candidates contains only one node of each degree of last level of active spine.

Definition at line 244 of file sloangraph.C.

References oofem::SloanGraphNode::giveDegree(), oofem::SloanLevelStructure::giveDepth(), oofem::SloanLevelStructure::giveLevel(), giveNode(), and oofem::sort().

Referenced by findPeripheralNodes().

int oofem::SloanGraph::findBestRoot ( )

Todo:: Use the timer functionalities from OOFEM here, instead of clock() directly

Definition at line 270 of file sloangraph.C.

References oofem::SloanLevelStructure::giveDepth(), nodes, OOFEM_LOG_INFO, and SLOAN_TIME_CHUNK.

Referenced by computeTrueDiameter(), and findPeripheralNodes().

void oofem::SloanGraph::findPeripheralNodes ( )

Finds the peripheral nodes (rooted in optimal start node) according to receiver quality and current weights.

Definition at line 181 of file sloangraph.C.

References Best, domain, endNode, extractCandidates(), findBestRoot(), giveNodeWithMinDegree(), oofem::Domain::giveNumberOfDofManagers(), Good, OOFEM_WARNING, SpineQuality, and startNode.

Referenced by initStatusAndPriority().

int oofem::SloanGraph::findTopPriorityInQueue ( )

private

Finds node with highest priority in queue, removes its entry and returns its number.

Definition at line 496 of file sloangraph.C.

References domain, giveNode(), oofem::Domain::giveNumberOfDofManagers(), oofem::SloanGraphNode::givePriority(), queue, and WeightDegree.

Referenced by assignNewNumbers().

Domain* oofem::SloanGraph::giveDomain ( )

inline

Returns associated domain.

Definition at line 124 of file sloangraph.h.

int oofem::SloanGraph::giveFullProfileSize ( )

Definition at line 625 of file sloangraph.C.

References nodes.

SloanGraphNode & oofem::SloanGraph::giveNode ( int num )

Return graph node.

Definition at line 157 of file sloangraph.C.

References nodes.

Referenced by assignNewNumbers(), oofem::SloanGraphNode::computeProfileHeight(), evaluateNodeDistances(), extractCandidates(), findTopPriorityInQueue(), giveNodeWithMinDegree(), initialize(), initStatusAndPriority(), insertNeigborsOf(), modifyPriorityAround(), oofem::SloanNodalDegreeOrderingCrit::operator()(), tryParameters(), and writeRenumberingTable().

int oofem::SloanGraph::giveNodeWithMinDegree ( )

private

Returns graph node number with minimal degree.

Definition at line 163 of file sloangraph.C.

References oofem::SloanGraphNode::giveDegree(), giveNode(), oofem::min(), and nodes.

Referenced by findPeripheralNodes().

double oofem::SloanGraph::giveOptimalProfileDensity ( )

Returns the optimal density of mesh.

Definition at line 300 of file sloangraph.C.

References MinimalProfileSize, and nodes.

int oofem::SloanGraph::giveOptimalProfileSize ( )

inline

Returns the optimal profile found.

Definition at line 140 of file sloangraph.h.

Referenced by oofem::EngngModel::forceEquationNumbering().

IntArray& oofem::SloanGraph::giveOptimalRenumberingTable ( )

inline

Returns the optimal reverse renumbering table.

Definition at line 153 of file sloangraph.h.

void oofem::SloanGraph::initialize ( )

Initialize graph from domain description.

Todo:: Add connections from dof managers to boundary condition internal dof managers.

Todo:: FIXME This is inherently limited; It assumes that dofmanagers cannot be slaves to internal dofmanagers in BCs or Elements. If we were able to get the masters dofmanagers are pointers we could fix this.

Definition at line 69 of file sloangraph.C.

References oofem::SloanGraphNode::addNeighbor(), oofem::IntArray::at(), dmans, domain, oofem::Domain::giveBcs(), oofem::Domain::giveDofManagers(), oofem::Domain::giveElements(), giveNode(), oofem::Domain::giveNumberOfDofManagers(), nodes, and oofem::IntArray::resize().

Referenced by oofem::EngngModel::forceEquationNumbering().

void oofem::SloanGraph::initStatusAndPriority ( )

private

Initializes statuses and priority of nodes of receiver.

Definition at line 313 of file sloangraph.C.

References domain, endNode, evaluateNodeDistances(), findPeripheralNodes(), oofem::SloanGraphNode::giveDegree(), oofem::SloanLevelStructure::giveDepth(), oofem::SloanLevelStructure::giveLevel(), giveNode(), oofem::Domain::giveNumberOfDofManagers(), oofem::SloanGraphNode::Inactive, nodes, oofem::SloanGraphNode::setDistance(), oofem::SloanGraphNode::setPriority(), oofem::SloanGraphNode::setStatus(), WeightDegree, and WeightDistance.

Referenced by assignNewNumbers().

void oofem::SloanGraph::insertNeigborsOf ( int next )

private

Inserts inactive neighbours of given node as preactive ones.

Definition at line 457 of file sloangraph.C.

References oofem::SloanGraphNode::giveNeighborList(), giveNode(), oofem::SloanGraphNode::giveStatus(), oofem::SloanGraphNode::Inactive, oofem::SloanGraphNode::Preactive, queue, and oofem::SloanGraphNode::setStatus().

Referenced by assignNewNumbers().

void oofem::SloanGraph::modifyPriorityAround ( int next )

private

Modifies the priority around node with max priority.

Definition at line 470 of file sloangraph.C.

References oofem::SloanGraphNode::Active, oofem::SloanGraphNode::giveNeighborList(), giveNode(), oofem::SloanGraphNode::giveStatus(), oofem::SloanGraphNode::Inactive, oofem::SloanGraphNode::increasePriorityBy(), oofem::SloanGraphNode::Preactive, queue, oofem::SloanGraphNode::setStatus(), and WeightDegree.

Referenced by assignNewNumbers().

void oofem::SloanGraph::numberIsolatedNodes	(	int &	NextNumber,
		int &	labeledNodes
	)

private

Numbers isolated nodes (those with degree equal to 0).

Definition at line 384 of file sloangraph.C.

References nodes.

Referenced by assignNewNumbers().

void oofem::SloanGraph::printParameters ( )

Prints actual parameters.

Definition at line 578 of file sloangraph.C.

References SpineQuality, WeightDegree, and WeightDistance.

void oofem::SloanGraph::resetAll ( )

inline

Resets the receiver state. Clears the startNode, endNode and nodeDistancesFlag values.

Definition at line 128 of file sloangraph.h.

void oofem::SloanGraph::setParameters	(	int	wdeg,
		int	wdis
	)

Sets weight degee and weight dist to given values.

Definition at line 587 of file sloangraph.C.

References setWeightDegree(), and setWeightDistance().

Referenced by tryParameters().

void oofem::SloanGraph::setSpineQuality ( SpineQualityType q )

inline

Select spine quality generation.

Definition at line 170 of file sloangraph.h.

void oofem::SloanGraph::setWeightDegree ( int w )

inline

Sets weight degree to given value.

Definition at line 164 of file sloangraph.h.

Referenced by setParameters().

void oofem::SloanGraph::setWeightDistance ( int w )

inline

Sets weight distance to given value.

Definition at line 158 of file sloangraph.h.

Referenced by setParameters().

void oofem::SloanGraph::tryParameters	(	int	wdeg,
		int	wdis
	)

Generates the new nodal numbering based on given parameters.

Can be used multiple times, the best result is stored in OptimalRenumberingTable, MinimalProfileSize, OptimalWeightDegree and OptimalWeightDistance attributes.

Definition at line 599 of file sloangraph.C.

References oofem::IntArray::at(), computeProfileSize(), giveNode(), MinimalProfileSize, nodes, OptimalRenumberingTable, OptimalWeightDegree, OptimalWeightDistance, oofem::IntArray::resize(), and setParameters().

Referenced by oofem::EngngModel::forceEquationNumbering().

int oofem::SloanGraph::writeOptimalRenumberingTable ( FILE * file )

Definition at line 562 of file sloangraph.C.

References oofem::IntArray::at(), oofem::IntArray::giveSize(), oofem::IntArray::isEmpty(), and OptimalRenumberingTable.

void oofem::SloanGraph::writeRenumberingTable ( FILE * file )

Definition at line 551 of file sloangraph.C.

References oofem::SloanGraphNode::giveNewNumber(), giveNode(), and nodes.

Member Data Documentation

std::vector< DofManager* > oofem::SloanGraph::dmans

private

List of dof managers corresponding to nodes.

Definition at line 89 of file sloangraph.h.

Referenced by askNewOptimalNumbering(), and initialize().

Domain* oofem::SloanGraph::domain

private

Domain asoociated to graph.

Definition at line 84 of file sloangraph.h.

Referenced by assignNewNumbers(), findPeripheralNodes(), findTopPriorityInQueue(), initialize(), initStatusAndPriority(), and SloanGraph().

int oofem::SloanGraph::endNode

private

End peripheral node.

Definition at line 93 of file sloangraph.h.

Referenced by evaluateNodeDistances(), findPeripheralNodes(), initStatusAndPriority(), and SloanGraph().

int oofem::SloanGraph::MinimalProfileSize

private

Minimal profile size obtained.

Definition at line 102 of file sloangraph.h.

Referenced by giveOptimalProfileDensity(), SloanGraph(), and tryParameters().

int oofem::SloanGraph::nodeDistancesFlag

private

Flag indicating that node distances from endNode were already computed.

Definition at line 108 of file sloangraph.h.

Referenced by evaluateNodeDistances(), and SloanGraph().

std::vector< SloanGraphNode > oofem::SloanGraph::nodes

private

List of graph nodes.

Definition at line 87 of file sloangraph.h.

Referenced by assignNewNumbers(), assignOldNumbers(), computeProfileSize(), findBestRoot(), giveFullProfileSize(), giveNode(), giveNodeWithMinDegree(), giveOptimalProfileDensity(), initialize(), initStatusAndPriority(), numberIsolatedNodes(), tryParameters(), and writeRenumberingTable().

IntArray oofem::SloanGraph::OptimalRenumberingTable

private

Inverse renumbering table.

Contains at i-th position the old node number corresponding to newly generated i-th node. Used directly in equation numbering, the nodes (still referenced by old numbers) are numbered in the order given by OptimalRenumberingTable values.

Definition at line 115 of file sloangraph.h.

Referenced by askNewOptimalNumbering(), tryParameters(), and writeOptimalRenumberingTable().

int oofem::SloanGraph::OptimalWeightDegree

private

Optimal degree weight.

Definition at line 104 of file sloangraph.h.

Referenced by SloanGraph(), and tryParameters().

int oofem::SloanGraph::OptimalWeightDistance

private

Optimal distance weight.

Definition at line 106 of file sloangraph.h.

Referenced by SloanGraph(), and tryParameters().