#!/usr/bin/python
# -*- coding: latin-1 -*-
"""
Python Library implementing basic graph manipulation and traversal
"""

class Node(object):
	"""Node class to store attributes and neighbors"""
	def __init__(self, id, attributes = {}):
		self.id = str(id)
		self.attributes = attributes
		self.neighbors = []  # list of neighbors id (ajacency list implementation)

	def dump(self):
		"""Simply prints node content"""
		print "  id: %s, attributes: %s, neighbors: %s" % (self.id, self.attributes, ','.join(self.neighbors))

class Edge(object):
	"""Edge class to store edge attributes"""
	def __init__(self, source, destination, attributes = {}):
		self.source      = source
		self.destination = destination
		self.attributes  = attributes

	def dump(self):
		"""Simply prints edge"""
		print "  %s -- %s , attributes: %s" % (self.source.id, self.destination.id, self.attributes)

class Graph(object):
	"""
	Abstract class representing a graph. It stores attributes for the graph, a dictionnary of nodes by id and the edges as a list.
	"""
	# constructor
	def __init__(self):
		self.attributes = {}
		self.nodesById  = {}
		self.edges      = []

	def dump(self):
		"""Dumps all nodes and edges of the graph."""
		print "Nodes"
		for n in self.nodes(): n.dump()
		print
		print "Edges"
		for e in self.edges: e.dump()
		print

	# modifiers
	###########
	def addNode(self, node, attributes = None):
		"""
		Add a node to the graph.
		It can be called with an already existing node:
			n = Node('youpi')
			g.addNode(n)
		or it can be called with an id:
			g.addNode('youpi')
		Attributes can be passed through a dictionnary:
			g.addNode('yopla', { 'color': 'yellow', 'flavour': 'lemon' })
		"""
		# TO DO
		return

	# accessors
	###########
	def node(self, obj): # convert node id or node to node (to ensure we have a node)
		"""
		Utility function to ensure we have a node:
			n = g.node(n)
		if n is a Node instance then it does nothing, but if n is the node id then it is replaced by the Node instance.
		"""
		# TO DO
		return None

	def nodes(self): # get all nodes as a vector
		"""
		Return the set of nodes of the graph as a list.
		"""
		# TO DO
		return None

	def neighbors(self, node):
		"""
		Returns the set of Nodes (as a list) that are accessible from node.
		"""
		# TO DO
		return None

	# traversal
	###########
	def dfs(self):
		"""
		Depth First Search travserval of the graph.
		Makes call to dfsVisit(node).
		After execution, nodes have additional attributes:
		  - dfs_color: should be black (node has been processed)
		  - dfs_predecessor: node id of predecessor in the traversal
		  - dfs_in: time when the node started to be processed
		  - dfs_out: time when the node processing finished
		edges have an additional attribute:
		  - dfs_type: dfs classification of edges
		     tree: the edge is part of a dfs tree
		     back: the edge creates a cycle
		     forward: from a node to a reachable node in the dfs tree
		     cross: from a node to a node from an other dfs tree
		"""
		# TO DO
		return None

	def dfsVisit(self, node):
		# TO DO
		return None

	def topologicalSort(self):
		"""
		Performs a topological sort of the nodes of the graph. Nodes are return as a list.
		Absence of cycle is not tested.
		"""
		# TO DO
		return None

	# input
	#######
	def loadSIF(self, filename):
		"""
		Loads a graph in a (simplified) SIF (Simple Interactipon Format, cf. Cytoscape doc).
		Assumed input:
		   node1	relation	node2
		   chaussettes	avant	chaussures
		   pantalon	avant	chaussures
		   ...
		"""
		# TO DO
		return None

class DirectedGraph(Graph):
	"""
	Class implementing a directed graph (subclasses Graph) as adjacency lists.
	"""
	# constructor
	def __init__(self):
		super(DirectedGraph, self).__init__()

	# modifiers
	###########
	def addEdge(self, source, destination, attributes = None):
		"""
		Add an edge to the graph.
		The source and destination can be either nodes or node ids.
		If the nodes do not exist, they will be created and added to the graph:
		   g=DirectedGraph()
		   g.addEdge('chaussettes','chaussures')
		is equivalent to:
		   src=Node('chaussettes')
		   dst=Node('chaussures')
		   g.addEdge(src,dst)
		Attributes can be set on edges:
		   g.addEdge('Toulouse', 'Bordeaux', { 'dist' : 250 } )
		"""
		# TO DO
		return None

	# accessors
	###########
	def isDirected(self):
		"""
		returns True!
		"""
		# TO DO
		return None

	def edge(self, source, destination):
		"""
		Used to ensure we have an edge from source to destination, and retrieve attributes:
		  e = g.edge('Toulouse', 'Bordeaux')
		  print e.attributes['dist']
		"""
		# TO DO
		return None

# TESTS
if __name__ == "__main__":
	g=DirectedGraph()
	# TO DO: LoadSIF
	# g.loadSIF('dressing.sif')
	# g.dump()
	# TO DO: DFS
	# g.dfs()
	# g.dump()
	# TO DO: Topological sort
	# nodes = g.topologicalSort()