unikl.disco.nc
Class TurnProhibition

java.lang.Object
  extended by unikl.disco.nc.TurnProhibition

public class TurnProhibition
extends java.lang.Object

Class implementing the full version of the turn-prohibition algorithm described in

Contains methods for determining the sets of prohibited (and permitted) turns and to update a given server graph accordingly.

Author:
Frank A. Zdarsky

Field Summary
protected  edu.uci.ics.jung.graph.impl.DirectedSparseGraph network_graph
          The network graph on which the turn prohibition algorithm runs
protected  java.util.Comparator node_comparator
          A comparator comparing the degree of nodes
protected  java.util.Map node_degrees
          A map of nodes to node degrees
protected  java.util.List node_queue
          A queue of nodes sorted by ascending node degree
protected  java.util.Set permitted_turns
          The set of permitted turns
protected  java.util.Set prohibited_turns
          The set of prohibited turns
protected  java.util.Set visited_links
          The set of links visited by the algorithm
protected  java.util.Set visited_nodes
          The set of nodes visited by the algorithm
 
Constructor Summary
TurnProhibition(edu.uci.ics.jung.graph.impl.DirectedSparseGraph network_graph)
          Creates a turn prohibition instance for the specified network graph which must be bidirectional (i.e. a directional in which for each link (u,v) there exists exactly one link (v,u)).
 
Method Summary
 void addPermittedTurns(edu.uci.ics.jung.graph.impl.DirectedSparseGraph server_graph, java.util.Map link_server_map, java.util.Map router_turns_map)
          Adds the turns contained in the current permission set to the specified server_graph, creating servers if necessary.
 java.util.Set getPermittedTurns()
          Returns the set of permitted turns (turn = a Pair instance containing two edges) computed during the last invokation of runTurnProhibition().
 java.util.Set getProhibitedTurns()
          Returns the set of prohibited turns (turn = a Pair instance containing two edges) computed during the last invokation of runTurnProhibition().
 void removeProhibitedTurns(edu.uci.ics.jung.graph.impl.DirectedSparseGraph server_graph, java.util.Map link_server_map, java.util.Map router_turns_map)
          Removes the turns contained in the current prohibition set from the specified server_graph, deleting servers that are no longer connected.
 java.util.Set runTurnProhibition()
          Applies the turn-prohibition algorithm to the current network graph and returns a set of prohibited turns.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

network_graph

protected edu.uci.ics.jung.graph.impl.DirectedSparseGraph network_graph
The network graph on which the turn prohibition algorithm runs


node_comparator

protected java.util.Comparator node_comparator
A comparator comparing the degree of nodes


visited_nodes

protected java.util.Set visited_nodes
The set of nodes visited by the algorithm


visited_links

protected java.util.Set visited_links
The set of links visited by the algorithm


permitted_turns

protected java.util.Set permitted_turns
The set of permitted turns


prohibited_turns

protected java.util.Set prohibited_turns
The set of prohibited turns


node_degrees

protected java.util.Map node_degrees
A map of nodes to node degrees


node_queue

protected java.util.List node_queue
A queue of nodes sorted by ascending node degree

Constructor Detail

TurnProhibition

public TurnProhibition(edu.uci.ics.jung.graph.impl.DirectedSparseGraph network_graph)
Creates a turn prohibition instance for the specified network graph which must be bidirectional (i.e. a directional in which for each link (u,v) there exists exactly one link (v,u)).

Parameters:
network_graph -
Method Detail

runTurnProhibition

public java.util.Set runTurnProhibition()
Applies the turn-prohibition algorithm to the current network graph and returns a set of prohibited turns. Turns are stored as instances of edu.uci.ics.jung.utils.Pair containing the two edges of the network graph that constitute the turn.

Returns:
a set of prohibited turns

getProhibitedTurns

public java.util.Set getProhibitedTurns()
Returns the set of prohibited turns (turn = a Pair instance containing two edges) computed during the last invokation of runTurnProhibition().

Returns:
a set of prohibited turns

getPermittedTurns

public java.util.Set getPermittedTurns()
Returns the set of permitted turns (turn = a Pair instance containing two edges) computed during the last invokation of runTurnProhibition().

Returns:
a set of permitted turns

removeProhibitedTurns

public void removeProhibitedTurns(edu.uci.ics.jung.graph.impl.DirectedSparseGraph server_graph,
                                  java.util.Map link_server_map,
                                  java.util.Map router_turns_map)
Removes the turns contained in the current prohibition set from the specified server_graph, deleting servers that are no longer connected. Updates the corresponding mappings between the network graph and the server_graph.

Parameters:
server_graph - the server graph in which the prohibited turns shall be removed
link_server_map - the mapping from links in the network graph to servers in the server graph; will be modified accordingly
router_turns_map - the mapping from routers in the network graph to servers in the server graph; will be modified accordingly

addPermittedTurns

public void addPermittedTurns(edu.uci.ics.jung.graph.impl.DirectedSparseGraph server_graph,
                              java.util.Map link_server_map,
                              java.util.Map router_turns_map)
Adds the turns contained in the current permission set to the specified server_graph, creating servers if necessary. Updates the corresponding mappings between the network graph and the server_graph.

Parameters:
server_graph - the server graph in which the permitted turns will be added
link_server_map - the mapping from links in the network graph to servers in the server graph; will be modified accordingly
router_turns_map - the mapping from routers in the network graph to servers in the server graph; will be modified accordingly