SourceForge Logo
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.

Eigenspaces dimensions optimization. Optimize eigenspaces dimensions over the distances defined on the cellular algebra $ \mathfrak{A} $ generated by the adjacency matrix $ A $
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:




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

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)
  • 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  doxygen 1.5.4