Package com.jgalgo.graph

Class Graphs

java.lang.Object

com.jgalgo.graph.Graphs

public class Graphs
extends Object

Static methods class for graphs.

Author:

Barak Ugav

Method Summary

Modifier and Type	Method	Description
static <V,E> boolean	containsParallelEdges(Graph<V,E> g)	Check whether a graph contain parallel edges.
static <E> E	randEdge(Graph<?,E> g, Random rand)	Get a random edge from the given graph.
static int	randEdge(IntGraph g, Random rand)	Get a random edge from the given int graph.
static <V> V	randVertex(Graph<V,?> g, Random rand)	Get a random vertex from the given graph.
static int	randVertex(IntGraph g, Random rand)	Get a random vertex from the given int graph.
static <V,E> Set<E>	selfEdges(Graph<V,E> g)	Get a view of all the self edges in a graph.
static IntSet	selfEdges(IntGraph g)	Get a view of all the self edges in an int graph.
static <V,E> Graph<V,E>	subGraph(Graph<V,E> g, Collection<V> vertices)	Create a new graph that is an induced subgraph of the given graph.
static <V,E> Graph<V,E>	subGraph(Graph<V,E> g, Collection<V> vertices, Collection<E> edges)	Create a new graph that is a subgraph of the given graph.
static <V,E> Graph<V,E>	subGraph(Graph<V,E> g, Collection<V> vertices, Collection<E> edges, boolean copyVerticesWeights, boolean copyEdgesWeights)	Create a new graph that is a subgraph of the given graph, with option to copy weights.
static IntGraph	subGraph(IntGraph g, IntCollection vertices, IntCollection edges, boolean copyVerticesWeights, boolean copyEdgesWeights)	Create a new graph that is a subgraph of the given int graph, with option to copy weights.

Methods inherited from class java.lang.Object

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

Method Detail

subGraph

public static <V,E> Graph<V,E> subGraph(Graph<V,E> g,
                                                    Collection<V> vertices)

Create a new graph that is an induced subgraph of the given graph.

An induced subgraph of a graph \(G=(V,E)\) is a graph \(G'=(V',E')\) where \(V' \subseteq V\) and \(E' = \{\{u,v\} \mid u,v \in V', \{u,v\} \in E\}\). The created graph will have the same type (directed/undirected) as the given graph. The vertices and edges of the created graph will be a subset of the vertices and edges of the given graph.

The weights of both vertices and edges will not be copied to the new sub graph. For more flexible sub graph creation, see subGraph(Graph, Collection, Collection, boolean, boolean).

If g is IntGraph, the returned sub graph is also an IntGraph.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - the graph to create a sub graph from

vertices - the vertices of the sub graph

Returns:

a new graph that is an induced subgraph of the given graph

subGraph

public static <V,E> Graph<V,E> subGraph(Graph<V,E> g,
                                                    Collection<V> vertices,
                                                    Collection<E> edges)

Create a new graph that is a subgraph of the given graph.

If edges is null, then the created graph will be an induced subgraph of the given graph, namely an induced subgraph of a graph \(G=(V,E)\) is a graph \(G'=(V',E')\) where \(V' \subseteq V\) and \(E' = \{\{u,v\} \mid u,v \in V', \{u,v\} \in E\}\). The behavior is similar to subGraph(Graph, Collection). vertices must not be null in this case.

If vertices is null, then edges must not be null, and the sub graph will contain all the vertices which are either a source or a target of an edge in edges.

The created graph will have the same type (directed/undirected) as the given graph. The vertices and edges of the created graph will be a subset of the vertices and edges of the given graph.

The weights of both vertices and edges will not be copied to the new sub graph. For more flexible sub graph creation, see subGraph(Graph, Collection, Collection, boolean, boolean).

If g is IntGraph, the returned sub graph is also an IntGraph.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - the graph to create a sub graph from

vertices - the vertices of the sub graph, if null then edges must not be null and the vertices of the sub graph will be all the vertices which are either a source or a target of an edge in edges

edges - the edges of the sub graph, if null then vertices must not be null and the sub graph will be an induced subgraph of the given graph

Returns:

a new graph that is a subgraph of the given graph

Throws:

NullPointerException - if both vertices and edges are null

subGraph

public static <V,E> Graph<V,E> subGraph(Graph<V,E> g,
                                                    Collection<V> vertices,
                                                    Collection<E> edges,
                                                    boolean copyVerticesWeights,
                                                    boolean copyEdgesWeights)

Create a new graph that is a subgraph of the given graph, with option to copy weights.

If edges is null, then the created graph will be an induced subgraph of the given graph, namely an induced subgraph of a graph \(G=(V,E)\) is a graph \(G'=(V',E')\) where \(V' \subseteq V\) and \(E' = \{\{u,v\} \mid u,v \in V', \{u,v\} \in E\}\). The behavior is similar to subGraph(Graph, Collection). vertices must not be null in this case.

If vertices is null, then edges must not be null, and the sub graph will contain all the vertices which are either a source or a target of an edge in edges.

The created graph will have the same type (directed/undirected) as the given graph. The vertices and edges of the created graph will be a subset of the vertices and edges of the given graph.

An additional parameter options for copying the weights of the vertices and edges of the given graph to the new sub graph are provided. If copyVerticesWeights is true, then all the vertices weights of the given graph will be copied to the new sub graph. If copyEdgesWeights is true, then all the edges weights of the given graph will be copied to the new sub graph.

If g is IntGraph, the returned sub graph is also an IntGraph.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - the graph to create a sub graph from

vertices - the vertices of the sub graph, if null then edges must not be null and the vertices of the sub graph will be all the vertices which are either a source or a target of an edge in edges

edges - the edges of the sub graph, if null then vertices must not be null and the sub graph will be an induced subgraph of the given graph

copyVerticesWeights - if true then all the vertices weights of the given graph will be copied to the new sub graph

copyEdgesWeights - if true then all the edges weights of the given graph will be copied to the new sub graph

Returns:

a new graph that is a subgraph of the given graph

Throws:

NullPointerException - if both vertices and edges are null

subGraph

public static IntGraph subGraph(IntGraph g,
                                IntCollection vertices,
                                IntCollection edges,
                                boolean copyVerticesWeights,
                                boolean copyEdgesWeights)

Create a new graph that is a subgraph of the given int graph, with option to copy weights.

If edges is null, then the created graph will be an induced subgraph of the given graph, namely an induced subgraph of a graph \(G=(V,E)\) is a graph \(G'=(V',E')\) where \(V' \subseteq V\) and \(E' = \{\{u,v\} \mid u,v \in V', \{u,v\} \in E\}\).

If vertices is null, then edges must not be null, and the sub graph will contain all the vertices which are either a source or a target of an edge in edges.

The created graph will have the same type (directed/undirected) as the given graph. The vertices and edges of the created graph will be a subset of the vertices and edges of the given graph.

An additional parameter options for copying the weights of the vertices and edges of the given graph to the new sub graph are provided. If copyVerticesWeights is true, then all the vertices weights of the given graph will be copied to the new sub graph. If copyEdgesWeights is true, then all the edges weights of the given graph will be copied to the new sub graph.

Parameters:

g - the graph to create a sub graph from

vertices - the vertices of the sub graph, if null then edges must not be null and the vertices of the sub graph will be all the vertices which are either a source or a target of an edge in edges

edges - the edges of the sub graph, if null then vertices must not be null and the sub graph will be an induced subgraph of the given graph

copyVerticesWeights - if true then all the vertices weights of the given graph will be copied to the new sub graph

copyEdgesWeights - if true then all the edges weights of the given graph will be copied to the new sub graph

Returns:

a new graph that is a subgraph of the given graph

Throws:

NullPointerException - if both vertices and edges are null

randVertex

public static <V> V randVertex(Graph<V,?> g,
                               Random rand)

Get a random vertex from the given graph.

Type Parameters:

V - the vertices type

Parameters:

g - the graph

rand - the random number generator

Returns:

a random vertex from the given graph

Throws:

IllegalArgumentException - if the graph is contains no vertices

randVertex

public static int randVertex(IntGraph g,
                             Random rand)

Get a random vertex from the given int graph.

Parameters:

g - the graph

rand - the random number generator

Returns:

a random vertex from the given graph

Throws:

IllegalArgumentException - if the graph is contains no vertices

randEdge

public static <E> E randEdge(Graph<?,E> g,
                             Random rand)

Get a random edge from the given graph.

Type Parameters:

E - the edges type

Parameters:

g - the graph

rand - the random number generator

Returns:

a random edge from the given graph

Throws:

IllegalArgumentException - if the graph is contains no edges

randEdge

public static int randEdge(IntGraph g,
                           Random rand)

Get a random edge from the given int graph.

Parameters:

g - the graph

rand - the random number generator

Returns:

a random edge from the given graph

Throws:

IllegalArgumentException - if the graph is contains no edges

selfEdges

public static <V,E> Set<E> selfEdges(Graph<V,E> g)

Get a view of all the self edges in a graph.

The returned set is a view, namely it will be updated when the graph is updated.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

Returns:

a view of all the self edges in the graph

selfEdges

public static IntSet selfEdges(IntGraph g)

Get a view of all the self edges in an int graph.

The returned set is a view, namely it will be updated when the graph is updated.

Parameters:

g - an int graph

Returns:

a view of all the self edges in the graph

containsParallelEdges

public static <V,E> boolean containsParallelEdges(Graph<V,E> g)

Check whether a graph contain parallel edges.

Two parallel edges are edges that have the same source and target vertices.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

Returns:

true if the graph contain at least one pair of parallel edges, else false