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

Distances used in Pigale

The following distances are used to embed a graph in Rⁿ

$\text{Czekanovski-Dice distance}$	$\qquad d^2(i,j)=1-\frac{\|N(i)\cap N(j)\|}{\|N(i)\|+\|N(j)\|}$
$\text{Oriented distance}$	$\qquad d^2(i,j)=1-\frac{\|N^-(i)\cap N^-(j)\|}{\|N^-(i)\|+\|N^-(j)\|}-\frac{\|N^+(i)\cap N^+(j)\|}{\|N^+(i)\|+\|N^+(j)\|}$
$\text{Adjacency distance (not Euclidean)}$	$\qquad d^2(i,j)=\begin{cases} 0,&\text{if $i=j$ or $i$ and $j$ are adjacent}\\ 1,&\text{otherwise} \end{cases}$
$\text{Translated adjacency distance}$	$\qquad d^2(i,j)=\begin{cases} 0,&\text{if $i=j$}\\ 1-\frac{2}{n},&\text{if $i$ and $j$ are adjacent}\\ 1,&\text{otherwise} \end{cases}$
$\text{Bisection distance}$	$\qquad d^2(i,j)=\begin{cases} 0,&\text{if $i=j$}\\ 1-\frac{2}{d(i)+d(j)+2},&\text{if $i$ and $j$ are adjacent}\\ 1,&\text{otherwise} \end{cases}$
$\mathbb{R}^2\text{distance}$	$\qquad d^2(i,j)=x^2(i)+y^2(i)$
$\text{Laplacian distance}$	$\qquad d^2(i,j)=\begin{cases} 0,&\text{if $i=j$}\\ 2n-d(i)-d(j),&\text{if $i$ and $j$ are adjacent}\\ 2n-d(i)-d(j)+2,&\text{otherwise} \end{cases}$
$\text{Q distance}$	$\qquad 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}$

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

doxygen

1.5.4