dev.roanh.cpqkeys

Class GraphUtil

java.lang.Object

dev.roanh.cpqkeys.GraphUtil

public class GraphUtil
extends java.lang.Object

Various utilities for transforming graphs.

See Also:

Util

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	GraphUtil.ColoredGraph Represents a coloured graph.

Constructor Summary

Constructors

Constructor and Description
GraphUtil()

Method Summary

Modifier and Type	Method and Description
static <V,E> GraphUtil.ColoredGraph	toColoredGraph(dev.roanh.gmark.util.Graph<V,E> graph) Converts the given input graph to a coloured graph instance by grouping vertices with their colour determined by the content of their DataProxy instance.
static <V,E> dev.roanh.gmark.util.Graph<java.lang.Object,E>	toUndirectedGraph(dev.roanh.gmark.util.Graph<V,E> in) Converts the given directed input graph to a graph where all directed edges are instead represented by labelled vertices.

Methods inherited from class java.lang.Object

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

Constructor Detail

GraphUtil

public GraphUtil()

Method Detail

toUndirectedGraph

public static <V,E> dev.roanh.gmark.util.Graph<java.lang.Object,E> toUndirectedGraph(dev.roanh.gmark.util.Graph<V,E> in)

Converts the given directed input graph to a graph where all directed edges are instead represented by labelled vertices. Essentially, for each edge (a) --b--> (c) the edge will be turned into three edges with and two new nodes. If the edge is labelled then the middle of the three new edges will inherit the label. The final result would looks as follows (a) -- (tail) --b-- (head) -- (c). Thus this transform triples the number of edges in the graph and adds two new nodes for every edge that used to be in the old graph. The returned graph has Object as the vertex data type. There are two options for the actual class of these vertex data objects. Either they are a vertex data object from the old graph and thus of generic type V. Or they are a DataProxy instance wrapping either the string "head" or "tail". It is worth noting that the returned graph instance is still technically a directed graph as Graph instances are always directed, but it can be treated as undirected. For performance reasons only the middle of the three new edges inherits the former edge label. This also keeps the growth of the graph to a minimum when the Util.edgeLabelsToNodes(Graph) is also used.

Type Parameters:

V - The vertex data type.

E - The edge label data type.

Parameters:

in - The input graph to transform.

Returns:

The transformed undirected graph.

See Also:

Notes on transforming directed graphs to undirected graphs

toColoredGraph

public static <V,E> GraphUtil.ColoredGraph toColoredGraph(dev.roanh.gmark.util.Graph<V,E> graph)

Converts the given input graph to a coloured graph instance by grouping vertices with their colour determined by the content of their DataProxy instance. All vertex data objects that are not DataProxy instances are given the same colour.

Type Parameters:

V - The vertex data type.

E - The edge label data type.

Parameters:

graph - The input graph to transform.

Returns:

The constructed coloured graph.

See Also:

GraphUtil.ColoredGraph