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

Class IncidenceMatrixSparseUndirectedSpecifics

  • All Implemented Interfaces:
    SparseGraphSpecifics
    public class IncidenceMatrixSparseUndirectedSpecifics
extends java.lang.Object
implements SparseGraphSpecifics
    Specifics for a sparse undirected graph using an incidence matrix representation.

    • Constructor Summary

      Constructors 
      Constructor Description
      IncidenceMatrixSparseUndirectedSpecifics​(int numVertices, int numEdges, java.util.function.Supplier<java.util.stream.Stream<Pair<java.lang.Integer,​java.lang.Integer>>> edges)
      Create a new graph from an edge stream

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      long degreeOf​(java.lang.Integer vertex)
      Returns the degree of the specified vertex.
      long edgesCount()
      Get the number of edges.
      java.util.Set<java.lang.Integer> edgesOf​(java.lang.Integer vertex)
      Returns a set of all edges touching the specified vertex.
      java.util.Set<java.lang.Integer> getAllEdges​(java.lang.Integer sourceVertex, java.lang.Integer targetVertex)
      Returns a set of all edges connecting source vertex to target vertex if such vertices exist in this graph.
      java.lang.Integer getEdge​(java.lang.Integer sourceVertex, java.lang.Integer targetVertex)
      Returns an edge connecting source vertex to target vertex if such vertices and such edge exist in this graph.
      java.lang.Integer getEdgeSource​(java.lang.Integer e)
      Returns the source vertex of an edge.
      java.lang.Integer getEdgeTarget​(java.lang.Integer e)
      Returns the target vertex of an edge.
      GraphType getType()
      Get the graph type.
      java.util.Set<java.lang.Integer> incomingEdgesOf​(java.lang.Integer vertex)
      Returns a set of all edges incoming into the specified vertex.
      long inDegreeOf​(java.lang.Integer vertex)
      Returns the "in degree" of the specified vertex.
      long outDegreeOf​(java.lang.Integer vertex)
      Returns the "out degree" of the specified vertex.
      java.util.Set<java.lang.Integer> outgoingEdgesOf​(java.lang.Integer vertex)
      Returns a set of all edges outgoing from the specified vertex.
      long verticesCount()
      Get the number of vertices

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • source

        protected int[] source

      • target

        protected int[] target

    • Constructor Detail

      • IncidenceMatrixSparseUndirectedSpecifics

        public IncidenceMatrixSparseUndirectedSpecifics​(int numVertices,
                                                int numEdges,
                                                java.util.function.Supplier<java.util.stream.Stream<Pair<java.lang.Integer,​java.lang.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 Detail

      • degreeOf

        public long degreeOf​(java.lang.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 java.util.Set<java.lang.Integer> edgesOf​(java.lang.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​(java.lang.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 java.util.Set<java.lang.Integer> incomingEdgesOf​(java.lang.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​(java.lang.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 java.util.Set<java.lang.Integer> outgoingEdgesOf​(java.lang.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 java.lang.Integer getEdgeSource​(java.lang.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 java.lang.Integer getEdgeTarget​(java.lang.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 java.lang.Integer getEdge​(java.lang.Integer sourceVertex,
                                 java.lang.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 java.util.Set<java.lang.Integer> getAllEdges​(java.lang.Integer sourceVertex,
                                                    java.lang.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.