edu.illinois.ncsa.isda.softwareserver.polyglot

Class IOGraph<V extends Comparable,E extends Comparable>

java.lang.Object

edu.illinois.ncsa.isda.softwareserver.polyglot.IOGraph<V,E>

All Implemented Interfaces:

Serializable

public class IOGraph<V extends Comparable,E extends Comparable>
extends Object
implements Serializable

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
static long	serialVersionUID

Constructor Summary

Constructors

Constructor and Description
IOGraph()
IOGraph(com.fasterxml.jackson.databind.JsonNode applications, String host) Class constructor.
IOGraph(SoftwareServerClient ss_client) Class constructor.
IOGraph(String url) Class constructor (loads data from a CSR database via a web script to bypass database access restrictions).
IOGraph(String server, String user, String password) Class constructor (loads data from a CSR database).

Method Summary

Methods

Modifier and Type	Method and Description
void	addEdge(V source, V target, E edge) Add an edge to the graph.
void	addEdge(V source, V target, E edge, Double w) Add an edge to the graph.
void	addEdgeOnce(V source, V target, E edge) Add an edge to the graph only if it doesn't exist.
void	addGraph(IOGraph<V,E> iograph) Merge another I/O-graph into this one.
int	addVertex(V vertex) Add a vertex to the graph if not already present.
kgm.utility.Pair<Vector<Integer>,Vector<Double>>	bellmanFord(int source) Bellman Ford shortest path.
void	clear() Clear the graph.
void	complexity() Display information regarding the complexity of the graph.
static void	debug1() Debug shortest paths.
kgm.utility.Pair<Vector<Integer>,Vector<Double>>	dijkstra(int source) Dijstra shortest path.
Vector<Vector<Boolean>>	getActiveEdges() Get the list indicating which edges are currently active.
Vector<Boolean>	getActiveVertices() Determine and return which vertices are being used by the currently active edges.
Vector<Vector<Integer>>	getAdjacencyList() Get the adjacency list representing graph edges.
PolyglotAuxiliary.Conversion<V,E>	getConversion(String edge_string, String input_string, String output_string) Get the conversion possessing the given name, input, and output
Vector<PolyglotAuxiliary.Conversion<V,E>>	getConversions(String conversions_string) Parse a string containing conversion information
TreeSet<Integer>	getDomain(int target) Get the set of all vertices that can reach the target vertex.
TreeSet<String>	getDomainStrings() Get a set of all vertices that can reach other vertices.
TreeSet<String>	getDomainStrings(String target) Get a set of all vertices that can reach the target vertex.
Vector<Vector<E>>	getEdges() Get the graph edges.
Vector<Vector<String>>	getEdgeStrings() Get the string representations for the edges.
double	getEdgeWeight(V input, V output, E edge) Return the weight associated with this conversion.
IOGraph<String,String>	getIOGraphStrings() Get a string only version of this IOGraph.
Double	getMaxEdgeWeight(int v0, int v1) Get the maximum weight among parallel edges between the vertices specified.
Vector<Double>	getMaxPathWeights(Vector<Integer> path) Get the maximum weights along the path specified.
double	getMinimumWeight() Returns the minimum weight a path can be to be considered.
Vector<E>	getParallelEdges(V source, V target, E edge) Get a list of edges parallel to the given edge.
static Vector<Integer>	getPath(Vector<Integer> paths, int source, int target) Follow a path back from target to source given the single source shortest paths from the source.
String	getPathString(Vector<Integer> path) Convert a path into a string representation.
TreeSet<Integer>	getRange(int index) Return a set of all reachable vertices from the given source.
TreeSet<Integer>	getRangeIntersection(TreeSet<Integer> set) Get the range intersection of the vertices in the given set.
TreeSet<String>	getRangeIntersectionStrings(TreeSet<String> set) Get the range intersection of the vertices in the given set.
TreeSet<String>	getRangeStrings() Returns a set of vertex strings that are reachable from other vertices.
TreeSet<String>	getRangeStrings(String string) Returns a set of vertex strings that are reachable from a given source vertex.
Vector<PolyglotAuxiliary.Conversion<V,E>>	getShortestConversionPath(String source_string, String target_string, boolean ENABLE_WEIGHTED_PATHS) Get the shortest list of the conversion tasks required to convert from a given input to a given output.
Vector<Vector<PolyglotAuxiliary.Conversion<V,E>>>	getShortestConversionPaths(String source_string, String target_string) Get the shortest list of the conversion tasks required to convert from a given input to a given output.
String	getShortestConversionPathString(String source_string, String target_string, boolean ENABLE_WEIGHTED_PATHS) Get the shortest list of the conversion tasks required to convert from a given input to a given output.
Vector<String>	getShortestConversionPathStrings(String source_string, String target_string) Get the shortest list of the conversion tasks required to convert from a given input to a given output.
Vector<Integer>	getShortestPaths(int source) Perform a breadth first search from the vertex at the given index and store the resulting paths.
kgm.utility.Pair<Vector<Integer>,Vector<Double>>	getShortestWeightedPaths(int source) Perform Dijkstra's algorithm from the vertex at the given source index and store the resulting paths.
kgm.utility.Pair<Vector<Integer>,Vector<Double>>	getShortestWeightedPathsOriginal(int source)
TreeSet<E>	getUniqueEdges() Get a set of the unique edges in the graph.
TreeSet<String>	getUniqueEdgeStrings() Get the string representations for the unique edges in the graph.
Vector<String>	getVertexStrings() Get the string representations for the vertices.
Vector<String>	getVertexStringsStartingWith(String prefix) Get the string representations for the vertices that start with the given prefix.
Vector<V>	getVertices() Get the graph vertices.
void	load(String filename) Load graph from the given file.
void	loadEdgeWeights(String filename, Double invalid_value) Load edge weights from the given file.
static void	main(String[] args) A main for debug purposes.
void	printEdgeInformation() Display information about each unique edge.
void	printEdgeInformation(E edge) Display information about an edge.
void	printMaxWeightedEdge() Find the edge with the largest weight.
void	printMinWeightedEdge() Find the edge with the smallest weight.
void	printMinWeightedVertex() Find the vertex with the shortest combined traversed weight when visited from other vertices.
void	removeEdges(String string) Remove edges matching the given string.
void	save(String filename) Save graph to the given file.
Vector<Vector<Boolean>>	setActiveEdges(Boolean value) Set all edges to the given value.
Vector<Vector<Boolean>>	setActiveEdges(TreeSet<String> selected_edges) Set only listed edges to active.
void	setEdgeWeight(Double weight) Sets the weight for all edges.
void	setEdgeWeight(String source, String target, String edge, Double weight) Set the weight of the given edge.
void	setMinimumWeight(double weight) Sets the minimum weight a path can be to be considered path of the graph.
boolean	showEdge(int source, int target)
static void	timings(int edges, int formats, int software) Compare time of various algorithms to find a shortest path in random graph.
void	transformEdgeWeights(String expression) Transform edge weights according to the given expression.

Methods inherited from class java.lang.Object

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

Field Detail

serialVersionUID

public static final long serialVersionUID

See Also:

Constant Field Values

Constructor Detail

IOGraph

public IOGraph()

IOGraph

public IOGraph(SoftwareServerClient ss_client)

Class constructor.

Parameters:

ss_client - a Software Server client

IOGraph

public IOGraph(com.fasterxml.jackson.databind.JsonNode applications,
       String host)

Class constructor.

Parameters:

applications - json encoded application information from a Software Server

host - the Software Server host

IOGraph

public IOGraph(String server,
       String user,
       String password)

Class constructor (loads data from a CSR database).

Parameters:

server - the server containing the database

user - the user name to use

password - the password for this user

IOGraph

public IOGraph(String url)

Class constructor (loads data from a CSR database via a web script to bypass database access restrictions).

Parameters:

url - the URL of the web script

Method Detail

clear

public void clear()

Clear the graph.

addVertex

public int addVertex(V vertex)

Add a vertex to the graph if not already present.

Parameters:

vertex - a vertex to add

Returns:

the index of the vertex

addEdge

public void addEdge(V source,
           V target,
           E edge)

Add an edge to the graph.

Parameters:

source - the source vertex

target - the target vertex

edge - the edge

addEdge

public void addEdge(V source,
           V target,
           E edge,
           Double w)

Add an edge to the graph.

Parameters:

source - the source vertex

target - the target vertex

edge - the edge

w - the weight of the edge

addEdgeOnce

public void addEdgeOnce(V source,
               V target,
               E edge)

Add an edge to the graph only if it doesn't exist.

Parameters:

source - the source vertex

target - the target vertex

edge - the edge

addGraph

public void addGraph(IOGraph<V,E> iograph)

Merge another I/O-graph into this one.

Parameters:

iograph - another I/O-graph

removeEdges

public void removeEdges(String string)

Remove edges matching the given string.

Parameters:

string - a string associated with edges to be removed (matched via the Comparable interface when compared to Strings)

getVertices

public Vector<V> getVertices()

Get the graph vertices.

Returns:

the vertices

getEdges

public Vector<Vector<E>> getEdges()

Get the graph edges.

Returns:

the edges

getAdjacencyList

public Vector<Vector<Integer>> getAdjacencyList()

Get the adjacency list representing graph edges.

Returns:

the edge adjacency list

setActiveEdges

public Vector<Vector<Boolean>> setActiveEdges(Boolean value)

Set all edges to the given value.

Returns:

the active edge list

setActiveEdges

public Vector<Vector<Boolean>> setActiveEdges(TreeSet<String> selected_edges)

Set only listed edges to active.

Parameters:

selected_edges - a set of strings associated with selected edges

Returns:

the active edge list

getActiveVertices

public Vector<Boolean> getActiveVertices()

Determine and return which vertices are being used by the currently active edges.

Returns:

the active vertices

getActiveEdges

public Vector<Vector<Boolean>> getActiveEdges()

Get the list indicating which edges are currently active.

Returns:

the active edge list

getVertexStrings

public Vector<String> getVertexStrings()

Get the string representations for the vertices.

Returns:

the string representation for each vertex

getVertexStringsStartingWith

public Vector<String> getVertexStringsStartingWith(String prefix)

Get the string representations for the vertices that start with the given prefix.

Parameters:

prefix - the string vertex strings should start with

Returns:

the string representation for each of the matching vertices

getEdgeStrings

public Vector<Vector<String>> getEdgeStrings()

Get the string representations for the edges.

Returns:

the string representation for each edge

getUniqueEdges

public TreeSet<E> getUniqueEdges()

Get a set of the unique edges in the graph.

Returns:

a set of unique edges

getUniqueEdgeStrings

public TreeSet<String> getUniqueEdgeStrings()

Get the string representations for the unique edges in the graph.

Returns:

the string representations for the unique edges in the graph

getParallelEdges

public Vector<E> getParallelEdges(V source,
                         V target,
                         E edge)

Get a list of edges parallel to the given edge.

Parameters:

source - the source vertex

target - the target vertex

edge - the actual edge (can be null)

Returns:

a list of parallel edges

getMinimumWeight

public double getMinimumWeight()

Returns the minimum weight a path can be to be considered.

Returns:

the minimum weight allowed.

setMinimumWeight

public void setMinimumWeight(double weight)

Sets the minimum weight a path can be to be considered path of the graph.

Parameters:

weight - the minimum weight a path is allowed to be.

showEdge

public boolean showEdge(int source,
               int target)

getMaxEdgeWeight

public Double getMaxEdgeWeight(int v0,
                      int v1)

Get the maximum weight among parallel edges between the vertices specified.

Parameters:

v0 - the index of the starting vertex

v1 - the index of the ending vertex

Returns:

the weight

setEdgeWeight

public void setEdgeWeight(Double weight)

Sets the weight for all edges.

Parameters:

weight - the weight for all edges.

setEdgeWeight

public void setEdgeWeight(String source,
                 String target,
                 String edge,
                 Double weight)

Set the weight of the given edge.

Parameters:

source - the source vertex string

target - the target vertex string

edge - the edge string

weight - the weight for this edge

getEdgeWeight

public double getEdgeWeight(V input,
                   V output,
                   E edge)

Return the weight associated with this conversion.

Parameters:

input -

output -

edge -

Returns:

save

public void save(String filename)

Save graph to the given file.

Parameters:

filename - a file to contain the graph as lines of: edge source target weight

load

public void load(String filename)

Load graph from the given file.

Parameters:

filename - a file containing the graph as lines of: edge source target weight

loadEdgeWeights

public void loadEdgeWeights(String filename,
                   Double invalid_value)

Load edge weights from the given file.

Parameters:

filename - a file containing lines with: edge source target weight (can be a URL)

invalid_value - the value to use for null weights (can be null indicating they should be ignored)

transformEdgeWeights

public void transformEdgeWeights(String expression)

Transform edge weights according to the given expression.

Parameters:

expression - an expression to apply to all edge weights

getShortestPaths

public Vector<Integer> getShortestPaths(int source)

Perform a breadth first search from the vertex at the given index and store the resulting paths.

Parameters:

source - the index of the source vertex

Returns:

the paths vector indicating from which vertex we must come to get to this vertex

dijkstra

public kgm.utility.Pair<Vector<Integer>,Vector<Double>> dijkstra(int source)

Dijstra shortest path. This is a greedy algorithm and will not be able to handle negative weights. This has a running time of O( |E| + |V| log |V| )

Parameters:

source - the node to start the search from

Returns:

a pair of distance for a node to the source, and the previous node to reach the source.

bellmanFord

public kgm.utility.Pair<Vector<Integer>,Vector<Double>> bellmanFord(int source)
                                                             throws Exception

Bellman Ford shortest path. Unlike Dijstra this can handle negative weights. This has a running time of O(|E| * |V|).

Parameters:

source - the node to start the search from

Returns:

a pair of distance for a node to the source, and the previous node to reach the source.

Throws:

will - throw an exception if a negative cycle is detected

Exception

getShortestWeightedPaths

public kgm.utility.Pair<Vector<Integer>,Vector<Double>> getShortestWeightedPaths(int source)

Perform Dijkstra's algorithm from the vertex at the given source index and store the resulting paths.

Parameters:

source - the index of the source vertex

Returns:

the paths vector indicating from which vertex we must come to get to this vertex and the weight along each path

getShortestWeightedPathsOriginal

public kgm.utility.Pair<Vector<Integer>,Vector<Double>> getShortestWeightedPathsOriginal(int source)

getPathString

public String getPathString(Vector<Integer> path)

Convert a path into a string representation.

Parameters:

path - the path from a source vertex to a target vertex

Returns:

the string representation

getMaxPathWeights

public Vector<Double> getMaxPathWeights(Vector<Integer> path)

Get the maximum weights along the path specified.

Parameters:

path - the indices of the conversion path

Returns:

a vector of weights along the given path

getRange

public TreeSet<Integer> getRange(int index)

Return a set of all reachable vertices from the given source.

Parameters:

index - the index of the source vertex

Returns:

the set of reachable vertex indices

getRangeStrings

public TreeSet<String> getRangeStrings()

Returns a set of vertex strings that are reachable from other vertices.

Returns:

the set of reachable vertex strings

getRangeStrings

public TreeSet<String> getRangeStrings(String string)

Returns a set of vertex strings that are reachable from a given source vertex.

Parameters:

string - string associated with the input vertex

Returns:

the set of reachable vertex strings

getDomain

public TreeSet<Integer> getDomain(int target)

Get the set of all vertices that can reach the target vertex.

Parameters:

target - the index of the target vertex

Returns:

the set of vertices which can reach the target

getDomainStrings

public TreeSet<String> getDomainStrings()

Get a set of all vertices that can reach other vertices.

Returns:

the set of vertices which can reach other vertices

getDomainStrings

public TreeSet<String> getDomainStrings(String target)

Get a set of all vertices that can reach the target vertex.

Parameters:

target - the target vertex string

Returns:

the set of vertices which can reach the target

getRangeIntersection

public TreeSet<Integer> getRangeIntersection(TreeSet<Integer> set)

Get the range intersection of the vertices in the given set.

Parameters:

set - a set of vertex indices

Returns:

a set of vertex indices within the given sets range intersection

getRangeIntersectionStrings

public TreeSet<String> getRangeIntersectionStrings(TreeSet<String> set)

Get the range intersection of the vertices in the given set.

Parameters:

set - a set of vertex strings

Returns:

a set of vertex strings within the given sets range intersection

getConversion

public PolyglotAuxiliary.Conversion<V,E> getConversion(String edge_string,
                                              String input_string,
                                              String output_string)

Get the conversion possessing the given name, input, and output

Parameters:

edge_string - the string associated with the conversion edge

input_string - the input

output_string - the output

Returns:

the conversion from input to output

getConversions

public Vector<PolyglotAuxiliary.Conversion<V,E>> getConversions(String conversions_string)

Parse a string containing conversion information

Parameters:

conversions_string - a string containing line separated conversions of the form: Application input output

Returns:

a vector of conversions corresponding to the given string

getShortestConversionPath

public Vector<PolyglotAuxiliary.Conversion<V,E>> getShortestConversionPath(String source_string,
                                                                  String target_string,
                                                                  boolean ENABLE_WEIGHTED_PATHS)

Get the shortest list of the conversion tasks required to convert from a given input to a given output.

Parameters:

source_string - a string representing the input type

target_string - a string representing the output type

ENABLE_WEIGHTED_PATHS - use edge weights to determine conversion paths

Returns:

a vector of conversions containing an edge, input, and output (null if no conversions found)

getShortestConversionPathString

public String getShortestConversionPathString(String source_string,
                                     String target_string,
                                     boolean ENABLE_WEIGHTED_PATHS)

Get the shortest list of the conversion tasks required to convert from a given input to a given output.

Parameters:

source_string - a string representing the input type

target_string - a string representing the output type

ENABLE_WEIGHTED_PATHS - use edge weights to determine conversion paths

Returns:

the line separated tasks, with each line containing an edge, input, and output

getShortestConversionPaths

public Vector<Vector<PolyglotAuxiliary.Conversion<V,E>>> getShortestConversionPaths(String source_string,
                                                                           String target_string)

Get the shortest list of the conversion tasks required to convert from a given input to a given output. Note: this version returns all parallel paths along the shortest path from the source

Parameters:

source_string - a string representing the input type

target_string - a string representing the output type

Returns:

a vector of conversions containing an edge, input, and output (null if no conversions found)

getShortestConversionPathStrings

public Vector<String> getShortestConversionPathStrings(String source_string,
                                              String target_string)

Get the shortest list of the conversion tasks required to convert from a given input to a given output. Note: this version returns all parallel paths along the shortest path from the source

Parameters:

source_string - a string representing the input type

target_string - a string representing the output type

Returns:

a vector of line separated tasks, with each line containing an edge, input, and output

getPath

public static Vector<Integer> getPath(Vector<Integer> paths,
                      int source,
                      int target)

Follow a path back from target to source given the single source shortest paths from the source.

Parameters:

paths - the single source shortest paths from the source

source - the source vertex

target - the destination vertex

Returns:

the path from source to target represented as indices to vertices

getIOGraphStrings

public IOGraph<String,String> getIOGraphStrings()

Get a string only version of this IOGraph.

Returns:

a string version of this IOGraph

printMinWeightedEdge

public void printMinWeightedEdge()

Find the edge with the smallest weight.

printMaxWeightedEdge

public void printMaxWeightedEdge()

Find the edge with the largest weight.

printMinWeightedVertex

public void printMinWeightedVertex()

Find the vertex with the shortest combined traversed weight when visited from other vertices.

printEdgeInformation

public void printEdgeInformation()

Display information about each unique edge.

printEdgeInformation

public void printEdgeInformation(E edge)

Display information about an edge.

Parameters:

edge - the edge to display information about

complexity

public void complexity()

Display information regarding the complexity of the graph.

timings

public static void timings(int edges,
           int formats,
           int software)

Compare time of various algorithms to find a shortest path in random graph.

Parameters:

edges - the number of edges

formats - the number of vertices

software - the number of applications

debug1

public static void debug1()

Debug shortest paths.

main

public static void main(String[] args)

A main for debug purposes.

Parameters:

args - command line arguments