Class NoIncomingNoReindexSparseDirectedSpecifics

java.lang.Object
org.jgrapht.opt.graph.sparse.specifics.NoIncomingNoReindexSparseDirectedSpecifics
All Implemented Interfaces:
SparseGraphSpecifics
Direct Known Subclasses:
IncomingNoReindexSparseDirectedSpecifics

public class NoIncomingNoReindexSparseDirectedSpecifics extends Object implements SparseGraphSpecifics
Specifics for a sparse directed graph which does not re-index the edges and does not support incoming edges. No reindexing means that the edges are numbered in increasing order using the order that the user loads the edges. Support for incoming edges is not provided. All methods that need access to incoming edges throw an exception.
  • Field Details

    • UNMODIFIABLE

      protected static final String UNMODIFIABLE
      See Also:
    • NO_INCOMING

      protected static final String NO_INCOMING
      See Also:
    • source

      protected int[] source
      Source vertex of edge
    • target

      protected int[] target
      Target vertex of edge
    • outIncidenceMatrix

      protected CSRBooleanMatrix outIncidenceMatrix
      Incidence matrix with outgoing edges
  • Constructor Details

    • NoIncomingNoReindexSparseDirectedSpecifics

      public NoIncomingNoReindexSparseDirectedSpecifics(int numVertices, int numEdges, Supplier<Stream<Pair<Integer,Integer>>> edges)
      Create a new graph from an edge list.
      Parameters:
      numVertices - the number of vertices
      numEdges - the number of edges
      edges - a supplier of an edge list
  • Method Details

    • edgesCount

      public long edgesCount()
      Description copied from interface: SparseGraphSpecifics
      Get the number of edges.
      Specified by:
      edgesCount in interface SparseGraphSpecifics
      Returns:
      the number of edges
    • degreeOf

      public long degreeOf(Integer vertex)
      Description copied from interface: SparseGraphSpecifics
      Returns the degree of the specified vertex.

      A degree of a vertex in an undirected graph is the number of edges touching that vertex. Edges with same source and target vertices (self-loops) are counted twice.

      In directed graphs this method returns the sum of the "in degree" and the "out degree".

      Specified by:
      degreeOf in interface SparseGraphSpecifics
      Parameters:
      vertex - vertex whose degree is to be calculated.
      Returns:
      the degree of the specified vertex.
    • edgesOf

      public Set<Integer> edgesOf(Integer vertex)
      Description copied from interface: SparseGraphSpecifics
      Returns a set of all edges touching the specified vertex. If no edges are touching the specified vertex returns an empty set.
      Specified by:
      edgesOf in interface SparseGraphSpecifics
      Parameters:
      vertex - the vertex for which a set of touching edges is to be returned.
      Returns:
      a set of all edges touching the specified vertex.
    • inDegreeOf

      public long inDegreeOf(Integer vertex)
      Description copied from interface: SparseGraphSpecifics
      Returns the "in degree" of the specified vertex.

      The "in degree" of a vertex in a directed graph is the number of inward directed edges from that vertex. See http://mathworld.wolfram.com/Indegree.html.

      In the case of undirected graphs this method returns the number of edges touching the vertex. Edges with same source and target vertices (self-loops) are counted twice.

      Specified by:
      inDegreeOf in interface SparseGraphSpecifics
      Parameters:
      vertex - vertex whose degree is to be calculated.
      Returns:
      the degree of the specified vertex.
    • incomingEdgesOf

      public Set<Integer> incomingEdgesOf(Integer vertex)
      Description copied from interface: SparseGraphSpecifics
      Returns a set of all edges incoming into the specified vertex.

      In the case of undirected graphs this method returns all edges touching the vertex, thus, some of the returned edges may have their source and target vertices in the opposite order.

      Specified by:
      incomingEdgesOf in interface SparseGraphSpecifics
      Parameters:
      vertex - the vertex for which the list of incoming edges to be returned.
      Returns:
      a set of all edges incoming into the specified vertex.
    • outDegreeOf

      public long outDegreeOf(Integer vertex)
      Description copied from interface: SparseGraphSpecifics
      Returns the "out degree" of the specified vertex.

      The "out degree" of a vertex in a directed graph is the number of outward directed edges from that vertex. See http://mathworld.wolfram.com/Outdegree.html.

      In the case of undirected graphs this method returns the number of edges touching the vertex. Edges with same source and target vertices (self-loops) are counted twice.

      Specified by:
      outDegreeOf in interface SparseGraphSpecifics
      Parameters:
      vertex - vertex whose degree is to be calculated.
      Returns:
      the degree of the specified vertex.
    • outgoingEdgesOf

      public Set<Integer> outgoingEdgesOf(Integer vertex)
      Description copied from interface: SparseGraphSpecifics
      Returns a set of all edges outgoing from the specified vertex.

      In the case of undirected graphs this method returns all edges touching the vertex, thus, some of the returned edges may have their source and target vertices in the opposite order.

      Specified by:
      outgoingEdgesOf in interface SparseGraphSpecifics
      Parameters:
      vertex - the vertex for which the list of outgoing edges to be returned.
      Returns:
      a set of all edges outgoing from the specified vertex.
    • verticesCount

      public long verticesCount()
      Description copied from interface: SparseGraphSpecifics
      Get the number of vertices
      Specified by:
      verticesCount in interface SparseGraphSpecifics
      Returns:
      the number of vertices
    • getEdgeSource

      public Integer getEdgeSource(Integer e)
      Description copied from interface: SparseGraphSpecifics
      Returns the source vertex of an edge. For an undirected graph, source and target are distinguishable designations (but without any mathematical meaning).
      Specified by:
      getEdgeSource in interface SparseGraphSpecifics
      Parameters:
      e - edge of interest
      Returns:
      source vertex
    • getEdgeTarget

      public Integer getEdgeTarget(Integer e)
      Description copied from interface: SparseGraphSpecifics
      Returns the target vertex of an edge. For an undirected graph, source and target are distinguishable designations (but without any mathematical meaning).
      Specified by:
      getEdgeTarget in interface SparseGraphSpecifics
      Parameters:
      e - edge of interest
      Returns:
      target vertex
    • getType

      public GraphType getType()
      Description copied from interface: SparseGraphSpecifics
      Get the graph type. The graph type can be used to query for additional metadata such as whether the graph supports directed or undirected edges, self-loops, multiple (parallel) edges, weights, etc.
      Specified by:
      getType in interface SparseGraphSpecifics
      Returns:
      the graph type
    • getEdge

      public Integer getEdge(Integer sourceVertex, Integer targetVertex)
      Returns an edge connecting source vertex to target vertex if such vertices and such edge exist in this graph. Otherwise returns null. If any of the specified vertices is null returns null

      In undirected graphs, the returned edge may have its source and target vertices in the opposite order.

      This operation costs $O(d)$ where $d$ is the out-degree of the source vertex.
      Specified by:
      getEdge in interface SparseGraphSpecifics
      Parameters:
      sourceVertex - source vertex of the edge.
      targetVertex - target vertex of the edge.
      Returns:
      an edge connecting source vertex to target vertex.
    • getAllEdges

      public Set<Integer> getAllEdges(Integer sourceVertex, Integer targetVertex)
      Returns a set of all edges connecting source vertex to target vertex if such vertices exist in this graph. If any of the vertices does not exist or is null, returns null. If both vertices exist but no edges found, returns an empty set.

      In undirected graphs, some of the returned edges may have their source and target vertices in the opposite order. In simple graphs the returned set is either singleton set or empty set.

      This operation costs $O(d)$ where $d$ is the out-degree of the source vertex.
      Specified by:
      getAllEdges in interface SparseGraphSpecifics
      Parameters:
      sourceVertex - source vertex of the edge.
      targetVertex - target vertex of the edge.
      Returns:
      a set of all edges connecting source vertex to target vertex.