Statistics
| Branch: | Revision:

## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / swap.py @ 5cef0f13

 1 ```# -*- coding: utf-8 -*- ``` ```"""Swap edges in a graph. ``` ```""" ``` ```# Copyright (C) 2004-2019 by ``` ```# Aric Hagberg ``` ```# Dan Schult ``` ```# Pieter Swart ``` ```# All rights reserved. ``` ```# BSD license. ``` ```from __future__ import division ``` ```import math ``` ```from networkx.utils import py_random_state ``` ```import networkx as nx ``` ```__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)', ``` ``` 'Pieter Swart (swart@lanl.gov)', ``` ``` 'Dan Schult (dschult@colgate.edu)', ``` ``` 'Joel Miller (joel.c.miller.research@gmail.com)', ``` ``` 'Ben Edwards']) ``` ```__all__ = ['double_edge_swap', ``` ``` 'connected_double_edge_swap'] ``` ```@py_random_state(3) ``` ```def double_edge_swap(G, nswap=1, max_tries=100, seed=None): ``` ``` """Swap two edges in the graph while keeping the node degrees fixed. ``` ``` ``` ``` A double-edge swap removes two randomly chosen edges u-v and x-y ``` ``` and creates the new edges u-x and v-y:: ``` ``` ``` ``` u--v u v ``` ``` becomes | | ``` ``` x--y x y ``` ``` ``` ``` If either the edge u-x or v-y already exist no swap is performed ``` ``` and another attempt is made to find a suitable edge pair. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : graph ``` ``` An undirected graph ``` ``` ``` ``` nswap : integer (optional, default=1) ``` ``` Number of double-edge swaps to perform ``` ``` ``` ``` max_tries : integer (optional) ``` ``` Maximum number of attempts to swap edges ``` ``` ``` ``` seed : integer, random_state, or None (default) ``` ``` Indicator of random number generation state. ``` ``` See :ref:`Randomness`. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` G : graph ``` ``` The graph after double edge swaps. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` Does not enforce any connectivity constraints. ``` ``` ``` ``` The graph G is modified in place. ``` ``` """ ``` ``` if G.is_directed(): ``` ``` raise nx.NetworkXError( ``` ``` "double_edge_swap() not defined for directed graphs.") ``` ``` if nswap > max_tries: ``` ``` raise nx.NetworkXError("Number of swaps > number of tries allowed.") ``` ``` if len(G) < 4: ``` ``` raise nx.NetworkXError("Graph has less than four nodes.") ``` ``` # Instead of choosing uniformly at random from a generated edge list, ``` ``` # this algorithm chooses nonuniformly from the set of nodes with ``` ``` # probability weighted by degree. ``` ``` n = 0 ``` ``` swapcount = 0 ``` ``` keys, degrees = zip(*G.degree()) # keys, degree ``` ``` cdf = nx.utils.cumulative_distribution(degrees) # cdf of degree ``` ``` discrete_sequence = nx.utils.discrete_sequence ``` ``` while swapcount < nswap: ``` ``` # if random.random() < 0.5: continue # trick to avoid periodicities? ``` ``` # pick two random edges without creating edge list ``` ``` # choose source node indices from discrete distribution ``` ``` (ui, xi) = discrete_sequence(2, cdistribution=cdf, seed=seed) ``` ``` if ui == xi: ``` ``` continue # same source, skip ``` ``` u = keys[ui] # convert index to label ``` ``` x = keys[xi] ``` ``` # choose target uniformly from neighbors ``` ``` v = seed.choice(list(G[u])) ``` ``` y = seed.choice(list(G[x])) ``` ``` if v == y: ``` ``` continue # same target, skip ``` ``` if (x not in G[u]) and (y not in G[v]): # don't create parallel edges ``` ``` G.add_edge(u, x) ``` ``` G.add_edge(v, y) ``` ``` G.remove_edge(u, v) ``` ``` G.remove_edge(x, y) ``` ``` swapcount += 1 ``` ``` if n >= max_tries: ``` ``` e = ('Maximum number of swap attempts (%s) exceeded ' % n + ``` ``` 'before desired swaps achieved (%s).' % nswap) ``` ``` raise nx.NetworkXAlgorithmError(e) ``` ``` n += 1 ``` ``` return G ``` ```@py_random_state(3) ``` ```def connected_double_edge_swap(G, nswap=1, _window_threshold=3, seed=None): ``` ``` """Attempts the specified number of double-edge swaps in the graph `G`. ``` ``` ``` ``` A double-edge swap removes two randomly chosen edges `(u, v)` and `(x, ``` ``` y)` and creates the new edges `(u, x)` and `(v, y)`:: ``` ``` ``` ``` u--v u v ``` ``` becomes | | ``` ``` x--y x y ``` ``` ``` ``` If either `(u, x)` or `(v, y)` already exist, then no swap is performed ``` ``` so the actual number of swapped edges is always *at most* `nswap`. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : graph ``` ``` An undirected graph ``` ``` ``` ``` nswap : integer (optional, default=1) ``` ``` Number of double-edge swaps to perform ``` ``` ``` ``` _window_threshold : integer ``` ``` ``` ``` The window size below which connectedness of the graph will be checked ``` ``` after each swap. ``` ``` ``` ``` The "window" in this function is a dynamically updated integer that ``` ``` represents the number of swap attempts to make before checking if the ``` ``` graph remains connected. It is an optimization used to decrease the ``` ``` running time of the algorithm in exchange for increased complexity of ``` ``` implementation. ``` ``` ``` ``` If the window size is below this threshold, then the algorithm checks ``` ``` after each swap if the graph remains connected by checking if there is a ``` ``` path joining the two nodes whose edge was just removed. If the window ``` ``` size is above this threshold, then the algorithm performs do all the ``` ``` swaps in the window and only then check if the graph is still connected. ``` ``` ``` ``` seed : integer, random_state, or None (default) ``` ``` Indicator of random number generation state. ``` ``` See :ref:`Randomness`. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` int ``` ``` The number of successful swaps ``` ``` ``` ``` Raises ``` ``` ------ ``` ``` ``` ``` NetworkXError ``` ``` ``` ``` If the input graph is not connected, or if the graph has fewer than four ``` ``` nodes. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` ``` ``` The initial graph `G` must be connected, and the resulting graph is ``` ``` connected. The graph `G` is modified in place. ``` ``` ``` ``` References ``` ``` ---------- ``` ``` .. [1] C. Gkantsidis and M. Mihail and E. Zegura, ``` ``` The Markov chain simulation method for generating connected ``` ``` power law random graphs, 2003. ``` ``` http://citeseer.ist.psu.edu/gkantsidis03markov.html ``` ``` """ ``` ``` if not nx.is_connected(G): ``` ``` raise nx.NetworkXError("Graph not connected") ``` ``` if len(G) < 4: ``` ``` raise nx.NetworkXError("Graph has less than four nodes.") ``` ``` n = 0 ``` ``` swapcount = 0 ``` ``` deg = G.degree() ``` ``` # Label key for nodes ``` ``` dk = list(n for n, d in G.degree()) ``` ``` cdf = nx.utils.cumulative_distribution(list(d for n, d in G.degree())) ``` ``` discrete_sequence = nx.utils.discrete_sequence ``` ``` window = 1 ``` ``` while n < nswap: ``` ``` wcount = 0 ``` ``` swapped = [] ``` ``` # If the window is small, we just check each time whether the graph is ``` ``` # connected by checking if the nodes that were just separated are still ``` ``` # connected. ``` ``` if window < _window_threshold: ``` ``` # This Boolean keeps track of whether there was a failure or not. ``` ``` fail = False ``` ``` while wcount < window and n < nswap: ``` ``` # Pick two random edges without creating the edge list. Choose ``` ``` # source nodes from the discrete degree distribution. ``` ``` (ui, xi) = discrete_sequence(2, cdistribution=cdf, seed=seed) ``` ``` # If the source nodes are the same, skip this pair. ``` ``` if ui == xi: ``` ``` continue ``` ``` # Convert an index to a node label. ``` ``` u = dk[ui] ``` ``` x = dk[xi] ``` ``` # Choose targets uniformly from neighbors. ``` ``` v = seed.choice(list(G.neighbors(u))) ``` ``` y = seed.choice(list(G.neighbors(x))) ``` ``` # If the target nodes are the same, skip this pair. ``` ``` if v == y: ``` ``` continue ``` ``` if x not in G[u] and y not in G[v]: ``` ``` G.remove_edge(u, v) ``` ``` G.remove_edge(x, y) ``` ``` G.add_edge(u, x) ``` ``` G.add_edge(v, y) ``` ``` swapped.append((u, v, x, y)) ``` ``` swapcount += 1 ``` ``` n += 1 ``` ``` # If G remains connected... ``` ``` if nx.has_path(G, u, v): ``` ``` wcount += 1 ``` ``` # Otherwise, undo the changes. ``` ``` else: ``` ``` G.add_edge(u, v) ``` ``` G.add_edge(x, y) ``` ``` G.remove_edge(u, x) ``` ``` G.remove_edge(v, y) ``` ``` swapcount -= 1 ``` ``` fail = True ``` ``` # If one of the swaps failed, reduce the window size. ``` ``` if fail: ``` ``` window = int(math.ceil(window / 2)) ``` ``` else: ``` ``` window += 1 ``` ``` # If the window is large, then there is a good chance that a bunch of ``` ``` # swaps will work. It's quicker to do all those swaps first and then ``` ``` # check if the graph remains connected. ``` ``` else: ``` ``` while wcount < window and n < nswap: ``` ``` # Pick two random edges without creating the edge list. Choose ``` ``` # source nodes from the discrete degree distribution. ``` ``` (ui, xi) = nx.utils.discrete_sequence(2, cdistribution=cdf) ``` ``` # If the source nodes are the same, skip this pair. ``` ``` if ui == xi: ``` ``` continue ``` ``` # Convert an index to a node label. ``` ``` u = dk[ui] ``` ``` x = dk[xi] ``` ``` # Choose targets uniformly from neighbors. ``` ``` v = seed.choice(list(G.neighbors(u))) ``` ``` y = seed.choice(list(G.neighbors(x))) ``` ``` # If the target nodes are the same, skip this pair. ``` ``` if v == y: ``` ``` continue ``` ``` if x not in G[u] and y not in G[v]: ``` ``` G.remove_edge(u, v) ``` ``` G.remove_edge(x, y) ``` ``` G.add_edge(u, x) ``` ``` G.add_edge(v, y) ``` ``` swapped.append((u, v, x, y)) ``` ``` swapcount += 1 ``` ``` n += 1 ``` ``` wcount += 1 ``` ``` # If the graph remains connected, increase the window size. ``` ``` if nx.is_connected(G): ``` ``` window += 1 ``` ``` # Otherwise, undo the changes from the previous window and decrease ``` ``` # the window size. ``` ``` else: ``` ``` while swapped: ``` ``` (u, v, x, y) = swapped.pop() ``` ``` G.add_edge(u, v) ``` ``` G.add_edge(x, y) ``` ``` G.remove_edge(u, x) ``` ``` G.remove_edge(v, y) ``` ``` swapcount -= 1 ``` ``` window = int(math.ceil(window / 2)) ``` ``` return swapcount ```