from collections import defaultdict, namedtuple
from utils.GraphDrawer import draw_graph
import numpy as np
Edge = namedtuple('Edge', 'weight, demand, distance')

Inf = np.Inf


class Graph(object):
	""" Graph data structure, undirected by default. """

	def __init__(self, CARP_data, directed=False):
		self.graph = defaultdict(set)
		self._directed = directed
		# self.add_connections(connections)
		self.node_number = int(CARP_data.specification.get('VERTICES'))
		self.edge_dict = dict()

		self.weight_dict = dict()
		self.distance_dict = dict()
		# self.path_map = np.zeros((self.node_number, self.node_number), dtype=np.int16)
		self.demand_dict = dict()
		self.connections = list()
		self.generator(CARP_data)

	def generator(self, CARP_data):
		""" Generate a graph with a CARP_data object """

		for i in CARP_data.data:
			tempt = tuple(i[0:2])
			self.connections.append(tempt)
			self.edge_dict[tempt] = Edge(i[2], i[3], i[2])
			self.weight_dict[tempt] = i[2]
			self.distance_dict[tempt] = i[2]
			self.demand_dict[tempt] = i[3]
		self.add_connections()

	def add_connections(self):
		""" Add connections (list of tuple pairs) to graph """

		for node1, node2 in self.connections:
			self.add(node1, node2)

	def add(self, node1, node2):
		""" Add connection between node1 and node2 """

		self.graph[node1].add(node2)
		if not self._directed:
			self.graph[node2].add(node1)

	def remove(self, node):
		""" Remove all references to node """

		for n, cxns in self.graph.iteritems():
			try:
				cxns.remove(node)
			except KeyError:
				pass
		try:
			del self.graph[node]
		except KeyError:
			pass

	def is_connected(self, node1, node2):
		""" Is node1 directly connected to node2 """

		return node1 in self.graph and node2 in self.graph[node1]

	def get_weight(self, node1, node2):
		""" Get the weight between two connected nodes """

		assert self.is_connected(node1, node2)
		tempt = (node1, node2) if node1 < node2 else (node2, node1)
		print('get_weight:', self.weight_dict[tempt] == getattr(self.edge_dict[tempt], 'weight'))
		return self.weight_dict[tempt]

	def set_distance(self, node1, node2, dis):
		""" Set the distance between two nodes """

		tempt = (node1, node2) if node1 < node2 else (node2, node1)
		is_edge = self.edge_dict.keys().__contains__(tempt)
		temp_demand = 0
		temp_weight = 0
		if is_edge:
			temp_weight = getattr(self.edge_dict[tempt], 'weight')
			temp_demand = getattr(self.edge_dict[tempt], 'demand')
		self.edge_dict[tempt] = Edge(temp_weight, temp_demand, dis)
		self.distance_dict[tempt] = dis

	def get_distance(self, node1, node2):
		""" Get the distance between two nodes """

		if node1 == node2:
			return 0
		tempt = (node1, node2) if node1 < node2 else (node2, node1)
		# if self.distance_dict.get(tempt) is None:
		if not self.edge_dict.keys().__contains__(tempt):
			return Inf
		print(tempt)
		print(getattr(self.edge_dict[tempt], 'distance'))
		print(self.distance_dict[tempt])
		# print('get_distance:', self.weight_dict[tempt] == getattr(self.edge_dict[tempt], 'distance'))
		return self.distance_dict[tempt]

	def get_distances(self, node):
		distances_list = list()
		for dest in self.graph:
			distances_list.append('{}->{}:{}'.format(node, dest, self.get_distance(node, dest)))
		return distances_list

	def floyd(self):
		for i in self.graph:
			for j in self.graph:
				for k in self.graph:
					tempt = self.get_distance(i, k) + self.get_distance(k, j)
					if self.get_distance(i, j) > tempt:
						self.set_distance(i, j, tempt)

	def find_path(self, node1, node2, path=[], cost=0):
		""" Find any path between node1 and node2 (may not be shortest) """

		path = path + [node1]
		# print(path)
		if node1 == node2:
			return path, cost
		if node1 not in self.graph:
			return None, cost
		for node in self.graph[node1]:
			tempt_cost = cost
			tempt_cost += self.get_weight(node, node1)
			if node not in path:
				new_path = self.find_path(node, node2, path, tempt_cost)
				if new_path[0] is not None:
					# print(new_path)
					return new_path, cost
		return None, cost
	#
	# def find_path(self, node1, node2, path=[]):
	# 	""" Find any path between node1 and node2 (may not be shortest) """
	#
	# 	path = path + [node1]
	# 	if node1 == node2:
	# 		return path
	# 	if node1 not in self.graph:
	# 		return None
	# 	for node in self.graph[node1]:
	# 		if node not in path:
	# 			new_path = self.find_path(node, node2, path)
	# 			if new_path:
	# 				return new_path
	# 	return None

	def find_all_path(self, node1, node2, path=list()):
		""" Find all the paths between node1 and node2 """

		path_list = list()
		cost_list = list()
		path = path + [node1]
		if node1 == node2:
			return path
		if node1 not in self.graph:
			return None
		for node in self.graph[node1]:
			if node not in path:
				new_path = self.find_path(node, node2, path)
				if new_path:
					path_list.append(new_path)
		return path_list

	@staticmethod
	def draw(CARP_data):
		edges = list()
		[edges.append(x[:3]) for x in CARP_data.data]
		draw_graph(edges)
		pass

	def __str__(self):
		return '{}({})'.format(self.__class__.__name__, dict(self.graph))\
		       + '\n{}({})'.format('Weight', dict(self.weight_dict)) \
		       + '\n{}({})'.format('Demand', dict(self.demand_dict)) \
		       + '\n{}({})'.format('Distance', dict(self.distance_dict)) \
		       + '\n{}({})'.format('Total', dict(self.edge_dict))

from collections import defaultdict, namedtuple
from utils.GraphDrawer import draw_graph
import numpy as np
Edge = namedtuple('Edge', 'weight, demand, distance')

Inf = np.Inf


class Graph(object):
	""" Graph data structure, undirected by default. """

	def __init__(self, CARP_data, directed=False):
		self.graph = defaultdict(set)
		self._directed = directed
		# self.add_connections(connections)
		self.node_number = int(CARP_data.specification.get('VERTICES'))
		self.edge_dict = dict()

		self.weight_dict = dict()
		self.distance_dict = dict()
		# self.path_map = np.zeros((self.node_number, self.node_number), dtype=np.int16)
		self.demand_dict = dict()
		self.connections = list()
		self.generator(CARP_data)

	def generator(self, CARP_data):
		""" Generate a graph with a CARP_data object """

		for i in CARP_data.data:
			tempt = tuple(i[0:2])
			self.connections.append(tempt)
			self.edge_dict[tempt] = Edge(i[2], i[3], i[2])
			self.weight_dict[tempt] = i[2]
			self.distance_dict[tempt] = i[2]
			self.demand_dict[tempt] = i[3]
		self.add_connections()

	def add_connections(self):
		""" Add connections (list of tuple pairs) to graph """

		for node1, node2 in self.connections:
			self.add(node1, node2)

	def add(self, node1, node2):
		""" Add connection between node1 and node2 """

		self.graph[node1].add(node2)
		if not self._directed:
			self.graph[node2].add(node1)

	def remove(self, node):
		""" Remove all references to node """

		for n, cxns in self.graph.iteritems():
			try:
				cxns.remove(node)
			except KeyError:
				pass
		try:
			del self.graph[node]
		except KeyError:
			pass

	def is_connected(self, node1, node2):
		""" Is node1 directly connected to node2 """

		return node1 in self.graph and node2 in self.graph[node1]

	def get_weight(self, node1, node2):
		""" Get the weight between two connected nodes """

		assert self.is_connected(node1, node2)
		tempt = (node1, node2) if node1 < node2 else (node2, node1)
		print('get_weight:', self.weight_dict[tempt] == getattr(self.edge_dict[tempt], 'weight'))
		return self.weight_dict[tempt]

	def set_distance(self, node1, node2, dis):
		""" Set the distance between two nodes """

		tempt = (node1, node2) if node1 < node2 else (node2, node1)
		is_edge = self.edge_dict.keys().__contains__(tempt)
		temp_demand = 0
		temp_weight = 0
		if is_edge:
			temp_weight = getattr(self.edge_dict[tempt], 'weight')
			temp_demand = getattr(self.edge_dict[tempt], 'demand')
		self.edge_dict[tempt] = Edge(temp_weight, temp_demand, dis)
		self.distance_dict[tempt] = dis

	def get_distance(self, node1, node2):
		""" Get the distance between two nodes """

		if node1 == node2:
			return 0
		tempt = (node1, node2) if node1 < node2 else (node2, node1)
		# if self.distance_dict.get(tempt) is None:
		if not self.edge_dict.keys().__contains__(tempt):
			return Inf
		print(tempt)
		print(getattr(self.edge_dict[tempt], 'distance'))
		print(self.distance_dict[tempt])
		# print('get_distance:', self.weight_dict[tempt] == getattr(self.edge_dict[tempt], 'distance'))
		return self.distance_dict[tempt]

	def get_distances(self, node):
		distances_list = list()
		for dest in self.graph:
			distances_list.append('{}->{}:{}'.format(node, dest, self.get_distance(node, dest)))
		return distances_list

	def floyd(self):
		for i in self.graph:
			for j in self.graph:
				for k in self.graph:
					tempt = self.get_distance(i, k) + self.get_distance(k, j)
					if self.get_distance(i, j) > tempt:
						self.set_distance(i, j, tempt)

	def find_path(self, node1, node2, path=[], cost=0):
		""" Find any path between node1 and node2 (may not be shortest) """

		path = path + [node1]
		# print(path)
		if node1 == node2:
			return path, cost
		if node1 not in self.graph:
			return None, cost
		for node in self.graph[node1]:
			tempt_cost = cost
			tempt_cost += self.get_weight(node, node1)
			if node not in path:
				new_path = self.find_path(node, node2, path, tempt_cost)
				if new_path[0] is not None:
					# print(new_path)
					return new_path, cost
		return None, cost
	#
	# def find_path(self, node1, node2, path=[]):
	# 	""" Find any path between node1 and node2 (may not be shortest) """
	#
	# 	path = path + [node1]
	# 	if node1 == node2:
	# 		return path
	# 	if node1 not in self.graph:
	# 		return None
	# 	for node in self.graph[node1]:
	# 		if node not in path:
	# 			new_path = self.find_path(node, node2, path)
	# 			if new_path:
	# 				return new_path
	# 	return None

	def find_all_path(self, node1, node2, path=list()):
		""" Find all the paths between node1 and node2 """

		path_list = list()
		cost_list = list()
		path = path + [node1]
		if node1 == node2:
			return path
		if node1 not in self.graph:
			return None
		for node in self.graph[node1]:
			if node not in path:
				new_path = self.find_path(node, node2, path)
				if new_path:
					path_list.append(new_path)
		return path_list

	@staticmethod
	def draw(CARP_data):
		edges = list()
		[edges.append(x[:3]) for x in CARP_data.data]
		draw_graph(edges)
		pass

	def __str__(self):
		return '{}({})'.format(self.__class__.__name__, dict(self.graph))\
		       + '\n{}({})'.format('Weight', dict(self.weight_dict)) \
		       + '\n{}({})'.format('Demand', dict(self.demand_dict)) \
		       + '\n{}({})'.format('Distance', dict(self.distance_dict)) \
		       + '\n{}({})'.format('Total', dict(self.edge_dict))

Graph data structure, undirected by default. # self.add_connections(connections) # self.path_map = np.zeros((self.node_number, self.node_number), dtype=np.int16) Generate a graph with a CARP_data object Add connections (list of tuple pairs) to graph Add connection between node1 and node2 Remove all references to node Is node1 directly connected to node2 Get the weight between two connected nodes Set the distance between two nodes Get the distance between two nodes # if self.distance_dict.get(tempt) is None: # print('get_distance:', self.weight_dict[tempt] == getattr(self.edge_dict[tempt], 'distance')) Find any path between node1 and node2 (may not be shortest) # print(path) # print(new_path) # # def find_path(self, node1, node2, path=[]): # 	""" Find any path between node1 and node2 (may not be shortest) """ # # 	path = path + [node1] # 	if node1 == node2: # 		return path # 	if node1 not in self.graph: # 		return None # 	for node in self.graph[node1]: # 		if node not in path: # 			new_path = self.find_path(node, node2, path) # 			if new_path: # 				return new_path # 	return None Find all the paths between node1 and node2