com.sun.sgs.impl.service.nodemap.affinity.dlpa
Class LabelPropagation

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

All Implemented Interfaces:

LPAClient, Remote

public class LabelPropagation
extends AbstractLPA
implements LPAClient

A distributed implementation of the algorithm presented in "Near linear time algorithm to detect community structures in large-scale networks" by U.N. Raghavan, R. Albert and S. Kumara 2007.

This is the portion of code that is on each application node.

The following properties are supported:

Property: com.sun.sgs.impl.service.nodemap.affinity.server.host
Default: the value of the com.sun.sgs.server.host property, if present, or localhost if this node is starting the server

The name of the host running the NodeMappingServer.

Property: com.sun.sgs.impl.service.nodemap.affinity.server.port
Default: 44537

The network port for the LabelPropagationServer. This value must be no less than 0 and no greater than 65535.

Property: com.sun.sgs.impl.service.nodemap.affinity.client.port
Default: 0 (anonymous port)

The network port for this app node's affinity group finder for communicating with affinity group finders on other app nodes and with the LabelPropagationServer. This value must be no less than 0 and no greater than 65535.

Field Summary

(package private) static String

SERVER_HOST_PROPERTY The property name for the server host.

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

DEFAULT_NUM_THREADS, executor, graph, iterations, localNodeId, logger, NUM_THREADS_PROPERTY, numThreads, PROP_NAME, ran, vertices

Constructor Summary

LabelPropagation(DLPAGraphBuilder builder, WatchdogService wdog, long nodeId, Properties properties)
Constructs a new instance of the label propagation algorithm.

Method Summary

void	disable() Indicates that the affinity group finding system is disabled, so no new data should be collected (old can be disgarded).
protected void	doOtherInitialization() Perform any algorithm specific initialization for an algorithm run.
protected long	doOtherNeighbors(LabelVertex vertex, Map<Integer,Long> labelMap, StringBuilder logSB) Update the label map with any other neighbors known to a particular algorithm.
void	enable() Indicates that the affinity group finding system is enabled, so new data should be collected again.
Set<AffinityGroup>	getAffinityGroups(long runNumber, boolean done) Returns the affinity groups found on this node.
ConcurrentMap<Long,Map<Object,Long>>	getNodeConflictMap() Returns the node conflict map.
ConcurrentMap<Identity,Map<Integer,Long>>	getRemoteLabelMap() Returns the remote label map.
Map<Object,Map<Integer,List<Long>>>	getRemoteLabels(Collection<Object> objIds) Get the labels for all vertices in our affinity graph for identities that have used the given objects.
void	notifyCrossNodeEdges(Collection<Object> objIds, long nodeId) Indicates that the given node probably contains edges to the graph on the local node.
void	prepareAlgorithm(long runNumber) A new run of the algorithm is about to start, so the client nodes should do whatever is necessary to set up for that run.
void	shutdown() Indicates that the affinity group finding system is shutting down, and all local resources should be cleaned up.
void	startIteration(int iteration) Start an iteration of the algorithm.

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

gatherGroups, initializeLPARun, setMostFrequentLabel

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

SERVER_HOST_PROPERTY

static final String SERVER_HOST_PROPERTY

The property name for the server host.

See Also:

Constant Field Values

Constructor Detail

LabelPropagation

public LabelPropagation(DLPAGraphBuilder builder,
                        WatchdogService wdog,
                        long nodeId,
                        Properties properties)
                 throws Exception

Constructs a new instance of the label propagation algorithm.

Parameters:

builder - the graph producer

wdog - the watchdog service, used for error reporting

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

getAffinityGroups

public Set<AffinityGroup> getAffinityGroups(long runNumber,
                                            boolean done)
                                     throws IOException

Returns the affinity groups found on this node. An empty set is returned if there are no affinity groups on this node. Called by the LPAServer. The LPAServer must call this with done set to true if it intends to start another algorithm run at any time in the future, even if the current run fails.

Specified by:

getAffinityGroups in interface LPAClient

Parameters:

runNumber - the run number provided to the last LPAClient.prepareAlgorithm(long) call

done - true if all iterations are done, allowing cleanup

Returns:

the affinity groups on this node

Throws:

IOException - if there is a communication problem

prepareAlgorithm

public void prepareAlgorithm(long runNumber)
                      throws IOException

A new run of the algorithm is about to start, so the client nodes should do whatever is necessary to set up for that run. When prepared, LPAServer.readyToBegin(long, boolean) should be called. Called by the LPAServer.

Asynchronously prepare ourselves for a run.

Specified by:

prepareAlgorithm in interface LPAClient

Parameters:

runNumber - the number of this algorithm run

Throws:

IOException - if there is a communication problem

notifyCrossNodeEdges

public void notifyCrossNodeEdges(Collection<Object> objIds,
                                 long nodeId)
                          throws IOException

Indicates that the given node probably contains edges to the graph on the local node. This informs the local node where non-local neighbors might reside. If there are no endpoints for the edges on this node, nothing is done. Called by other LPAClients.

Specified by:

notifyCrossNodeEdges in interface LPAClient

Parameters:

objIds - the collection of objects, representing edges, that probably have endpoints to vertices on this node

nodeId - the node with vertices attached to the edges

Throws:

IOException - if there is a communication problem

startIteration

public void startIteration(int iteration)
                    throws IOException

Start an iteration of the algorithm. When finished, LPAServer.finishedIteration(long, boolean, boolean, int) should be called. Called by the LPAServer.

This method is run asynchronously.

Specified by:

startIteration in interface LPAClient

Parameters:

iteration - the iteration number

Throws:

IOException - if there is a communication problem

getRemoteLabels

public Map<Object,Map<Integer,List<Long>>> getRemoteLabels(Collection<Object> objIds)
                                                    throws IOException

Get the labels for all vertices in our affinity graph for identities that have used the given objects. If no such vertices exist, nothing is done and an empty map is returned. Called by other LPAClients.

Specified by:

getRemoteLabels in interface LPAClient

Parameters:

objIds - the collection of objects, representing potential graph edges, that we want neighbor node information for

Returns:

a map of Objects (one for each element of objIds) to neighbor labels, with a count of each use

Throws:

IOException - if there is a communication problem

enable

public void enable()

Indicates that the affinity group finding system is enabled, so new data should be collected again.

Specified by:

enable in interface LPAClient

disable

public void disable()

Indicates that the affinity group finding system is disabled, so no new data should be collected (old can be disgarded).

Specified by:

disable in interface LPAClient

shutdown

public void shutdown()

Indicates that the affinity group finding system is shutting down, and all local resources should be cleaned up.

Specified by:

shutdown in interface LPAClient

doOtherInitialization

protected void doOtherInitialization()

Perform any algorithm specific initialization for an algorithm run.

Initialize our vertex conflicts. This needs to happen before we send our vertex conflict information to other nodes in response to an prepareAlgorithm call from the server, and before any notifyCrossNodeEdges calls.

Specified by:

doOtherInitialization in class AbstractLPA

doOtherNeighbors

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

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

Specified by:

doOtherNeighbors in class AbstractLPA

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.

getNodeConflictMap

public ConcurrentMap<Long,Map<Object,Long>> getNodeConflictMap()

Returns the node conflict map.

Returns:

the node conflict map.

getRemoteLabelMap

public ConcurrentMap<Identity,Map<Integer,Long>> getRemoteLabelMap()

Returns the remote label map.

Returns:

the remote label map