uka.graph.dlf
Class IncDLF

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

public class IncDLF

extends DLF

Incremental graph coloring algorithm. IncDLF is similar to DLF with the difference that IncDLF can restore a coloring with incremental changes instead of starting the algorithm from scratch.

 Collective procedure: Incremental DLF for node k.
    Precondition: Node k is colored with color c.
    Precondition: All neighbors of k are marked active.

    If there is a color nc < c that is not used:
       Set c to nc.

    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 color c produces no conflict:
       Set accept to TRUE.
       For all active neighbors n with higher degree:
          Call: Receive reply message m from neighbor n.
          If received message m was CANCEL():
             Set accept to FALSE.

       If accept:
          Send message COLOR(c) to all neighbors.
       Else:
          Send message CANCEL() to all active neighbors.

       For all active neighbors n with lower or equal degree:
          Call: Receive reply message m from neighbor n.

       If accept:
          Call: Receive missing color messages.
       Else:
          Call: DLF for node k.

    Else if k has heighest priority:
       Send message COLOR(c) to all neighbors.
       Set node k colored.
       Call: Receive reply messages.
       Call: Receive missing color messages.

    Else:
       Send message CANCEL() to all neighbors with less priority
          or no conflict.
       Call: Receive reply messages.
       Call: DLF for node k.

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

   Procedure: Receive reply messages.
     For all active neighbors n with higher priority or no conflict:
       Call: Receive reply message m from neighbor n.

   Procedure: Receive reply message m from neighbor n.
     Receive message m from neighbor n.
     Switch message m:
       COLOR(cn):
          Call: Handle message COLOR(cn).

       CANCEL():
          Do nothing.

   Procedure: Receive missing color messages.
     For each active neighbor n:
       Receive message COLOR(cn) from neighbor n.
       Call: Handle message COLOR(cn) from neighbor n.

   Procedure: Handle message COLOR(cn) from neighbor n.
     Assign color cn to neighbor n.
     Mark color cn as USED.
     Mark neighbor n as not ACTIVE.
 

Author:

Björn-Oliver Hartmann

Nested Class Summary

Nested classes inherited from class uka.graph.ColoringAlgorithm

uka.graph.ColoringAlgorithm.Statistics

Field Summary

Fields inherited from class uka.graph.dlf.DLF

activeNeighbors, colored, neighborColors, rank, rnd, rounds

Fields inherited from class uka.graph.ColoringAlgorithm

channel, node

Constructor Summary

IncDLF(uka.graph.GraphNode node)

Method Summary

void	init()
private boolean	receiveProposals(DLFProposalMessage msg, IntIterator from, IntQueue regularRanks, IntQueue priorityRanks)

Methods inherited from class uka.graph.dlf.DLF

dlf, getRounds, getSmallestPossibleColor, receiveColors, sendColorReply, sendTo, start

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

Constructor Detail

IncDLF

public IncDLF(uka.graph.GraphNode node)

Method Detail

init

public void init()
          throws uka.graph.MessageDeliveryException

Overrides:

init in class DLF

Throws:

uka.graph.MessageDeliveryException

receiveProposals

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

Throws:

uka.graph.MessageDeliveryException