grph.algo.distance

Class FourSweepIterativeFringeDiameterAlgorithm

java.lang.Object

grph.GrphAlgorithm<java.lang.Integer>

grph.algo.distance.FourSweepIterativeFringeDiameterAlgorithm

All Implemented Interfaces:

java.io.Serializable

public class FourSweepIterativeFringeDiameterAlgorithm
extends GrphAlgorithm<java.lang.Integer>

Computes the diameter of the graph using the heuristic algorithm proposed by Pierluigi Crescenzi, Roberto Grossi, Michel Habib, Leonardo Lanzi and Andrea Marino in “On computing the diameter of real-world undirected graphs”. The result is always exact. This heuristic appears to take linear time on many real world graphs. Its worst case time complexity is O(nm). Assumes that the graph is undirected. It picks a random node and returns the diameter of its connected component (probably the giant connected component if there is one).

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
FourSweepIterativeFringeDiameterAlgorithm()

Method Summary

Modifier and Type	Method and Description
java.lang.Integer	compute(Grph g)
static void	main(java.lang.String[] args)

Methods inherited from class grph.GrphAlgorithm

cacheResultForGraph, getSourceCode

Methods inherited from class java.lang.Object

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

Constructor Detail

FourSweepIterativeFringeDiameterAlgorithm

public FourSweepIterativeFringeDiameterAlgorithm()

Method Detail

compute

public java.lang.Integer compute(Grph g)

Specified by:

compute in class GrphAlgorithm<java.lang.Integer>

main

public static void main(java.lang.String[] args)