bcds.phison.gm
Class CheegerConstantBruteForce<V,E>

java.lang.Object
  bcds.phison.gm.GraphMetricBase<V,E>
      bcds.phison.gm.CheegerConstantBruteForce<V,E>

All Implemented Interfaces:

GraphMetric<V,E>, WithEnvParams

public class CheegerConstantBruteForce<V,E>
extends GraphMetricBase<V,E>
implements GraphMetric<V,E>

XXX Computes ........... Descripcion temporal. ... Isoperimetric constant. Esencia: Dado un grafo G y un subrafo H de tamanho m, encontrar cuantos enlaces de los elementos en H apuntan hacia nodos que no estan en H (es decir, cuantos "puentes" aportan al exterior). A partir de esto se puede calcular la media del aporte por nodo, por ejemplo.

Author:

Juan Segovia S.

Constructor Summary

CheegerConstantBruteForce()
Default constructor.

CheegerConstantBruteForce(SimGraph<V,E> g, Environ env)
Creates a new instance and calls setup to complete the initialization.

Method Summary

java.lang.String	getDescription() Returns a string describing the metric, for example, article where it has been published, URL where to find reference implementation, etc.
java.lang.Object[]	getEnvParams() Returns the environment parameters used by this class.
double	getGraphMetric() Returns the network diameter.
java.lang.String	getLabel() Returns the string "Cheeger constant (brute force)".
double	getMeanCheeger() Returns mean (|EDGES(S, ~S)| / |S|)
boolean	isApplicableTo(MetricTarget m) Returns true if m is MetricTarget.GRAPH.
void	run() Default implementation.
void	run(int m)
void	setup(SimGraph<V,E> g, Environ env) Makes sure all links in the topology are bi-directional.

Methods inherited from class bcds.phison.gm.GraphMetricBase

dump, getEdgeMetric, getEnviron, getGraph, getGraphMetricStdev, getName, getNodeMetric

Methods inherited from class java.lang.Object

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

Methods inherited from interface bcds.phison.gm.GraphMetric

dump, getEdgeMetric, getGraphMetricStdev, getNodeMetric

Methods inherited from interface bcds.phison.WithEnvParams

getEnviron, getName

Constructor Detail

CheegerConstantBruteForce

public CheegerConstantBruteForce()

Default constructor.

CheegerConstantBruteForce

public CheegerConstantBruteForce(SimGraph<V,E> g,
                                 Environ env)

Creates a new instance and calls setup to complete the initialization.

Method Detail

isApplicableTo

public boolean isApplicableTo(MetricTarget m)

Returns true if m is MetricTarget.GRAPH.

Specified by:

isApplicableTo in interface GraphMetric<V,E>

Overrides:

isApplicableTo in class GraphMetricBase<V,E>

setup

public void setup(SimGraph<V,E> g,
                  Environ env)

Makes sure all links in the topology are bi-directional.

Specified by:

setup in interface GraphMetric<V,E>

Overrides:

setup in class GraphMetricBase<V,E>

Throws:

java.lang.IllegalArgumentException - if there a exists a link with only one direction.

run

public void run()

Description copied from class: GraphMetricBase

Default implementation. Does nothing.

Specified by:

run in interface GraphMetric<V,E>

Overrides:

run in class GraphMetricBase<V,E>

run

public void run(int m)

Parameters:

m - the subgroup size.

getGraphMetric

public double getGraphMetric()

Returns the network diameter.

Specified by:

getGraphMetric in interface GraphMetric<V,E>

Overrides:

getGraphMetric in class GraphMetricBase<V,E>

getMeanCheeger

public double getMeanCheeger()

Returns mean (|EDGES(S, ~S)| / |S|)

getLabel

public java.lang.String getLabel()

Returns the string "Cheeger constant (brute force)".

Specified by:

getLabel in interface GraphMetric<V,E>

getDescription

public java.lang.String getDescription()

Description copied from interface: GraphMetric

Returns a string describing the metric, for example, article where it has been published, URL where to find reference implementation, etc.

Specified by:

getDescription in interface GraphMetric<V,E>

getEnvParams

public java.lang.Object[] getEnvParams()

Returns the environment parameters used by this class. The parameters are prefixed with "BrandesBC." and are:

• subset_size (default: 1): The size of the subsets to generate. Must be in the range [1..floor(|V|/2)].
• verbose (default: false): Prints each subset and the number of "bridges" it has to the rest of the nodes.

Specified by:

getEnvParams in interface WithEnvParams

Overrides:

getEnvParams in class GraphMetricBase<V,E>