agape.tools

Class Operations

java.lang.Object

agape.tools.Operations

public class Operations
extends java.lang.Object

This class provides a set of methods used in graph algorithms.

Author:

V. Levorato

Constructor Summary

Constructors

Constructor and Description
Operations()

Method Summary

Methods

Modifier and Type	Method and Description
static <V,E> void	addAllVertices(edu.uci.ics.jung.graph.Graph<V,E> G, java.util.Set<V> A) Add all the vertices of set A to the graph G.
static <V,E> V	chooseRandVertex(edu.uci.ics.jung.graph.Graph<V,E> G) Return a vertex of G choosen randomly.
static <V,E> edu.uci.ics.jung.graph.Graph<V,E>	copyDirectedSparseGraph(edu.uci.ics.jung.graph.Graph<V,E> G) Full copy (arcs + vertices) of the Graph.
static <V,E> edu.uci.ics.jung.graph.Graph<V,E>	copyGraph(edu.uci.ics.jung.graph.Graph<V,E> G, org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> f) Full copy (arcs + vertices) of a graph using the given factory.
static <V,E> edu.uci.ics.jung.graph.Graph<V,E>	copyUndirectedSparseGraph(edu.uci.ics.jung.graph.Graph<V,E> G) Full copy (edges + vertices) of the Graph.
static <V,E> java.util.Set<V>	getAllDegVertex(edu.uci.ics.jung.graph.Graph<V,E> G, int deg) Retunrs the set of all the vertices of degree 'deg' for the graph G.
static <V,E> java.util.Set<V>	getAllMaxDegVertex(edu.uci.ics.jung.graph.Graph<V,E> G) Returns a set containing vertices of G with highest degree.
static <V,E> java.util.Set<V>	getAllMinDegVertex(edu.uci.ics.jung.graph.Graph<V,E> G) Returns a set containing vertices of G with lowest degree.
static <V,E> V	getDegVertex(edu.uci.ics.jung.graph.Graph<V,E> G, int deg) Returns a vertex of degree 'deg' for the graph G.
static <V,E> double	getDensity(edu.uci.ics.jung.graph.Graph<V,E> G) Returns density of a graph G.
static <V,E> int	getDiameter(edu.uci.ics.jung.graph.Graph<V,E> G) Returns the diameter of a graph.
static <V,E> int	getMaxDeg(edu.uci.ics.jung.graph.Graph<V,E> G) Returns the maximum degree of G.
static <V,E> V	getMaxDegVertex(edu.uci.ics.jung.graph.Graph<V,E> G) Returns a vertex of G with maximum degree.
static <V,E> int	getMinDeg(edu.uci.ics.jung.graph.Graph<V,E> G) Returns the minimum degree of G.
static <V,E> V	getMinDegVertex(edu.uci.ics.jung.graph.Graph<V,E> G) Returns a vertex of G with minimum degree.
static <V,E> int	getNbEdges(edu.uci.ics.jung.graph.Graph<V,E> G, java.util.Set<V> A) Returns the amount of edges which are linking vertices of A.
static <V,E> java.util.Set<V>	getNeighbors(edu.uci.ics.jung.graph.Graph<V,E> G, java.util.Set<V> S) Returns all neighbors of S without S (usually denoted as N(S)).
static <V,E> java.util.Set<V>	getNeighbors(edu.uci.ics.jung.graph.Graph<V,E> G, V v, int dist) Returns the neighbors vertices of a set of v at a given distance.
static <V,E> boolean	isAcyclic(edu.uci.ics.jung.graph.Graph<V,E> G) Returns true if a directed graph has no circuit.
static <V,E> boolean	isClique(edu.uci.ics.jung.graph.Graph<V,E> G, java.util.Set<V> K) Tests if a set of vertices is a clique for the Graph G.
static <V,E> boolean	isCycle(edu.uci.ics.jung.graph.Graph<V,E> G, java.util.Set<V> C) Return true if the subset C of G contains at least one cycle.
static <V,E> boolean	isEdge(edu.uci.ics.jung.graph.Graph<V,E> G, V v1, V v2) Tests if an edge exists between vertices v1 and v2.
static <V,E> boolean	isRegular(edu.uci.ics.jung.graph.Graph<V,E> G) Tests if a graph is regular.
static <V,E> boolean	isRegular(edu.uci.ics.jung.graph.Graph<V,E> G, int deg) Tests if a graph is d-regular.
static <V,E> void	mergeGraph(edu.uci.ics.jung.graph.Graph<V,E> G, edu.uci.ics.jung.graph.Graph<V,E> subG) Merge graph subG into G.
static <V> void	quickSortSet(java.util.ArrayList<java.util.Set<V>> tab, int p, int r) Ascending sort of a list of sets of vertices following their cardinality.
static <V,E> void	removeAllEdges(edu.uci.ics.jung.graph.Graph<V,E> G, java.util.Set<E> R) Remove all the edges of set R of the graph G.
static <V,E> void	removeAllVertices(edu.uci.ics.jung.graph.Graph<V,E> G, java.util.Set<V> R) Remove all the vertices of set R of the graph G.
static <V,E> void	rewireEdge(edu.uci.ics.jung.graph.Graph<V,E> G, E edge, org.apache.commons.collections15.Factory<E> edgeFactory) Randomly rewire a given edge in a graph.
static <V,E> void	rewireEdgesRand(edu.uci.ics.jung.graph.Graph<V,E> G, int amount, org.apache.commons.collections15.Factory<E> edgeFactory) Randomly rewire edges in a graph.
static <V,E> void	subGraph(edu.uci.ics.jung.graph.Graph<V,E> G, edu.uci.ics.jung.graph.Graph<V,E> subG, java.util.Set<V> S) Insert into subG nodes and edges of N[S] in G.
static <V,E> void	subGraph(edu.uci.ics.jung.graph.Graph<V,E> G, edu.uci.ics.jung.graph.Graph<V,E> subG, V x) Insert into subG nodes and edges of N[x] in G.

Methods inherited from class java.lang.Object

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

Constructor Detail

Operations

public Operations()

Method Detail

subGraph

public static <V,E> void subGraph(edu.uci.ics.jung.graph.Graph<V,E> G,
                  edu.uci.ics.jung.graph.Graph<V,E> subG,
                  V x)

Insert into subG nodes and edges of N[x] in G.

Parameters:

G - original graph

subG - subgraph of G

x - node to add with its neighborhood in Gtarget

subGraph

public static <V,E> void subGraph(edu.uci.ics.jung.graph.Graph<V,E> G,
                  edu.uci.ics.jung.graph.Graph<V,E> subG,
                  java.util.Set<V> S)

Insert into subG nodes and edges of N[S] in G. S is a set of nodes.

Parameters:

G - original graph

subG - subgraph of G

S - nodes to add with its neighborhoods in subG

mergeGraph

public static <V,E> void mergeGraph(edu.uci.ics.jung.graph.Graph<V,E> G,
                    edu.uci.ics.jung.graph.Graph<V,E> subG)

Merge graph subG into G.

Parameters:

G - result graph of G ∪ subG

subG - graph to merge into G

copyUndirectedSparseGraph

public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> copyUndirectedSparseGraph(edu.uci.ics.jung.graph.Graph<V,E> G)

Full copy (edges + vertices) of the Graph. (Undirected version)

Parameters:

G - Graph to copy

Returns:

copy of the Graph G

copyDirectedSparseGraph

public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> copyDirectedSparseGraph(edu.uci.ics.jung.graph.Graph<V,E> G)

Full copy (arcs + vertices) of the Graph. (Directed version)

Parameters:

G - Graph to copy

Returns:

copy of the Graph G

copyGraph

public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> copyGraph(edu.uci.ics.jung.graph.Graph<V,E> G,
                                                org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> f)

Full copy (arcs + vertices) of a graph using the given factory.

Type Parameters:

V -

E -

Parameters:

G -

f -

Returns:

a full copy a a graph

getDiameter

public static <V,E> int getDiameter(edu.uci.ics.jung.graph.Graph<V,E> G)

Returns the diameter of a graph.

Parameters:

G - graph

Returns:

diameter of G

getMinDegVertex

public static <V,E> V getMinDegVertex(edu.uci.ics.jung.graph.Graph<V,E> G)

Returns a vertex of G with minimum degree.

Parameters:

G - Graph in which vertex has to be found

Returns:

a vertex with min degree.

getAllMinDegVertex

public static <V,E> java.util.Set<V> getAllMinDegVertex(edu.uci.ics.jung.graph.Graph<V,E> G)

Returns a set containing vertices of G with lowest degree.

Parameters:

G - Graph in which all vertices of min degree has to be found

Returns:

a set with all vertices of min degree

getMaxDegVertex

public static <V,E> V getMaxDegVertex(edu.uci.ics.jung.graph.Graph<V,E> G)

Returns a vertex of G with maximum degree.

Parameters:

G - Graph in which vertex has to be found

Returns:

a vertex with max degree.

getAllMaxDegVertex

public static <V,E> java.util.Set<V> getAllMaxDegVertex(edu.uci.ics.jung.graph.Graph<V,E> G)

Returns a set containing vertices of G with highest degree.

Parameters:

G - Graph in which all vertices of max degree has to be found

Returns:

a set with all vertices of max degree

getMaxDeg

public static <V,E> int getMaxDeg(edu.uci.ics.jung.graph.Graph<V,E> G)

Returns the maximum degree of G.

Parameters:

G - Graph in which max degree has to be found

Returns:

max degree.

getMinDeg

public static <V,E> int getMinDeg(edu.uci.ics.jung.graph.Graph<V,E> G)

Returns the minimum degree of G.

Parameters:

G - Graph in which min degree has to be found

Returns:

min degree.

getDegVertex

public static <V,E> V getDegVertex(edu.uci.ics.jung.graph.Graph<V,E> G,
                   int deg)

Returns a vertex of degree 'deg' for the graph G.

Parameters:

G - graph

deg - degree

Returns:

a vertex of degree 'deg'

getAllDegVertex

public static <V,E> java.util.Set<V> getAllDegVertex(edu.uci.ics.jung.graph.Graph<V,E> G,
                                     int deg)

Retunrs the set of all the vertices of degree 'deg' for the graph G.

Parameters:

G - graph

deg - degree

Returns:

the set of all the vertices of degree 'deg'

getNbEdges

public static <V,E> int getNbEdges(edu.uci.ics.jung.graph.Graph<V,E> G,
                   java.util.Set<V> A)

Returns the amount of edges which are linking vertices of A.

Parameters:

G - Graph where edges appear

A - Set containing vertices to test

Returns:

the number of edges linking elements of A

getNeighbors

public static <V,E> java.util.Set<V> getNeighbors(edu.uci.ics.jung.graph.Graph<V,E> G,
                                  java.util.Set<V> S)

Returns all neighbors of S without S (usually denoted as N(S)).

Parameters:

G - graph

S - set of vertices

Returns:

neighbors of S

getNeighbors

public static <V,E> java.util.Set<V> getNeighbors(edu.uci.ics.jung.graph.Graph<V,E> G,
                                  V v,
                                  int dist)

Returns the neighbors vertices of a set of v at a given distance. For instance, with dist=2, the method returns N²(v).

Parameters:

G - Graph

v - vertex

dist - distance of the neighbors

Returns:

neighbors vertices of v at a given distance

isRegular

public static <V,E> boolean isRegular(edu.uci.ics.jung.graph.Graph<V,E> G)

Tests if a graph is regular.

Parameters:

G - graph

Returns:

true if G is regular, else false.

isRegular

public static <V,E> boolean isRegular(edu.uci.ics.jung.graph.Graph<V,E> G,
                      int deg)

Tests if a graph is d-regular.

Parameters:

G - graph

deg - degree

Returns:

true if G is regular, else false.

isAcyclic

public static <V,E> boolean isAcyclic(edu.uci.ics.jung.graph.Graph<V,E> G)

Returns true if a directed graph has no circuit.

Parameters:

G - graph

Returns:

true if G has no circuit, else false.

isCycle

public static <V,E> boolean isCycle(edu.uci.ics.jung.graph.Graph<V,E> G,
                    java.util.Set<V> C)

Return true if the subset C of G contains at least one cycle.

Parameters:

G - graph

C - subset of G

Returns:

true if C contains a cycle, false else.

isEdge

public static <V,E> boolean isEdge(edu.uci.ics.jung.graph.Graph<V,E> G,
                   V v1,
                   V v2)

Tests if an edge exists between vertices v1 and v2.

Parameters:

G - Graph in which edge has to be found

v1 - 1st vertex of the edge

v2 - 2nd vertex of the edge

Returns:

true if the edge v1-v2 exits, false if not.

isClique

public static <V,E> boolean isClique(edu.uci.ics.jung.graph.Graph<V,E> G,
                     java.util.Set<V> K)

Tests if a set of vertices is a clique for the Graph G.

Parameters:

G - Graph where the set has to be tested.

K - Set of vertices to test

Returns:

true if K is a clique in G, if not returns false.

addAllVertices

public static <V,E> void addAllVertices(edu.uci.ics.jung.graph.Graph<V,E> G,
                        java.util.Set<V> A)

Add all the vertices of set A to the graph G.

Parameters:

G - graph

A - set of vertices to add to G

removeAllVertices

public static <V,E> void removeAllVertices(edu.uci.ics.jung.graph.Graph<V,E> G,
                           java.util.Set<V> R)

Remove all the vertices of set R of the graph G.

Parameters:

G - graph

R - set of vertices to remove of G

removeAllEdges

public static <V,E> void removeAllEdges(edu.uci.ics.jung.graph.Graph<V,E> G,
                        java.util.Set<E> R)

Remove all the edges of set R of the graph G.

Parameters:

G - graph

R - set of edges to remove of G

quickSortSet

public static <V> void quickSortSet(java.util.ArrayList<java.util.Set<V>> tab,
                    int p,
                    int r)

Ascending sort of a list of sets of vertices following their cardinality.

Parameters:

tab - list of sets

p - min boundary

r - max boundary

chooseRandVertex

public static <V,E> V chooseRandVertex(edu.uci.ics.jung.graph.Graph<V,E> G)

Return a vertex of G choosen randomly.

Parameters:

G - graph

Returns:

a vertex choosen randomly.

getDensity

public static <V,E> double getDensity(edu.uci.ics.jung.graph.Graph<V,E> G)

Returns density of a graph G.

Parameters:

G - graph

Returns:

density of G.

rewireEdgesRand

public static <V,E> void rewireEdgesRand(edu.uci.ics.jung.graph.Graph<V,E> G,
                         int amount,
                         org.apache.commons.collections15.Factory<E> edgeFactory)

Randomly rewire edges in a graph.

Parameters:

G - graph

amount - number of edges to rewire.

edgeFactory - factory used to create edge.

rewireEdge

public static <V,E> void rewireEdge(edu.uci.ics.jung.graph.Graph<V,E> G,
                    E edge,
                    org.apache.commons.collections15.Factory<E> edgeFactory)

Randomly rewire a given edge in a graph.

Parameters:

G - graph

edge - edge to rewire.

edgeFactory - factory used to create edge.