#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.
	~SloanGraph ()
	Destructor.
Domain *	giveDomain ()
	Returns associated domain.
void	initialize ()
	Initialize graph from domain description.
void	resetAll ()
	Resets the receiver state. Clears the startNode, endNode and nodeDistancesFlag values.
SloanGraphNode &	giveNode (int num)
	Return graph node.
void	findPeripheralNodes ()
	Finds the peripheral nodes (rooted in optimal start node) according to receiver quality and current weights.
int	getNumberOfNodes ()
int	computeTrueDiameter ()
int	findBestRoot ()
int	giveFullProfileSize ()
int	giveOptimalProfileSize ()
	Returns the optimal profile found.
double	giveOptimalProfileDensity ()
	Returns the optimal density of mesh.
int	computeProfileSize ()
void	askNewOptimalNumbering (TimeStep *tStep)
	Numbers all the DOFs according to the optimal renumbering found.
IntArray &	giveOptimalRenumberingTable ()
	Returns the optimal reverse renumbering table.
void	writeRenumberingTable (FILE *file)
int	writeOptimalRenumberingTable (FILE *file)
void	setWeightDistance (int w)
	Sets weight distance to given value.
void	setWeightDegree (int w)
	Sets weight degree to given value.
void	setSpineQuality (SpineQualityType q)
	Select spine quality generation.
void	printParameters ()
	Prints actual parameters.
void	setParameters (int wdeg, int wdis)
	Sets weight degee and weight dist to given values.
void	tryParameters (int wdeg, int wdis)

Private Member Functions
int	giveNodeWithMinDegree ()
	Returns graph node number with minimal degree.
void	extractCandidates (std ::list< int > &candidates, SloanLevelStructure &Spine)
void	initStatusAndPriority ()
	Initializes statuses and priority of nodes of receiver.
void	evaluateNodeDistances ()
	Evaluates the nodal distances from backSpine. The backSpine is generated if not available.
void	assignOldNumbers ()
	Assigns old node numbers as new ones. Used to compute the profile of existing old numbering.
void	assignNewNumbers ()
	Implementation of node labeling algorithm.
void	insertNeigborsOf (int)
	Inserts inactive neighbours of given node as preactive ones.
void	modifyPriorityAround (int)
	Modifies the priority around node with max priority.
int	findTopPriorityInQueue ()
	Finds node with highest priority in queue, removes its entry and returns its number.
void	numberIsolatedNodes (int &NextNumber, int &labeledNodes)
	Numbers isolated nodes (those with degree equal to 0).

Private Attributes
Domain *	domain
	Domain asoociated to graph.
std::vector< SloanGraphNode >	nodes
	List of graph nodes.
std::vector< DofManager * >	dmans
	List of dof managers corresponding to nodes.
int	numberOfNodes
	number of graph nodes (=numberOfNodes+numberOfElementInternalNodes)
int	startNode
	Start peripheral node.
int	endNode
	End peripheral node.
std ::list< int >	queue
	Priority queue of active or preactive nodes.
int	WeightDistance
	Integer distance weight.
int	WeightDegree
	Integer degree weight.
SpineQualityType	SpineQuality
int	MinimalProfileSize
	Minimal profile size obtained.
int	OptimalWeightDegree
	Optimal degree weight.
int	OptimalWeightDistance
	Optimal distance weight.
int	nodeDistancesFlag
	Flag indicating that node distances from endNode were already computed.
IntArray	OptimalRenumberingTable

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

◆ SpineQualityType

enum oofem::SloanGraph::SpineQualityType

Quality type definition.

Enumerator
Good
Best

Definition at line 81 of file sloangraph.h.

Constructor & Destructor Documentation

◆ SloanGraph()

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, nodes, OptimalRenumberingTable, OptimalWeightDegree, OptimalWeightDistance, queue, SpineQuality, startNode, WeightDegree, and WeightDistance.

◆ ~SloanGraph()

oofem::SloanGraph::~SloanGraph ( )

Destructor.

Definition at line 65 of file sloangraph.C.

Member Function Documentation

◆ askNewOptimalNumbering()

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

Numbers all the DOFs according to the optimal renumbering found.

Definition at line 543 of file sloangraph.C.

References dmans, and OptimalRenumberingTable.

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

◆ assignNewNumbers()

void oofem::SloanGraph::assignNewNumbers ( )

private

Implementation of node labeling algorithm.

Definition at line 397 of file sloangraph.C.

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

Referenced by computeProfileSize().

◆ assignOldNumbers()

void oofem::SloanGraph::assignOldNumbers ( )

private

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

Definition at line 376 of file sloangraph.C.

References nodes.

Referenced by computeProfileSize().

◆ 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 520 of file sloangraph.C.

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

Referenced by tryParameters().

◆ computeTrueDiameter()

int oofem::SloanGraph::computeTrueDiameter ( )

Definition at line 264 of file sloangraph.C.

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

◆ evaluateNodeDistances()

void oofem::SloanGraph::evaluateNodeDistances ( )

private

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

Definition at line 354 of file sloangraph.C.

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

Referenced by initStatusAndPriority().

◆ extractCandidates()

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 245 of file sloangraph.C.

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

Referenced by findPeripheralNodes().

◆ findBestRoot()

int oofem::SloanGraph::findBestRoot ( )

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

Definition at line 271 of file sloangraph.C.

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

Referenced by computeTrueDiameter(), and findPeripheralNodes().

◆ findPeripheralNodes()

void oofem::SloanGraph::findPeripheralNodes ( )

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

Definition at line 182 of file sloangraph.C.

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

Referenced by initStatusAndPriority().

◆ findTopPriorityInQueue()

int oofem::SloanGraph::findTopPriorityInQueue ( )

private

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

Definition at line 497 of file sloangraph.C.

References domain, giveNode(), queue, and WeightDegree.

Referenced by assignNewNumbers().

◆ getNumberOfNodes()

int oofem::SloanGraph::getNumberOfNodes ( )

inline

Definition at line 138 of file sloangraph.h.

References numberOfNodes.

◆ giveDomain()

Domain * oofem::SloanGraph::giveDomain ( )

inline

Returns associated domain.

Definition at line 126 of file sloangraph.h.

◆ giveFullProfileSize()

int oofem::SloanGraph::giveFullProfileSize ( )

Definition at line 626 of file sloangraph.C.

References nodes.

◆ giveNode()

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

Return graph node.

Definition at line 158 of file sloangraph.C.

References nodes.

Referenced by assignNewNumbers(), evaluateNodeDistances(), extractCandidates(), findTopPriorityInQueue(), giveNodeWithMinDegree(), initialize(), initStatusAndPriority(), insertNeigborsOf(), modifyPriorityAround(), tryParameters(), and writeRenumberingTable().

◆ giveNodeWithMinDegree()

int oofem::SloanGraph::giveNodeWithMinDegree ( )

private

Returns graph node number with minimal degree.

Definition at line 164 of file sloangraph.C.

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

Referenced by findPeripheralNodes().

◆ giveOptimalProfileDensity()

double oofem::SloanGraph::giveOptimalProfileDensity ( )

Returns the optimal density of mesh.

Definition at line 301 of file sloangraph.C.

References MinimalProfileSize, and nodes.

◆ giveOptimalProfileSize()

int oofem::SloanGraph::giveOptimalProfileSize ( )

inline

Returns the optimal profile found.

Definition at line 143 of file sloangraph.h.

References MinimalProfileSize.

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

◆ giveOptimalRenumberingTable()

IntArray & oofem::SloanGraph::giveOptimalRenumberingTable ( )

inline

Returns the optimal reverse renumbering table.

Definition at line 156 of file sloangraph.h.

References OptimalRenumberingTable.

◆ initialize()

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::IntArray::at(), dmans, domain, giveNode(), nodes, numberOfNodes, and oofem::IntArray::resize().

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

◆ initStatusAndPriority()

void oofem::SloanGraph::initStatusAndPriority ( )

private

Initializes statuses and priority of nodes of receiver.

Definition at line 314 of file sloangraph.C.

References domain, endNode, evaluateNodeDistances(), findPeripheralNodes(), oofem::SloanLevelStructure::giveDepth(), oofem::SloanLevelStructure::giveLevel(), giveNode(), nodes, WeightDegree, and WeightDistance.

Referenced by assignNewNumbers().

◆ insertNeigborsOf()

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

private

Inserts inactive neighbours of given node as preactive ones.

Definition at line 458 of file sloangraph.C.

References oofem::SloanGraphNode::giveNeighborList(), giveNode(), and queue.

Referenced by assignNewNumbers().

◆ modifyPriorityAround()

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

private

Modifies the priority around node with max priority.

Definition at line 471 of file sloangraph.C.

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

Referenced by assignNewNumbers().

◆ numberIsolatedNodes()

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

private

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

Definition at line 385 of file sloangraph.C.

References nodes.

Referenced by assignNewNumbers().

◆ printParameters()

void oofem::SloanGraph::printParameters ( )

Prints actual parameters.

Definition at line 579 of file sloangraph.C.

References SpineQuality, WeightDegree, and WeightDistance.

◆ resetAll()

void oofem::SloanGraph::resetAll ( )

inline

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

Definition at line 130 of file sloangraph.h.

References endNode, nodeDistancesFlag, and startNode.

Referenced by setSpineQuality().

◆ setParameters()

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

Sets weight degee and weight dist to given values.

Definition at line 588 of file sloangraph.C.

References setWeightDegree(), and setWeightDistance().

Referenced by tryParameters().

◆ setSpineQuality()

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

inline

Select spine quality generation.

Definition at line 173 of file sloangraph.h.

References resetAll(), and SpineQuality.

◆ setWeightDegree()

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

inline

Sets weight degree to given value.

Definition at line 167 of file sloangraph.h.

References WeightDegree.

Referenced by setParameters().

◆ setWeightDistance()

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

inline

Sets weight distance to given value.

Definition at line 161 of file sloangraph.h.

References WeightDistance.

Referenced by setParameters().

◆ tryParameters()

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 600 of file sloangraph.C.

References computeProfileSize(), giveNode(), MinimalProfileSize, nodes, OptimalRenumberingTable, OptimalWeightDegree, OptimalWeightDistance, and setParameters().

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

◆ writeOptimalRenumberingTable()

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

Definition at line 563 of file sloangraph.C.

References OptimalRenumberingTable.

◆ writeRenumberingTable()

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

Definition at line 552 of file sloangraph.C.

References giveNode(), and nodes.

Member Data Documentation

◆ dmans

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

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().

◆ endNode

int oofem::SloanGraph::endNode

private

End peripheral node.

Definition at line 95 of file sloangraph.h.

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

◆ MinimalProfileSize

int oofem::SloanGraph::MinimalProfileSize

private

Minimal profile size obtained.

Definition at line 104 of file sloangraph.h.

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

◆ nodeDistancesFlag

int oofem::SloanGraph::nodeDistancesFlag

private

Flag indicating that node distances from endNode were already computed.

Definition at line 110 of file sloangraph.h.

Referenced by evaluateNodeDistances(), resetAll(), and SloanGraph().

◆ nodes

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(), SloanGraph(), tryParameters(), and writeRenumberingTable().

◆ numberOfNodes

int oofem::SloanGraph::numberOfNodes

private

number of graph nodes (=numberOfNodes+numberOfElementInternalNodes)

Definition at line 91 of file sloangraph.h.

Referenced by assignNewNumbers(), getNumberOfNodes(), and initialize().

◆ OptimalRenumberingTable

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 117 of file sloangraph.h.

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

◆ OptimalWeightDegree

int oofem::SloanGraph::OptimalWeightDegree

private

Optimal degree weight.

Definition at line 106 of file sloangraph.h.

Referenced by SloanGraph(), and tryParameters().

◆ OptimalWeightDistance

int oofem::SloanGraph::OptimalWeightDistance

private

Optimal distance weight.

Definition at line 108 of file sloangraph.h.

Referenced by SloanGraph(), and tryParameters().

◆ queue

std :: list< int > oofem::SloanGraph::queue

private

Priority queue of active or preactive nodes.

Definition at line 97 of file sloangraph.h.

Referenced by assignNewNumbers(), findTopPriorityInQueue(), insertNeigborsOf(), modifyPriorityAround(), and SloanGraph().

◆ SpineQuality

SpineQualityType oofem::SloanGraph::SpineQuality

private

Definition at line 102 of file sloangraph.h.

Referenced by findPeripheralNodes(), printParameters(), setSpineQuality(), and SloanGraph().

◆ startNode

int oofem::SloanGraph::startNode

private

Start peripheral node.

Definition at line 93 of file sloangraph.h.

Referenced by assignNewNumbers(), findPeripheralNodes(), resetAll(), and SloanGraph().

◆ WeightDegree

int oofem::SloanGraph::WeightDegree

private

Integer degree weight.

Definition at line 101 of file sloangraph.h.

Referenced by computeProfileSize(), findTopPriorityInQueue(), initStatusAndPriority(), modifyPriorityAround(), printParameters(), setWeightDegree(), and SloanGraph().

◆ WeightDistance

int oofem::SloanGraph::WeightDistance

private

Integer distance weight.

Definition at line 99 of file sloangraph.h.

Referenced by computeProfileSize(), initStatusAndPriority(), printParameters(), setWeightDistance(), and SloanGraph().

The documentation for this class was generated from the following files:

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ SpineQualityType

Constructor & Destructor Documentation

◆ SloanGraph()

◆ ~SloanGraph()

Member Function Documentation

◆ askNewOptimalNumbering()

◆ assignNewNumbers()

◆ assignOldNumbers()

◆ computeProfileSize()

◆ computeTrueDiameter()

◆ evaluateNodeDistances()

◆ extractCandidates()

◆ findBestRoot()

◆ findPeripheralNodes()

◆ findTopPriorityInQueue()

◆ getNumberOfNodes()

◆ giveDomain()

◆ giveFullProfileSize()

◆ giveNode()

◆ giveNodeWithMinDegree()

◆ giveOptimalProfileDensity()

◆ giveOptimalProfileSize()

◆ giveOptimalRenumberingTable()

◆ initialize()

◆ initStatusAndPriority()

◆ insertNeigborsOf()

◆ modifyPriorityAround()

◆ numberIsolatedNodes()

◆ printParameters()

◆ resetAll()

◆ setParameters()

◆ setSpineQuality()

◆ setWeightDegree()

◆ setWeightDistance()

◆ tryParameters()

◆ writeOptimalRenumberingTable()

◆ writeRenumberingTable()

Member Data Documentation

◆ dmans

◆ domain

◆ endNode

◆ MinimalProfileSize

◆ nodeDistancesFlag

◆ nodes

◆ numberOfNodes

◆ OptimalRenumberingTable

◆ OptimalWeightDegree

◆ OptimalWeightDistance

◆ queue

◆ SpineQuality

◆ startNode

◆ WeightDegree

◆ WeightDistance