Package org.graph4j

Interface Multigraph<V,E>

Type Parameters:

V - the type of vertex labels in this graph.

E - the type of edge labels in this graph.

All Superinterfaces:

Graph<V,E>

All Known Subinterfaces:

DirectedMultigraph<V,E>, DirectedPseudograph<V,E>, Pseudograph<V,E>

public interface Multigraph<V,E>
extends Graph<V,E>

Multiple (parallel) edges are allowed.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from interface org.graph4j.Graph

DEFAULT_EDGE_WEIGHT, DEFAULT_VERTEX_WEIGHT, WEIGHT

Method Summary

Modifier and Type	Method	Description
int	addEdge(int v, int u, double weight)	Adds a new weighted edge to the 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	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.
Multigraph<V,E>	copy()	Creates and returns an identical copy of the graph.
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)
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.
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)
default boolean	isUniversal(int v)	Checks if a vertex is universal, meaning that it is adjacent to all other vertices in the graph.
default long	maxEdges()	Returns the maximum number of edges the graph can have.
int	multiplicity(int v, int u)
default int	multiplicity(Edge e)
void	resetEdgeData(int dataType, double value)
void	setEdgeData(int dataType, int v, int u, double value)
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	setVertexLabel(int v, V label)	Sets the label for the specified vertex.
void	setVertexWeight(int v, double weight)	Sets the weight of a vertex.
Multigraph<V,E>	subgraph(Collection<Edge> edges)	Creates and returns the subgraph generated by a collection of edges.
Multigraph<V,E>	subgraph(VertexSet vertexSet)	Creates and returns the subgraph induced by a set of vertices.
Graph<V,E>	supportGraph()	The support graph of a multigraph or a pseudograph G is an undirected graph containing all the vertices of G, self loops are removed and multiple edges are merged into a single one.

Methods inherited from interface org.graph4j.Graph

addEdge, addEdge, addEdge, addGraph, addVertex, addVertex, addVertices, adjacencyMatrix, adjListPos, complement, containsEdge, containsEdge, containsVertex, contractVertices, copy, copyAsMultigraph, copyAsPseudograph, degree, degrees, duplicateVertex, edge, edgeIterator, edges, edgesOf, getEdgeDataSize, getName, incidenceMatrix, indexOf, isAllowingMultipleEdges, isAllowingSelfLoops, isComplete, isDefaultVertexNumbering, isDirected, isEdgeless, isEmpty, isIsolated, isPendant, isSafeMode, isSimple, maxVertexNumber, neighborIterator, neighborIterator, neighbors, numEdges, numVertices, removeAllEdges, removeEdge, removeEdge, removeVertex, removeVertices, renumberAdding, setEdgeDataSize, setName, setSafeMode, splitEdge, subgraph, vertexAt, vertexIterator, vertices, weightMatrix

Method Details

supportGraph

Graph<V,E> supportGraph()

The support graph of a multigraph or a pseudograph G is an undirected graph containing all the vertices of G, self loops are removed and multiple edges are merged into a single one. The edge labels are all set to null. In case of directed multigraphs graphs, edge data is removed. For undirected multigraphs, edge data is cumulated.

Returns:

a new graph, representing the support graph.

copy

Multigraph<V,E> copy()

Description copied from interface: Graph

Creates and returns an identical copy of the graph.

Specified by:

copy in interface Graph<V,E>

Returns:

an identical copy of the multigraph.

subgraph

Multigraph<V,E> subgraph(VertexSet vertexSet)

Description copied from interface: Graph

Creates and returns the subgraph induced by a set of vertices.

Specified by:

subgraph in interface Graph<V,E>

Parameters:

vertexSet - a set of vertices.

Returns:

the subgraph induced by the specified vertices.

subgraph

Multigraph<V,E> subgraph(Collection<Edge> edges)

Description copied from interface: Graph

Creates and returns the subgraph generated by a collection of edges.

Specified by:

subgraph in interface Graph<V,E>

Parameters:

edges - a collection of edges.

Returns:

the subgraph generated by the given edges.

multiplicity

int multiplicity(int v,
 int u)

Parameters:

v - a vertex number.

u - a vertex number.

Returns:

how many times u appears in the adjacency list of v.

multiplicity

default int multiplicity(Edge e)

Parameters:

e - an edge.

Returns:

how many times an edge appears in the multigraph.

isUniversal

default boolean isUniversal(int v)

Description copied from interface: Graph

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.

Specified by:

isUniversal in interface Graph<V,E>

Parameters:

v - a vertex number.

Returns:

true if v is universal.

maxEdges

default long maxEdges()

Description copied from interface: Graph

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.

Specified by:

maxEdges in interface Graph<V,E>

Returns:

the maximum number of edges the graph can have.

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