de.ipk_gatersleben.ag_nw.centilib.utils
Class GraphCachingUtils<V,E>

java.lang.Object
  extended by de.ipk_gatersleben.ag_nw.centilib.utils.GraphCachingUtils<V,E>

public class GraphCachingUtils<V,E>
extends Object

All values like centrality values, graph properties, edge weights or connected components can be stored and accessed via this class. As default, the cache is not activated to avoid unreliable values when a graph changes. If you want to store values activate the cache via setUseCache(true) and make sure to remove a graph and its values if a node or an edge was added or removed because already computed values get unreliable.
If the cache is activated, every time a method is called for an unknown graph an instance of Distance is created. It computes and stores the distances between the nodes of a graph. If edge weights are set, weighted shortest paths will be computed. Make use of this instance via getDistance(graph), to compute a shortest path only if needed and only once.

If a value is not available yet, it will be computed (and stored if the chache is activated) automatically. This is not true for centralities. Use CentralityHandler to compute centralities.

Author:
Johannes Graessler

Constructor Summary
GraphCachingUtils()
           
 
Method Summary
static
<V,E> void
addGraphCentrality(Graph<V,E> graph, String centName, Double value)
          Adds the given graph centrality value for graph to the cache.
static
<V,E> void
addScorer(Graph<V,E> graph, VertexCentrality<V,E> scorer, String name)
          Adds the given node centrality for graph to the cache.
static
<V,E> boolean
containsParallelEdges(Graph<V,E> graph)
          Determines whether graph contains parallel edges or not.
static
<V,E> boolean
containsSelfLoops(Graph<V,E> graph)
          Determines whether graph contains self loops or not.
static
<V,E> Collection<String>
getAvailableScorerNames(Graph<V,E> graph)
          Returns the list of names of already computed centralities for the given graph.
static
<V,E> Set<Set<V>>
getConnectedComponents(Graph<V,E> graph)
          Returns a set of connected components for the given graph.
static
<V,E> Distance<V>
getDistance(Graph<V,E> graph)
          Returns an instance of the interface Distance for the given graph.
static
<V,E> Set<E>
getEdgesOfComponent(Graph<V,E> graph, Set<V> vertices)
          Returns the edges between the given vertices.
static
<V,E> Map<E,Number>
getEdgeWeights(Graph<V,E> graph)
          Returns the edge weights for the given graph, if they exist.
static
<V,E> org.apache.commons.collections15.Transformer<E,Double>
getEdgeWeightTransformer(Graph<V,E> graph)
          Returns a transformer for edge weights if they were set.
static
<V,E> Double
getGraphCentrality(Graph<V,E> graph, String centName)
          Returns the requested centrality value for the given graph if it exists.
static
<V,E> String
getGraphName(Graph<V,E> graph)
          Returns the name of the given graph, if it exists.
static
<V,E> Collection<Graph<V,E>>
getGraphs()
          Returns the list of known graphs.
static
<V,E> DoubleAttribute<E>
getLastEdgeAttribute(Graph<V,E> graph)
          Returns the last edge attribute for the given graph if it exists.
static
<V,E> VertexCentrality<V,E>
getLastScorer(Graph<V,E> graph)
          Returns the currently selected centrality instance for graph.
static
<V,E> String
getLastScorerName(Graph<V,E> graph)
          Returns the name of the last scorer that was added to the cache.
static
<V,E> org.apache.commons.collections15.BidiMap<V,Integer>
getResultList(Graph<V,E> graph, VertexCentrality<V,E> ranker)
          This method is for CentiLib internal use only (result panel).
static
<V,E> VertexCentrality<V,E>
getScorer(Graph<V,E> graph, String scorerName)
          Returns the centrality with name scorerName for the given graph.
static
<V,E> ShortestPath<V,E>
getShortestPath(Graph<V,E> graph)
          Returns an instance of the interface ShortestPath for the given graph.
static
<V,E> Set<Set<V>>
getStrongConnectedComponents(Graph<V,E> graph)
          Returns a set of strongly connected components for the given graph.
static
<V,E> boolean
isConnected(Graph<V,E> graph)
          Determines whether the given graph is connected or not.
static
<V,E> boolean
isDirected(Graph<V,E> graph)
          Determines whether graph is directed or not.
static
<V,E> boolean
isStrongConnected(Graph<V,E> graph)
          Determines whether graph is strongly connected or not.
static
<V,E> boolean
isUndirected(Graph<V,E> graph)
          Determines whether graph is undirected or not.
static
<V,E> void
remove(Graph<V,E> graph)
          Removes the given graph and all it's values from the cache.
static void removeAllGraphsFromCache()
          Removes all graphs from the cache.
static
<V,E> void
removeEdgeWeights(Graph<V,E> graph)
          Removes existing edge weights for the given graph.
static
<V,E> boolean
setEdgeWeights(Graph<V,E> graph, Map<E,Number> weights)
          Stores the given weights for the graph 'graph'.
static
<V,E> void
setGraphName(Graph<V,E> graph, String name)
          Stores the name of a graph.
static
<V,E> void
setLastEdgeAttribute(Graph<V,E> graph, DoubleAttribute<E> attribute)
          Sets the current edge attribute for the given graph.
static
<V,E> void
setResultList(Graph<V,E> graph, VertexCentrality<V,E> ranker, org.apache.commons.collections15.BidiMap<V,Integer> list)
          This method is for CentiLib internal use only (result panel).
static void setUseCache(boolean useCache)
          Sets whether to store computed values or not.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

GraphCachingUtils

public GraphCachingUtils()
Method Detail

setUseCache

public static void setUseCache(boolean useCache)
Sets whether to store computed values or not.

Parameters:
useCache - True if values should be stored.

setGraphName

public static <V,E> void setGraphName(Graph<V,E> graph,
                                      String name)
Stores the name of a graph.

Type Parameters:
V - Type of nodes.
E - Type of edges.
Parameters:
graph - The graph to store the name for.
name - The name of the given graph.

getGraphName

public static <V,E> String getGraphName(Graph<V,E> graph)
Returns the name of the given graph, if it exists.

Type Parameters:
V - Type of nodes.
E - Type of edges.
Parameters:
graph - The graph to return the name for.
Returns:
The name of the given graph. Null if it does not exist.

setEdgeWeights

public static <V,E> boolean setEdgeWeights(Graph<V,E> graph,
                                           Map<E,Number> weights)
Stores the given weights for the graph 'graph'. If no weights are given, existing ones are deleted. Returns false, if useCache is set to false or graph is null;

Type Parameters:
V - Type of the vertices
E - Type of the edges
Parameters:
graph - The graph for which the edge weights will be stored
weights - A Map to resolve the weights for all edges
Returns:
True if useCache is set to true, false otherwise

setLastEdgeAttribute

public static <V,E> void setLastEdgeAttribute(Graph<V,E> graph,
                                              DoubleAttribute<E> attribute)
Sets the current edge attribute for the given graph. This only stores the attribute for reference. No edge weights will be generated. If null is given, the last attribute will be deleted for the given graph.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to store the attribute for.
attribute - The attribute to store.

removeEdgeWeights

public static <V,E> void removeEdgeWeights(Graph<V,E> graph)
Removes existing edge weights for the given graph. The last edge attribute will be deleted, too. Furthermore the weighted distances will be replaced by unweighted ones.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to remove the edge weights for.

getEdgeWeights

public static <V,E> Map<E,Number> getEdgeWeights(Graph<V,E> graph)
Returns the edge weights for the given graph, if they exist. Otherwise it returns null.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to get edge weights for.
Returns:
the edge weights for the given graph if they exist, null otherwise.

getEdgeWeightTransformer

public static <V,E> org.apache.commons.collections15.Transformer<E,Double> getEdgeWeightTransformer(Graph<V,E> graph)
Returns a transformer for edge weights if they were set. Call transformer.transform(edge) to use it.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to get the transformer for.
Returns:
a transformer for edge weights or null

getLastEdgeAttribute

public static <V,E> DoubleAttribute<E> getLastEdgeAttribute(Graph<V,E> graph)
Returns the last edge attribute for the given graph if it exists. Otherwise null is returned.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to get the attribute for.
Returns:
the last attribute for the given graph or null

getGraphs

public static <V,E> Collection<Graph<V,E>> getGraphs()
Returns the list of known graphs.

Type Parameters:
V - Type of nodes
E - Type of edges
Returns:
the list of known graphs

getGraphCentrality

public static <V,E> Double getGraphCentrality(Graph<V,E> graph,
                                              String centName)
Returns the requested centrality value for the given graph if it exists. Otherwise null is returned.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph a centrality should be returned for
centName - The name of the centrality to get for the given graph
Returns:
the graph centrality value for the given graph or null

getDistance

public static <V,E> Distance<V> getDistance(Graph<V,E> graph)
Returns an instance of the interface Distance for the given graph. It computes and stores the lengths of shortest paths for a single graph. If edge weights were set, they will be taken into account.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to get the distances for.
Returns:
an instance for weighted or unweighted lengths of shortest paths for the given graph

getShortestPath

public static <V,E> ShortestPath<V,E> getShortestPath(Graph<V,E> graph)
Returns an instance of the interface ShortestPath for the given graph. In contrast to the interface Distance you get the exact shortest paths instead of the length.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to shortest paths for.
Returns:
an instance for the shortest paths of the given graph.

isConnected

public static <V,E> boolean isConnected(Graph<V,E> graph)
Determines whether the given graph is connected or not.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph -
Returns:
true if graph is connected, false otherwise

isStrongConnected

public static <V,E> boolean isStrongConnected(Graph<V,E> graph)
Determines whether graph is strongly connected or not.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to check.
Returns:
true if graph is strongly connected, false otherwise.

isDirected

public static <V,E> boolean isDirected(Graph<V,E> graph)
Determines whether graph is directed or not.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to check.
Returns:
true if graph is directed, false otherwise.

isUndirected

public static <V,E> boolean isUndirected(Graph<V,E> graph)
Determines whether graph is undirected or not.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to check.
Returns:
true if graph is undirected, false otherwise.

containsSelfLoops

public static <V,E> boolean containsSelfLoops(Graph<V,E> graph)
Determines whether graph contains self loops or not.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to find self loops in.
Returns:
true if graph contains self loops, false otherwise.

containsParallelEdges

public static <V,E> boolean containsParallelEdges(Graph<V,E> graph)
Determines whether graph contains parallel edges or not.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to find parallel edeges in.
Returns:
true if graph contains parallel edges.

addGraphCentrality

public static <V,E> void addGraphCentrality(Graph<V,E> graph,
                                            String centName,
                                            Double value)
Adds the given graph centrality value for graph to the cache.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to store the centrality value for
centName - The name of the graph centrality
value - The value of the graph centrality

addScorer

public static <V,E> void addScorer(Graph<V,E> graph,
                                   VertexCentrality<V,E> scorer,
                                   String name)
Adds the given node centrality for graph to the cache.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to store the centrality for.
scorer - The instance that contains the centrality values.
name - The name of the centrality

getLastScorer

public static <V,E> VertexCentrality<V,E> getLastScorer(Graph<V,E> graph)
Returns the currently selected centrality instance for graph. That is, the last centrality added.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to return the lastly added centrality for.
Returns:
the last centrality that was added for graph or null

getLastScorerName

public static <V,E> String getLastScorerName(Graph<V,E> graph)
Returns the name of the last scorer that was added to the cache.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to get the name of the lastly added centrality for.
Returns:
the name of the last centrality that was added for graph or an empty string.

getScorer

public static <V,E> VertexCentrality<V,E> getScorer(Graph<V,E> graph,
                                                    String scorerName)
Returns the centrality with name scorerName for the given graph.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to return the centrality for.
scorerName - The name of the centrality
Returns:
a centrality instance or null

getAvailableScorerNames

public static <V,E> Collection<String> getAvailableScorerNames(Graph<V,E> graph)
Returns the list of names of already computed centralities for the given graph.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph -
Returns:
the list of names of available centralities.

getResultList

public static <V,E> org.apache.commons.collections15.BidiMap<V,Integer> getResultList(Graph<V,E> graph,
                                                                                      VertexCentrality<V,E> ranker)
This method is for CentiLib internal use only (result panel).

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - !document me!
ranker - !document me!
Returns:
!document me!

setResultList

public static <V,E> void setResultList(Graph<V,E> graph,
                                       VertexCentrality<V,E> ranker,
                                       org.apache.commons.collections15.BidiMap<V,Integer> list)
This method is for CentiLib internal use only (result panel).

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - !document me!
ranker - !document me!
list - !document me!

getConnectedComponents

public static <V,E> Set<Set<V>> getConnectedComponents(Graph<V,E> graph)
Returns a set of connected components for the given graph.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to return the connected components for.
Returns:
a set of connected components.

getStrongConnectedComponents

public static <V,E> Set<Set<V>> getStrongConnectedComponents(Graph<V,E> graph)
Returns a set of strongly connected components for the given graph.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to return the strongly connected components for.
Returns:
a set of strongly connected components or null.

getEdgesOfComponent

public static <V,E> Set<E> getEdgesOfComponent(Graph<V,E> graph,
                                               Set<V> vertices)
Returns the edges between the given vertices.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph the vertices and edges belong to.
vertices - The nodes to get the edges for.
Returns:
the edges that exist betwenn the given nodes in the graph or null.

remove

public static <V,E> void remove(Graph<V,E> graph)
Removes the given graph and all it's values from the cache.

Type Parameters:
V - Type of nodes
E - Type of edges
Parameters:
graph - The graph to remove from the cache.

removeAllGraphsFromCache

public static void removeAllGraphsFromCache()
Removes all graphs from the cache. That is, cleans it.