edu.ucla.sspace.graph

Class Graphs

java.lang.Object

edu.ucla.sspace.graph.Graphs

public final class Graphs
extends Object

A collection of static utility methods for interacting with Graph instances. This class is modeled after the Collections class.

Unless otherwise noted, all methods will throw an NullPointerException if passed a null graph.

Method Summary

Methods

Modifier and Type	Method and Description
static <E extends DirectedEdge> DirectedGraph<E>	asDirectedGraph(Graph<E> g)
static <T,E extends TypedEdge<T>> Multigraph<T,E>	asMultigraph(Graph<E> g)
static <E extends WeightedEdge> WeightedGraph<E>	asWeightedGraph(Graph<E> g)
static <E extends Edge> Graph<E>	pack(Graph<E> g) Creates a copy of the provided graph where all vertices are remapped to a contiguous range from 0 to g.order()-1.
static <E extends Edge> int	shufflePreserve(Graph<E> g, int shufflesPerEdge) Shuffles the edges of g while still preserving the degree sequence of the graph.
static <E extends Edge> int	shufflePreserve(Graph<E> g, int shufflesPerEdge, Random rnd) Shuffles the edges of g while still preserving the degree sequence of the graph.
static <T,E extends TypedEdge<T>> int	shufflePreserveType(Multigraph<T,E> g, int shufflesPerEdge) Shuffles the edges of g while still preserving the degree sequence of the graph and that edges are only swapped with those of the same type.
static <T,E extends TypedEdge<T>> int	shufflePreserveType(Multigraph<T,E> g, int shufflesPerEdge, Random rnd) Shuffles the edges of g while still preserving the degree sequence of the graph and that edges are only swapped with those of the same type.
static <T extends Edge> Graph<T>	synchronizedGraph(Graph<T> g) To-do
static String	toAdjacencyMatrixString(Graph<?> g) Returns a pretty-print string version of the graph as an adjacency matrix where a 1 indicates an edge and a 0 indicates no edge.
static <E extends Edge,G extends Graph<E>> Graph<Edge>	toLineGraph(G graph) Converts the provided graph into a line graph, where each edge is mapped to a vertex and edges that share vertices are connected by an edge in the line graph.
static <E extends Edge,G extends Graph<E>> Graph<Edge>	toLineGraph(G graph, Indexer<E> edgeIndices) Converts the provided graph into a line graph, where each edge is mapped to a vertex and edges that share vertices are connected by an edge in the line graph, using edgeIndices to specify the mapping between edges in the input graph and their corresponding vertices in the line graph.
static <T extends Edge> Graph<T>	unmodifiable(Graph<T> g) To-do

Methods inherited from class java.lang.Object

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

Method Detail

asDirectedGraph

public static <E extends DirectedEdge> DirectedGraph<E> asDirectedGraph(Graph<E> g)

asWeightedGraph

public static <E extends WeightedEdge> WeightedGraph<E> asWeightedGraph(Graph<E> g)

asMultigraph

public static <T,E extends TypedEdge<T>> Multigraph<T,E> asMultigraph(Graph<E> g)

pack

public static <E extends Edge> Graph<E> pack(Graph<E> g)

Creates a copy of the provided graph where all vertices are remapped to a contiguous range from 0 to g.order()-1. If the graph's vertices are already contiguous, returns the original graph.

shufflePreserve

public static <E extends Edge> int shufflePreserve(Graph<E> g,
                                   int shufflesPerEdge)

Shuffles the edges of g while still preserving the degree sequence of the graph. Each edge in the graph will attempted to be conflated with another edge in the graph the specified number of times. If the edge cannot be swapped (possible due to the new version of the edge already existing), the attempt fails.

Parameters:

g - the graph whose elemets will be shuffled

shufflesPerEdge - the number of swaps to attempt per edge.

Returns:

the total number of times an edge's endpoint was swapped with another edge's endpoint. At its maximum value, this will be shufflesPerEdge * g.size() assuming that each swap was successful. For dense graphs, this return value will be much less.

Throws:

IllegalArgumentException - if shufflesPerEdge is non-positive

shufflePreserve

public static <E extends Edge> int shufflePreserve(Graph<E> g,
                                   int shufflesPerEdge,
                                   Random rnd)

Shuffles the edges of g while still preserving the degree sequence of the graph. Each edge in the graph will attempted to be conflated with another edge in the graph the specified number of times. If the edge cannot be swapped (possible due to the new version of the edge already existing), the attempt fails.

Parameters:

g - the graph whose elemets will be shuffled

shufflesPerEdge - the number of swaps to attempt per edge.

rnd - the source of randomness used to shuffle the graph's edges

Returns:

the total number of times an edge's endpoint was swapped with another edge's endpoint. At its maximum value, this will be shufflesPerEdge * g.size() assuming that each swap was successful. For dense graphs, this return value will be much less.

Throws:

IllegalArgumentException - if shufflesPerEdge is non-positive

shufflePreserveType

public static <T,E extends TypedEdge<T>> int shufflePreserveType(Multigraph<T,E> g,
                                                 int shufflesPerEdge)

Shuffles the edges of g while still preserving the degree sequence of the graph and that edges are only swapped with those of the same type. Each edge in the graph will attempted to be conflated with another edge in the graph the specified number of times. If the edge cannot be swapped (possible due to the new version of the edge already existing), the attempt fails.

Note that the Multigraph#subview(Set,Set) method makes it possilble to shuffle the edges for only a subset of the types in the multigraph.

Parameters:

g - the graph whose elemets will be shuffled

shufflesPerEdge - the number of swaps to attempt per edge.

Returns:

the total number of times an edge's endpoint was swapped with another edge's endpoint. At its maximum value, this will be shufflesPerEdge * g.size() assuming that each swap was successful. For dense graphs, this return value will be much less.

Throws:

IllegalArgumentException - if shufflesPerEdge is non-positive

shufflePreserveType

public static <T,E extends TypedEdge<T>> int shufflePreserveType(Multigraph<T,E> g,
                                                 int shufflesPerEdge,
                                                 Random rnd)

Shuffles the edges of g while still preserving the degree sequence of the graph and that edges are only swapped with those of the same type. Each edge in the graph will attempted to be conflated with another edge in the graph the specified number of times. If the edge cannot be swapped (possible due to the new version of the edge already existing), the attempt fails.

Note that the Multigraph#subview(Set,Set) method makes it possilble to shuffle the edges for only a subset of the types in the multigraph.

Parameters:

g - the graph whose elemets will be shuffled

shufflesPerEdge - the number of swaps to attempt per edge.

rnd - the source of randomness used to shuffle the graph's edges

Returns:

the total number of times an edge's endpoint was swapped with another edge's endpoint. At its maximum value, this will be shufflesPerEdge * g.size() assuming that each swap was successful. For dense graphs, this return value will be much less.

Throws:

IllegalArgumentException - if shufflesPerEdge is non-positive

synchronizedGraph

public static <T extends Edge> Graph<T> synchronizedGraph(Graph<T> g)

To-do

toLineGraph

public static <E extends Edge,G extends Graph<E>> Graph<Edge> toLineGraph(G graph)

Converts the provided graph into a line graph, where each edge is mapped to a vertex and edges that share vertices are connected by an edge in the line graph.

Returns:

the line graph for the input graph

toLineGraph

public static <E extends Edge,G extends Graph<E>> Graph<Edge> toLineGraph(G graph,
                                                          Indexer<E> edgeIndices)

Converts the provided graph into a line graph, where each edge is mapped to a vertex and edges that share vertices are connected by an edge in the line graph, using edgeIndices to specify the mapping between edges in the input graph and their corresponding vertices in the line graph. If an edge is not mapped to a vertex in edgeIndices, a new mapping will be added for it.

Returns:

the line graph for the input graph

toAdjacencyMatrixString

public static String toAdjacencyMatrixString(Graph<?> g)

Returns a pretty-print string version of the graph as an adjacency matrix where a 1 indicates an edge and a 0 indicates no edge.

unmodifiable

public static <T extends Edge> Graph<T> unmodifiable(Graph<T> g)

To-do