unikl.disco.misc
Class GraphUtils

java.lang.Object
  extended by unikl.disco.misc.GraphUtils

public class GraphUtils
extends java.lang.Object

A tiny collection of methods useful in dealing with graphs but not provided by JUNG.

Author:
Frank A. Zdarsky

Constructor Summary
GraphUtils()
           
 
Method Summary
static edu.uci.ics.jung.graph.impl.DirectedSparseGraph createServerGraph(edu.uci.ics.jung.graph.impl.DirectedSparseGraph network_graph, java.util.Map link_server_map, java.util.Map router_turns_map)
          Creates and returns server graph from a given network_graph by creating a server for each link and an edge between servers for each turn around a router.
static edu.uci.ics.jung.graph.impl.DirectedSparseGraph createServerGraphFromPaths(java.util.List paths, java.util.Map link_server_map, java.util.Map router_turns_map)
          Creates and returns server graph by traversing all elements in the list of paths pahts and creating a server for each each traversed link (if none exists yet) and an edge between servers for each pair of traversed links (if none exists yet.
static java.util.Set getServerSet(edu.uci.ics.jung.graph.impl.DirectedSparseGraph g)
          Returns the subsets of all nodes of the directed graph g that are neither sources nor sinks, i.e. who have both (a) predecessor(s) and (a) successor(s) (in-degree > 0 and out-degree > 0).
static java.util.Set getSinkSet(edu.uci.ics.jung.graph.impl.DirectedSparseGraph g)
          Returns the subsets of all nodes of the directed graph g that are sinks, i.e. whose successor set is empty (out-degree == 0).
static java.util.Set getSourceSet(edu.uci.ics.jung.graph.impl.DirectedSparseGraph g)
          Returns the subsets of all nodes of the directed graph g that are sources, i.e. whose predecessor set is empty (in-degree == 0).
static java.util.List getSubPath(java.util.List path, edu.uci.ics.jung.graph.Vertex from, edu.uci.ics.jung.graph.Vertex to)
          Returns a sublist view of the given edge path path from the vertex from to vertex to or an empty list if the vertices are not both on the path and traversed in order.
 
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

getSourceSet

public static java.util.Set getSourceSet(edu.uci.ics.jung.graph.impl.DirectedSparseGraph g)
Returns the subsets of all nodes of the directed graph g that are sources, i.e. whose predecessor set is empty (in-degree == 0).

Parameters:
g - the graph
Returns:
the set of source nodes

getSinkSet

public static java.util.Set getSinkSet(edu.uci.ics.jung.graph.impl.DirectedSparseGraph g)
Returns the subsets of all nodes of the directed graph g that are sinks, i.e. whose successor set is empty (out-degree == 0).

Parameters:
g - the graph
Returns:
the set of sink nodes

getServerSet

public static java.util.Set getServerSet(edu.uci.ics.jung.graph.impl.DirectedSparseGraph g)
Returns the subsets of all nodes of the directed graph g that are neither sources nor sinks, i.e. who have both (a) predecessor(s) and (a) successor(s) (in-degree > 0 and out-degree > 0).

Parameters:
g - the graph
Returns:
the set of server nodes

getSubPath

public static java.util.List getSubPath(java.util.List path,
                                        edu.uci.ics.jung.graph.Vertex from,
                                        edu.uci.ics.jung.graph.Vertex to)
Returns a sublist view of the given edge path path from the vertex from to vertex to or an empty list if the vertices are not both on the path and traversed in order.

Parameters:
path -
from -
to -
Returns:
the sub path from from to to

createServerGraph

public static edu.uci.ics.jung.graph.impl.DirectedSparseGraph createServerGraph(edu.uci.ics.jung.graph.impl.DirectedSparseGraph network_graph,
                                                                                java.util.Map link_server_map,
                                                                                java.util.Map router_turns_map)
Creates and returns server graph from a given network_graph by creating a server for each link and an edge between servers for each turn around a router.
If empty map instances are passed for link_server_map and/or router_turns_map, the maps will be filled with mappings of links (instance of DirectedEdge) to servers (instance of SimpleSparseVertex and routers (instance of SimpleSparseVertex) to a set of turns (instance of DirectedEdge). If you do not need these mappings, simply pass null instead.

Parameters:
network_graph - the network graph
link_server_map - a mapping of links to servers
router_turns_map - a mapping of routers to sets of turns (= edge between two servers)
Returns:
a server graph

createServerGraphFromPaths

public static edu.uci.ics.jung.graph.impl.DirectedSparseGraph createServerGraphFromPaths(java.util.List paths,
                                                                                         java.util.Map link_server_map,
                                                                                         java.util.Map router_turns_map)
Creates and returns server graph by traversing all elements in the list of paths pahts and creating a server for each each traversed link (if none exists yet) and an edge between servers for each pair of traversed links (if none exists yet.
If empty map instances are passed for link_server_map and/or router_turns_map, the maps will be filled with mappings of links (instance of DirectedEdge) to servers (instance of SimpleSparseVertex and routers (instance of SimpleSparseVertex) to a set of turns (instance of DirectedEdge). If you do not need these mappings, simply pass null instead.

Parameters:
paths - a list of edge paths
link_server_map - a mapping of links to servers
router_turns_map - a mapping of routers to sets of turns (= edge between two servers)
Returns:
a server graph