Class IncidenceMatrixSparseUndirectedSpecifics
- java.lang.Object
-
- org.jgrapht.opt.graph.sparse.specifics.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.
-
-
Field Summary
Fields Modifier and Type Field Description protected CSRBooleanMatrix
incidenceMatrix
protected int[]
source
protected int[]
target
protected static java.lang.String
UNMODIFIABLE
-
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
-
Methods inherited from interface org.jgrapht.opt.graph.sparse.specifics.SparseGraphSpecifics
assertEdgeExist, assertVertexExist, containsEdge, containsVertex, edgeSet, getEdgeWeight, setEdgeWeight, vertexSet
-
-
-
-
Field Detail
-
UNMODIFIABLE
protected static final java.lang.String UNMODIFIABLE
- See Also:
- Constant Field Values
-
incidenceMatrix
protected CSRBooleanMatrix incidenceMatrix
-
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 verticesnumEdges
- number of edgesedges
- a supplier of an edge stream
-
-
Method Detail
-
edgesCount
public long edgesCount()
Description copied from interface:SparseGraphSpecifics
Get the number of edges.- Specified by:
edgesCount
in interfaceSparseGraphSpecifics
- Returns:
- the number of edges
-
verticesCount
public long verticesCount()
Description copied from interface:SparseGraphSpecifics
Get the number of vertices- Specified by:
verticesCount
in interfaceSparseGraphSpecifics
- Returns:
- the number of vertices
-
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 interfaceSparseGraphSpecifics
- 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 interfaceSparseGraphSpecifics
- 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 interfaceSparseGraphSpecifics
- 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 interfaceSparseGraphSpecifics
- 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 interfaceSparseGraphSpecifics
- 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 interfaceSparseGraphSpecifics
- 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 interfaceSparseGraphSpecifics
- 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 interfaceSparseGraphSpecifics
- 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 interfaceSparseGraphSpecifics
- 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 returnsnull
. If any of the specified vertices isnull
returnsnull
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 interfaceSparseGraphSpecifics
- 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 isnull
, returnsnull
. 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 interfaceSparseGraphSpecifics
- 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.
-
-