OOFEM  2.4
OOFEM.org - Object Oriented Finite Element Solver
oofem::SloanGraph Class Reference

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...
 
DomaingiveDomain ()
 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...
 
SloanGraphNodegiveNode (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...
 
IntArraygiveOptimalRenumberingTable ()
 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

Domaindomain
 Domain asoociated to graph. More...
 
std::vector< SloanGraphNodenodes
 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

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::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.

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::insertNeigborsOf ( int  next)
private
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)
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
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().

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

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

Priority queue of active or preactive nodes.

Definition at line 95 of file sloangraph.h.

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

SpineQualityType oofem::SloanGraph::SpineQuality
private

Definition at line 100 of file sloangraph.h.

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

int oofem::SloanGraph::startNode
private

Start peripheral node.

Definition at line 91 of file sloangraph.h.

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

int oofem::SloanGraph::WeightDegree
private
int oofem::SloanGraph::WeightDistance
private

Integer distance weight.

Definition at line 97 of file sloangraph.h.

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


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

This page is part of the OOFEM documentation. Copyright (c) 2011 Borek Patzak
Project e-mail: info@oofem.org
Generated at Tue Jan 2 2018 20:07:41 for OOFEM by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2011