# distutils: language=c++

from libc.stdint cimport uint64_t
from libcpp cimport bool as bool_t
from libcpp.vector cimport vector
from libcpp.utility cimport pair
from libcpp.unordered_map cimport unordered_map
from libcpp.unordered_set cimport unordered_set

ctypedef uint64_t count
ctypedef uint64_t index
ctypedef index node
ctypedef double edgeweight

from .graph cimport _Graph, Graph

cdef extern from "<networkit/graph/GraphTools.hpp>" namespace "NetworKit::GraphTools":

	count maxDegree(_Graph G) nogil except +
	count maxInDegree(_Graph G) nogil except +
	edgeweight maxWeightedDegree(_Graph G) nogil except +
	edgeweight maxWeightedInDegree(_Graph G) nogil except +
	node randomNode(_Graph G) nogil except +
	node randomNeighbor(_Graph G, node u) nogil except +
	pair[node, node] randomEdge(_Graph G, bool_t uniformDistribution) nogil except +
	vector[pair[node, node]] randomEdges(_Graph G, count numEdges) nogil except +
	pair[count, count] size(_Graph G) nogil except +
	double density(_Graph G) nogil except +
	double volume(_Graph G) nogil except +
	_Graph copyNodes(_Graph G) nogil except +
	_Graph toUndirected(_Graph G) nogil except +
	_Graph toUnweighted(_Graph G) nogil except +
	_Graph toWeighted(_Graph G) nogil except +
	_Graph subgraphFromNodes(_Graph G, unordered_set[node], bool_t, bool_t) nogil except +
	void append(_Graph G, _Graph G1) nogil except +
	void merge(_Graph G, _Graph G1) nogil except +
	void removeEdgesFromIsolatedSet[InputIt](_Graph G, InputIt first, InputIt last) except +
	_Graph getCompactedGraph(_Graph G, unordered_map[node,node]) nogil except +
	_Graph transpose(_Graph G) nogil except +
	unordered_map[node,node] getContinuousNodeIds(_Graph G) nogil except +
	unordered_map[node,node] getRandomContinuousNodeIds(_Graph G) nogil except +

cdef class GraphTools:

	@staticmethod
	def maxDegree(Graph G):
		"""
		Returns the maximum out-degree of the graph.

		Parameters
		----------
		G : networkit.Graph
			The input graph.

		Returns
		-------
		count
			The maximum out-degree of the graph.
		"""
		return maxDegree(G._this)

	@staticmethod
	def maxInDegree(Graph G):
		"""
		Returns the maximum in-degree of the graph.

		Parameters
		----------
		G : networkit.Graph
			The input graph.

		Returns
		-------
		count
			The maximum in-degree of the graph.
		"""
		return maxInDegree(G._this)

	@staticmethod
	def maxWeightedDegree(Graph G):
		"""
		Returns the maximum weighted out-degree of the graph.

		Parameters
		----------
		G : networkit.Graph
			The input graph.

		Returns
		-------
		edgeweight
			The maximum weighted out-degree of the graph.
		"""
		return maxWeightedDegree(G._this)

	@staticmethod
	def maxWeightedInDegree(Graph G):
		"""
		Returns the maximum weighted in-degree of the graph.

		Parameters
		----------
		G : networkit.Graph
			The input graph.

		Returns
		-------
		edgeweight
			The maximum weighted in-degree of the graph.
		"""
		return maxWeightedInDegree(G._this)

	@staticmethod
	def randomNode(Graph G):
		"""
		Returns a random node of the input graph.

		Parameters
		----------
		G : networkit.Graph
			The input graph.

		Returns
		-------
		node
			A random node.
		"""
		return randomNode(G._this)

	@staticmethod
	def randomNeighbor(Graph G, node u):
		"""
		Returns a random neighbor of node `u`.

		Parameters
		----------
		G : networkit.Graph
			The input graph.
		u : node
			A node in `G`.

		Returns
		-------
		node
			A random neighbor of `u`.
		"""
		return randomNeighbor(G._this, u)

	@staticmethod
	def randomEdge(Graph G, uniformDistribution = False):
		""" Get a random edge of the graph.

		Parameters
		----------
		G : networkit.Graph
			The input graph.
		uniformDistribution : bool
			If the distribution of the edge shall be uniform.

		Returns
		-------
		pair
			Random edge.

		Notes
		-----
		Fast, but not uniformly random if uniformDistribution is not set,
		slow and uniformly random otherwise.
		"""
		return randomEdge(G._this, uniformDistribution)

	@staticmethod
	def randomEdges(Graph G, numEdges):
		"""
		Returns a list with numEdges random edges. The edges are chosen uniformly at random.

		Parameters
		----------
		G : networkit.Graph
			The input graph.
		numEdges : count
			The number of edges to choose.

		Returns
		-------
		list of pairs
			List of with `numEdges` random edges.
		"""
		return randomEdges(G._this, numEdges)

	@staticmethod
	def append(Graph G, Graph G1):
		"""
		Appends graph `G1` to graph `G` as a new subgraph. Performs node id remapping.

		Parameters
		----------
		G : networkit.Graph
			Graph where `G1` will be appended to.
		G1 : networkit.Graph
			Graph that will be appended to `G`.
		"""
		append(G._this, G1._this)

	@staticmethod
	def merge(Graph G, Graph G1):
		"""
		Modifies graph `G` to be the union of it and graph `G1`.
		Nodes with the same ids are identified with each other.

		Parameters
		----------
		G : networkit.Graph
			Result of the merge.
		G1 : networkit.Graph
			Graph that will be merged with `G`.
		"""
		merge(G._this, G1._this)

	@staticmethod
	def removeEdgesFromIsolatedSet(Graph graph, nodes):
		"""
		Efficiently removes all the edges adjacent to a set of nodes that is
		not connected to the rest of the graph. This is meant to optimize the
		Kadabra algorithm.

		Parameters
		----------
		G : networkit.Graph
			The input graph.
		nodes : list
			Isolates set of nodes from where the edges will be removed.
		"""
		cdef vector[node] isolatedSet

		try:
			isolatedSet = <vector[node]?>nodes
		except TypeError:
			raise RuntimeError("Error, nodes must be a list of nodes.")
		removeEdgesFromIsolatedSet[vector[node].iterator](graph._this,
				isolatedSet.begin(), isolatedSet.end())

	@staticmethod
	def toUndirected(Graph graph):
		"""
		Returns an undirected copy of the input graph.

		Parameters
		----------
		graph : networkit.Graph
			The input graph.

		Returns
		-------
		graph : networkit.Graph
			Undirected copy of the input graph.
		"""
		return Graph().setThis(toUndirected(graph._this))

	@staticmethod
	def toUnweighted(Graph graph):
		"""
		Returns an unweighted copy of the input graph.

		Parameters
		----------
		graph : networkit.Graph
			The input graph.

		Returns
		-------
		graph : networkit.Graph
			Unweighted copy of the input graph.
		"""
		return Graph().setThis(toUnweighted(graph._this))

	@staticmethod
	def toWeighted(Graph graph):
		"""
		Returns a weighted copy of the input graph.

		Parameters
		----------
		graph : networkit.Graph
			The input graph.

		Returns
		-------
		graph : networkit.Graph
			Weighted copy of the input graph.
		"""
		return Graph().setThis(toWeighted(graph._this))

	@staticmethod
	def size(Graph graph):
		"""
		Return the size of the graph.

		Returns
		-------
		tuple
			a pair (n, m) where n is the number of nodes and m is the number of edges.
		"""
		return size(graph._this)

	@staticmethod
	def density(Graph graph):
		"""
		Get the density of the input graph.

		Parameters
		----------
		graph : networkit.Graph
			The input graph.

		Returns
		-------
		double
			The density of the input graph.
		"""
		return density(graph._this)

	@staticmethod
	def volume(Graph graph):
		"""
		Get the volume of the input graph.

		Parameters
		----------
		graph : networkit.Graph
			The input graph.

		Returns
		-------
		double
			The volume of the input graph.
		"""
		return volume(graph._this)

	@staticmethod
	def copyNodes(Graph graph):
		"""
		Copies all nodes of the input graph to a new graph (edges are not copied).

		Parameters
		----------
		graph : networkit.Graph
			The input graph.

		Returns
		-------
		graph : networkit.Graph
			Graph with the same nodes as the input graph (and without any edge).
		"""
		return Graph().setThis(copyNodes(graph._this))

	@staticmethod
	def subgraphFromNodes(Graph graph, nodes, includeOutNeighbors=False, includeInNeighbors=False):
		"""
		Returns an induced subgraph of the input graph (including potential edge
		weights/directions).

		Parameters
		----------
		graph : networkit.Graph
			The input graph.
		nodes : set
			Nodes in the induced subgraph.
		includeOutNeighbors : bool
			If set to true, out-neighbors will also be included.
		includeInNeighbors : bool
			If set to true, in-neighbors will also be included.

		Returns
		-------
		graph : networkit.Graph
			Induced subgraph.
		"""
		return Graph().setThis(subgraphFromNodes(
			graph._this, nodes, includeOutNeighbors, includeInNeighbors))

	@staticmethod
	def transpose(Graph graph):
		"""
		Returns the transpose of the input graph. The graph must be directed.

		Parameters
		----------
		graph : networkit.Graph
			The input graph.

		Returns
		graph : networkit.Graph
			Transpose of the input graph.
		"""
		return Graph().setThis(transpose(graph._this))

	@staticmethod
	def getCompactedGraph(Graph graph, nodeIdMap):
		"""
		Computes a graph with the same structure but with continuous node ids.

		Parameters
		----------
		graph : networkit.Graph
			The graph to be compacted.
		nodeIdMap:
			The map providing the information about the node ids.

		Returns
		-------
		networkit.Graph
			The compacted graph
		"""
		cdef unordered_map[node,node] cNodeIdMap
		for key in nodeIdMap:
			cNodeIdMap[key] = nodeIdMap[key]
		return Graph().setThis(getCompactedGraph(graph._this,cNodeIdMap))

	@staticmethod
	def getContinuousNodeIds(Graph graph):
		"""
		Computes a map of node ids to continuous node ids.

		Parameters
		----------
		graph : networkit.Graph
			The graph of which the node id map is wanted.
		Returns
		-------
			Returns the node id map
		"""
		cdef unordered_map[node,node] cResult
		with nogil:
			cResult = getContinuousNodeIds(graph._this)
		result = dict()
		for elem in cResult:
			result[elem.first] = elem.second
		return result

	@staticmethod
	def getRandomContinuousNodeIds(Graph graph):
		"""
		Computes a map of node ids to continuous, randomly permutated node ids.

		Parameters
		----------
		graph : networkit.Graph
			The graph of which the node id map is wanted.
		Returns
		-------
			Returns the node id map
		"""
		cdef unordered_map[node,node] cResult
		with nogil:
			cResult = getRandomContinuousNodeIds(graph._this)
		result = dict()
		for elem in cResult:
			result[elem.first] = elem.second
		return result