"""
Markov Graph Generation
"""
__author__ = 'Brian Cloteaux (brian.cloteaux@nist.gov)'

# Mathematical and Computational Sciences Division
# National Institute of Standards and Technology,
# Gaithersburg, MD USA
#
# This software was developed at the National Institute of Standards and
# Technology (NIST) by employees of the Federal Government in the course
# of their official duties. Pursuant to title 17 Section 105 of the
# United States Code, this software is not subject to copyright protection
# and is in the public domain. NIST assumes no responsibility whatsoever for
# its use by other parties, and makes no guarantees, expressed or implied,
# about its quality, reliability, or any other characteristic.

import networkx as nx

def markov_random_graph(deg_sequence, swaps=None, create_using=None, name=None):
    """ 
    Returns a random graph with the given degree sequence.

    Notes
    -----
    The randomization aspect of this algorithm is a simple Markov chain walk.
    The state transition uses a double-edge swap where the two randomly
    chosen edges (u,v) and (x,y) are removed and replace with the edges
    (u,x) and (v,y). 
    """ 

    graph = nx.havel_hakimi_graph(deg_sequence, create_using)
    if name is not None:
        graph.name = name
    if swaps is not None:
        numIter = swaps
    else:
        numIter = 3 * nx.number_of_edges(graph)
    for i in xrange(numIter):
        nx.double_edge_swap(graph)
    return graph

def connected_markov_random_graph(deg_sequence, swaps=None, create_using=None,
        name=None):
    """ 
    Returns a connected random graph with the given degree sequence.

    Notes
    -----
    This algorithm is based on Gkantsidis, Mihail, and Zegura [1]_.

    References
    ----------
    ..[1] C. Gkantsidis, M. Mihail, and E. W. Zegura, "The Markov Chain
        Simulation Method for Generating Connected Power Law Random Graphs,"
        in ALENEX, 2003, pp. 16-25.
        http://www.siam.org/meetings/alenex03/Abstracts/CGkantsidis.pdf
    """ 

    nodes = len(deg_sequence)
    if sum(deg_sequence) < 2 * (nodes-1):
        raise nx.NetworkXError(
                'Degree sequence is not connectable.')

    graph = nx.havel_hakimi_graph(deg_sequence, create_using)
    graph = component_merge(graph)

    if name is not None:
        graph.name = name
    if swaps is not None:
        numIter = swaps
    else:
        numIter = 3 * nx.number_of_edges(graph)
    for i in xrange(numIter):
        nx.connected_double_edge_swap(graph)
    return graph


def component_merge(graph):
    """ 
    Merges the components in a graph to form a connected graph with
    identical degree sequence.

    Notes
    -----
    The algorithm is based on Gkantsidis, Mihail, and Zegura [1]_.

    References
    ----------
    ..[1] C. Gkantsidis, M. Mihail, and E. W. Zegura, "The Markov Chain
        Simulation Method for Generating Connected Power Law Random Graphs,"
        in ALENEX, 2003, pp. 16-25.
        http://www.siam.org/meetings/alenex03/Abstracts/CGkantsidis.pdf
    """ 

    gr = None
    if nx.number_of_edges(graph) >= nx.number_of_nodes(graph)-1: 
        # Find the components of the graph and sort based on number of excess 
        # edges
        comps = nx.connected_component_subgraphs(graph)
        comps.sort(key=lambda comp:
                nx.number_of_nodes(comp)-nx.number_of_edges(comp))

        # Merge the components 
        gr = comps[0]
        for i in xrange(1,len(comps)):
            cycles = nx.cycle_basis(gr)
            cycle = cycles[0]
            u = cycle[0]
            v = cycle[1]
            x, y = (comps[i].edges())[0]
            gr = nx.union(gr,comps[i])
            gr.remove_edge(u,v)
            gr.remove_edge(x,y)
            gr.add_edge(u,x)
            gr.add_edge(v,y)
    return gr