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

Inheritance diagram for SplitGraph:

[legend]

Collaboration diagram for SplitGraph:

[legend]

List of all members.

---

Detailed Description

Class used to partition a graph using a factorial embedding in .

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

• svector< int > ClassNumber
• svector< int > NumberElementsInClass
• int NumberOfClasses
• int MinDimension
• int MaxDimension
• int CurrentNumberOfClasses

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

~SplitGraph

(

)

[inline]

Destructor.

---

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.

int Segment

(

)

Computes the requested partition.

void init

(

)

[private]

Class initialization.

Reimplemented from TopologicalGraph.

---

Member Data Documentation

svector<int> ClassNumber

Class index of a vertex.

svector<int> NumberElementsInClass

Cardinality of the classes.

int NumberOfClasses

Requested number of classes.

int MinDimension

Minimum dimension to be used for optimization.

Fixed to by init()

int MaxDimension

Maximum dimension to be used for optimization.

Actually fixed to by init()

int CurrentNumberOfClasses

Current number of classes

---