PIGALE 1.3.9 Documentation (original) (raw)

P.I.G.A.L.E.
1.3.9
Public Implementation of a Graph Algorithm
Library and Editor
H. de Fraysseix P. Ossona de Mendez

SplitGraph Class Reference

List of all members.

Detailed Description

Class used to partition a graph using a factorial embedding in $\mathbb{R}^{n-1}$ .

Public Member Functions

SplitGraph (Graph &G, int numclasses, int maxdim, int usedDistance)
~SplitGraph ()
void ComputeMaxDistance3d ()
void NewClass (int dimension, int worst)
void ComputeProjectDistance (int dimension)
void SearchFarVertices (int dimension)
void SearchWorst (int dimension, int &worst)
void AffectExtrems (int extrem0, int extrem1)
void BuildClasses (int dimension, double &inertie, int &worst)
void Optimize (int dimension, int &worst, double &inertie)
void ComputeBarycenters (int dimension)
double TotalInertia (double &ClassVarianceNumber)
int Segment ()

Public Attributes

Private Member Functions

void init ()

Constructor & Destructor Documentation

SplitGraph	(	Graph &	G,
int	numclasses,
int	maxdim,
int	usedDistance
)	[inline]

Constructor.

Parameters:

G	Graph to be partitioned
numclasses	Requested number of classes
maxdim	Maximum dimension to be used for optimization

Warning:

maxdim is overridden by init()

Member Function Documentation

| void ComputeMaxDistance3d | ( | | ) | | ------------------------- | - | | - |

void NewClass	(	int	dimension,
int	worst
)

Creates a new class.

Parameters:

dimension	Current space dimension
worst	Index of the point used as a representative for the new class

void ComputeProjectDistance	(	int	dimension	)

Computes projective distance.

void SearchFarVertices	(	int	dimension	)

Partitions into 2 initial classes and computes projective distance.

void SearchWorst	(	int	dimension,
int &	worst
)

Searches worst represented point.

Parameters:

dimension	Current space dimension
worst	Index of the worst represented point (returned value)

void AffectExtrems	(	int	extrem0,
int	extrem1
)

Partitions into 2 classes with given representatives.

void BuildClasses	(	int	dimension,
double &	inertie,
int &	worst
)

Builds classes from the barycenters.

void Optimize	(	int	dimension,
int &	worst,
double &	inertie
)

Representative affectation optimization.

void ComputeBarycenters	(	int	dimension	)

Computes the barycenters of the classes.

double TotalInertia	(	double &	ClassVarianceNumber	)

Computes the total inertia of the partition.

Computes the requested partition.

Member Data Documentation

Cardinality of the classes.

Requested number of classes.

Minimum dimension to be used for optimization.

Fixed to $\max (1,\#\text{classes}-2)$ by init()

Maximum dimension to be used for optimization.

Actually fixed to $\min (n-1,\#\text{classes})$ by init()

Current number of classes

Generated on Thu Jan 31 16:52:06 2008 for Pigale by 1.5.4