peersim.graph
Class GraphAlgorithms

java.lang.Object
  peersim.graph.GraphAlgorithms

public class GraphAlgorithms
extends java.lang.Object

Implements graph algorithms. The current implementation is NOT thread safe. Some algorithms are not static, many times the result of an algorithm can be read from non-static fields.

Field Summary

static int	BLACK
java.util.Set<java.lang.Integer>	cluster output of some algorithms is passed here
int[]	color output of some algorithms is passed here
int[]	d output of some algorithms is passed here
static int	GREY
int[]	root output of some algorithms is passed here
static int	WHITE

Constructor Summary

GraphAlgorithms()

Method Summary

static double	clustering(Graph g, int i) Calculates the clustering coefficient for the given node in the given graph.
void	dist(Graph g, int i) In d[j] returns the length of the shortest path between i and j.
void	flooding(Graph g, int[] b, int k) Performs flooding from given node.
static void	multicast(Graph g, int[] b, java.util.Random r) Performs anti-entropy epidemic multicasting from node 0.
java.util.Map	tarjan(Graph g) Returns the strongly connected cluster roots with size as a value.
java.util.Map	weaklyConnectedClusters(Graph g) Returns the weakly connected cluster indexes with size as a value.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

root

public int[] root

output of some algorithms is passed here

WHITE

public static final int WHITE

See Also:

Constant Field Values

GREY

public static final int GREY

See Also:

Constant Field Values

BLACK

public static final int BLACK

See Also:

Constant Field Values

color

public int[] color

output of some algorithms is passed here

cluster

public java.util.Set<java.lang.Integer> cluster

output of some algorithms is passed here

d

public int[] d

output of some algorithms is passed here

Constructor Detail

GraphAlgorithms

public GraphAlgorithms()

Method Detail

weaklyConnectedClusters

public java.util.Map weaklyConnectedClusters(Graph g)

Returns the weakly connected cluster indexes with size as a value. Cluster membership can be seen from the content of the array color; each node has the cluster index as color. The cluster indexes carry no information; we guarantee only that different clusters have different indexes.

dist

public void dist(Graph g,
                 int i)

In d[j] returns the length of the shortest path between i and j. The value -1 indicates that j is not accessible from i.

clustering

public static double clustering(Graph g,
                                int i)

Calculates the clustering coefficient for the given node in the given graph. The clustering coefficient is the number of edges between the neighbours of i divided by the number of possible edges. If the graph is directed, an exception is thrown. If the number of neighbours is 1, returns 1. For zero neighbours returns NAN.

Throws:

java.lang.IllegalArgumentException - if g is directed

multicast

public static void multicast(Graph g,
                             int[] b,
                             java.util.Random r)

Performs anti-entropy epidemic multicasting from node 0. As a result the number of nodes that have been reached in cycle i is put into b[i]. The number of cycles performed is determined by b.length. In each cycle each node contacts a random neighbour and exchanges information. The simulation is generational: when a node contacts a neighbor in cycle i, it sees their state as in cycle i-1, besides, all nodes update their state at the same time point, synchronously.

flooding

public void flooding(Graph g,
                     int[] b,
                     int k)

Performs flooding from given node. As a result b[i] contains the number of nodes reached in exactly i steps, and always b[0]=1. If the maximal distance from k is lower than b.length, then the remaining elements of b are zero.

tarjan

public java.util.Map tarjan(Graph g)

Returns the strongly connected cluster roots with size as a value. Cluster membership can be seen from the content of the array root; each node has the root of the strongly connected cluster it belongs to. A word of caution: for large graphs that have a large diameter and that are strongly connected (such as large rings) you can get stack overflow because of the large depth of recursion.