fr.umlv.roadcoloring.graph
Class QuotientGraph

java.lang.Object
  extended by fr.umlv.roadcoloring.graph.Graph
      extended by fr.umlv.roadcoloring.graph.QuotientGraph

public class QuotientGraph
extends Graph

Manage the quotient graph created in each iteration The quotient graph is like the initial graph but collapses nodes with the same class

Author:
fsikora

Field Summary
 
Fields inherited from class fr.umlv.roadcoloring.graph.Graph
BLUEEDGE, REDEDGE
 
Constructor Summary
QuotientGraph(Graph g)
          Construct the quotient graph from the initial graph (reduce nodes)
 
Method Summary
protected  void computeIndexes()
          Run the computation of indexes, i.e. the levels or each nodes (distance to the circle, root of the tree) fill the data tab.
protected  void edgeSwap(int node)
          flip the edge of node
protected  StablePair findStablePair()
          find and return a stable pair in the graph compute the distance of each nodes to circles made a threatman exchange if necessary for finding a stable pair
 int getQuotientSize()
          Number of node in the quotient graph
 
Methods inherited from class fr.umlv.roadcoloring.graph.Graph
browse, coloring, dotty, get, getBlue, getClasses, getNodeClass, getRed, getSize, getSucessorByRed, isAcceptable, isAperiodic, isStronglyConnected, setBlue, setRed, toDot, toString, verifySyncWord
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

QuotientGraph

public QuotientGraph(Graph g)
Construct the quotient graph from the initial graph (reduce nodes)

Parameters:
g - initial graph
Method Detail

getQuotientSize

public int getQuotientSize()
Number of node in the quotient graph

Returns:
size

edgeSwap

protected void edgeSwap(int node)
flip the edge of node

Overrides:
edgeSwap in class Graph
Parameters:
node - node to be flip

findStablePair

protected StablePair findStablePair()
find and return a stable pair in the graph compute the distance of each nodes to circles made a threatman exchange if necessary for finding a stable pair

Returns:
a stable pair (2 nodes)

computeIndexes

protected void computeIndexes()
Run the computation of indexes, i.e. the levels or each nodes (distance to the circle, root of the tree) fill the data tab. fill the maxNodes list with a list of nodes with max level