Package org.graph4j

Interface Graph<V,E>

Type Parameters:
V - the type of vertex labels in this graph.
E - the type of edge labels in this graph.
All Known Subinterfaces:
Digraph<V,E>, DirectedMultigraph<V,E>, DirectedPseudograph<V,E>, Multigraph<V,E>, Network<V,E>, Pseudograph<V,E>
public interface Graph<V,E>
The base data type for all graphs: directed or not, weighted or not, labeled or not, allowing self loops and multiple edges or not. Vertices and edges of all graph types can be labeled using any reference data type.
Author:
Cristian Frăsinaru

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final double
    DEFAULT_EDGE_WEIGHT
    1
    static final double
    DEFAULT_VERTEX_WEIGHT
    1
    static final int
    WEIGHT
    0

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    addEdge(int v, int u)
    Adds a new edge to the graph.
    int
    addEdge(int v, int u, double weight)
    Adds a new weighted edge to the graph.
    int
    addEdge(Edge<E> e)
    Adds a new edge to the graph.
    default int
    addEdge(V vLabel, V uLabel)
    Adds a new edge to the graph.
    default void
    addGraph(Graph<V,E> graph)
    Adds the vertices and edges of another graph.
    int
    addLabeledEdge(int v, int u, E label)
    Adds a new labeled edge to the graph.
    int
    addLabeledEdge(int v, int u, E label, double weight)
    Adds a new weighted and labeled edge to the graph.
    default int
    addLabeledEdge(V vLabel, V uLabel, E edgeLabel)
    Adds a new labeled edge to the graph.
    int
    addLabeledVertex(int v, V label)
    Adds a new vertex to the graph having the specified number and label.
    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.
    int
    addVertex()
    Adds a new vertex to the graph having the number equal to the maximum vertex number plus one.
    int
    addVertex(int v)
    Adds a new vertex to the graph having a specified number.
    default void
    addVertices(int... vertices)
    Convenience method for adding multiple vertices to the graph.
    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.
    int
    addWeightedVertex(int v, double weight)
    Adds a new vertex to the graph having the specified number and weight.
    int[][]
    adjacencyMatrix()
    Creates and return the adjacency matrix.
    int
    adjListPos(int v, int u)
    Returns the first position of u in the neighbor list of v.
    Graph<V,E>
    complement()
    Creates the complement of the graph.
    boolean
    containsEdge(int v, int u)
    Checks if two vertices of the graph are adjacent.
    default boolean
    containsEdge(Edge e)
    Checks if an edge belongs to the graph.
    default boolean
    containsVertex(int v)
    Checks if the graph contains a specific vertex number.
    int
    contractVertices(int... vertices)
    Creates a new vertex that will replace the specified vertices, being connected to all their neighbors.
    Graph<V,E>
    copy()
    Creates and returns an identical copy of the graph.
    Graph<V,E>
    copy(boolean vertexWeights, boolean vertexLabels, boolean edges, boolean edgeWeights, boolean edgeLabels)
    Creates and returns a copy of the graph.
    Multigraph<V,E>
    copyAsMultigraph()
    Creates and returns an identical copy of the graph, as a Multigraph object.
    Multigraph<V,E>
    copyAsPseudograph()
    Creates and returns an identical copy of the graph, as a Pseudograph object.
    int
    degree(int v)
    The degree of a vertex is the number of its neighbors, that is vertices that are in its adjacency list.
    int[]
    degrees()
    Creates and returns an array representing the degree sequence of the graph.
    int
    duplicateVertex(int v)
    Creates a new vertex adjacent to all the neighbors of a specified vertex.
    Edge<E>
    edge(int v, int u)
    Returns an Edge object corresponding to the specified vertices (its endpoints).
    EdgeIterator<E>
    edgeIterator()
    Returns an iterator over the edges in this graph.
    Edge[]
    edges()
    Creates and returns an array holding all the edges of the graph.
    Edge[]
    edgesOf(int v)
    Creates and returns an array holding the edges incident to a specified vertex.
    EdgeSet
    findAllEdges(E label)
    Returns a set containing all the edges having the specified label.
    VertexSet
    findAllVertices(V label)
    Returns a set containing all the vertex numbers having the specified label.
    Edge
    findEdge(E label)
    Returns the edge having the specified label.
    int
    findVertex(V label)
    Returns the number of the vertex having the specified label.
    default double
    getEdgeData(int dataType, int v, int u)
     
    double
    getEdgeData(int dataType, int v, int u, double defaultValue)
     
    default double
    getEdgeData(int dataType, Edge e)
     
    default double
    getEdgeData(int dataType, Edge e, double defaultValue)
     
    int
    getEdgeDataSize()
    Returns the maximum number of values that can be stored on edges.
    E
    getEdgeLabel(int v, int u)
    Returns the label of a specified edge.
    double
    getEdgeWeight(int v, int u)
    Returns the weight of an edge.
    default double
    getEdgeWeight(Edge e)
    Returns the weight of an edge.
    String
    getName()
    Returns the name of the graph, or null if the graph has no name.
    V
    getVertexLabel(int v)
    Returns the label of the specified vertex or null if no label has been set.
    double
    getVertexWeight(int v)
    Returns the weight of a vertex.
    boolean
    hasEdgeData(int dataType)
     
    boolean
    hasEdgeLabels()
    Checks if the graph has at least one edge that has been assigned a label (is edge labeled).
    boolean
    hasEdgeWeights()
    Checks if the graph is has at least one edge that has been assigned a weight (is edge weighted).
    boolean
    hasVertexLabels()
    Checks if the graph has at least one vertex that has been assigned a label (is vertex labeled).
    boolean
    hasVertexWeights()
    Checks if the graph has at least one vertex that has been assigned a weight (is vertex weighted).
    void
    incEdgeData(int dataType, int v, int u, double amount)
     
    int[][]
    incidenceMatrix()
    Creates and returns the incidence matrix.
    int
    indexOf(int v)
    Returns the index corresponding to a vertex number.
    boolean
    isAllowingMultipleEdges()
    Convenience method for testing if the graph is a multigraph.
    boolean
    isAllowingSelfLoops()
    Convenience method for testing if the graph is a pseudograph.
    boolean
    isComplete()
    Checks if the graph is complete.
    boolean
    isDefaultVertexNumbering()
    Checks if the vertex numbers are the default ones, in the range 0..numVertices-1.
    boolean
    isDirected()
    Convenience method for testing if the graph is a directed graph.
    default boolean
    isEdgeless()
    Checks if the graph has no edges.
    default boolean
    isEmpty()
    Checks if the graph has no vertices.
    default boolean
    isIsolated(int v)
    Checks if a vertex is isolated, meaning that it has no neighbors.
    default boolean
    isPendant(int v)
    Checks if a vertex is pendant, meaning that it has a single neighbor.
    boolean
    isSafeMode()
    Checks if the graph is in safe mode.
    default boolean
    isSimple()
    Convenience method for testing if the graph does not contain multiple edges or self loops.
    default boolean
    isUniversal(int v)
    Checks if a vertex is universal, meaning that it is adjacent to all other vertices in the graph.
    long
    maxEdges()
    Returns the maximum number of edges the graph can have.
    static long
    maxEdges(int numVertices)
    Utility method that returns the maximum number of edges a graph with a specified number of vertices can have.
    int
    maxVertexNumber()
    Returns the maximum vertex number in the graph.
    default NeighborIterator<E>
    neighborIterator(int v)
    Creates an iterator over the neighbors of a vertex.
    NeighborIterator<E>
    neighborIterator(int v, int pos)
    Creates an iterator over the neighbors of a vertex, starting from a specified position in the adjacency list.
    int[]
    neighbors(int v)
    Returns the neighbors of a vertex.
    long
    numEdges()
    Returns the number of edges in the graph.
    int
    numVertices()
    Returns the number of vertices in the graph.
    void
    removeAllEdges(int v)
    Removes all edges incident with a vertex.
    void
    removeEdge(int v, int u)
    Removes the specified edge from the graph.
    default void
    removeEdge(Edge e)
    Removes the specified edge from the graph.
    void
    removeVertex(int v)
    Removes the specified vertex from the graph, together with all the edges incident to or from it.
    default void
    removeVertices(int... vertices)
    Convenience method for removing multiple vertices from the graph.It invokes the removeVertex(int) method for each vertex.
    void
    renumberAdding(int amount)
    Renumbers all the vertices of the graph, adding the specified amount to each of them.
    void
    resetEdgeData(int dataType, double value)
     
    void
    setEdgeData(int dataType, int v, int u, double value)
     
    void
    setEdgeDataSize(int edgeDataSize)
    Sets the maximum number of numerical values that can be stored on edges.
    void
    setEdgeLabel(int v, int u, E label)
    Sets the label of a specified edge.
    void
    setEdgeWeight(int v, int u, double weight)
    Sets the weight of an edge.
    void
    setName(String name)
    Sets the name of the graph, for example "K4", "C5", "Petersen", etc.
    void
    setSafeMode(boolean safeMode)
    Sets the flag indicating whether the graph is in safe mode or not.
    void
    setVertexLabel(int v, V label)
    Sets the label for the specified vertex.
    void
    setVertexWeight(int v, double weight)
    Sets the weight of a vertex.
    int
    splitEdge(int v, int u)
    Creates a new vertex adjacent to v and u, and removes the edge (v,u).
    default Graph<V,E>
    subgraph(int... vertices)
    Creates and returns the subgraph induced by an array of vertices.
    Graph<V,E>
    subgraph(Collection<Edge> edges)
    Creates and returns the subgraph generated by a collection of edges.
    Graph<V,E>
    subgraph(VertexSet vertexSet)
    Creates and returns the subgraph induced by a set of vertices.
    int
    vertexAt(int index)
    Returns the number of the vertex with the specified index.
    VertexIterator<V>
    vertexIterator()
    Creates an iterator over the vertices of the graph.
    int[]
    vertices()
    Returns the array in which the vertices of the graph are stored.
    double[][]
    weightMatrix()
    Creates and returns the weight matrix.

  • Field Details

  • Method Details

    • getName

      String getName()
      Returns the name of the graph, or null if the graph has no name.
      Returns:
      the name of the graph.

    • setName

      void setName(String name)
      Sets the name of the graph, for example "K4", "C5", "Petersen", etc.
      Parameters:
      name - the name of the graph.

    • numVertices

      int numVertices()
      Returns the number of vertices in the graph. The number of vertices is also called the order of the graph.
      Returns:
      the number of vertices in the graph.

    • numEdges

      long numEdges()
      Returns the number of edges in the graph. The number of edges is also called the dimension of the graph.
      Returns:
      the number of edges in the graph.

    • maxEdges

      long maxEdges()
      Returns the maximum number of edges the graph can have. A simple graph with n vertices can have at most n*(n-1)/2 edges. A directed graph may have n*(n-1) edges (also called arcs). For multigraphs and pseudographs, this method returns Long.MAX_VALUE.
      Returns:
      the maximum number of edges the graph can have.

    • maxEdges

      static long maxEdges(int numVertices)
      Utility method that returns the maximum number of edges a graph with a specified number of vertices can have. A simple graph with n vertices can have at most n*(n-1)/2 edges.
      Parameters:
      numVertices - a number of vertices.
      Returns:
      the maximum number of edges a graph of order numVertices can have.

    • vertices

      int[] vertices()
      Returns the array in which the vertices of the graph are stored. By default, the vertices have numbers between 0 and numVertices()-1, however this is not mandatory. Vertices can be removed from the graph, new vertices with any number can be added, etc. For performance reasons, this is the actual array where the vertices are stored, so do not modify it.
      Returns:
      the vertices of the graph.

    • isEmpty

      default boolean isEmpty()
      Checks if the graph has no vertices. An empty graph is also called the null graph.
      Returns:
      true if the number of vertices is 0, false otherwise.

    • isEdgeless

      default boolean isEdgeless()
      Checks if the graph has no edges.
      Returns:
      true if the number of edges is 0, false otherwise.

    • isComplete

      boolean isComplete()
      Checks if the graph is complete. In case of undirected graphs, that means that there is an edge between every two vertices. In case of directed graphs, for every two vertices v and u, both vu and uv edges must exist. In case of multigraphs and pseudographs, the presence of self-loops or multiple edges between two vertices does not affect this property.
      Returns:
      true if the graph is complete, false otherwise.

    • vertexAt

      int vertexAt(int index)
      Returns the number of the vertex with the specified index. The vertices of a graph are indexed in the array returned by the method vertices().
      Parameters:
      index - a value between 0 and numVertices() - 1.
      Returns:
      the vertex at the specified index (position) in the array.

    • vertexIterator

      VertexIterator<V> vertexIterator()
      Creates an iterator over the vertices of the graph.
      Returns:
      an iterator over the vertices of the graph.

    • indexOf

      int indexOf(int v)
      Returns the index corresponding to a vertex number. The index of a vertex represents the position where it is stored in the array returned by the method vertices(). The index of a vertex may change if other vertices are removed from the graph.
      Parameters:
      v - a vertex number.
      Returns:
      the index of the specified vertex number.

    • edges

      Edge[] edges()
      Creates and returns an array holding all the edges of the graph. This method has a high memory overhead, since the edge objects are not stored internally in the graph, so it should only be used if all the edges are required to be in the same data structure for a specific purpose. In order to iterate efficiently over the edges of the graph it is better to use edgeIterator() or neighborIterator(int). The method works only if the number of edges is less than Integer.MAX_VALUE.
      Returns:
      an array of all the edges in the graph.

    • edgesOf

      Edge[] edgesOf(int v)
      Creates and returns an array holding the edges incident to a specified vertex.
      Parameters:
      v - a vertex number.
      Returns:
      the edges formed by v with its neighbors (successors).

    • edgeIterator

      EdgeIterator<E> edgeIterator()
      Returns an iterator over the edges in this graph. There are no guarantees concerning the order in which the edges are returned.
      Returns:
      an iterator over the edges in this graph.

    • edge

      Edge<E> edge(int v, int u)
      Returns an Edge object corresponding to the specified vertices (its endpoints). If there is no such edge in the graph, it throws InvalidEdgeException.
      Parameters:
      v - a vertex number.
      u - a vertex number.
      Returns:
      the edge in the graph with the endpoints v and u.
      Throws:
      InvalidEdgeException - if there is no vu edge in the graph.

    • containsEdge

      boolean containsEdge(int v, int u)
      Checks if two vertices of the graph are adjacent. In case of undirected graphs, that means that v is in the adjacency list of u and u is also in the adjacency list of v. In case of directed graphs, the method returns true only if u is in the adjacency list of v (u is a successor of v).
      Parameters:
      v - a vertex number
      u - a vertex number
      Returns:
      true if u is in the adjacency list of v, false otherwise.

    • containsEdge

      default boolean containsEdge(Edge e)
      Checks if an edge belongs to the graph. See also containsEdge(int, int).
      Parameters:
      e - an edge.
      Returns:
      true if the edge belongs to the graph, false otherwise.

    • containsVertex

      default boolean containsVertex(int v)
      Checks if the graph contains a specific vertex number.
      Parameters:
      v - a vertex number.
      Returns:
      true if v belongs to the graph.

    • neighbors

      int[] neighbors(int v)
      Returns the neighbors of a vertex. The neighbors of a vertex v are the vertices in the adjacency list of v. For performance reasons, this method returns the actual array used for storing the adjacency list, so do not modify it. In case of directed graphs, this method returns the same as Digraph.successors(int). For a more efficient iteration over the neighbors of a vertex, use neighborIterator(int).
      Parameters:
      v - a vertex number.
      Returns:
      the vertices that are adjacent to v.

    • neighborIterator

      default NeighborIterator<E> neighborIterator(int v)
      Creates an iterator over the neighbors of a vertex. The iterator returns the neighbors of a vertex v, along with information regarding the edges connecting v to them. Using this method is the most efficient way to explore the neighborhood of a vertex.
      Parameters:
      v - a vertex number.
      Returns:
      an iterator over the neighbors of v.

    • neighborIterator

      NeighborIterator<E> neighborIterator(int v, int pos)
      Creates an iterator over the neighbors of a vertex, starting from a specified position in the adjacency list.
      Parameters:
      v - a vertex number.
      pos - a position in the adjacency list of v.
      Returns:
      an iterator over the neighbors of v, starting from the position pos in the adjacency list of v.

    • adjListPos

      int adjListPos(int v, int u)
      Returns the first position of u in the neighbor list of v.
      Parameters:
      v - a vertex number.
      u - a vertex number;
      Returns:
      the first position of u in the neighbor list of v.

    • degree

      int degree(int v)
      The degree of a vertex is the number of its neighbors, that is vertices that are in its adjacency list. In case of directed graphs, this method returns the number of successors, same as Digraph.outdegree(int).
      Parameters:
      v - a vertex number.
      Returns:
      the degree of the vertex v.

    • isIsolated

      default boolean isIsolated(int v)
      Checks if a vertex is isolated, meaning that it has no neighbors. In case of directed graphs, it checks if the vertex has no successors, same as Digraph.isSink(int).
      Parameters:
      v - a vertex number.
      Returns:
      true if v has degree 0.

    • isPendant

      default boolean isPendant(int v)
      Checks if a vertex is pendant, meaning that it has a single neighbor. In case of directed graphs, it checks if the vertex has outdegree 1.
      Parameters:
      v - a vertex number.
      Returns:
      true if v has degree 1.

    • isUniversal

      default boolean isUniversal(int v)
      Checks if a vertex is universal, meaning that it is adjacent to all other vertices in the graph. In case of simple graphs, it has the degree numVertices()-1. In case of directed graphs it has the outdegree numVertices()-1.
      Parameters:
      v - a vertex number.
      Returns:
      true if v is universal.

    • degrees

      int[] degrees()
      Creates and returns an array representing the degree sequence of the graph. The value degrees()[index] represents the degree of the vertex with the specified index, that is vertexAt(index).
      Returns:
      the degree sequence of the graph.

    • addEdge

      int addEdge(int v, int u)
      Adds a new edge to the graph. The endpoints of the edge are identified using their vertex numbers. The edge is not added if it already exists and the graph does not allow multiple edges, or if the endpoints are equal and the graph does not allow self loops. If the edge is not added, the method returns -1.
      Parameters:
      v - a vertex number.
      u - a vertex number.
      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.

    • addEdge

      int addEdge(Edge<E> e)
      Adds a new edge to the graph. The Edge object contains the endpoints and, if necessary, its weight and label. The directed property of an edge is ignored when it is added to the graph as it will assume the graph type. Note that the Edge objects are not actually stored in the graph.
      Parameters:
      e - an edge object.
      Returns:
      the position of the target node in the source node adjacency list if the edge was added, or -1 if the edge was not added.
      Throws:
      InvalidVertexException - if the source or the target of the edge are not in the graph.

    • addEdge

      default int addEdge(V vLabel, V uLabel)
      Adds a new edge to the graph. The endpoints of the edge are specified using the labels of the vertices, which should be uniquely identifiable.
      Parameters:
      vLabel - the label of a uniquely identifiable vertex.
      uLabel - the label of a uniquely identifiable vertex.
      Returns:
      the position of u in the adjacency list of v, or -1 if the edge is already in the graph or vLabel and uLabel are the same.

    • removeEdge

      void removeEdge(int v, int u)
      Removes the specified edge from the graph.
      Parameters:
      v - a vertex number.
      u - a vertex number.
      Throws:
      IllegalArgumentException - if the edge does not exist.

    • removeEdge

      default void removeEdge(Edge e)
      Removes the specified edge from the graph.
      Parameters:
      e - an edge of the graph.
      Throws:
      IllegalArgumentException - if the edge does not exist.

    • removeAllEdges

      void removeAllEdges(int v)
      Removes all edges incident with a vertex. In case of digraphs, it removes all the edges incident from and to the vertex.
      Parameters:
      v - a vertex number.

    • addVertex

      int addVertex()
      Adds a new vertex to the graph having the number equal to the maximum vertex number plus one. The weight and the label are null.
      Returns:
      the number of the added vertex.

    • addVertex

      int addVertex(int v)
      Adds a new vertex to the graph having a specified number. The vertex number should not be negative and must not exist already in the graph. Adding vertices with unnecessary large numbers may increase the memory occupied by the graph.
      Parameters:
      v - a vertex number that does not exist in the graph.
      Returns:
      the index of the added vertex.
      Throws:
      InvalidVertexException - if v is negative or it is already in the graph.

    • addVertices

      default void addVertices(int... vertices)
      Convenience method for adding multiple vertices to the graph. It invokes the addVertex(int) method for each vertex.
      Parameters:
      vertices - an array of vertex numbers.
      Throws:
      InvalidVertexException - if there are negative numbers or any of them already exists in the graph.

    • removeVertex

      void removeVertex(int v)
      Removes the specified vertex from the graph, together with all the edges incident to or from it.
      Parameters:
      v - a vertex number.
      Throws:
      InvalidVertexException - if any of the vertices is not in the graph.

    • removeVertices

      default void removeVertices(int... vertices)
      Convenience method for removing multiple vertices from the graph.It invokes the removeVertex(int) method for each vertex.
      Parameters:
      vertices - an array of vertex numbers.
      Throws:
      InvalidVertexException - if any of the vertices is not in the graph.

    • duplicateVertex

      int duplicateVertex(int v)
      Creates a new vertex adjacent to all the neighbors of a specified vertex.
      Parameters:
      v - the vertex to be duplicated.
      Returns:
      the number of the newly created vertex.

    • contractVertices

      int contractVertices(int... vertices)
      Creates a new vertex that will replace the specified vertices, being connected to all their neighbors. If the graph has weights on its edges, the edges that form between the new vertex and its neighbors cumulate the weights of the corresponding edges that are removed from the graph.
      Parameters:
      vertices - the vertices which will be contracted.
      Returns:
      the number of the newly created vertex.

    • maxVertexNumber

      int maxVertexNumber()
      Returns the maximum vertex number in the graph. If the default vertex numbering is used, the maximum vertex number is numVertices() - 1.
      Returns:
      the maximum vertex number in the graph, or -1 if the graph is empty (it contains no vertices).

    • isDefaultVertexNumbering

      boolean isDefaultVertexNumbering()
      Checks if the vertex numbers are the default ones, in the range 0..numVertices-1.
      Returns:
      true if the vertex numbers are in the range 0..numVertices-1, false otherwise.

    • splitEdge

      int splitEdge(int v, int u)
      Creates a new vertex adjacent to v and u, and removes the edge (v,u).
      Parameters:
      v - a vertex number.
      u - a vertex number.
      Returns:
      the number of the newly created vertex.
      Throws:
      InvalidEdgeException - if the edge vu does not exist.

    • renumberAdding

      void renumberAdding(int amount)
      Renumbers all the vertices of the graph, adding the specified amount to each of them.
      Parameters:
      amount - a positive number.

    • addGraph

      default void addGraph(Graph<V,E> graph)
      Adds the vertices and edges of another graph. The vertex sets of the two graphs must be disjoint.
      Parameters:
      graph - the graph to be added.

    • copy

      Graph<V,E> copy()
      Creates and returns an identical copy of the graph.
      Returns:
      an identical copy of the graph.

    • copyAsMultigraph

      Multigraph<V,E> copyAsMultigraph()
      Creates and returns an identical copy of the graph, as a Multigraph object. If the input graph is directed, so it will be the result.
      Returns:
      a multigraph, identical with this graph.

    • copyAsPseudograph

      Multigraph<V,E> copyAsPseudograph()
      Creates and returns an identical copy of the graph, as a Pseudograph object. If the input graph is directed, so it will be the result.
      Returns:
      a pseudograph, identical with this graph.

    • copy

      Graph<V,E> copy(boolean vertexWeights, boolean vertexLabels, boolean edges, boolean edgeWeights, boolean edgeLabels)
      Creates and returns a copy of the graph. Vertices are copied by default. All other elements may or may not be copied.
      Parameters:
      vertexWeights - true if the vertex weights should be copied.
      vertexLabels - true if the vertex labels should be copied.
      edges - true if the edges should be copied.
      edgeWeights - true if the edge weights should be copied.
      edgeLabels - true if the edge labels should be copied.
      Returns:
      a copy of the graph.

    • subgraph

      default Graph<V,E> subgraph(int... vertices)
      Creates and returns the subgraph induced by an array of vertices.
      Parameters:
      vertices - an array of vertices.
      Returns:
      the subgraph induced by the specified vertices.

    • subgraph

      Graph<V,E> subgraph(VertexSet vertexSet)
      Creates and returns the subgraph induced by a set of vertices.
      Parameters:
      vertexSet - a set of vertices.
      Returns:
      the subgraph induced by the specified vertices.

    • subgraph

      Graph<V,E> subgraph(Collection<Edge> edges)
      Creates and returns the subgraph generated by a collection of edges.
      Parameters:
      edges - a collection of edges.
      Returns:
      the subgraph generated by the given edges.

    • complement

      Graph<V,E> complement()
      Creates the complement of the graph. The complement of a graph G has the same vertex set as G and its edge set consists of the pairs of vertices that do not form an edge in G.
      Returns:
      the complement of the graph.

    • adjacencyMatrix

      int[][] adjacencyMatrix()
      Creates and return the adjacency matrix. The adjacency matrix of a graph shows the relationship between vertices. The matrix is square, the number of lines and columns being equal to the number of vertices, and it contains non-negative integers. An element at row i and column j has a positive value if u = vertexAt(j) appears in the adjacency list of v = vertexAt(i), where(v,u) represents an edge, and the value denotes the multiplicity of the edge (v,u), otherwise it is 0. The elements on the main diagonal denote the number of self-loops.

      In case of simple graphs, the matrix contains only values of 0 and 1. In case of undirected graphs, the matrix is symmetrical. If a graph implementation does not allow self-loops, the elements on the main diagonal are all 0.

      Returns:
      the adjacency matrix.

    • weightMatrix

      double[][] weightMatrix()
      Creates and returns the weight matrix. The weight matrix is created according to the same principles as the adjacency matrix. An element at row i and column j corresponding to an edge (v,u), where v = vertexAt(i) and u = vertexAt(j), has as value the weight of that edge: getEdgeWeight(v,u). The values on the main diagonal are all 0 otherwise, if the cell does not correspond to an edge, it has the value Graph.NO_EDGE_WEIGHT. The weight-matrix is not defined for multigraphs and pseudographs.
      Returns:
      the weight matrix.

    • incidenceMatrix

      int[][] incidenceMatrix()
      Creates and returns the incidence matrix. The incidence matrix shows the relationship between vertices and edges. Lines are associated with the vertices and columns with the edges. A vertex v = vertexAt(i) has the line number i, while an edge between v = vertexAt(i) and u = vertexAt(j) has the column number equal to its index, that is the position it appears in the array returned by the edges() method. In case of undirected graphs, an element at row i and column k has the value 1 if the edge having the index k is incident with the vertex v = vertexAt(i), and 0 otherwise. In case of directed graphs, an element at row i and column k has the value 1 if the edge having the index k is incident from the vertex v = vertexAt(i), -1 if it is incident to v, and 0 otherwise. Works only if the number of edges is less than Integer.MAX_VALUE.
      Returns:
      the incidence matrix.

    • isDirected

      boolean isDirected()
      Convenience method for testing if the graph is a directed graph.
      Returns:
      true if this is an instance of Digraph, false otherwise.

    • isAllowingMultipleEdges

      boolean isAllowingMultipleEdges()
      Convenience method for testing if the graph is a multigraph.
      Returns:
      true if this is an instance of Multigraph, false otherwise.

    • isAllowingSelfLoops

      boolean isAllowingSelfLoops()
      Convenience method for testing if the graph is a pseudograph.
      Returns:
      true if this is an instance of Pseudograph, false otherwise.

    • isSimple

      default boolean isSimple()
      Convenience method for testing if the graph does not contain multiple edges or self loops.
      Returns:
      true if this is an instance of Pseudograph.

    • setSafeMode

      void setSafeMode(boolean safeMode)
      Sets the flag indicating whether the graph is in safe mode or not. In safe mode, various checks are performed in order to respect the graph constraints and to prevent illegal method invocations. Setting the safe mode to false is useful when generating various type of graphs using algorithms that are guaranteed to respect the graph constraints. By default, all graphs are in safe mode.
      Parameters:
      safeMode - true if the safe mode is enabled (default), false otherwise.

    • isSafeMode

      boolean isSafeMode()
      Checks if the graph is in safe mode.
      Returns:
      true if the graph is in safe mode, false otherwise.

    • setEdgeDataSize

      void setEdgeDataSize(int edgeDataSize)
      Sets the maximum number of numerical values that can be stored on edges. Each such value must have an index corresponding to a number between 0 and edgeDataSize - 1.
      Parameters:
      edgeDataSize - how many numeric values are stored on the edges.

    • getEdgeDataSize

      int getEdgeDataSize()
      Returns the maximum number of values that can be stored on edges. By default, the method returns 1, since all graphs allow setting the weight of an edge. The weight has the predefined index WEIGHT, equal to 0. In case of Networks, the method returns 3, corresponding to Network.CAPACITY, Network.COST and Network.FLOW.
      Returns:
      the maximum number of values that can be stored on edges.

    • 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 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 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 neighborIterator(int) or 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 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 neighborIterator(int) or 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 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 neighborIterator(int) or 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 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 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 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 neighborIterator(int) or 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 neighborIterator(int) or 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.