Package org.jgrapht.alg.isomorphism

Class GraphOrdering<V,E>

java.lang.Object

org.jgrapht.alg.isomorphism.GraphOrdering<V,E>

Type Parameters:

V - the type of the vertices

E - the type of the edges

class GraphOrdering<V,E>
extends java.lang.Object

This class represents the order on the graph vertices. There are also some helper-functions for receiving outgoing/incoming edges, etc.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static class	GraphOrdering.GeneralVertexDegreeComparator<V2>

Field Summary

Fields

Modifier and Type	Field	Description
private java.lang.Boolean[][]	adjMatrix
private boolean	cacheEdges
private Graph<V,E>	graph
private int[][]	incomingEdges
private java.util.ArrayList<V>	mapOrderToVertex
private java.util.Map<V,java.lang.Integer>	mapVertexToOrder
private int[][]	outgoingEdges
private int	vertexCount

Constructor Summary

Constructors

Constructor	Description
GraphOrdering(Graph<V,E> graph)
GraphOrdering(Graph<V,E> graph, boolean orderByDegree, boolean cacheEdges)

Method Summary

Modifier and Type	Method	Description
E	getEdge(int v1Number, int v2Number)
int[]	getEdgeNumbers(E e)
Graph<V,E>	getGraph()
int[]	getInEdges(int vertexNumber)
int[]	getOutEdges(int vertexNumber)
V	getVertex(int vertexNumber)	be careful: there's no check against an invalid vertexNumber
int	getVertexCount()
int	getVertexNumber(V v)
boolean	hasEdge(int v1Number, int v2Number)

Methods inherited from class java.lang.Object

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

Field Detail

graph

private Graph<V,E> graph

mapVertexToOrder

private java.util.Map<V,java.lang.Integer> mapVertexToOrder

mapOrderToVertex

private java.util.ArrayList<V> mapOrderToVertex

vertexCount

private int vertexCount

outgoingEdges

private int[][] outgoingEdges

incomingEdges

private int[][] incomingEdges

adjMatrix

private java.lang.Boolean[][] adjMatrix

cacheEdges

private boolean cacheEdges

Constructor Detail

GraphOrdering

public GraphOrdering(Graph<V,E> graph,
                     boolean orderByDegree,
                     boolean cacheEdges)

Parameters:

graph - the graph to be ordered

orderByDegree - should the vertices be ordered by their degree. This speeds up the VF2 algorithm.

cacheEdges - if true, the class creates a adjacency matrix and two arrays for incoming and outgoing edges for fast access.

GraphOrdering

public GraphOrdering(Graph<V,E> graph)

Parameters:

graph - the graph to be ordered

Method Detail

getVertexCount

public int getVertexCount()

Returns:

returns the number of vertices in the graph.

getOutEdges

public int[] getOutEdges(int vertexNumber)

Parameters:

vertexNumber - the number which identifies the vertex v in this order.

Returns:

the identifying numbers of all vertices which are connected to v by an edge outgoing from v.

getInEdges

public int[] getInEdges(int vertexNumber)

Parameters:

vertexNumber - the number which identifies the vertex v in this order.

Returns:

the identifying numbers of all vertices which are connected to v by an edge incoming to v.

hasEdge

public boolean hasEdge(int v1Number,
                       int v2Number)

Parameters:

v1Number - the number of the first vertex v1

v2Number - the number of the second vertex v2

Returns:

exists the edge from v1 to v2

getVertex

public V getVertex(int vertexNumber)

be careful: there's no check against an invalid vertexNumber

Parameters:

vertexNumber - the number identifying the vertex v

Returns:

v

getEdge

public E getEdge(int v1Number,
                 int v2Number)

Parameters:

v1Number - the number identifying the vertex v1

v2Number - the number identifying the vertex v2

Returns:

the edge from v1 to v2

getVertexNumber

public int getVertexNumber(V v)

getEdgeNumbers

public int[] getEdgeNumbers(E e)

getGraph

public Graph<V,E> getGraph()