Module org.jgrapht.opt
Package org.jgrapht.opt.graph.sparse.specifics

Class IncidenceMatrixSparseUndirectedSpecifics

java.lang.Object
org.jgrapht.opt.graph.sparse.specifics.IncidenceMatrixSparseUndirectedSpecifics
All Implemented Interfaces:
SparseGraphSpecifics
public class IncidenceMatrixSparseUndirectedSpecifics extends Object implements SparseGraphSpecifics
Specifics for a sparse undirected graph using an incidence matrix representation.
Author:
Dimitrios Michail

  • Field Details

    • UNMODIFIABLE

      protected static final String UNMODIFIABLE
      See Also:

    • incidenceMatrix

      protected CSRBooleanMatrix incidenceMatrix

    • source

      protected int[] source

    • target

      protected int[] target

  • Constructor Details

    • IncidenceMatrixSparseUndirectedSpecifics

      public IncidenceMatrixSparseUndirectedSpecifics(int numVertices, int numEdges, Supplier<Stream<Pair<Integer,Integer>>> edges)
      Create a new graph from an edge stream
      Parameters:
      numVertices - number of vertices
      numEdges - number of edges
      edges - a supplier of an edge stream

  • 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

    • 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

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

    • 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

    • 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

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