ca.uqac.lif.ecp

Class CayleyGraph<T extends Event,U>

java.lang.Object

ca.uqac.lif.ecp.graphs.LabelledGraph<T>

ca.uqac.lif.ecp.CayleyGraph<T,U>

Type Parameters:

T - The type of event this graph has for edge labels

U - The type of the categories in the Cayley Graph

Direct Known Subclasses:

AtomicCayleyGraph

public class CayleyGraph<T extends Event,U>
extends LabelledGraph<T>

Implementation of a Cayley Graph. The vertices of the graph are identified by integers.

Author:

Sylvain Hallé

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	CayleyGraph.IsomorphismException
static class	CayleyGraph.LabelFormatter<X>

Nested classes/interfaces inherited from class ca.uqac.lif.ecp.graphs.LabelledGraph

LabelledGraph.DepthVisitor

Field Summary

Fields inherited from class ca.uqac.lif.ecp.graphs.LabelledGraph

s_maxRecursionSteps

Constructor Summary

Constructors

Constructor and Description
CayleyGraph() Creates an empty graph
CayleyGraph(CayleyGraph<T,U> graph) Creates a copy of a Cayley graph

Method Summary

Modifier and Type	Method and Description
protected boolean	checkMapping(int current_node_id, CayleyGraph<T,U> other_graph, int other_node_id, java.util.Map<java.lang.Integer,java.lang.Integer> mapping)
protected Edge<T>	findEdgeWithLabel(java.util.Set<Edge<T>> edges, T label)
float[][]	getAdjacencyMatrix() Produces the adjacency matrix of the Cayley Graph.
java.util.Map<MathSet<U>,java.lang.Integer>	getClassCardinality(int length, boolean cumulative) Computes the number of traces of a given length that belong to each equivalence class
java.util.Map<java.lang.Integer,java.util.Set<MathSet<U>>>	getClassesByDepth() Produces a map telling what are the equivalence classes reachable at each depth of the Cayley graph
protected void	getClassesByDepth(java.util.Map<java.lang.Integer,java.util.Set<MathSet<U>>> map, java.util.Map<MathSet<U>,java.lang.Integer> visited, java.util.Set<java.lang.Integer> visited_ids, Vertex<T> node, int cur_depth, int max_depth) Produces a map telling what are the equivalence classes reachable at each depth of the Cayley graph
protected Edge<T>	getEdgeWithDestinationId(java.util.Set<Edge<T>> edges, T label, int id)
protected Vertex<T>	getFirstVertexWithLabelling(MathSet<U> eq_class) Gets the first vertex that is labelled with a given equivalence class
CayleyVertexLabelling<U>	getLabelling() Gets the labelling associated to the vertices of the graph
boolean	isIsomorphicTo(CayleyGraph<T,U> other_graph) Determines if some graph is isomorphic to the current graph.
boolean	isIsomorphicToThrowable(CayleyGraph<T,U> other_graph) Same as isIsomorphicTo(CayleyGraph) but throws an exception explaining why the graphs are not isomorphic when they are not.
GraphPlotter<T,U>	plotter() Gets an instance of a plotter for this Cayley graph
void	setLabelFormatter(CayleyGraph.LabelFormatter<U> formatter)
void	setLabelling(CayleyVertexLabelling<U> l) Sets the labelling associated to the vertices of the graph
java.lang.String	toString()

Methods inherited from class ca.uqac.lif.ecp.graphs.LabelledGraph

add, addAll, getDepth, getEdgeCount, getEdges, getInitialVertex, getVertex, getVertexCount, getVertexLabels, getVertexWithId, getVertices, setInitialVertexId

Methods inherited from class java.lang.Object

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

Constructor Detail

CayleyGraph

public CayleyGraph()

Creates an empty graph

CayleyGraph

public CayleyGraph(CayleyGraph<T,U> graph)

Creates a copy of a Cayley graph

Parameters:

graph - The graph to copy

Method Detail

setLabelFormatter

public void setLabelFormatter(CayleyGraph.LabelFormatter<U> formatter)

getAdjacencyMatrix

public float[][] getAdjacencyMatrix()

Produces the adjacency matrix of the Cayley Graph. This matrix is such that entry (i,j) = k if there exist k directed edges from vertex labelled i to vertex labelled j. Although the entries of that matrix are natural numbers, their type is float, as that matrix can be used in algorithms that multiply it by a vector of floats.

Overrides:

getAdjacencyMatrix in class LabelledGraph<T extends Event>

Returns:

The matrix

getFirstVertexWithLabelling

protected Vertex<T> getFirstVertexWithLabelling(MathSet<U> eq_class)

Gets the first vertex that is labelled with a given equivalence class

Parameters:

eq_class - The equivalence class

Returns:

The first vertex found, null if no vertex exists with that category

plotter

public GraphPlotter<T,U> plotter()

Gets an instance of a plotter for this Cayley graph

Returns:

The plotter

setLabelling

public void setLabelling(CayleyVertexLabelling<U> l)

Sets the labelling associated to the vertices of the graph

Parameters:

l - The labelling

getLabelling

public CayleyVertexLabelling<U> getLabelling()

Gets the labelling associated to the vertices of the graph

Returns:

The labelling

getClassCardinality

public java.util.Map<MathSet<U>,java.lang.Integer> getClassCardinality(int length,
                                                                       boolean cumulative)

Computes the number of traces of a given length that belong to each equivalence class

Parameters:

length - The length

cumulative - If set to true, will compute the number of traces of length at most length (instead of exactly of length length)

Returns:

A map telling how many traces there are for each equivalence class

isIsomorphicTo

public boolean isIsomorphicTo(CayleyGraph<T,U> other_graph)

Determines if some graph is isomorphic to the current graph. The two graphs are isomorphic if there exists a one-to-one mapping between the vertices of the two graphs, such that their labelled transition function is identical modulo this mapping.

This method is not used for test case generation, but is useful to perform unit tests to check the output of various graph solvers.

Parameters:

other_graph - The other graph

Returns:

true if they are isomorphic, false otherwise

isIsomorphicToThrowable

public boolean isIsomorphicToThrowable(CayleyGraph<T,U> other_graph)
                                throws CayleyGraph.IsomorphismException

Same as isIsomorphicTo(CayleyGraph) but throws an exception explaining why the graphs are not isomorphic when they are not.

Parameters:

other_graph - The other graph

Returns:

true if they are isomorphic, false otherwise

Throws:

CayleyGraph.IsomorphismException

checkMapping

protected boolean checkMapping(int current_node_id,
                               CayleyGraph<T,U> other_graph,
                               int other_node_id,
                               java.util.Map<java.lang.Integer,java.lang.Integer> mapping)
                        throws CayleyGraph.IsomorphismException

Throws:

CayleyGraph.IsomorphismException

findEdgeWithLabel

protected Edge<T> findEdgeWithLabel(java.util.Set<Edge<T>> edges,
                                    T label)

getEdgeWithDestinationId

protected Edge<T> getEdgeWithDestinationId(java.util.Set<Edge<T>> edges,
                                           T label,
                                           int id)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

getClassesByDepth

public java.util.Map<java.lang.Integer,java.util.Set<MathSet<U>>> getClassesByDepth()

Produces a map telling what are the equivalence classes reachable at each depth of the Cayley graph

getClassesByDepth

protected void getClassesByDepth(java.util.Map<java.lang.Integer,java.util.Set<MathSet<U>>> map,
                                 java.util.Map<MathSet<U>,java.lang.Integer> visited,
                                 java.util.Set<java.lang.Integer> visited_ids,
                                 Vertex<T> node,
                                 int cur_depth,
                                 int max_depth)

Produces a map telling what are the equivalence classes reachable at each depth of the Cayley graph

Parameters:

map -

visited -

visited_ids -

node -

cur_depth -

max_depth -