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

EmbedRnGraph Class Reference

Inheritance diagram for EmbedRnGraph:

[legend]

Collaboration diagram for EmbedRnGraph:

[legend]

List of all members.

Detailed Description

Topological graph embedded in $\mathbb{R}^n$ .

Public Member Functions

int ComputeCzekanovskiDistances ()
int ComputeAdjacenceMatrix ()
double ComputeCzekanovskiDistance (int vertex1, int vertex2)
int ComputeOrientDistances ()
int ComputeInOutList ()
double ComputeInDist (int vertex1, int vertex2)
double ComputeOutDist (int vertex1, int vertex2)
int ComputeAdjacenceDistances ()
int ComputeLaplacianDistances ()
int ComputeAdjacenceMDistances ()
int ComputeBisectDistances ()
int ComputeR2Distances ()
int ComputeQDistances ()
EmbedRnGraph (Graph &G, int usedDistance)
~EmbedRnGraph ()

Public Attributes

Prop< short > vcolor
Prop< long > vlabel
Prop< int > ewidth
Prop< short > ecolor
Prop< long > elabel
svector< int > degree
int ** vvadj
int ** inList
int ** outList
double ** Distances
double ** Coords
bool ok
svector< int > indegree
svector< int > outdegree
svector< double > EigenValues

Private Member Functions

void init (int usedDistance)
void release ()

Related Functions

(Note that these are not member functions.)

int Embed3d (TopologicalGraph &G0, int usedDistance)

Constructor & Destructor Documentation

EmbedRnGraph	(	Graph &	G,
		int	usedDistance
	)			`[inline]`

Constructor.

Parameters:

Graph to be embedded

~EmbedRnGraph ( ) [inline]

Destructor.

Member Function Documentation

int ComputeCzekanovskiDistances ( )

Computes Czekanovski-Dice distances.

$d^2(i,j)=1-\frac{|N(i)\cap N(j)|}{|N(i)|+|N(j)|},$

where $ N(i) $ is the set including $ i $ and its neighbors.

int ComputeAdjacenceMatrix ( )

Computes the vertex/vertex adjacency matrix.

double ComputeCzekanovskiDistance	(	int	vertex1,
		int	vertex2
	)

Computes Czekanovski-Dice distances between two vertices.

$d^2(i,j)=1-\frac{|N(i)\cap N(j)|}{|N(i)|+|N(j)|},$

where $ N(i) $ is the set including $ i $ and its neighbors.

int ComputeOrientDistances ( )

Computes oriented distances.

$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)|},$

where $ N^-(i) $ is the set including $ i $ and its incoming neighbors, and $ N^+(i) $ is the set including $ i $ and its outgoing neighbors.

int ComputeInOutList ( )

Computes incoming and outgoing neighbor sets.

double ComputeInDist	(	int	vertex1,
		int	vertex2
	)

Computes the part of the oriented distance due to incoming edges.

$d^2(i,j)=1-\frac{|N^-(i)\cap N^-(j)|}{|N^-(i)|+|N^-(j)|},$

where $ N^-(i) $ is the set including $ i $ and its incoming neighbors.

double ComputeOutDist	(	int	vertex1,
		int	vertex2
	)

Computes the part of the oriented distance due to outgoing edges.

$d^2(i,j)=1-\frac{|N^+(i)\cap N^+(j)|}{|N^+(i)|+|N^+(j)|},$

where $ N^+(i) $ is the set including $ i $ and its outgoing neighbors.

int ComputeAdjacenceDistances ( )

Computes adjacency distances.

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

int ComputeLaplacianDistances ( )

Computes Laplacian distances on the complement graph.

Actually computes the bilinear form corresponding to the Laplacian distance on the complement graph:

$b(i,j)=\begin{cases} n-d(i),&\text{if $i=j$}\\ 0,&\text{if $i$ and $j$ are adjacent}\\ -1,&\text{otherwise} \end{cases}$

It is semi-definite positive, as $B=\bar{D}\bar{D}^{\rm t}$ if $\bar{D}$ is the oriented adjacency matrix of the complement graph for any arbitrary orientation.

The distance corresponding to this bilinear form is:

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

int ComputeAdjacenceMDistances ( )

Computes translated adjacency distances.

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

int ComputeBisectDistances ( )

Computes bisection distances.

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

where $ d(i) $ is the degree of $ i $

int ComputeR2Distances ( )

Computes distances in $\mathbb{R}^2$ .

$d^2(i,j)=x^2(i)+y^2(i),$

where $ x(i) $ and $ y(i) $ are the coordinates of $ i $ in the plane.

int ComputeQDistances ( )

void init ( int usedDistance ) [private]

Class initialization.

Computes a distance among the vertices of the graph and embed it in $\mathbb{R}^{n-1}$ .

void release ( ) [private]

Member destructions.

release the memory

Friends And Related Function Documentation

int Embed3d	(	TopologicalGraph &	G0,
		int	usedDistance
	)			`[related]`

Defines the distance that will be used to isometrically embed the graph in $\mathbb{R}^{n-1}$ .

The returned reference has the following meaning:

0 Czekanovski-Dice distance
1 Bisection distance
2 Adjacency distance
3 Translated adjacency distance
4 Laplacian distance
5 Oriented distance
6 R2 distance
See also:
EmbedRnGraph::init() Embed the graph in $\mathbb{R}^{n-1}$ and fill the coordinates of the point in an $\mathbb{R}^3$ projection

Parameters:

G0 Refrence to the topologcal graph to embed

Precondition:
The graph should have at least 3 vertices and 2 edges

Member Data Documentation

Prop<short> vcolor

colors of the vertices

Prop<long> vlabel

labels of the vertices

Prop<int> ewidth

width of the edges

Prop<short> ecolor

colors of the edges

Prop<long> elabel

labels of the edges

svector<int> degree

degrees of the vertices

int** vvadj

vertex/vertex sorted adjacency

int** inList

incoming adjacency lists

int** outList

outgoing adjacency lists

double** Distances

squared Euclidean distances

double** Coords

coordinates in $\mathbb{R}^{n-1}$

bool ok

computation status

svector<int> indegree

indegrees of the vertices

svector<int> outdegree

outdegrees of the vertices

svector<double> EigenValues

eigenvalues

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

1.5.4