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

netcut.h File Reference

Detailed Description

Embedder and Partitioner class definitions.

Todo:: Eigenspaces dimensions optimization. Optimize eigenspaces dimensions over the distances defined on the cellular algebra $\mathfrak{A}$ generated by the adjacency matrix

Todo:

Q distance. Test the distance

$d^2(i,j)=\begin{cases} 0,&\text{if $i=j$}\\ 1,&\text{if $i$ and $j$ are non adjacent}\\ 1-\frac{1}{\sqrt{d(i)d(j)}},&\text{otherwise} \end{cases}$

Remark that the matrix $\left(\frac{A_{i,j}}{\sqrt{d(i)d(j)}}\right)_{i,j}$ is symmetric, stochastic and hence have real eigenvalues, the largest one being equal to $ 1$ . Nevertheless, a multigraph is not reconstructible from this distance as replacing every edge by $ k $ parallel edges does not affect the distances between the vertices.

Include dependency graph for netcut.h:

This graph shows which files directly or indirectly include this file:

Classes

class TriangularMatrix
Triangular matrix handling as a symmetric square matrix. More...
class RectangularMatrix
Rectangular matrix. More...
struct Classifier
Class used to spread vertices in classes. More...
struct Locals
Locals of the embedder. More...
class EmbedRnGraph
Topological graph embedded in $\mathbb{R}^n$ . More...
class SplitGraph
Class used to partition a graph using a factorial embedding in $\mathbb{R}^{n-1}$ . More...

Defines

#define SEUIL 0.00001

Functions

int & useDistance ()
int diag (double **Coords, int nb_vertex, double **Distances, svector< double > &EigenValues, bool Project=true)

Define Documentation

#define SEUIL 0.00001

Threshold for clustering optimization termination.

Clustering optimization process is repeated until the inertia is modified by less than SEUIL

Function Documentation

int diag	(	double **	dis,
		int	NumberOfPoints,
		double **	Distances,
		svector< double > &	EigenValues,
		bool	project
	)

Isometrically embed a set of points with given distances among them in the Euclidean space $\mathbb{R}^n$ .

Parameters:

	dis	coordinates of the points (returned value)
	NumberOfPoints	number of points > 2
	Distances	distances among the points
	EigenValues	eigenvalues of `dis` (returned value)
	project	indicates if one should project the matrix of distances before putting it in diagonal form (always true except when using the Laplacian)

Actions:

copies the Distances matrix into the dis matrix,
call ComputeBilinearForm() to compute the projection matrix dis to be put in diagonal form
compute the trace of dis
call symqr() to compute the spectrum of dis
normalise the coordinates
compute the multiplicities of the eigenvalues and print some useful information.

See also:: ComputeBilinearForm() and symqr()

int& useDistance ( )

Generated on Thu Jan 31 16:51:14 2008 for Pigale by

1.5.4