Source code for bioa.util.graph
"""
=======================
Graph Utility Functions
=======================
"""
__all__ = ["max_bandwidth",
"graph_rank"]
__author__ = """Nicholas Mancuso (nick.mancuso@gmail.com)"""
# Copyright (C) 2011-2012 by
# Nicholas Mancuso <nick.mancuso@gmail.com>
# Bassam Tork <basamt@gmail.com>
# All rights reserved.
# BSD license.
import sys
import networkx as nx
import bioa as ba
[docs]def max_bandwidth(graph, source="source", freq_name="count", epsilon=1e-3):
""" Given a graph G = (V,E) with capacity over vertices and a source,
find the set of paths which maximize the bandwidth (minimize the
bottleneck) from the source.
Parameters
----------
graph : NetworkX Graph
Graph to find the maximum bandwidth path of.
source : str (optional, default="source")
Name of the source vertex to begin the search from.
freq_name : str (optional, default="count")
Name of the frequency or count property to use.
epsilon : float (optional, default=1e-3)
Threshold for edge values to consider.
Returns
-------
bandwidth_and_paths : (dict, dict) tuple
Dictionary of the bandwidth from the source to a node along with
the dictionary of the maximum bandwidth path from a source to a
node.
"""
bwidths = {} # dictionary of final bandwidths
paths = {source: [source]} # dictionary of paths
seen = {source: sys.maxint}
fringe = ba.PQueue([(sys.maxint, source)], behave="max")
while len(fringe) > 0:
v, b = fringe.get_max()
if v in bwidths:
continue # already searched this node.
bwidths[v] = b
edata = iter(graph[v].items())
for w, edgedata in edata:
vw_band = min([bwidths[v], edgedata[freq_name]])
if vw_band > seen.get(w, epsilon):
seen[w] = vw_band
fringe.add_node(vw_band, w)
paths[w] = paths[v] + [w]
return (bwidths, paths)
[docs]def graph_rank(graph):
""" Rank of an undirected graph is defined as n - c where n is the
number of vertices in the graph and c is the number of connected
components of the graph. This is the same rank as the representative
incidence matrix.
Parameters
----------
graph : NetworkX Graph
Undirected graph.
Returns
-------
rank : int
Rank of the graph.
"""
if graph is None:
raise ValueError("Valid graph must be used!")
if graph.is_directed():
raise ValueError("Rank of a directed graph not defined")
ncount = len(graph)
nconcomps = nx.number_connected_components(graph)
return ncount - nconcomps