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

final class GraphOrdering<V,E> extends Object
This class represents the order on the graph vertices. There are also some helper-functions for receiving outgoing/incoming edges, etc.
  • Field Details

    • graph

      private final Graph<V,E> graph
    • mapVertexToOrder

      private final Map<V,Integer> mapVertexToOrder
    • mapOrderToVertex

      private final List<V> mapOrderToVertex
    • vertexCount

      private final int vertexCount
    • outgoingEdges

      private final int[][] outgoingEdges
    • incomingEdges

      private final int[][] incomingEdges
    • edgeCache

      private final E[] edgeCache
    • adjMatrix

      private final byte[] adjMatrix
      if caching is enabled, adjMatrix contains cached information on existing edges, valid values:
      • 0 - no cached value
      • 1 - edge exists
      • -1 - no edge exists
    • cacheEdges

      private final boolean cacheEdges
  • Constructor Details

    • 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 Details

    • 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 $v_1$
      v2Number - the number of the second vertex $v_2$
      Returns:
      exists the edge from $v_1$ to $v_2$
    • 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 $v_1$
      v2Number - the number identifying the vertex $v_2$
      Returns:
      the edge from $v_1$ to $v_2$
    • getVertexNumber

      public int getVertexNumber(V v)
    • getEdgeNumbers

      public int[] getEdgeNumbers(E e)
    • getGraph

      public Graph<V,E> getGraph()