ca.uqac.lif.ecp.graphs

Class LabelledGraph<T extends Event>

java.lang.Object

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

Type Parameters:

T - The type of the labels on the edges

Direct Known Subclasses:

CayleyGraph

public class LabelledGraph<T extends Event>
extends java.lang.Object

A graph with labels on its edges

Author:

Sylvain Hallé

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	LabelledGraph.DepthVisitor Graph visitor computing the depth of a graph

Field Summary

Fields

Modifier and Type	Field and Description
static int	s_maxRecursionSteps The maximum number of recursion steps in a graph algorithm

Constructor Summary

Constructors

Constructor and Description
LabelledGraph() Creates an empty graph
LabelledGraph(LabelledGraph<T> graph) Creates a copy of a graph graph

Method Summary

Modifier and Type	Method and Description
void	add(Vertex<T> v) Adds a vertex to this graph.
void	addAll(java.util.Collection<Vertex<T>> vertices) Adds a set of vertices to this graph.
float[][]	getAdjacencyMatrix() Produces the adjacency matrix of the Cayley Graph.
int	getDepth() Gets the depth of the graph.
int	getEdgeCount() Gets the number of edges in the graph
java.util.List<Edge<T>>	getEdges() Gets the list of all edges in the graph
Vertex<T>	getInitialVertex() Gets the initial vertex of the Cayley graph
Vertex<T>	getVertex(int id) Gets the vertex with given ID
int	getVertexCount() Gets the number of vertices in the graph
java.util.List<java.lang.Integer>	getVertexLabels() Fetches the list of all vertex IDs present in the graph
Vertex<T>	getVertexWithId(int id) Gets the vertex with given ID
java.util.Set<Vertex<T>>	getVertices() Gets the set of vertices of this graph
void	setInitialVertexId(int id) Sets the ID of the initial vertex

Methods inherited from class java.lang.Object

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

Field Detail

s_maxRecursionSteps

public static final transient int s_maxRecursionSteps

The maximum number of recursion steps in a graph algorithm

See Also:

Constant Field Values

Constructor Detail

LabelledGraph

public LabelledGraph()

Creates an empty graph

LabelledGraph

public LabelledGraph(LabelledGraph<T> graph)

Creates a copy of a graph graph

Parameters:

graph - The graph to copy

Method Detail

getVertex

public Vertex<T> getVertex(int id)

Gets the vertex with given ID

Parameters:

id - The ID

Returns:

The vertex, or null if no vertex exists with that ID

add

public void add(Vertex<T> v)

Adds a vertex to this graph. If this is the first vertex to be added, it will by default be taken as the initial vertex of the graph.

Parameters:

v - The vertex

addAll

public void addAll(java.util.Collection<Vertex<T>> vertices)

Adds a set of vertices to this graph. If the first vertex is added to an empty graph, it will by default be taken as the initial vertex of the graph.

Parameters:

v - The vertex

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.

Returns:

The matrix

getVertexLabels

public java.util.List<java.lang.Integer> getVertexLabels()

Fetches the list of all vertex IDs present in the graph

Returns:

The list of IDs

getVertexWithId

public Vertex<T> getVertexWithId(int id)

Gets the vertex with given ID

Parameters:

id - The ID

Returns:

The vertex, or null if not found

getEdgeCount

public int getEdgeCount()

Gets the number of edges in the graph

Returns:

The number of edges

getVertexCount

public int getVertexCount()

Gets the number of vertices in the graph

Returns:

The number of vertices

getVertices

public java.util.Set<Vertex<T>> getVertices()

Gets the set of vertices of this graph

Returns:

The set of vertices

getEdges

public java.util.List<Edge<T>> getEdges()

Gets the list of all edges in the graph

Returns:

The list of edges

getInitialVertex

public Vertex<T> getInitialVertex()

Gets the initial vertex of the Cayley graph

Returns:

The initial vertex

setInitialVertexId

public void setInitialVertexId(int id)

Sets the ID of the initial vertex

Parameters:

id - The ID

getDepth

public int getDepth()

Gets the depth of the graph. The depth is defined as the length of the shortest path to the vertex furthest from the start vertex.

Returns:

The length