fr.umlv.roadcoloring.graph
Class Graph

java.lang.Object
  extended by fr.umlv.roadcoloring.graph.Graph
Direct Known Subclasses:
QuotientGraph

public class Graph
extends java.lang.Object

Manage a graph strongly connected, aperiodic, 2 colored (blue and red) run coloring() for change the coloring in order to have a synchronized word Can be generated randomly if size n, or from a file The syntax of the graph is : n i r b with n size of the graph and, for each node i, the red edge and the blue edge Can be seen by dotty()

Author:
fsikora

Field Summary
protected static byte BLUEEDGE
           
protected static byte REDEDGE
           
 
Constructor Summary
protected Graph(Graph g)
          Create a graph from another graph create array but not the edges
  Graph(int n, java.lang.String generatorPgrm)
          Generate a randomly acceptable graph of size n
  Graph(java.lang.String fileName)
          Create a graph from a file
 
Method Summary
 int browse(int startNode, java.lang.String word)
          Browse the word in the graph, start from the node graph Word is a succession of R or B.
 void coloring()
          eventually change the colloring of the graph in order to be synchronizing compute the quotient graph until it's a size > 1 compute the quotient from the classes.
 void dotty()
          launch dotty and print the graph
protected  void edgeSwap(int node)
          flip the edges of the node
 int get(int index, byte color)
          Get the next by color of index
 int getBlue(int index)
          get the next by blue for index
 int[] getClasses()
          get the classes for each node
protected  int getNodeClass(int node)
          get the class of a node from the initial graph -1 is the status of a node not in a class (so return herself)
 int getRed(int index)
          get the next by red for index
 int getSize()
          get graph size
protected  int getSucessorByRed(int start, int len)
          browse the red edge len time from the start node
 boolean isAcceptable()
          tell if the graph is acceptable (strongly connected and aperiodic)
 boolean isAperiodic()
          tell if the graph is aperiodic
 boolean isStronglyConnected()
          test if this graph is strongly connected
protected  void setBlue(int index, int value)
          set the next by blue of index
protected  void setRed(int index, int value)
          set the next by red of index
 java.lang.String toDot()
          usefull for dotty
 java.lang.String toString()
           
 boolean verifySyncWord(java.lang.String word)
          Check if the word synchronize the graph (if browse the word from each node, they're going on the same node)
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

REDEDGE

protected static final byte REDEDGE
See Also:
Constant Field Values

BLUEEDGE

protected static final byte BLUEEDGE
See Also:
Constant Field Values
Constructor Detail

Graph

public Graph(int n,
             java.lang.String generatorPgrm)
      throws java.io.IOException
Generate a randomly acceptable graph of size n

Parameters:
n - size of graph
generatorPgrm - a program for generate a randomly graph. If null, use Random JDK classes
Throws:
java.io.IOException

Graph

protected Graph(Graph g)
Create a graph from another graph create array but not the edges

Parameters:
g -

Graph

public Graph(java.lang.String fileName)
Create a graph from a file

Parameters:
fileName - name of the graph
Throws:
{@link - IllegalArgumentException} if the graph is not acceptable
Method Detail

getSize

public int getSize()
get graph size

Returns:
graph size

getRed

public int getRed(int index)
get the next by red for index

Parameters:
index - node
Returns:
the next of index by red

getBlue

public int getBlue(int index)
get the next by blue for index

Parameters:
index - node
Returns:
the next of index by blue

get

public int get(int index,
               byte color)
Get the next by color of index

Parameters:
index - node
color - can by BLUEEDGE or REDEDGE
Returns:
the next by color

setRed

protected void setRed(int index,
                      int value)
set the next by red of index

Parameters:
index - start node
value - node next by red

setBlue

protected void setBlue(int index,
                       int value)
set the next by blue of index

Parameters:
index - start node
value - node next by blue

getClasses

public int[] getClasses()
get the classes for each node

Returns:
the array of classes

getNodeClass

protected int getNodeClass(int node)
get the class of a node from the initial graph -1 is the status of a node not in a class (so return herself)

Parameters:
node - node which we seach class
Returns:
the node's class

isStronglyConnected

public boolean isStronglyConnected()
test if this graph is strongly connected

Returns:
true if it's, false else

isAperiodic

public boolean isAperiodic()
tell if the graph is aperiodic

Returns:
true if it is, false else

isAcceptable

public boolean isAcceptable()
tell if the graph is acceptable (strongly connected and aperiodic)

Returns:
true if it's acceptable, false else

coloring

public void coloring()
eventually change the colloring of the graph in order to be synchronizing compute the quotient graph until it's a size > 1 compute the quotient from the classes. Find two node (and more) with same class by stable pair. Find stable pair by computing levels of each node, and perform some exchange if needed at the end of this function, the graph is seems to be synchronizing (a word who synchronized can be found)


edgeSwap

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

Parameters:
node - node to be flip

getSucessorByRed

protected int getSucessorByRed(int start,
                               int len)
browse the red edge len time from the start node

Parameters:
start - start node
len - length in the red edges
Returns:
the end node

browse

public int browse(int startNode,
                  java.lang.String word)
Browse the word in the graph, start from the node graph Word is a succession of R or B. Get the red edge if R, blue edge if B

Parameters:
startNode - start node in the graph
word - word to browse
Returns:
the final state

verifySyncWord

public boolean verifySyncWord(java.lang.String word)
Check if the word synchronize the graph (if browse the word from each node, they're going on the same node)

Parameters:
word - synchronize word to be test
Returns:
true if word synchronize, false else

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object

toDot

public java.lang.String toDot()
usefull for dotty

Returns:
a string wich can be put in dotty program (for visualazing)

dotty

public void dotty()
launch dotty and print the graph