def __init__(self):

        self.original_dungeon = []
        self.dungeon = []
        self.size = 0
        self.LoopGraph = graph()
        self.FullGraph = graph()
        self.DistanceGraphOriginal = graph()
        self.DistanceGraph = graph()
        self.MonsterChar = "A"
        self.monster_location = '12'
        self.rogue_location = '12'
        self.is_infinitive = False
        self.all_the_moves = []

def merge_graphs(g1, g2):
    """
    Merge two graphs to a new graph (V, E) with V = g1.nodes \union g2.nodes
    and Edge e \in g1 or e \in g2 -> e \in E.
    """

    if g1.DIRECTED or g2.DIRECTED:
        g = digraph()
    else:
        g = graph()

    for n in g1.nodes():
        g.add_node(n)
    for n in g2.nodes():
        if not n in g.nodes():
            g.add_node(n)
    for e in g1.edges():
        try:
            g.add_edge(e, g1.edge_weight(e))
        except:
            logging.info("merge_graphs: adding edge %d %d failed" % (e[0], e[1]))
    for e in g2.edges():
        try:
            g.add_edge(e, g2.edge_weight(e))
        except:
            logging.info("merge_graphs: adding edge %d %d failed" % (e[0], e[1]))
    return g

def teo_1(g, k):
  if k > len(g.nodes()):
    raise ValueError('FORBIDDEN: K > |V|')
  if k <= 0:
    raise ValueError('FORBIDDEN: K <= 0')

  # Caso base
  if k == 1:
    tree = graph()
    tree.add_node(1)
    return tree

  # Hipotese indutiva
  tree = teo_1(g, k-1)

  all_nodes = g.nodes()
  used_nodes = tree.nodes()
  external_nodes = [node for node in all_nodes if node not in used_nodes]

  r = []
  for used_node in used_nodes:
    for external_node in external_nodes:
      if g.has_edge((used_node, external_node)):
        r.append((used_node, external_node))

  new_edge = max(r, key=lambda e: g.edge_weight(e))

  a, b = new_edge
  tree.add_node(b)

  tree.add_edge(new_edge)

  return tree

def build_graph():
	gr = graph()

	for i in range(1,11):
		gr.add_node(i)
		gr.add_node_attribute(i, ('level', 0) )

	gr.add_edge((1,3))
	gr.add_edge((1,4))
	gr.add_edge((2,3))
	gr.add_edge((2,5))
	gr.add_edge((5,3))
	gr.add_edge((5,6))
	gr.add_edge((6,3))
	gr.add_edge((4,6))
	gr.add_edge((6,7))
	gr.add_edge((7,8))
	gr.add_edge((7,10))
	gr.add_edge((8,9))
	gr.add_edge((9,10))

	#gr.add_edge((2,8))

	gr.add_node_attribute(3, ('in', 10))

	return gr

 def drawGraph(self, inputs):
     
     fileName = 'planetModel.png'
     gr = graph()
     self.addGraphNode(1,gr, inputs)
 # Draw as PNG
     #with open("./planetModel.viz", 'wb') as f:
         #dot = write(gr,f)
         #f.write(dot)
         #gvv = gv.readstring(dot)
         #gv.layout(gvv,'dot')
         #gv.render(gvv,'png', fileName)
         #f.close()
         
     gst = digraph()
     self.addGraphNode(1,gst, inputs)            
     with open("./planetModel.viz", 'wb') as f:            
         #st, order = breadth_first_search(gst, root=1)
         #gst2 = digraph()
         #gst2.add_spanning_tree(gst.nodes())
         #gst2.(1, 'post')
         dot = write(gst,f)
         f.write(dot)
         gvv = gv.readstring(dot)
         gv.layout(gvv,'dot')
         gv.render(gvv,'png', fileName)   
         f.close()         
         
         
          
     return fileName

 def __init__(self):
     """
     Initialize a hypergraph.
     """
     self.node_links = {}    # Pairing: Node -> Hyperedge
     self.edge_links = {}     # Pairing: Hyperedge -> Node
     self.graph = graph()    # Ordinary graph

def import_network_erl(data_file,eps):
    gr = graph()
    
    with open(data_file) as f:
        line = f.readline()
        while line != '':
            
            if not coin(eps): 
                line = f.readline()
                continue

            link = line.split('"')
            #print link
            #_ = raw_input()
            n1 = link[1]
            n2 = link[3]
            #print n1,n2
            if not gr.has_node(n1): 
                gr.add_node(n1)
                gr.add_node_attribute(n1, ('col', n1))
            if not gr.has_node(n2): 
                gr.add_node(n2)
                gr.add_node_attribute(n2, ('col', n2))

            if not gr.has_edge((n1,n2)): 
                gr.add_edge((n1,n2))
            #s = raw_input()
            line = f.readline()

    f.close()
    print "Graph has %i nodes and %i edges\n" % (len(gr.nodes()), len(gr.edges()) )
    return gr

def make_graph(data):
    gr = graph()

    with open(data) as f:
        line = f.readline()
        while line != '':
            link = line.split()
            n1 = int(link[0])
            n2 = int(link[1])
            #print n1,n2
            if not gr.has_node(n1): 
                gr.add_node(n1)
                gr.add_node_attribute(n1, ('col', n1))
            if not gr.has_node(n2): 
                gr.add_node(n2)
                gr.add_node_attribute(n2, ('col', n2))

            if not gr.has_edge((n1,n2)): 
                gr.add_edge((n1,n2))
            #s = raw_input()
            line = f.readline()
    f.close()
    print "Graph has %i nodes and %i edges\n" % (len(gr.nodes()), len(gr.edges()) ) 

    return gr

    def getSSAroundSS(self, solarSystemID, jumps):
        ss = self.getSSInfo(solarSystemID)

        color = 0
        if ss[2] > 0.5:
            color = "green"
        else:
            color = "red"

        ssRegion = colored(ss[0], color)
        ssName = colored(ss[1], color)
        ssSecruity = colored("%.1f" % ss[2], color)

        if self.ssgraph:
            gr = self.ssgraph
        else:
            gr = graph()
            nodes = self.getAllSS()
            gr.add_nodes(nodes)
            for edge in self.getAllSSEdges():
                gr.add_edge(edge)

        print "Searching for Solar Systems around %s: %s(%s) in %d jumps." % (ssRegion, ssName, ssSecruity, jumps)

        ssinrad = breadth_first_search(gr, solarSystemID, radius(jumps))
        ssinrad = ssinrad[1]

        text = "Found %d systems" % len(ssinrad)
        text = colored(text, "cyan")
        print "Done. %s, including current one." % text

        return ssinrad

 def test_graph_equality_attributes(self):
     """
     Graph equality test. This one checks node equality. 
     """
     gr = graph()
     gr.add_nodes([0,1,2])
     gr.add_edge((0,1))
     gr.add_node_attribute(1, ('a','x'))
     gr.add_node_attribute(2, ('b','y'))
     gr.add_edge_attribute((0,1), ('c','z'))
     
     gr2 = deepcopy(gr)
     
     gr3 = deepcopy(gr)
     gr3.del_edge((0,1))
     gr3.add_edge((0,1))
     
     gr4 = deepcopy(gr)
     gr4.del_edge((0,1))
     gr4.add_edge((0,1))
     gr4.add_edge_attribute((0,1), ('d','k'))
     
     gr5 = deepcopy(gr)
     gr5.del_node(2)
     gr5.add_node(2)
     gr5.add_node_attribute(0, ('d','k'))
     
     assert gr == gr2
     assert gr2 == gr
     assert gr != gr3
     assert gr3 != gr
     assert gr != gr4
     assert gr4 != gr
     assert gr != gr5
     assert gr5 != gr

def drawGraphFromSM(SM, names, outFile):
	fig = plt.figure(1)
	plot1 = plt.imshow(SM, origin='upper', cmap=cm.gray, interpolation='nearest')
	plt.show()
		
	gr = graph()

	namesNew = []
	for i,f in enumerate(names):	
		if sum(SM[i,:])>0:
			gr.add_nodes([f])
			namesNew.append(f)
			
	Max = SM.max()
	Mean = mean(SM)

	Threshold = Mean * 1.5
	for i in range(len(names)):
		for j in range(len(names)):
			if i<j:
				if SM[i][j] > 0:
					gr.add_edge((names[i], names[j]))
	# Draw as PNG
	dot = write(gr)
	gvv = gv.readstring(dot)
	gv.layout(gvv,'dot')
	gv.render(gvv,'png', outFile)

 def test_complete_graph(self):
     gr = graph()
     gr.add_nodes(xrange(10))
     gr.complete()
     for i in xrange(10):
         for j in range(10):
             self.assertTrue((i, j) in gr.edges() or i == j)

def create_graph():
    g = graph()
    g.add_node("1")
    g.add_node("2")
    g.add_node("3")
    g.add_node("4")
    g.add_node("5")
    g.add_node("6")
    g.add_node("7")
    g.add_node("8")
    g.add_node("9")

    g.add_edge(("1", "2"))
    g.add_edge(("1", "4"))
    g.add_edge(("1", "5"))
    g.add_edge(("2", "3"))
    g.add_edge(("2", "4"))
    g.add_edge(("2", "5"))
    g.add_edge(("2", "6"))
    g.add_edge(("3", "5"))
    g.add_edge(("3", "6"))
    g.add_edge(("4", "5"))
    g.add_edge(("4", "7"))
    g.add_edge(("4", "8"))
    g.add_edge(("5", "6"))
    g.add_edge(("5", "7"))
    g.add_edge(("5", "8"))
    g.add_edge(("5", "9"))
    g.add_edge(("6", "8"))
    g.add_edge(("6", "9"))
    g.add_edge(("7", "8"))
    g.add_edge(("8", "9"))
    return g

 def __init__(self):
     # graph that holds the street network
     self._graph = graph()
     self.bounds = None
     # give every street a sequential index (used for perfomance optimization)
     self.street_index = 0
     self.streets_by_index = dict()

    def __init__(self, point_free_cb, line_free_cb, dimensions):
        """
        Construct a randomized roadmap planner.

        'point_free_cb' is a function that accepts a point (two-tuple) and
        outputs a boolean value indicating whether the point is in free space.

        'line_free_cb' is a function that accepts two points (the start and the
        end of a line segment) and outputs a boolen value indicating whether
        the line segment is free from obstacles.

        'dimensions' is a tuple of tuples that define the x and y dimensions of
        the world, e.g. ((-8, 8), (-8, 8)). It should be used when generating
        random points.
        """
        self.point_free_cb = point_free_cb
        self.line_free_cb = line_free_cb
        self.dimensions = dimensions

        self.search_algorithm = euclidean()
        self.number_of_trials = 500
        self.search_result = False
        self.output_path = None
        self.id_generator = 10000
        self.graph = graph()

 def test_add_spanning_tree(self):
     gr = graph()
     st = {0: None, 1: 0, 2:0, 3: 1, 4: 2, 5: 3}
     gr.add_spanning_tree(st)
     for each in st:
         self.assertTrue((each, st[each]) in gr.edges() or (each, st[each]) == (0, None))
         self.assertTrue((st[each], each) in gr.edges() or (each, st[each]) == (0, None))

 def _update_hyki_graph(self):
     import re
     from pygraph.classes.graph import graph
     pattern = re.compile(LINK_RE)
     articles = HykiArticle.objects.all()
     gr = graph()
     if len(articles) > 0:
         for article in articles:
             if article.id not in gr.nodes():
                 self.create_node(gr, article)
             article_text = self._get_revision_text(article)
             results = pattern.findall(article_text)
             for link in results:
                 _source = link[7].split('/')[1]
                 _link = link[7].split('/')[2]
                 if _source == 'hyki':
                     #adjacency article links
                     for _article in articles:
                         #match link with article
                         if _article.slug == _link:
                             #doesnt point to itself
                             if _article != article:
                                 #target node doesn't exist yet
                                 if _article.id not in gr.nodes():
                                     self.create_node(gr, _article)
                                     gr.add_edge((article.id, _article.id))
                                 else:
                                     if not gr.has_edge((_article.id,article.id)):
                                         gr.add_edge((article.id, _article.id))
         self.graph_info = self.format_graph_to_thejit_tree(gr)
     else:
         self.graph_info = False

def plot_graph(gr):
    """
    draws the graph to file
    """
    p = 100.0 / (len(gr.nodes())+1)
    gr_ext = graph()

    
    for node in gr.nodes():
        if coin(p):
            if not gr_ext.has_node(node):
                gr_ext.add_node(node,attrs=gr.node_attributes(node))
            for n in [ ed[0] for ed in gr.edges() if ed[1] == node ]:
                if coin(0.3):
                    if not gr_ext.has_node(n):
                        gr_ext.add_node(n,attrs=gr.node_attributes(n))
                    #print "Edges:",gr_ext.edges()
                    if not gr_ext.has_edge((node,n)):
                        gr_ext.add_edge((node,n)) 
    dot = write(gr_ext)
    gvv = gv.readstring(dot)
    gv.layout(gvv,'dot')    
    if args[1]== 'karate.txt':
        gv.render(gvv,'png','community1.png') 
    elif args[1] == 'email.txt':
        gv.render(gvv,'png','community2.png')
    elif args[1] == 'hep-th-citations.txt':
        gv.render(gvv,'png','community3.png')
    elif args[1] == 'amazon1.txt':
        gv.render(gvv,'png','community4.png')
    elif args[1] == 'p2p-Gnutella30.txt':
        gv.render(gvv,'png','community5.png')

 def test_graph_equality_labels(self):
     """
     Graph equality test. This one checks node equality. 
     """
     gr = graph()
     gr.add_nodes([0,1,2])
     gr.add_edge((0,1), label="l1")
     gr.add_edge((1,2), label="l2")
     
     gr2 = deepcopy(gr)
     
     gr3 = deepcopy(gr)
     gr3.del_edge((0,1))
     gr3.add_edge((0,1))
     
     gr4 = deepcopy(gr)
     gr4.del_edge((0,1))
     gr4.add_edge((0,1), label="l3")
          
     assert gr == gr2
     assert gr2 == gr
     assert gr != gr3
     assert gr3 != gr
     assert gr != gr4
     assert gr4 != gr

 def calGraph(self):
     grafo = graph()
     for item in self.items:
         grafo.add_node(item, attrs = [("splines",  "")])
     for key, stream in self.streams.iteritems():
         grafo.add_edge((stream[0], stream[1]), attrs = [("splines",  "")])
     return grafo