def test_cartesian_product_classic():
    # test some classic product graphs
    P2 = nx.path_graph(2)
    P3 = nx.path_graph(3)
    # cube = 2-path X 2-path
    G=cartesian_product(P2,P2)
    G=cartesian_product(P2,G)
    assert_true(nx.is_isomorphic(G,nx.cubical_graph()))

    # 3x3 grid
    G=cartesian_product(P3,P3)
    assert_true(nx.is_isomorphic(G,nx.grid_2d_graph(3,3)))

def test_cartesian_product_size():
    # order(GXH)=order(G)*order(H)
    K5=nx.complete_graph(5)
    P5=nx.path_graph(5)
    K3=nx.complete_graph(3)
    G=cartesian_product(P5,K3)
    assert_equal(nx.number_of_nodes(G),5*3)
    assert_equal(nx.number_of_edges(G),
                 nx.number_of_edges(P5)*nx.number_of_nodes(K3)+
                 nx.number_of_edges(K3)*nx.number_of_nodes(P5))
    G=cartesian_product(K3,K5)
    assert_equal(nx.number_of_nodes(G),3*5)
    assert_equal(nx.number_of_edges(G),
                 nx.number_of_edges(K5)*nx.number_of_nodes(K3)+
                 nx.number_of_edges(K3)*nx.number_of_nodes(K5))

def __test_cartesian_try_01__():

   # You'll also find a product-type fcn. in networkx.

   dir_graph, node_first, node_final = __test_get_graph_01__()

   graphed = networkx.cartesian_product(dir_graph, dir_graph)
   log.debug('test_cartesian:  once: cnt. graphed.nodes: %d' % (len(graphed),))

   graphed = networkx.cartesian_product(dir_graph, graphed)
   log.debug('test_cartesian: twice: cnt. graphed.nodes: %d' % (len(graphed),))

   graphed = networkx.cartesian_product(dir_graph, graphed)
   log.debug('test_cartesian: thrice: cnt graphed.nodes: %d' % (len(graphed),))

   graphed = networkx.cartesian_product(dir_graph, graphed)
   log.debug('test_cartesian: fource: cnt graphed.nodes: %d' % (len(graphed),))

	def __init__(self,L):
		#compute vertices, edges and faces
		torus = nx.cartesian_product(nx.generators.classic.cycle_graph(L), nx.generators.classic.cycle_graph(L))
		rlabels = dict(enumerate(torus.nodes()))
		labels = dict(zip(rlabels.values(),rlabels.keys()))
		torus = nx.relabel_nodes(torus,labels)
		faces = [ [[labels[v,u], labels[(v+1)%L,u]], [labels[v,u], labels[v,(u+1)%L]], [labels[(v+1)%L,u], labels[(v+1)%L,(u+1)%L]], [labels[v,(u+1)%L], labels[(v+1)%L,(u+1)%L]]] for v in range(L) for u in range(L) ]
		#initialize TwoComplex
		super(ToricLattice,self).__init__(torus.nodes(),torus.edges(),faces,L)

def test_cartesian_product_random():
    G = nx.erdos_renyi_graph(10,2/10.)
    H = nx.erdos_renyi_graph(10,2/10.)
    GH = cartesian_product(G,H)

    for (u_G,u_H) in GH.nodes_iter():
        for (v_G,v_H) in GH.nodes_iter():
            if (u_G==v_G and H.has_edge(u_H,v_H)) or \
               (u_H==v_H and G.has_edge(u_G,v_G)):
                assert_true(GH.has_edge((u_G,u_H),(v_G,v_H)))
            else:
                assert_true(not GH.has_edge((u_G,u_H),(v_G,v_H)))

def test_cartesian_product_multigraph():
    G=nx.MultiGraph()
    G.add_edge(1,2,key=0)
    G.add_edge(1,2,key=1)
    H=nx.MultiGraph()
    H.add_edge(3,4,key=0)
    H.add_edge(3,4,key=1)
    GH=cartesian_product(G,H)
    assert_equal( set(GH) , set([(1, 3), (2, 3), (2, 4), (1, 4)]))
    assert_equal( set(GH.edges(keys=True)) ,
                  set([((1, 3), (2, 3), 0), ((1, 3), (2, 3), 1), 
                       ((1, 3), (1, 4), 0), ((1, 3), (1, 4), 1), 
                       ((2, 3), (2, 4), 0), ((2, 3), (2, 4), 1), 
                       ((2, 4), (1, 4), 0), ((2, 4), (1, 4), 1)]))    

def test_cartesian_product_multigraph():
    G = nx.MultiGraph()
    G.add_edge(1, 2, key=0)
    G.add_edge(1, 2, key=1)
    H = nx.MultiGraph()
    H.add_edge(3, 4, key=0)
    H.add_edge(3, 4, key=1)
    GH = cartesian_product(G, H)
    assert_equal(set(GH), {(1, 3), (2, 3), (2, 4), (1, 4)})
    assert_equal({(frozenset([u, v]), k) for u, v, k in GH.edges(keys=True)},
                 {(frozenset([u, v]), k) for u, v, k in
                  [((1, 3), (2, 3), 0), ((1, 3), (2, 3), 1),
                   ((1, 3), (1, 4), 0), ((1, 3), (1, 4), 1),
                   ((2, 3), (2, 4), 0), ((2, 3), (2, 4), 1),
                   ((2, 4), (1, 4), 0), ((2, 4), (1, 4), 1)]})

def random_walk_kernel(g1, g2, parameter_lambda, node_attribute="label"):
    """ Compute the random walk kernel of two graphs as described by Neuhaus
        and Bunke in the chapter 5.9 of "Bridging the Gap Between Graph Edit
        Distance and Kernel Machines (2007)"
    """
    p = nx.cartesian_product(g1, g2)
    M = nx.attr_sparse_matrix(p, node_attr=node_attribute)
    A = M[0]
    L = A.shape[0]
    k = 0
    A_exp = A
    for n in xrange(L):
        k += (parameter_lambda ** n) * long(A_exp.sum())
        if n < L:
            A_exp = A_exp * A

    return k

def grid_graph(dim, periodic=False, create_using=None):
    """ Return the n-dimensional grid graph.

    The dimension is the length of the list 'dim' and the
    size in each dimension is the value of the list element.

    E.g. G=grid_graph(dim=[2,3]) produces a 2x3 grid graph.

    If periodic=True then join grid edges with periodic boundary conditions.

    """
    from networkx.utils import is_list_of_ints

    if create_using is not None and create_using.is_directed():
        raise nx.NetworkXError("Directed Graph not supported")
    dlabel = "%s" % dim
    if dim == []:
        G = empty_graph(0, create_using)
        G.name = "grid_graph(%s)" % dim
        return G
    if not is_list_of_ints(dim):
        raise nx.NetworkXError("dim is not a list of integers")
    if min(dim) <= 0:
        raise nx.NetworkXError("dim is not a list of strictly positive integers")
    if periodic:
        func = cycle_graph
    else:
        func = path_graph

    current_dim = dim.pop()
    G = func(current_dim, create_using)
    while len(dim) > 0:
        current_dim = dim.pop()
        # order matters: copy before it is cleared during the creation of Gnew
        Gold = G.copy()
        Gnew = func(current_dim, create_using)
        # explicit: create_using=None
        # This is so that we get a new graph of Gnew's class.
        G = nx.cartesian_product(Gnew, Gold, create_using=None)
    # graph G is done but has labels of the form (1,(2,(3,1)))
    # so relabel
    H = nx.relabel_nodes(G, utils.flatten)
    H.name = "grid_graph(%s)" % dlabel
    return H

def generate_product_graph():
    """Generates k cuts for cartesian product of a path and a double tree"""
    k = int(input("k for product of tree & path:"))
    trials = int(input("number of trials:"))
    prodfname = input("output file:")
    prodfname = "hard_instances/" + prodfname
    prodfile = open(prodfname, "wb", 0)
    h = int(input("height of the tree: "))
    H1 = nx.balanced_tree(2, h)
    H2 = nx.balanced_tree(2, h)
    H = nx.disjoint_union(H1, H2)
    n = H.number_of_nodes()
    p = math.pow(2, h + 1) - 1
    H.add_edge(0, p)
    n = 4 * math.sqrt(n)
    n = math.floor(n)
    print("Length of path graph: " + str(n))
    G = nx.path_graph(n)
    tmpL = nx.normalized_laplacian_matrix(G).toarray()
    T = nx.cartesian_product(G, H)
    A = nx.adjacency_matrix(T).toarray()
    L = nx.normalized_laplacian_matrix(T).toarray()
    (tmpw, tmpv) = la.eigh(L)
    tmp = 2 * math.sqrt(tmpw[1])
    print("cheeger upperbound:" + str(tmp))
    (w, v) = spectral_projection(L, k)
    lambda_k = w[k - 1]
    tmp_str = "Cartesian product of balanced tree of height " + str(h)
    tmp_str += " and path of length " + str(n - 1) + "\n"
    tmp_str += "k = " + str(k) + ", "
    tmp_str += "trials = " + str(trials) + "\n\n\n"
    tmp_str = tmp_str.encode("utf-8")
    prodfile.write(tmp_str)
    k_cuts_list = lrtv(A, v, k, lambda_k, trials, prodfile)
    plotname = prodfname + "plot"
    plot(k_cuts_list, plotname)
    for i in range(len(k_cuts_list)):
        k_cuts = k_cuts_list[i]
        tmp_str = list(map(str, k_cuts))
        tmp_str = " ".join(tmp_str)
        tmp_str += "\n\n"
        tmp_str = tmp_str.encode("utf-8")
        prodfile.write(tmp_str)

def grid_graph(dim, periodic=False):
    """ Return the n-dimensional grid graph.

    'dim' is a list with the size in each dimension or an
    iterable of nodes for each dimension. The dimension of
    the grid_graph is the length of the list 'dim'.

    E.g. G=grid_graph(dim=[2, 3]) produces a 2x3 grid graph.

    E.g. G=grid_graph(dim=[range(7, 9), range(3, 6)]) produces a 2x3 grid graph.

    If periodic=True then join grid edges with periodic boundary conditions.

    """
    dlabel = "%s" % dim
    if dim == []:
        G = empty_graph(0)
        G.name = "grid_graph(%s)" % dim
        return G
    if periodic:
        func = cycle_graph
    else:
        func = path_graph

    dim = list(dim)
    current_dim = dim.pop()
    G = func(current_dim)
    while len(dim) > 0:
        current_dim = dim.pop()
        # order matters: copy before it is cleared during the creation of Gnew
        Gold = G.copy()
        Gnew = func(current_dim)
        # explicit: create_using=None
        # This is so that we get a new graph of Gnew's class.
        G = nx.cartesian_product(Gnew, Gold)
    # graph G is done but has labels of the form (1, (2, (3, 1)))
    # so relabel
    H = nx.relabel_nodes(G, flatten)
    H.name = "grid_graph(%s)" % dlabel
    return H

def test_cartesian_product_null():
    null=nx.null_graph()
    empty10=nx.empty_graph(10)
    K3=nx.complete_graph(3)
    K10=nx.complete_graph(10)
    P3=nx.path_graph(3)
    P10=nx.path_graph(10)
    # null graph
    G=cartesian_product(null,null)
    assert_true(nx.is_isomorphic(G,null))
    # null_graph X anything = null_graph and v.v.
    G=cartesian_product(null,empty10)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(null,K3)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(null,K10)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(null,P3)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(null,P10)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(empty10,null)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(K3,null)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(K10,null)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(P3,null)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(P10,null)
    assert_true(nx.is_isomorphic(G,null))

def test_cartesian_product_raises():
    P = cartesian_product(nx.DiGraph(), nx.Graph())

""" Union disjointe de graphes """
#Change les labels en entiers
GH1=nx.disjoint_union(G,H)
GH1.nodes()
GH1.edges()

""" Composition de graphes """
GH2=nx.compose(G,H)
GH2.nodes()
#['a', 1, 'c', 'b', 4, 'd', 2, 3]
GH2.edges()
#[('a', 'b'), (1, 2), ('c', 'b'), ('c', 'd'), (4, 3), (2, 3)]

""" Produit cartesien """
GH3=nx.cartesian_product(G,H)
GH3.nodes()
#[(1, 'c'), (3, 'c'), (1, 'b'), (3, 'b'), (2, 'a'), (3, 'a'), (4, 'd'), (1, 'd'), (2, 'b'), (4, 'b'), (2, 'c'), (4, 'c'), (1, 'a'), (4, 'a'), (2, 'd'), (3, 'd')]
GH3.edges()
#[((1, 'c'), (1, 'd')), ((1, 'c'), (1, 'b')), ((1, 'c'), (2, 'c')), ((3, 'c'), (4, 'c')), ((3, 'c'), (2, 'c')), ((3, 'c'), (3, 'b')), ((3, 'c'), (3, 'd')), ((1,'b'), (1, 'a')), ((1, 'b'), (2, 'b')), ((3, 'b'), (3, 'a')), ((3, 'b'), (2, 'b')), ((3, 'b'), (4, 'b')), ((2, 'a'), (3, 'a')), ((2, 'a'), (1, 'a')), ((2, 'a'),(2, 'b')), ((3, 'a'), (4, 'a')), ((4, 'd'), (4, 'c')), ((4, 'd'), (3, 'd')), ((1, 'd'), (2, 'd')), ((2, 'b'), (2, 'c')), ((4, 'b'), (4, 'c')), ((4, 'b'), (4, 'a')), ((2, 'c'), (2, 'd')), ((2, 'd'), (3, 'd'))]

""" Complement """
#Graphe complementaire
G1=nx.complement(G)
G1.nodes()
G1.edges()

""" Intersection de graphes """
# Les noeuds de H et G doivent etre les memes
H.clear()
H.add_nodes_from([1,2,3,4])

'''
Theorem 3 of

Mahadevan, S., & Maggioni, M. (2007). Proto-value functions: A Laplacian
framework for learning representation and control in Markov decision
processes. Journal of Machine Learning Research, 8

states that the eigenvalues of the Laplacian of graph G that is the cartesian
product of two graphs G1 and G2, are the sums of all the combination of the
eigenvalues of G1 and G2.

This program illustrates this by generating a grid as the cartesian product of
two paths.
'''

from itertools import product
import networkx as nx

n = 5
P = nx.path_graph(n)
G = nx.cartesian_product(P, P)

ev_P = nx.laplacian_spectrum(P)
ev_G = nx.laplacian_spectrum(G).real

ev = []
for i,j in product(range(n), repeat=2):
    ev.append(ev_P[i] + ev_P[j])

    return kovalev_code(G, G)

if __name__ == "__main__":
    pl.close("all")
    d = 7

    # gridded torus
    pl.figure()
    pl.title("%i-by-%i regular paving of the torus" % (d, d))
    nx.draw_graphviz(tanner_graph(tanner_cartesian_power(tanner_cycle(d), 2)),
                     node_size=30, with_labels=False)

    # Tillich-Zemor hypergraph-product constructions
    s1 = s2 = tanner_cycle(d)
    s = tanner_cartesian_product(s1, s2, split=True)
    t = nx.cartesian_product(tanner_graph(s1), tanner_graph(s2))
    pl.figure()
    pl.suptitle("Sum decomposition of Tanner graph products")
    for j, support in enumerate([s1, s2]):
        ax = pl.subplot("32%i" % (j + 1))
        ax.set_title("t%i = tanner(%s)" % (j + 1, support))
        tj = tanner_graph(support)
        nx.draw_graphviz(tj, with_labels=0, node_size=30)
    ax = pl.subplot("312")
    ax.set_title("t1 x t2 =: t =: t1' + t2'")
    nx.draw_graphviz(t, with_labels=0, node_size=30)
    for j, sj in enumerate(s):
        ax = pl.subplot("32%i" % (4 + j + 1))
        ax.set_title("t%i'" % (j + 1))
        tj = tanner_graph(sj)
        nx.draw_graphviz(tj, with_labels=0, node_size=30)