edu.uci.ics.jung.utils
Class GraphUtils

java.lang.Object
  extended by edu.uci.ics.jung.utils.GraphUtils

public class GraphUtils
extends Object

A series of helpful utility methods. All methods in GraphUtils can be accomplished with public members of other code; these are simply combinations that we found useful.

Author:
Danyel Fisher, Scott White, Joshua O'Madadhain

Constructor Summary
GraphUtils()
           
 
Method Summary
static void addDirectedVertices(Graph g, int count)
          Deprecated. As of version 1.2, replaced by addVertices(edu.uci.ics.jung.graph.Graph, int).
static Edge addEdge(Graph g, Vertex v1, Vertex v2)
          Adds an appropriate edge between two vertices.
static void addEdges(Graph g, Set edges)
          Adds all edges in the specified set to g.
static void addEdges(Hypergraph g, Set edges)
          Adds all edges in the specified set to g.
static void addUndirectedVertices(Graph g, int count)
          Deprecated. As of version 1.2, replaced by addVertices(edu.uci.ics.jung.graph.Graph, int).
static void addVertices(Graph g, int count)
          Adds count vertices into a graph.
static void addVertices(Graph g, Set vertices)
          Adds all vertices in the specified set to g.
static void addVertices(Hypergraph g, Set vertices)
          Adds all vertices in the specified set to g.
static boolean areEquivalent(ArchetypeGraph g1, ArchetypeGraph g2)
          Returns true if g1 and g2 have equivalent vertex and edge sets (that is, if each vertex and edge in g1 has an equivalent in g2, and vice versa), and false otherwise.
static void copyLabels(StringLabeller source, StringLabeller target)
          Copies the labels of vertices from one StringLabeller to another.
static void copyValues(ArchetypeGraph g, NumberVertexValue source, NumberVertexValue dest)
          Copies, for each vertex v in g, source's value to dest.
static Graph edgeSetToGraph(Set edges, boolean retain)
          Given a set of edges, creates a new Graph that contains all of those edges, and at least all the vertices that are attached to them.
static Set getEqualEdges(Set s, ArchetypeGraph g)
          Returns the set of edges in g which are equal to the edges in g.
static Set getEqualVertices(Set s, ArchetypeGraph g)
          Returns the set of vertices in g which are equal to the vertices in g.
static VertexGenerator getVertexGenerator(ArchetypeGraph g)
          Returns the VertexGenerator, if any, stored in g's user data at the standardized location specified by the VG interface: VertexGenerator.TAG.
static String printVertices(Collection s, StringLabeller sl)
          For every vertex in s, prints sl.get(s).
static void removeEdges(Graph g, Set edges)
          Removes all vertices in the specified set from g.
static void removeEdges(Hypergraph g, Set edges)
          Removes all vertices in the specified set from g.
static void removeVertices(Graph g, Set vertices)
          Removes all vertices in the specified set from g.
static void removeVertices(Hypergraph g, Set vertices)
          Removes all vertices in the specified set from g.
static UndirectedGraph transform(DirectedGraph dGraph)
          Deprecated. As of version 1.4, replaced by DirectionTransformer.toUndirected(Graph)
static DirectedGraph transform(Graph uGraph)
          Deprecated. As of version 1.4, replaced by DirectionTransformer.toDirected(Graph)
static Set translateAll(Set s, Graph g)
          Deprecated. As of version 1.4, replaced by getEqualVertices(Set, ArchetypeGraph)
static Set translateAllEdges(Set s, Graph g)
          Deprecated. As of version 1.4, replaced by getEqualEdges(Set, ArchetypeGraph)
static ArchetypeGraph union(ArchetypeGraph g1, ArchetypeGraph g2)
          Returns a graph which consists of the union of the two input graphs.
static DoubleArrayList vertexMapToDAL(Map vertex_values, Indexer indexer)
          Converts vertex_values (a Map of vertex to Number values) to a DoubleArrayList, using indexer to determine the location of each vertex's value in the DAL.
static Graph vertexSetToGraph(Set s)
          Given a set of vertices, creates a new Graph that contains all of those vertices, and all the edges that connect them.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

GraphUtils

public GraphUtils()
Method Detail

addEdge

public static Edge addEdge(Graph g,
                           Vertex v1,
                           Vertex v2)
Adds an appropriate edge between two vertices. Specifically, this method confirms that both vertices are from the same graph, and then checks whether the Graph is directed or not. If so, it creates a new DirectedSparseEdge, otherwise a new UndirectedSparseEdge. This is a convenience method; one might instead just call g.addEdge( new XXSparseEdge(v1, v2))) .

The input vertices must be of type Vertex, or the method will throw a ClassCastException.

Returns:
the edge that was added
Throws:
ClassCastException - if the input aren't Vertices
IllegalArgumentException - if the vertices don't belong to the same graph
See Also:
Graph.addEdge(edu.uci.ics.jung.graph.Edge), AbstractSparseGraph.addEdge(edu.uci.ics.jung.graph.Edge)

addVertices

public static void addVertices(Graph g,
                               int count)
Adds count vertices into a graph. This is a convenience method; one might instead just call g.addVertex( new SparseVertex())) count times.

The input graph must be one that can accept a series of directed vertices.

Parameters:
g - A graph to add the vertices to
count - how many vertices to add
See Also:
AbstractSparseGraph.addVertex(edu.uci.ics.jung.graph.Vertex)

addDirectedVertices

public static void addDirectedVertices(Graph g,
                                       int count)
Deprecated. As of version 1.2, replaced by addVertices(edu.uci.ics.jung.graph.Graph, int).

Adds count directed vertices into a graph. This is a convenience method; one might instead just call g.addVertex( new DirectedSparseVertex())) count times.

The input graph must be one that can accept a series of directed vertices.

Parameters:
g - A graph to add the vertices to
count - how many vertices to add
See Also:
AbstractSparseGraph.addVertex(edu.uci.ics.jung.graph.Vertex)

addUndirectedVertices

public static void addUndirectedVertices(Graph g,
                                         int count)
Deprecated. As of version 1.2, replaced by addVertices(edu.uci.ics.jung.graph.Graph, int).

Adds count undirected vertices into a graph. This is a convenience method; one might instead just call g.addVertex( new UndirectedSparseVertex())) count times.

The input graph must be one that can accept a series of undirected vertices.

Parameters:
g - A graph to add the vertices to
count - how many vertices to add
See Also:
AbstractSparseGraph.addVertex(edu.uci.ics.jung.graph.Vertex)

translateAll

public static Set translateAll(Set s,
                               Graph g)
Deprecated. As of version 1.4, replaced by getEqualVertices(Set, ArchetypeGraph)

Translates every vertex from the input set into the graph given. For each vertex, then, it gets the equivalent vertex in g, and returns the collated set.

Parameters:
s - The set of input vertices, not from g
g - The graph which has the corresponding vertices
Returns:
a resulting set
See Also:
ArchetypeVertex.getEqualVertex(edu.uci.ics.jung.graph.ArchetypeGraph)

getEqualVertices

public static Set getEqualVertices(Set s,
                                   ArchetypeGraph g)
Returns the set of vertices in g which are equal to the vertices in g.

Since:
1.4

translateAllEdges

public static Set translateAllEdges(Set s,
                                    Graph g)
Deprecated. As of version 1.4, replaced by getEqualEdges(Set, ArchetypeGraph)

Translates every edge from the input set into the graph given. For each edge, then, it gets the equivalent edge in g, and returns the collated set.

Parameters:
s - The set of input edges, not from g
g - The graph which has the corresponding edges
Returns:
a resulting set
See Also:
ArchetypeEdge.getEqualEdge(edu.uci.ics.jung.graph.ArchetypeGraph)

getEqualEdges

public static Set getEqualEdges(Set s,
                                ArchetypeGraph g)
Returns the set of edges in g which are equal to the edges in g.

Since:
1.4

vertexSetToGraph

public static Graph vertexSetToGraph(Set s)
Given a set of vertices, creates a new Graph that contains all of those vertices, and all the edges that connect them. Uses the UnassembledGraph mechanism to create the graph.

Parameters:
s - A set of Vertex s that want to be a part of a new Graph
Returns:
A graph, created with Graph.newInstance, containing vertices equivalent to (and that are copies of!) all the vertices in the input set. Note that if the input is an empty set, null is returned.

edgeSetToGraph

public static Graph edgeSetToGraph(Set edges,
                                   boolean retain)
Given a set of edges, creates a new Graph that contains all of those edges, and at least all the vertices that are attached to them. Uses UnassembledGraph mechanism to create the graph. The parameter decides what to do with disconnected vertices: true says that they should be retained, false says that they should be discarded (with a DropSoloNodesFilter).

Parameters:
edges - A set of Edge s that want to be a part of a new Graph
retain - Is true if all isolated vertices should be retained; is false if they should be discarded.
Returns:
A graph, created with Graph.newInstance, containing edges equivalent to (and that are copies of!) all the edges in the input set. Note that if the input is an empty set, null is returned.

union

public static ArchetypeGraph union(ArchetypeGraph g1,
                                   ArchetypeGraph g2)
Returns a graph which consists of the union of the two input graphs. Assumes that both graphs are of a type that can accept the vertices and edges found in both graphs. The resultant graph contains all constraints that are common to both graphs.


transform

public static DirectedGraph transform(Graph uGraph)
Deprecated. As of version 1.4, replaced by DirectionTransformer.toDirected(Graph)

Transforms an (possibly undirected) graph into a directed graph. All user data on the graph,edges & vertices are copied to their corresponding counterparts. Returns a new graph with a directed edge from a to b iff a was a predecessor of b in the original. For an undirected edge, this will create two new edges.

Parameters:
uGraph - the undirected graph to transform
Returns:
the resultant directed graph

transform

public static UndirectedGraph transform(DirectedGraph dGraph)
Deprecated. As of version 1.4, replaced by DirectionTransformer.toUndirected(Graph)

Transforms a directed graph into a undirected graph. All user data on the graph,edges & vertices are copied to their corresponding counterparts.

Parameters:
dGraph - the directed graph to transform
Returns:
the resultant undirected graph

copyLabels

public static void copyLabels(StringLabeller source,
                              StringLabeller target)
                       throws StringLabeller.UniqueLabelException
Copies the labels of vertices from one StringLabeller to another. Only the labels of vertices that are equivalent are copied.

Parameters:
source - the source StringLabeller
target - the target StringLabeller
Throws:
StringLabeller.UniqueLabelException

areEquivalent

public static boolean areEquivalent(ArchetypeGraph g1,
                                    ArchetypeGraph g2)
Returns true if g1 and g2 have equivalent vertex and edge sets (that is, if each vertex and edge in g1 has an equivalent in g2, and vice versa), and false otherwise.


printVertices

public static String printVertices(Collection s,
                                   StringLabeller sl)
For every vertex in s, prints sl.get(s). S must be made up of only vertices.

Parameters:
s -
sl -

copyValues

public static void copyValues(ArchetypeGraph g,
                              NumberVertexValue source,
                              NumberVertexValue dest)
Copies, for each vertex v in g, source's value to dest.

Parameters:
g - the graph from which the vertices are taken
source - the NumberVertexValue from which values are to be copied
dest - the NumberVertexValue into which values are to be copied

getVertexGenerator

public static VertexGenerator getVertexGenerator(ArchetypeGraph g)
Returns the VertexGenerator, if any, stored in g's user data at the standardized location specified by the VG interface: VertexGenerator.TAG.


vertexMapToDAL

public static DoubleArrayList vertexMapToDAL(Map vertex_values,
                                             Indexer indexer)
Converts vertex_values (a Map of vertex to Number values) to a DoubleArrayList, using indexer to determine the location of each vertex's value in the DAL. Note: assumes that indexer is 0-based and covers all the vertices in vertex_values, and that vertex_values contains Number instances.

Parameters:
vertex_values - a map of vertices to Number instances
indexer - a 0-based index of the vertices
Returns:

addVertices

public static void addVertices(Graph g,
                               Set vertices)
Adds all vertices in the specified set to g. Syntactic sugar for a loop that calls g.addVertex on all elements of the set. If any element of vertices may not be legally added to this graph, throws an exception: ClassCastException if the type is inappropriate, and IllegalArgumentException otherwise. If an exception is thrown, any vertices that may already have been added are not guaranteed to be retained.


addVertices

public static void addVertices(Hypergraph g,
                               Set vertices)
Adds all vertices in the specified set to g. Syntactic sugar for a loop that calls g.addVertex on all elements of the set. If any element of vertices may not be legally added to this graph, throws an exception: ClassCastException if the type is inappropriate, and IllegalArgumentException otherwise. If an exception is thrown, any vertices that may already have been added are not guaranteed to be retained.


addEdges

public static void addEdges(Graph g,
                            Set edges)
Adds all edges in the specified set to g. Syntactic sugar for a loop that calls g.addEdge on all elements of the set. If any element of edges may not be legally added to this graph, throws an exception: ClassCastException if the type is inappropriate, and IllegalArgumentException otherwise. If an exception is thrown, any edges that may already have been added are not guaranteed to be retained.


addEdges

public static void addEdges(Hypergraph g,
                            Set edges)
Adds all edges in the specified set to g. Syntactic sugar for a loop that calls g.addEdge on all elements of the set. If any element of edges may not be legally added to this graph, throws an exception: ClassCastException if the type is inappropriate, and IllegalArgumentException otherwise. If an exception is thrown, any edges that may already have been added are not guaranteed to be retained.


removeVertices

public static void removeVertices(Graph g,
                                  Set vertices)
Removes all vertices in the specified set from g. Syntactic sugar for a loop that calls g.removeVertex on all elements of the set. If any element of vertices is not part of this graph, then throws IllegalArgumentException. If this exception is thrown, any vertices that may have been removed already are not guaranteed to be restored to the graph.


removeVertices

public static void removeVertices(Hypergraph g,
                                  Set vertices)
Removes all vertices in the specified set from g. Syntactic sugar for a loop that calls g.removeVertex on all elements of the set. If any element of vertices is not part of this graph, then throws IllegalArgumentException. If this exception is thrown, any vertices that may have been removed already are not guaranteed to be restored to the graph.


removeEdges

public static void removeEdges(Graph g,
                               Set edges)
Removes all vertices in the specified set from g. Syntactic sugar for a loop that calls g.removeVertex on all elements of the set. If any element of edges is not part of this graph, then throws IllegalArgumentException. If this exception is thrown, any edges that may have been removed already are not guaranteed to be restored to the graph.


removeEdges

public static void removeEdges(Hypergraph g,
                               Set edges)
Removes all vertices in the specified set from g. Syntactic sugar for a loop that calls g.removeVertex on all elements of the set. If any element of edges is not part of this graph, then throws IllegalArgumentException. If this exception is thrown, any edges that may have been removed already are not guaranteed to be restored to the graph.