Topology Related Utility Functions

bluefog.common.topology_util.IsTopologyEquivalent(topo1: networkx.classes.digraph.DiGraph, topo2: networkx.classes.digraph.DiGraph) → bool

Determine two topologies are equivalent or not.

Notice we do not check two topologies are isomorphism. Instead checking the adjacenty matrix is the same only.

bluefog.common.topology_util.GetWeights(topo: networkx.classes.digraph.DiGraph, rank: int) → Tuple[float, Dict[int, float]]

Return a Tuple of self_weight and neighbor_weights dictionary.

bluefog.common.topology_util.PowerTwoRingGraph(size: int) → networkx.classes.digraph.DiGraph

Generate graph topology such that each points only connected to a point such that the index difference is power of 2.

Example: Plot a PowerTwoRingGraph with 12 nodes:

>>> import networkx as nx
>>> from bluefog.common import topology_util
>>> G = topology_util.PowerTwoRingGraph(12)
>>> nx.draw_circular(G)

bluefog.common.topology_util.MeshGrid2DGraph(size: int, shape: Tuple[int, int] = None) → networkx.classes.digraph.DiGraph

Generate 2D MeshGrid structure of graph.

Assume shape = (nrow, ncol), when shape is provided, a meshgrid of nrow*ncol will be generated. when shape is not provided, nrow and ncol will be the two closest factors of size.

For example: size = 24, nrow and ncol will be 4 and 6, respectively. We assume nrow will be equal to or smaller than ncol. If size is a prime number, nrow will be 1, and ncol will be size, which degrades the topology into a linear one.

Example: Plot a MeshGrid2DGraph with 16 nodes:

>>> import networkx as nx
>>> from bluefog.common import topology_util
>>> G = topology_util.MeshGrid2DGraph(16)
>>> nx.draw_spring(G)

bluefog.common.topology_util.StarGraph(size: int, center_rank: int = 0) → networkx.classes.digraph.DiGraph

Generate star structure of graph.

All other ranks are connected to the center_rank. The connection is bidirection, i.e. if the weight from node i to node j is non-zero, so is the weight from node j to node i.

Example: Plot a StarGraph with 16 nodes:

>>> import networkx as nx
>>> from bluefog.common import topology_util
>>> G = topology_util.StarGraph(16)
>>> nx.draw_spring(G)

bluefog.common.topology_util.RingGraph(size: int, connect_style: int = 0) → networkx.classes.digraph.DiGraph

Generate ring structure of graph (uniliteral). Argument connect_style should be an integer between 0 and 2, where 0 represents the bi-connection, 1 represents the left-connection, and 2 represents the right-connection.

Example: Plot a RingGraph with 16 nodes:

>>> import networkx as nx
>>> from bluefog.common import topology_util
>>> G = topology_util.RingGraph(16)
>>> nx.draw_circular(G)

bluefog.common.topology_util.FullyConnectedGraph(size: int) → networkx.classes.digraph.DiGraph

Generate fully connected structure of graph. For example, a FullyConnectedGraph with 16 nodes:

Example: Plot a FullyConnectedGraph 16 nodes

>>> import networkx as nx
>>> from bluefog.common import topology_util
>>> G = topology_util.FullyConnectedGraph(16)
>>> nx.draw_spring(G)

bluefog.common.topology_util.np