uka.graph.dlf
Class DLF

java.lang.Object
  uka.graph.ColoringAlgorithm
      uka.graph.dlf.DLF

Direct Known Subclasses:

IncDLF

public class DLF

extends uka.graph.ColoringAlgorithm

The distributed largest first graph coloring algorithm from Marek Kubale and Lukasz Kuszner.

 Collective procedure "Color node k"

 Precondition: Node k is not colored.
 Precondition: All neighbors of k are marked active.

 While (node k is not colored)
    Choose color c as the smalest number [0, 1, ...] not already
       assigned to any neighbor that is not active.
    Choose a random number r;

    Send CHECK(c, deg(k), r) to all active neighbors.
    Receive CHECK(c(n), deg(n), r(n)) from all active neighbors n.

    Compare (c, deg(k), r) against all received parameters.
    If (k has highest priority or color c produces no conflict)
       Send message COLOR(c) to all neighbors.
       Receive a message m from all non-conflicting neighbors.
          (They send these messages, because they cannot know,
          that node k was successful.)
       Set node k colored.
    Else
       Send message CANCEL() to all neighbors with less priority
          and all non-conflicting neighbors.
       Receive a message m from all neighbors with higher priority
          and all non-conflicting neighbors.

    Switch (message m)
       COLOR(cn):
          Assign color c(n) to the corresponding neighbor
             (color c(n) is now marked as used color).
          Mark the corresponding neighbor as being "not active".

       CANCEL():
          Do nothing.
 End of while

 For each active neighbor n:
    Receive message COLOR(c(n)) from neighbor n.
    Assign color c(n) to neighbor n.
    Mark neighbor n as being "not active".

 Postcondition: Node k is colored.
 Postcondition: All neighbors have a color assigned.
 Postcondition: All neighbors are not active.

 With:
    node x has a higher priority than node y  <=>
       (deg(x), r(x), rank(x)) >,>,> (deg(y), r(y), rank(y))

 

Author:

Björn-Oliver Hartmann

Nested Class Summary

Nested classes inherited from class uka.graph.ColoringAlgorithm

uka.graph.ColoringAlgorithm.Statistics

Field Summary

protected IntSet	activeNeighbors
(package private) boolean	colored
protected IntSet	neighborColors
(package private) int	rank
protected java.util.Random	rnd
protected int	rounds The number of rounds necessary to find a valid coloring.

Fields inherited from class uka.graph.ColoringAlgorithm

channel, node

Constructor Summary

DLF(uka.graph.GraphNode node)

Method Summary

protected void	dlf()
int	getRounds()
protected int	getSmallestPossibleColor()
protected void	init()
private void	processColorMessage(DLFColorMessage msg)
protected boolean	receiveColors(IntIterator from)
private boolean	receiveProposals(DLFProposalMessage msg, IntIterator from)
protected void	sendColorReply(boolean colored, int color)
void	sendTo(uka.graph.Message msg, IntIterator to) Sends message to all acitve neighbors.
void	start() Starts the DLF-algorithm.

Methods inherited from class uka.graph.ColoringAlgorithm

registerChannel

Methods inherited from class java.lang.Object

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

Field Detail

rank

final int rank

rounds

protected int rounds

The number of rounds necessary to find a valid coloring. This is used for statistical purpose only.

colored

boolean colored

rnd

protected java.util.Random rnd

activeNeighbors

protected IntSet activeNeighbors

neighborColors

protected IntSet neighborColors

Constructor Detail

DLF

public DLF(uka.graph.GraphNode node)

Method Detail

getRounds

public int getRounds()

Returns:

the number of rounds the DLF-algorithm needed to find a valid coloring.

getSmallestPossibleColor

protected int getSmallestPossibleColor()

Returns:

The smallest possible color for the this node.

start

public final void start()
                 throws uka.graph.MessageDeliveryException

Description copied from class: uka.graph.ColoringAlgorithm

Starts the DLF-algorithm.

Throws:

uka.graph.MessageDeliveryException

See Also:

ColoringAlgorithm.start()

init

protected void init()
             throws uka.graph.MessageDeliveryException

Throws:

uka.graph.MessageDeliveryException

dlf

protected void dlf()
            throws uka.graph.MessageDeliveryException

Throws:

uka.graph.MessageDeliveryException

sendTo

public void sendTo(uka.graph.Message msg,
                   IntIterator to)
            throws uka.graph.MessageDeliveryException

Sends message to all acitve neighbors.

Parameters:

msg - message to sent.

to - neighbor ranks.

Throws:

uka.graph.MessageDeliveryException

receiveProposals

private boolean receiveProposals(DLFProposalMessage msg,
                                 IntIterator from)
                          throws uka.graph.MessageDeliveryException

Throws:

uka.graph.MessageDeliveryException

sendColorReply

protected void sendColorReply(boolean colored,
                              int color)
                       throws uka.graph.MessageDeliveryException

Throws:

uka.graph.MessageDeliveryException

receiveColors

protected boolean receiveColors(IntIterator from)
                         throws uka.graph.MessageDeliveryException

Throws:

uka.graph.MessageDeliveryException

processColorMessage

private void processColorMessage(DLFColorMessage msg)