bcds.phison
Class GraphUtil

java.lang.Object
  bcds.phison.GraphUtil

public abstract class GraphUtil
extends java.lang.Object

This class provides utility functions for creating new graph object, computing a number of metrics, writing or reading topology files, among others.

By design, this is a non-instantiatable class. All public methods must be static.

Author:

Juan Segovia S.

Constructor Summary

GraphUtil()

Method Summary

static <V,E> double	assortativity(SimGraph<V,E> g) Returns graph's assortativity coefficient.
static <V,E> SimGraph<V,E>	asUndirectedGraph(SimGraph<V,E> g) Returns a new subgraph in which the edges are only those considered as canonic in the graph g.
static <V,E> java.util.Map<SimplePair<V,V>,java.lang.Double>	booleanRandomTrafficMatrix(SimGraph<V,E> g, java.util.Random rnd) Generates a random traffic matrix consisting of 0s and 1s.
static <V,E> E	canonicEdge(SimGraph<V,E> g, E e) Deprecated. It is better to use g.canonicEdge(e) directly.
static <V,E> java.util.Map<V,java.lang.Float>	clusteringCoefficients(SimGraph<V,E> g) Deprecated. New code should use the ClusteringCoeff class directly.
static <V,E> java.util.Map<E,java.lang.Double>	constantEdgeCost(SimGraph<V,E> g, double c) Returns a HashMap in which the keys are the edges of graph g, all of them with value c.
static <V extends GraphIONode,E> GraphReader<V,E>	createGraphReader(java.lang.String fname, SimGraph<V,E> g) Instantiates a new graph reader based on the filename extension.
static <V extends GraphIONode,E> GraphWriter<V,E>	createGraphWriter(java.io.PrintStream out, java.lang.String ftype, SimGraph<V,E> g) Creates a GraphWriter tied to a java.io.PrintStream object.
static <V extends GraphIONode,E> GraphWriter<V,E>	createGraphWriter(java.lang.String fname, SimGraph<V,E> g) Instantiates a new graph writer based on the filename extension.
static <V extends GraphIONode,E> GraphWriter<V,E>	createGraphWriter(java.io.Writer out, java.lang.String ftype, SimGraph<V,E> g) Creates a GraphWriter tied to a java.io.Writer object.
static <V extends GraphIONode,E> java.util.Map<java.lang.String,java.lang.String>	createNodeLabelToIdMap(SimGraph<V,E> g) Returns a HashMap that associats node labels to node ids, as in ("Athens" : 0), ("Berlin" : 14), etc.
static <V,E> void	fillWithLatticeTopology(SimGraph<V,E> g, int num_rows, int num_cols) Removes all the links and nodes in the graph g and inserts new ones so that the result is a two-dimensional grid topology (a lattice).
static <V,E> void	fillWithRingTopology(SimGraph<V,E> g, int num_nodes) Removes all the links and nodes in the graph g and inserts new ones so that the result is ring topology.
static <V,E> SimGraph<V,E>	filterOutBidiLinks(SimGraph<V,E> g, Path<V,E> path) Returns a subgraph in which the edges of path do not appear.
static <V,E> SimGraph<V,E>	filterOutIntermediateNodes(SimGraph<V,E> g, Path<V,E> path) Returns a subgraph in which the non-end of path are absent.
static <V,E> boolean	isStronglyConnected(SimGraph<V,E> g) Returns true if g is a strongly-connected graph and false otherwise.
static <V,E> java.lang.Object[]	networkDiameter(SimGraph<V,E> g) Returns information about the network diameter and shortest path lengths when the link cost is 1, that is, when path length is measured in number of hops.
static <V,E,N extends java.lang.Number> java.lang.Object[]	networkDiameter(SimGraph<V,E> g, java.util.Map<E,N> cost) Computes the network diameter and the average path length, and returns information about these two measures in an array.
static <V,E> SimGraph<V,E>	newGraph(java.lang.Class<V> node_cls, java.lang.Class<E> link_cls) Creates a new graph whose nodes and links will be of the given types.
static <V,E> FreqTable<java.lang.Integer>	nodalDegreeFreq(SimGraph<V,E> g) Returns the frequency distribution of the nodal degrees of the graph g.
static <V,E> boolean	pathContainsBidiLink(SimGraph<V,E> g, E e, Path<V,E> path) Returns true if path contains the link e, either as e itself or as reverse(e).
static <V,E> E	reverseEdge(SimGraph<V,E> g, E e) Deprecated. Better use g.reverseEdge() directly.
static <V,E> SimplePair<Path<V,E>,Path<V,E>>	splitProtAndUnprotParts(Path<V,E> pri, Path<V,E> sec) Given two paths pri and sec, of which the first is the primary path and the second the backup path, returns pri split into two segments, the unprotected and protected parts.
static <V,E> float	twoTerminalReliability(SimGraph<V,E> g) Returns the average two-terminal reliability.

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

newGraph

public static <V,E> SimGraph<V,E> newGraph(java.lang.Class<V> node_cls,
                                           java.lang.Class<E> link_cls)

Creates a new graph whose nodes and links will be of the given types. The graph returned is an instance of SdiGraph.

reverseEdge

public static <V,E> E reverseEdge(SimGraph<V,E> g,
                                  E e)

Deprecated. Better use g.reverseEdge() directly.

Returns the reverse of edge e.

canonicEdge

public static <V,E> E canonicEdge(SimGraph<V,E> g,
                                  E e)

Deprecated. It is better to use g.canonicEdge(e) directly.

Returns the "canonic" edge that corresponds to e.

asUndirectedGraph

public static <V,E> SimGraph<V,E> asUndirectedGraph(SimGraph<V,E> g)

Returns a new subgraph in which the edges are only those considered as canonic in the graph g.

Beware that the returned graph is not, strictly speaking, undirected; it is just graph in which each pair of neighbours has at most one directed link.

The subgraph is created by calling SimGraph.createSubgraph(java.util.Set, java.util.Set).

filterOutBidiLinks

public static <V,E> SimGraph<V,E> filterOutBidiLinks(SimGraph<V,E> g,
                                                     Path<V,E> path)

Returns a subgraph in which the edges of path do not appear. If the edges in path have two directions, both are removed.

The subgraph is created by calling SimGraph.createSubgraph(java.util.Set, java.util.Set).

filterOutIntermediateNodes

public static <V,E> SimGraph<V,E> filterOutIntermediateNodes(SimGraph<V,E> g,
                                                             Path<V,E> path)

Returns a subgraph in which the non-end of path are absent. If path consists of only one link, no "intermediate" node exists, and so no nodes are excluded from the output.

The subgraph is created by calling SimGraph.createSubgraph(java.util.Set, java.util.Set).

splitProtAndUnprotParts

public static <V,E> SimplePair<Path<V,E>,Path<V,E>> splitProtAndUnprotParts(Path<V,E> pri,
                                                                            Path<V,E> sec)

Given two paths pri and sec, of which the first is the primary path and the second the backup path, returns pri split into two segments, the unprotected and protected parts. Example:

   a ---- b  ----- c ---- d ---- e ---- f ---- g ---- h ---- i
                   \                          /
                    \                        /
                     n ---- m ------ o ---- p
 

In this example, node c is the split point, whereas g is the merge point. The two parts returned are:

• (a-b, b-c) + (g-h, h-i): the unprotected part.
• c-d, d-e, e-f, f-g: the protected part.

The path sec must "touch" the path pri at exactly two nodes.

Note the objects returned are of type bcds.phison.Path, but the caller must see them simply as list of edges. In particular, as the example illustrates, the unprotected part in fact more than one subpath.

Throws:

java.lang.IllegalArgumentException - if sec does not comply with the requirement that it has exactly two nodes in common with pri.

pathContainsBidiLink

public static <V,E> boolean pathContainsBidiLink(SimGraph<V,E> g,
                                                 E e,
                                                 Path<V,E> path)

Returns true if path contains the link e, either as e itself or as reverse(e). If path is null, returns false.

networkDiameter

public static <V,E,N extends java.lang.Number> java.lang.Object[] networkDiameter(SimGraph<V,E> g,
                                                                                  java.util.Map<E,N> cost)

Computes the network diameter and the average path length, and returns information about these two measures in an array. The shortest paths are computed taking into account the link costs given in the parameter cost. The returned array elements are:

• Element 0 (of type double): the network diameter.
• Element 1 (of type bcds.phison.Path): the path corresponding to [0].
• element 2 (of type double): the average minimum distance between node-pairs.

This method is a wrapper on Diameter.

networkDiameter

public static <V,E> java.lang.Object[] networkDiameter(SimGraph<V,E> g)

Returns information about the network diameter and shortest path lengths when the link cost is 1, that is, when path length is measured in number of hops. See networkDiameter(SimGraph, Map).

clusteringCoefficients

public static <V,E> java.util.Map<V,java.lang.Float> clusteringCoefficients(SimGraph<V,E> g)

Deprecated. New code should use the ClusteringCoeff class directly.

A wrapper on ClusteringCoeff.

constantEdgeCost

public static <V,E> java.util.Map<E,java.lang.Double> constantEdgeCost(SimGraph<V,E> g,
                                                                       double c)

Returns a HashMap in which the keys are the edges of graph g, all of them with value c.

This method should be used when it is anticipated that the values in the map will change. If they will not, it is more efficient to use an instance of MapToConst.

isStronglyConnected

public static <V,E> boolean isStronglyConnected(SimGraph<V,E> g)

Returns true if g is a strongly-connected graph and false otherwise. It uses ConnectedComponents.

booleanRandomTrafficMatrix

public static <V,E> java.util.Map<SimplePair<V,V>,java.lang.Double> booleanRandomTrafficMatrix(SimGraph<V,E> g,
                                                                                               java.util.Random rnd)

Generates a random traffic matrix consisting of 0s and 1s. Therefore traffic between any given node-pair is either "allowed" or not. If the parameter rnd is not null, that object is used to draw random numbers. Otherwise, Math.ramdom()

The returned matrix is not symmetric, that is, the traffic between the pair (a, b) might not match that of the pair (b, a).

nodalDegreeFreq

public static <V,E> FreqTable<java.lang.Integer> nodalDegreeFreq(SimGraph<V,E> g)

Returns the frequency distribution of the nodal degrees of the graph g. It is assumed that g is directed and that both directions of each link are present.

createGraphReader

public static <V extends GraphIONode,E> GraphReader<V,E> createGraphReader(java.lang.String fname,
                                                                           SimGraph<V,E> g)

Instantiates a new graph reader based on the filename extension. The supported extensions are:

• .net or .net.gz. Reader type: NetGraphReader
• .sgf or .sgf.gz: Reader type: SgfGraphReader
• .graphml or .graphml.gz: Reader type: GraphMLReader
• (stdin) -: SgfGraphReader is used.

When fname is stdin, that is, -, the new reader object references Java's System.in.

Please note that generic parameter V, the type of nodes, must be a class that implements GraphIONode. Otherwise, the compiler reports that the method does not exist. The same is applicable to createGraphWriter(java.lang.String, bcds.phison.SimGraph).

Throws:

java.lang.IllegalArgumentException - if the file type cannot be determined, for example because the filename does not include an "extension".

createGraphWriter

public static <V extends GraphIONode,E> GraphWriter<V,E> createGraphWriter(java.lang.String fname,
                                                                           SimGraph<V,E> g)

Instantiates a new graph writer based on the filename extension. The supported extensions are:

• .net or .net.gz. Writer type: NetGraphWriter
• .sgf or .sgf.gz: Writer type: SgfGraphWriter
• .graphml or .graphml.gz: Writer type: GraphMLWriter
• (stdout) -: SgfGraphWriter is used.

When fname is stdout, that is, -, the new reader object references Java's System.in.

Throws:

java.lang.IllegalArgumentException - if the file type cannot be determined, for example because the filename does not include an "extension".

java.io.IOException - wrapped in a AnyException if any IOException occurs during object instantiation.

createGraphWriter

public static <V extends GraphIONode,E> GraphWriter<V,E> createGraphWriter(java.io.PrintStream out,
                                                                           java.lang.String ftype,
                                                                           SimGraph<V,E> g)

Creates a GraphWriter tied to a java.io.PrintStream object. This method is equivalent to createGraphWriter(new OutputStreamWriter(out), ftype, g).

createGraphWriter

public static <V extends GraphIONode,E> GraphWriter<V,E> createGraphWriter(java.io.Writer out,
                                                                           java.lang.String ftype,
                                                                           SimGraph<V,E> g)

Creates a GraphWriter tied to a java.io.Writer object. The parameter ftype indicates the "extension", for example ".net" or ".sgf", not a filenane. The supported extensions are the ones given in createGraphWriter(String, SimGraph).

This method calls createGraphWriter(Writer, String, SimGraph) and thus throws the same exceptions thrown there.

note that a dot is expected in ftype. Thus, ".sgf" is recognized while "sgf" is not.

fillWithLatticeTopology

public static <V,E> void fillWithLatticeTopology(SimGraph<V,E> g,
                                                 int num_rows,
                                                 int num_cols)

Removes all the links and nodes in the graph g and inserts new ones so that the result is a two-dimensional grid topology (a lattice).

fillWithRingTopology

public static <V,E> void fillWithRingTopology(SimGraph<V,E> g,
                                              int num_nodes)

Removes all the links and nodes in the graph g and inserts new ones so that the result is ring topology.

createNodeLabelToIdMap

public static <V extends GraphIONode,E> java.util.Map<java.lang.String,java.lang.String> createNodeLabelToIdMap(SimGraph<V,E> g)

Returns a HashMap that associats node labels to node ids, as in ("Athens" : 0), ("Berlin" : 14), etc. If a node does not have the attribute "label", then the attribute "id" is used instead; if "id" is also missing, the node's toString method is used.

twoTerminalReliability

public static <V,E> float twoTerminalReliability(SimGraph<V,E> g)

Returns the average two-terminal reliability. This method is a wrapper on AvgTwoTermReliability.

assortativity

public static <V,E> double assortativity(SimGraph<V,E> g)

Returns graph's assortativity coefficient. This method is a wrapper on Assortativity.