org.graphstream.algorithm

## Class Centroid

• java.lang.Object
• org.graphstream.algorithm.Centroid
• All Implemented Interfaces:
Algorithm

```public class Centroid
extends java.lang.Object
implements Algorithm```
Compute the centroid of a connected graph.

In a graph G, if d(u,v) is the shortest length between two nodes u and v (ie the number of edges of the shortest path) let m(u) be the sum of d(u,v) for all nodes v of G. Centroid of a graph G is a subgraph induced by vertices u with minimum m(u).

## Requirements

This algorithm needs that APSP algorithm has been computed before its own computation.

## Example

``` import java.io.StringReader;
import java.io.IOException;

import org.graphstream.algorithm.APSP;
import org.graphstream.algorithm.Centroid;
import org.graphstream.graph.Graph;
import org.graphstream.graph.Node;
import org.graphstream.graph.implementations.DefaultGraph;
import org.graphstream.stream.file.FileSourceDGS;

//                     +--- E
// A --- B --- C -- D -|--- F
//                     +--- G

public class CentroidTest {
static String my_graph = "DGS004\n" + "my 0 0\n" + "an A \n" + "an B \n"
+ "an C \n" + "an D \n" + "an E \n" + "an F \n" + "an G \n"
+ "ae AB A B \n" + "ae BC B C \n" + "ae CD C D \n" + "ae DE D E \n"
+ "ae DF D F \n" + "ae DG D G \n";

public static void main(String[] args) throws IOException {
Graph graph = new DefaultGraph("Centroid Test");

FileSourceDGS source = new FileSourceDGS();

APSP apsp = new APSP();
apsp.init(graph);
apsp.compute();

Centroid centroid = new Centroid();
centroid.init(graph);
centroid.compute();

for (Node n : graph.getEachNode()) {
Boolean in = n.getAttribute("centroid");

System.out.printf("%s is%s in the centroid.\n", n.getId(), in ? ""
: " not");
}

// Output will be :
//
// A is not in the centroid
// B is not in the centroid
// C is not in the centroid
// D is in the centroid
// E is not in the centroid
// F is not in the centroid
// G is not in the centroid
}
}
```
`APSP.APSPInfo`
Computational Complexity:
O(n2)
Scientific Reference:
F. Harary, Graph Theory. Westview Press, Oct. 1969. [Online]. Available: http://www.amazon.com/exec/obidos/ redirect?tag=citeulike07-20\&path=ASIN/ 0201410338
• ### Constructor Summary

Constructors
Constructor and Description
`Centroid()`
Build a new centroid algorithm with default parameters.
`Centroid(java.lang.String centroidAttribute)`
Build a new centroid algorithm, specifying the attribute name of the computation result
```Centroid(java.lang.String centroidAttribute, java.lang.Object isInCentroid, java.lang.Object isNotInCentroid)```
Build a new centroid as in `Centroid(String)` but specifying values of centroid membership.
```Centroid(java.lang.String centroidAttribute, java.lang.Object isInCentroid, java.lang.Object isNotInCentroid, java.lang.String apspInfoAttribute)```
Build a new centroid algorithm as in `Centroid(String, Object, Object)` but specifying the name of the attribute where the APSP informations are stored.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`void` `compute()`
Run the algorithm.
`java.lang.String` `defaultResult()`
`java.lang.String` `getAPSPInfoAttribute()`
Get the APSP info attribute name.
`java.lang.String` `getCentroidAttribute()`
Get the name of the attribute where computation result is stored.
`java.lang.Object` `getIsInCentroidValue()`
Get the value of the centroid attribute when element is in the centroid.
`java.lang.Object` `getIsNotInCentroidValue()`
Get the value of the centroid attribute when element is not in the centroid.
`void` `init(org.graphstream.graph.Graph graph)`
Initialization of the algorithm.
`void` `setAPSPInfoAttribute(java.lang.String attribute)`
Set the APSP info attribute name.
`void` `setCentroidAttribute(java.lang.String centroidAttribute)`
Set the name of the attribute where computation result is stored.
`void` `setIsInCentroidValue(java.lang.Object value)`
Set the value of the centroid attribute when element is in the centroid.
`void` `setIsNotInCentroidValue(java.lang.Object value)`
Set the value of the centroid attribute when element is not in the centroid.
• ### Methods inherited from class java.lang.Object

`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### Centroid

`public Centroid()`
Build a new centroid algorithm with default parameters.
• #### Centroid

`public Centroid(java.lang.String centroidAttribute)`
Build a new centroid algorithm, specifying the attribute name of the computation result
Parameters:
`centroidAttribute` - attribute name of the computation result.
• #### Centroid

```public Centroid(java.lang.String centroidAttribute,
java.lang.Object isInCentroid,
java.lang.Object isNotInCentroid)```
Build a new centroid as in `Centroid(String)` but specifying values of centroid membership.
Parameters:
`centroidAttribute` - attribute name of the computation result.
`isInCentroid` - the value of elements centroid attribute when this element is in the centroid.
`isNotInCentroid` - the value of elements centroid attribute when this element is not in the centroid.
• #### Centroid

```public Centroid(java.lang.String centroidAttribute,
java.lang.Object isInCentroid,
java.lang.Object isNotInCentroid,
java.lang.String apspInfoAttribute)```
Build a new centroid algorithm as in `Centroid(String, Object, Object)` but specifying the name of the attribute where the APSP informations are stored.
Parameters:
`centroidAttribute` - attribute name of the computation result.
`isInCentroid` - the value of elements centroid attribute when this element is in the centroid.
`isNotInCentroid` - the value of elements centroid attribute when this element is not in the centroid.
`apspInfoAttribute` - the name of the attribute where the APSP informations are stored
• ### Method Detail

• #### init

`public void init(org.graphstream.graph.Graph graph)`
Description copied from interface: `Algorithm`
Initialization of the algorithm. This method has to be called before the `Algorithm.compute()` method to initialize or reset the algorithm according to the new given graph.
Specified by:
`init` in interface `Algorithm`
Parameters:
`graph` - The graph this algorithm is using.
• #### compute

`public void compute()`
Description copied from interface: `Algorithm`
Run the algorithm. The `Algorithm.init(Graph)` method has to be called before computing.
Specified by:
`compute` in interface `Algorithm`
`Algorithm.init(Graph)`
• #### getAPSPInfoAttribute

`public java.lang.String getAPSPInfoAttribute()`
Get the APSP info attribute name.
Returns:
the name of the attribute where the APSP informations are stored.
• #### setAPSPInfoAttribute

`public void setAPSPInfoAttribute(java.lang.String attribute)`
Set the APSP info attribute name.
Parameters:
`attribute` - the name of the attribute where the APSP informations are stored.
• #### getIsInCentroidValue

`public java.lang.Object getIsInCentroidValue()`
Get the value of the centroid attribute when element is in the centroid. Default value is Boolean.TRUE.
Returns:
the value of elements centroid attribute when this element is in the centroid.
• #### setIsInCentroidValue

`public void setIsInCentroidValue(java.lang.Object value)`
Set the value of the centroid attribute when element is in the centroid. On computation, this value is used to set the centroid attribute.
Parameters:
`value` - the value of elements centroid attribute when this element is in the centroid.
• #### getIsNotInCentroidValue

`public java.lang.Object getIsNotInCentroidValue()`
Get the value of the centroid attribute when element is not in the centroid. Default value is Boolean.FALSE.
Returns:
the value of elements centroid attribute when this element is not in the centroid.
• #### setIsNotInCentroidValue

`public void setIsNotInCentroidValue(java.lang.Object value)`
Set the value of the centroid attribute when element is not in the centroid. On computation, this value is used to set the centroid attribute.
Parameters:
`value` - the value of elements centroid attribute when this element is not in the centroid.
• #### setCentroidAttribute

`public void setCentroidAttribute(java.lang.String centroidAttribute)`
Set the name of the attribute where computation result is stored.
Parameters:
`centroidAttribute` - the name of the element attribute where computation result is stored.
• #### defaultResult

`public java.lang.String defaultResult()`