com.sun.sgs.impl.service.nodemap.affinity
Class AbstractLPA

java.lang.Object
  com.sun.sgs.impl.service.nodemap.affinity.BasicState
      com.sun.sgs.impl.service.nodemap.affinity.AbstractLPA

Direct Known Subclasses:

LabelPropagation, SingleLabelPropagation

public abstract class AbstractLPA
extends BasicState

Abstract class implementing parts of the label propagation algorithm used by both the single node and distributed versions.

The following property is supported:

Property: com.sun.sgs.impl.service.nodemap.affinity.numThreads
Default: 4

The number of threads to use while running the algorithm. Set to 1 to run single-threaded.

The logger for the affinity group finding system is named "com.sun.sgs.impl.service.nodemap.affinity".

Set logging to Level.FINEST for a trace of the algorithm (very verbose and slow). Set logging to Level.FINER to see the final labeled graph. Set logging to Level.FINE for any errors or unexpected conditions encountered during the run.

Nested Class Summary

Nested classes/interfaces inherited from class com.sun.sgs.impl.service.nodemap.affinity.BasicState

BasicState.State

Field Summary

static int	DEFAULT_NUM_THREADS The default value for the number of threads to use.
protected ExecutorService	executor Our executor, for running tasks in parallel.
protected edu.uci.ics.jung.graph.UndirectedGraph<LabelVertex,WeightedEdge>	graph The graph in which we're finding communities.
protected int	iterations The number of iterations required for the last run.
protected long	localNodeId The local node id.
protected static LoggerWrapper	logger Our logger.
static String	NUM_THREADS_PROPERTY The property name for the number of threads to use.
protected int	numThreads The number of threads this algorithm should use.
protected static String	PROP_NAME Our base property name.
protected Random	ran A random number generator, to break ties.
protected List<LabelVertex>	vertices For now, we're only grabbing the vertices of interest at the start of the algorithm.

Fields inherited from class com.sun.sgs.impl.service.nodemap.affinity.BasicState

state

Constructor Summary

AbstractLPA(long nodeId, Properties properties)
Constructs a new instance of the label propagation algorithm.

Method Summary

protected abstract void	doOtherInitialization() Perform any algorithm specific initialization for an algorithm run.
protected abstract long	doOtherNeighbors(LabelVertex vertex, Map<Integer,Long> labelMap, StringBuilder logSB) Update the label map with any other neighbors known to a particular algorithm.
protected static Set<AffinityGroup>	gatherGroups(List<LabelVertex> vertices, boolean reinitialize, long gen) Return the affinity groups found within the given vertices, putting all vertices with the same label in a group.
protected void	initializeLPARun(AffinityGraphBuilder builder) Initialize ourselves for a run of the algorithm.
protected boolean	setMostFrequentLabel(LabelVertex vertex, boolean self) Sets the label of vertex to the label used most frequently by vertex's neighbors.

Methods inherited from class com.sun.sgs.impl.service.nodemap.affinity.BasicState

checkForDisabledOrShutdownState, checkForShutdownState, setDisabledState, setEnabledState, setShutdownState

Methods inherited from class java.lang.Object

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

Field Detail

PROP_NAME

protected static final String PROP_NAME

Our base property name.

See Also:

Constant Field Values

logger

protected static final LoggerWrapper logger

Our logger. Note this is shared between graph builders and group finders.

NUM_THREADS_PROPERTY

public static final String NUM_THREADS_PROPERTY

The property name for the number of threads to use.

See Also:

Constant Field Values

DEFAULT_NUM_THREADS

public static final int DEFAULT_NUM_THREADS

The default value for the number of threads to use.

See Also:

Constant Field Values

localNodeId

protected final long localNodeId

The local node id.

ran

protected final Random ran

A random number generator, to break ties.

executor

protected final ExecutorService executor

Our executor, for running tasks in parallel.

numThreads

protected final int numThreads

The number of threads this algorithm should use.

iterations

protected int iterations

The number of iterations required for the last run.

graph

protected volatile edu.uci.ics.jung.graph.UndirectedGraph<LabelVertex,WeightedEdge> graph

The graph in which we're finding communities. This is a live graph for some graph builders; we have to be able to handle changes.

vertices

protected volatile List<LabelVertex> vertices

For now, we're only grabbing the vertices of interest at the start of the algorithm. This could change so we update for each run, but for now it's easiest to leave this list fixed.

Constructor Detail

AbstractLPA

public AbstractLPA(long nodeId,
                   Properties properties)
            throws Exception

Constructs a new instance of the label propagation algorithm.

Parameters:

nodeId - the local node ID

properties - the properties for configuring this service

Throws:

IllegalArgumentException - if numThreads is less than 1

Exception - if any other error occurs

Method Detail

initializeLPARun

protected void initializeLPARun(AffinityGraphBuilder builder)

Initialize ourselves for a run of the algorithm.

Parameters:

builder - the graph producer

doOtherInitialization

protected abstract void doOtherInitialization()

Perform any algorithm specific initialization for an algorithm run.

setMostFrequentLabel

protected boolean setMostFrequentLabel(LabelVertex vertex,
                                       boolean self)

Sets the label of vertex to the label used most frequently by vertex's neighbors. Returns true if vertex's label changed.

Parameters:

vertex - a vertex in the graph

self - true if we should pick our own label if it is in the set of highest labels

Returns:

true if vertex's label is changed, false if it is not changed

doOtherNeighbors

protected abstract long doOtherNeighbors(LabelVertex vertex,
                                         Map<Integer,Long> labelMap,
                                         StringBuilder logSB)

Update the label map with any other neighbors known to a particular algorithm.

Parameters:

vertex - the vertex whose neighbors labels will be examined

labelMap - a map of labels to counts of neighbors using that label

logSB - a StringBuilder for gathering log info about neighbors

Returns:

the highest number of times a particular label is used among the other neighbors, or -1L if there are no other neighbors.

gatherGroups

protected static Set<AffinityGroup> gatherGroups(List<LabelVertex> vertices,
                                                 boolean reinitialize,
                                                 long gen)

Return the affinity groups found within the given vertices, putting all vertices with the same label in a group. The affinity group's id will be the common label of the group. As an optimization, this method can reinitialize the labels in the graph to their initial setting. Each affinity group in the returned set will have the same generation number, which will be gen.

Parameters:

vertices - the vertices that we gather groups from

reinitialize - if true, reinitialize the labels

gen - the generation number

Returns:

an unmodifiable set of affinity groups found in the graph