Package org.graph4j.isomorphism

Class OrderedDigraph

java.lang.Object
org.graph4j.isomorphism.OrderedDigraph
public class OrderedDigraph extends Object

Class that orders the vertices of a digraph according to their degree.

Also, this class caches(if wanted) the predecessors, successors, and edges of the vertices, for a faster access.

Author:
Ignat Gabriel-Andrei

  • Field Details

    • dg

      protected final Digraph dg

    • n

      protected final int n

  • Constructor Details

    • OrderedDigraph

      public OrderedDigraph(Digraph dg, boolean cache)
      Constructor that orders the vertices of the given digraph according to their degree.
      Parameters:
      dg - the digraph to be ordered and possibly cached
      cache - if true, the algorithm will cache the predecessors, successors, the adjacency relations

    • OrderedDigraph

      public OrderedDigraph(Digraph dg)

  • Method Details

    • getGraph

      public Digraph getGraph()
      Returns:
      the digraph

    • getNumVertices

      public int getNumVertices()
      Returns:
      the number of vertices in the digraph

    • getVertexNumber

      public int getVertexNumber(int vertexIndex)
      Return the vertex number of the vertex at the given position in the order.
      Parameters:
      vertexIndex - the order in the sorted list of vertices
      Returns:
      the vertex number

    • getVertexOrder

      public int getVertexOrder(int vertexNumber)
      Parameters:
      vertexNumber - the vertex number in the digraph
      Returns:
      the index of the vertex in the sorted list of vertices

    • getEdge

      public Edge getEdge(int vertexIndex1, int vertexIndex2)
      Parameters:
      vertexIndex1 - the index of the source vertex in the sorted list of vertices
      vertexIndex2 - the index of the target vertex in the sorted list of vertices
      Returns:
      the corresponding edge

    • predecessors

      public int[] predecessors(int vertexIndex)
      Parameters:
      vertexIndex - the index of the vertex in the sorted list of vertices
      Returns:
      the indices in the order of the predecessors of the corresponding vertex number

    • successors

      public int[] successors(int vertexIndex)
      Parameters:
      vertexIndex - the order of the vertex in the sorted list of vertices
      Returns:
      the successors of the corresponding vertex number

    • containsEdge

      public boolean containsEdge(int vertexIndex1, int vertexIndex2)
      Checks if there is an edge between the two vertices.
      Parameters:
      vertexIndex1 - the index of the source vertex in the sorted list of vertices
      vertexIndex2 - the index of the target vertex in the sorted list of vertices
      Returns:
      true if there is an edge between the two vertices, false otherwise

    • indegree

      public int indegree(int vertexIndex)
      Parameters:
      vertexIndex - the index of the vertex in the sorted list of vertices
      Returns:
      the indegree of the vertex

    • outdegree

      public int outdegree(int vertexIndex)
      Parameters:
      vertexIndex - the index of the vertex in the sorted list of vertices
      Returns:
      the outdegree of the vertex