Package org.graph4j

Interface Network<V,E>

Type Parameters:

V - the type of vertex labels in this graph.

E - the type of edge labels in this graph.

All Superinterfaces:

Digraph<V,E>, Graph<V,E>

public interface Network<V,E>
extends Digraph<V,E>

Represents a single commodity transportation (flow) network. In addition to the weight, a network offers the possibility to set the capacity, cost and flow of the edges, using the methods that set the custom edge data of any graph, specifying the following data types: Network.CAPACITY, Network.COST and NETWORK.FLOW.

Author:

Cristian Frăsinaru

Field Summary

Fields

Modifier and Type	Field	Description
static final int	CAPACITY	0 (same as Graph.WEIGHT)
static final int	COST	1
static final double	DEFAULT_EDGE_CAPACITY	1
static final double	DEFAULT_EDGE_COST	0
static final double	DEFAULT_EDGE_FLOW	0
static final int	FLOW	2

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 capacity)	Adds a new edge to the network, having the specified capacity.
int	addEdge(int v, int u, double capacity, double cost)	Adds a new edge to the network, having the specified capacity and cost.
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 capacity)	Adds a new edge to the network, having the specified label and capacity The endpoints of the edge are identified using their vertex numbers.
int	addLabeledEdge(int v, int u, E label, double capacity, double cost)	Adds a new edge to the network, having the specified label, capacity and cost.
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.
void	checkFlow()	Checks if the flow values of the network represent a valid flow.
void	checkPreflow()	Checks if the flow values of the network represent a valid preflow.
Network<V,E>	complement()	Creates the complement of the digraph.
Network<V,E>	copy()	Creates an identical copy of the digraph.
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.
int	getSink()	Returns the sink of the network.
int	getSource()	Returns the source of the network.
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	isFlowValid()	Checks if the flow values of the network represent a valid flow.
default boolean	isPreflowValid()	Checks if the flow values of the network represent a valid preflow.
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	setSink(int sink)	Sets the sink of the network.
void	setSource(int source)	Sets the source of the network.
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.
default Network<V,E>	subgraph(int... vertices)	Creates and returns the subgraph induced by an array of vertices.
Network<V,E>	subgraph(Collection<Edge> edges)	Creates and returns the subgraph generated by a collection of edges.
Network<V,E>	subgraph(VertexSet vertexSet)	Creates and returns the subgraph induced by a set of vertices.

Methods inherited from interface org.graph4j.Digraph

incomingEdgesTo, indegree, indegrees, isSink, isSource, isSymmetrical, neighborIterator, outdegree, outdegrees, outgoingEdgesFrom, predecessorIterator, predecessorIterator, predecessors, successorIterator, successorIterator, successors, supportGraph

Methods inherited from interface org.graph4j.Graph

addEdge, addEdge, addEdge, addGraph, addVertex, addVertex, addVertices, adjacencyMatrix, adjListPos, 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, isUniversal, maxEdges, maxVertexNumber, neighborIterator, neighborIterator, neighbors, numEdges, numVertices, removeAllEdges, removeEdge, removeEdge, removeVertex, removeVertices, renumberAdding, setEdgeDataSize, setName, setSafeMode, splitEdge, vertexAt, vertexIterator, vertices, weightMatrix

Field Details

CAPACITY

static final int CAPACITY

0 (same as Graph.WEIGHT)

See Also:

• Constant Field Values

COST

static final int COST

1

See Also:

• Constant Field Values

FLOW

static final int FLOW

2

See Also:

• Constant Field Values

DEFAULT_EDGE_CAPACITY

static final double DEFAULT_EDGE_CAPACITY

1

See Also:

• Constant Field Values

DEFAULT_EDGE_COST

static final double DEFAULT_EDGE_COST

0

See Also:

• Constant Field Values

DEFAULT_EDGE_FLOW

static final double DEFAULT_EDGE_FLOW

0

See Also:

• Constant Field Values

Method Details

setSource

void setSource(int source)

Sets the source of the network.

Parameters:

source - the source of the network.

getSource

int getSource()

Returns the source of the network.

Returns:

the source of the network.

setSink

void setSink(int sink)

Sets the sink of the network.

Parameters:

sink - the sink of the network.

getSink

int getSink()

Returns the sink of the network.

Returns:

the sink of the network.

addEdge

int addEdge(int v,
 int u,
 double capacity)

Adds a new edge to the network, having the specified capacity. 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.

capacity - the capacity of the edge.

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.

addEdge

int addEdge(int v,
 int u,
 double capacity,
 double cost)

Adds a new edge to the network, having the specified capacity and cost. 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.

capacity - the capacity of the edge.

cost - the cost of the edge.

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,
 double capacity)

Adds a new edge to the network, having the specified label and capacity 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 - the label of the edge.

capacity - the capacity of the edge.

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,
 double capacity,
 double cost)

Adds a new edge to the network, having the specified label, capacity and cost. 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 - the label of the edge.

capacity - the capacity of the edge.

cost - the cost of the edge.

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.

copy

Network<V,E> copy()

Description copied from interface: Digraph

Creates an identical copy of the digraph.

Specified by:

copy in interface Digraph<V,E>

Specified by:

copy in interface Graph<V,E>

Returns:

an identical copy of the digraph.

complement

Network<V,E> complement()

Description copied from interface: Digraph

Creates the complement of the digraph. The complement of a directed graph G has the same vertex set as G and its edge set consists of the edges not present in G.

Specified by:

complement in interface Digraph<V,E>

Specified by:

complement in interface Graph<V,E>

Returns:

the complement of the digraph.

subgraph

Network<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 Digraph<V,E>

Specified by:

subgraph in interface Graph<V,E>

Parameters:

vertexSet - a set of vertices.

Returns:

the subgraph induced by the specified vertices.

subgraph

default Network<V,E> subgraph(int... vertices)

Description copied from interface: Graph

Creates and returns the subgraph induced by an array of vertices.

Specified by:

subgraph in interface Digraph<V,E>

Specified by:

subgraph in interface Graph<V,E>

Parameters:

vertices - an array of vertices.

Returns:

the subgraph induced by the specified vertices.

subgraph

Network<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 Digraph<V,E>

Specified by:

subgraph in interface Graph<V,E>

Parameters:

edges - a collection of edges.

Returns:

the subgraph generated by the given edges.

checkFlow

void checkFlow()
        throws InvalidFlowException

Checks if the flow values of the network represent a valid flow.

Throws:

InvalidFlowException - if the flow is not valid.

isFlowValid

default boolean isFlowValid()

Checks if the flow values of the network represent a valid flow.

Returns:

true if the flow is valid, false otherwise.

checkPreflow

void checkPreflow()
           throws InvalidFlowException

Checks if the flow values of the network represent a valid preflow.

Throws:

InvalidFlowException - if the preflow is not valid.

isPreflowValid

default boolean isPreflowValid()

Checks if the flow values of the network represent a valid preflow.

Returns:

true if the flow is valid, false otherwise.

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.

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)

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.