Package org.graph4j

Interface Digraph<V,E>

Type Parameters:
V - the type of vertex labels in this graph.
E - the type of edge labels in this graph.
All Superinterfaces:
Graph<V,E>
All Known Subinterfaces:
DirectedMultigraph<V,E>, DirectedPseudograph<V,E>, Network<V,E>
public interface Digraph<V,E> extends Graph<V,E>
Represents a directed graph.
Author:
Cristian Frăsinaru

  • Method Details

    • maxEdges

      static long maxEdges(int numVertices)
      Utility method that returns the maximum number of edges a directed graph with a specified number of vertices can have. A digraph with n vertices, without multiple edges or self-loops, can have at most n*(n-1) edges.
      Parameters:
      numVertices - a number of vertices.
      Returns:
      the maximum number of edges a graph of order numVertices can have.

    • supportGraph

      Graph<V,E> supportGraph()
      Creates the support graph of this digraph. The support graph of a digraph G is an undirected graph containing all the vertices of G and one edge (v,u) for any pair of vertices v and u of the digraph that are connected by an arc, in either direction: from v to u, form u to v or both ways. The resulting graph has no data on its edges, does not contain self loops or multiple edges and the labels are all null.
      Returns:
      an undirected graph, representing the support graph.

    • copy

      Digraph<V,E> copy()
      Creates an identical copy of the digraph.
      Specified by:
      copy in interface Graph<V,E>
      Returns:
      an identical copy of the digraph.

    • complement

      Digraph<V,E> complement()
      Creates the complement of the digraph. The complement of a directed graph G has the same vertex set as G and its edge set consists of the edges not present in G.
      Specified by:
      complement in interface Graph<V,E>
      Returns:
      the complement of the digraph.

    • subgraph

      Digraph<V,E> subgraph(VertexSet vertexSet)
      Description copied from interface: Graph
      Creates and returns the subgraph induced by a set of vertices.
      Specified by:
      subgraph in interface Graph<V,E>
      Parameters:
      vertexSet - a set of vertices.
      Returns:
      the subgraph induced by the specified vertices.

    • subgraph

      default Digraph<V,E> subgraph(int... vertices)
      Description copied from interface: Graph
      Creates and returns the subgraph induced by an array of vertices.
      Specified by:
      subgraph in interface Graph<V,E>
      Parameters:
      vertices - an array of vertices.
      Returns:
      the subgraph induced by the specified vertices.

    • subgraph

      Digraph<V,E> subgraph(Collection<Edge> edges)
      Description copied from interface: Graph
      Creates and returns the subgraph generated by a collection of edges.
      Specified by:
      subgraph in interface Graph<V,E>
      Parameters:
      edges - a collection of edges.
      Returns:
      the subgraph generated by the given edges.

    • outdegree

      default int outdegree(int v)
      Returns the outdegree of a vertex, i.e. the number of its successors.
      Parameters:
      v - a vertex number.
      Returns:
      the outdegree of v.

    • outdegrees

      default int[] outdegrees()
      Creates the outdegree sequence.
      Returns:
      the array of vertex outdegrees.

    • indegree

      default int indegree(int v)
      Returns the indegree of a vertex, i.e. the number of its predecessors.
      Parameters:
      v - a vertex number.
      Returns:
      the indegree of v.

    • indegrees

      default int[] indegrees()
      Creates the indegree sequence.
      Returns:
      the array of vertex indegrees.

    • successors

      default int[] successors(int v)
      Creates an array containing the vertex numbers of the successors of a specified vertex. If all that is wanted is iterating over the predecessors of v, predecessorIterator(int) method is more effective in terms of memory and time required to access information regarding the edges incident to v.
      Parameters:
      v - a vertex number.
      Returns:
      the successors of v.

    • successorIterator

      default SuccessorIterator<E> successorIterator(int v)
      Creates an iterator over the successors of v. The iterator offers in O(1) time information regarding the edges incident from v.
      Parameters:
      v - a vertex number.
      Returns:
      an iterator over the successors of v.

    • successorIterator

      SuccessorIterator successorIterator(int v, int pos)
      Creates an iterator over the edges incident from v, returning the successors of v, starting from a specified position in the successors adjacency list of v, along with information regarding their edges.
      Parameters:
      v - a vertex number.
      pos - a position in the successors adjacency list of v.
      Returns:
      an iterator over the successors of v, starting from a specified position in the adjacency list of v.

    • predecessors

      default int[] predecessors(int v)
      Creates an array holding the predecessors of a specified vertex. If all that is wanted is iterating over the predecessors of v, predecessorIterator(int) method is more effective in terms of memory and time required to access information regarding the edges incident to v.
      Parameters:
      v - a vertex number.
      Returns:
      the predecessors of v.

    • predecessorIterator

      default PredecessorIterator predecessorIterator(int v)
      Creates an iterator over the predecessors of a specified vertex. The iterator offers in O(1) time information regarding the edges incident to v.
      Parameters:
      v - a vertex number.
      Returns:
      an iterator over the predecessors of v.

    • predecessorIterator

      PredecessorIterator predecessorIterator(int v, int pos)
      Creates an iterator over the predecessors of a vertex v, starting from a specified position in the predecessors adjacency list of v. The iterator offers in @{code O(1)} time information regarding the edges incident to v.
      Parameters:
      v - a vertex number.
      pos - a position in the predecessors adjacency list of v.
      Returns:
      an iterator over the successors of v, starting from a specified position in the predecessors adjacency list of v.

    • neighborIterator

      NeighborIterator neighborIterator(int v, boolean allEdges)

    • outgoingEdgesFrom

      default Edge[] outgoingEdgesFrom(int v)
      Creates an array holding the edges outgoing from a vertex. If creating the Edge objects is not required, a more effective method is successorIterator(int).
      Parameters:
      v - a vertex number.
      Returns:
      outgoing edges from v.

    • incomingEdgesTo

      default Edge[] incomingEdgesTo(int v)
      Creates an array holding the edges incoming to a vertex. If creating the Edge objects is not required, a more effective method is predecessorIterator(int).
      Parameters:
      v - a vertex number.
      Returns:
      incoming edges to v.

    • isSymmetrical

      default boolean isSymmetrical()
      Checks if the digraph is symmetrical. A symmetrical digraph has only pairs of symmetrical edges, i.e. if the edge (v,u) belongs to the digraph, so does (u,v).
      Returns:
      true if the digraph is symmetrical.

    • isSource

      default boolean isSource(int v)
      Checks if a vertex is a source, meaning that it has no predecessors.
      Parameters:
      v - a vertex number.
      Returns:
      true if v has indegree 0, false otherwise.

    • isSink

      default boolean isSink(int v)
      Checks if a vertex is a sink, meaning that it has no successors.
      Parameters:
      v - a vertex number.
      Returns:
      true if v has outdegree 0, false otherwise.

    • addWeightedVertex

      int addWeightedVertex(int v, double weight)
      Adds a new vertex to the graph having the specified number and weight. After the execution of this method, the graph is considered vertex weighted.
      Parameters:
      v - a vertex number.
      weight - the weight to be set for vertex v.
      Returns:
      the index of the added vertex.
      Throws:
      InvalidVertexException - if v is negative or it is already in the graph.

    • addWeightedVertex

      int addWeightedVertex(double weight)
      Adds a new vertex to the graph having the number equal to the maximum vertex number plus one, and the specified weight. After the execution of this method, the graph is considered vertex weighted.
      Parameters:
      weight - the weight to be set for the added vertex.
      Returns:
      the number of the added vertex.

    • addEdge

      int addEdge(int v, int u, double weight)
      Adds a new weighted edge to the graph. The endpoints of the edge are specified using their vertex numbers. After a successful execution of this method, the graph is considered edge weighted. See also Graph.addEdge(int, int).
      Parameters:
      v - a vertex number
      u - a vertex number
      weight - the weight to be set for the edge (v,u).
      Returns:
      the position of u in the adjacency list of v if (v,u) edge was added, or -1 if the edge was not added.
      Throws:
      InvalidVertexException - if either of the two vertices is not in the graph.

    • setVertexWeight

      void setVertexWeight(int v, double weight)
      Sets the weight of a vertex. If at least one vertex has been assigned a weight, the graph is considered vertex weighted. The time complexity of this method is O(1).
      Parameters:
      v - a vertex number.
      weight - the weight to be set for vertex v.
      Throws:
      InvalidVertexException - if v is not in the graph.

    • getVertexWeight

      double getVertexWeight(int v)
      Returns the weight of a vertex. If no weights have been set (the graph is vertex unweighted) it returns Graph.DEFAULT_VERTEX_WEIGHT, which is 1. The time complexity of this method is O(1).
      Parameters:
      v - a vertex number.
      Returns:
      the weight of the vertex, 1 if the graph is unweighted.
      Throws:
      InvalidVertexException - if v is not in the graph.

    • setEdgeWeight

      void setEdgeWeight(int v, int u, double weight)
      Sets the weight of an edge. The time complexity of this method is O(degree(v)). It is more efficient to set the weights of the edges while iterating over them, see Graph.neighborIterator(int) or Graph.edgeIterator().
      Parameters:
      v - a vertex number.
      u - a vertex number.
      weight - the weight to be set for the edge (v,u).
      Throws:
      InvalidEdgeException - if the graph does not contain the edge (v,u).

    • getEdgeWeight

      double getEdgeWeight(int v, int u)
      Returns the weight of an edge. If no weights have been set on edges (the graph is edge unweighted) it returns Graph.DEFAULT_EDGE_WEIGHT, which is 1. If the endpoints v and u do not represent an edge, it returns Double.POSITIVE_INFINITY. The time complexity of this method is O(degree(v)). It is more efficient to get the weights of the edges while iterating over them, see Graph.neighborIterator(int) or Graph.edgeIterator().
      Parameters:
      v - a vertex number.
      u - a vertex number.
      Returns:
      the weight of the edge (v,u).
      Throws:
      InvalidEdgeException - if the graph does not contain the edge (v,u).

    • getEdgeWeight

      default double getEdgeWeight(Edge e)
      Returns the weight of an edge. If no weights have been set on edges (the graph is edge unweighted) it returns Graph.DEFAULT_EDGE_WEIGHT, which is 1. If the argument does not represent an edge, it returns Double.POSITIVE_INFINITY. The time complexity of this method is O(degree(v)). It is more efficient to get the weights of the edges while iterating over them, see Graph.neighborIterator(int) or Graph.edgeIterator().
      Parameters:
      e - an edge.
      Returns:
      the weight of the edge e.
      Throws:
      InvalidEdgeException - if the graph does not contain the edge e.

    • hasEdgeWeights

      boolean hasEdgeWeights()
      Checks if the graph is has at least one edge that has been assigned a weight (is edge weighted).
      Returns:
      true if weights have been set on edges, false otherwise.

    • hasVertexWeights

      boolean hasVertexWeights()
      Checks if the graph has at least one vertex that has been assigned a weight (is vertex weighted).
      Returns:
      true if weights have been set on vertices, false otherwise.

    • getEdgeData

      double getEdgeData(int dataType, int v, int u, double defaultValue)

    • getEdgeData

      default double getEdgeData(int dataType, int v, int u)

    • getEdgeData

      default double getEdgeData(int dataType, Edge e, double defaultValue)

    • getEdgeData

      default double getEdgeData(int dataType, Edge e)

    • setEdgeData

      void setEdgeData(int dataType, int v, int u, double value)

    • incEdgeData

      void incEdgeData(int dataType, int v, int u, double amount)

    • hasEdgeData

      boolean hasEdgeData(int dataType)

    • resetEdgeData

      void resetEdgeData(int dataType, double value)

    • addLabeledVertex

      int addLabeledVertex(int v, V label)
      Adds a new vertex to the graph having the specified number and label. After the execution of this method, the graph is considered vertex labeled.
      Parameters:
      v - a vertex number.
      label - a vertex label.
      Returns:
      the index of the added vertex.
      Throws:
      InvalidVertexException - if v is negative or it is already in the graph.

    • addLabeledVertex

      int addLabeledVertex(V label)
      Adds a new vertex to the graph having the number equal to the maximum vertex number plus one, and the specified label. After the execution of this method, the graph is considered vertex labeled.
      Parameters:
      label - a vertex label.
      Returns:
      the number of the added vertex.

    • addLabeledEdge

      int addLabeledEdge(int v, int u, E label, double weight)
      Adds a new weighted and labeled edge to the graph. The endpoints of the edge are identified using their vertex numbers. See also Graph.addEdge(int, int).
      Parameters:
      v - a vertex number.
      u - a vertex number.
      label - edge label.
      weight - edge weight.
      Returns:
      the position of u in the adjacency list of v if (v,u) edge was added, or -1 if the edge was not added.
      Throws:
      InvalidVertexException - if either of the two vertices is not in the graph.

    • addLabeledEdge

      int addLabeledEdge(int v, int u, E label)
      Adds a new labeled edge to the graph. The endpoints of the edge are identified using their vertex numbers. After a successful execution of this method, the graph is considered edge labeled. See also Graph.addEdge(int, int).
      Parameters:
      v - a vertex number
      u - a vertex number
      label - an edge label.
      Returns:
      the position of u in the adjacency list of v if (v,u) edge was added, or -1 if the edge was not added.
      Throws:
      InvalidVertexException - if either of the two vertices is not in the graph.

    • addLabeledEdge

      default int addLabeledEdge(V vLabel, V uLabel, E edgeLabel)
      Adds a new labeled edge to the graph. The endpoints of the edge are identified using their uniquely identifiable vertex labels. After a successful execution of this method, the graph is considered edge labeled. See also Graph.addEdge(int, int).
      Parameters:
      vLabel - a vertex label.
      uLabel - a vertex label.
      edgeLabel - an edge label.
      Returns:
      the position of u in the adjacency list of v if (v,u) edge was added, or -1 if the edge was not added.
      Throws:
      InvalidVertexException - if either of the two vertices is not in the graph.

    • setVertexLabel

      void setVertexLabel(int v, V label)
      Sets the label for the specified vertex. If at least one vertex has been assigned a label, the graph is considered vertex labeled. The time complexity of this method is O(1).
      Parameters:
      v - a vertex number.
      label - a vertex label.
      Throws:
      InvalidVertexException - if v is not in the graph.

    • getVertexLabel

      V getVertexLabel(int v)
      Returns the label of the specified vertex or null if no label has been set. The time complexity of this method is O(1).
      Parameters:
      v - a vertex number.
      Returns:
      the label of the specified vertex.
      Throws:
      InvalidVertexException - if v is not in the graph.

    • setEdgeLabel

      void setEdgeLabel(int v, int u, E label)
      Sets the label of a specified edge. The time complexity of this method is O(degree(v)). It is more efficient to set the labels of the edges while iterating over them, see Graph.neighborIterator(int) or Graph.edgeIterator().
      Parameters:
      v - a vertex number.
      u - a vertex number.
      label - an edge label.
      Throws:
      InvalidEdgeException - if the graph does not contain the edge (v,u).

    • getEdgeLabel

      E getEdgeLabel(int v, int u)
      Returns the label of a specified edge. The time complexity of this method is O(degree(v)). It is more efficient to get the weights of the edges while iterating over them, see Graph.neighborIterator(int) or Graph.edgeIterator().
      Parameters:
      v - a vertex number.
      u - a vertex number.
      Returns:
      the label of the edge (v,u).
      Throws:
      InvalidEdgeException - if the graph does not contain the edge (v,u).

    • hasEdgeLabels

      boolean hasEdgeLabels()
      Checks if the graph has at least one edge that has been assigned a label (is edge labeled).
      Returns:
      true if labels have been set on edges, false otherwise.

    • hasVertexLabels

      boolean hasVertexLabels()
      Checks if the graph has at least one vertex that has been assigned a label (is vertex labeled).
      Returns:
      true if labels have been set on vertices, false otherwise.

    • findVertex

      int findVertex(V label)
      Returns the number of the vertex having the specified label. If there are more vertices having the specified label, it returns the last one that has been assigned that label. If no vertex has the specified label, it returns -1.
      Parameters:
      label - a vertex label.
      Returns:
      the number of the vertex which has the specified label, or -1 if no such vertex exists.

    • findAllVertices

      VertexSet findAllVertices(V label)
      Returns a set containing all the vertex numbers having the specified label.
      Parameters:
      label - a vertex label.
      Returns:
      all the vertices of the graph which have been assigned the specified label.

    • findEdge

      Edge findEdge(E label)
      Returns the edge having the specified label. If there are more edges with the specified label, it returns the last one added in the graph.
      Parameters:
      label - an edge label.
      Returns:
      the edge with the specified label.

    • findAllEdges

      EdgeSet findAllEdges(E label)
      Returns a set containing all the edges having the specified label.
      Parameters:
      label - an edge label.
      Returns:
      all the edges with the specified label.