# distutils: language=c++

from libcpp cimport bool as bool_t
from libcpp.vector cimport vector
from libcpp.map cimport map
from libcpp.unordered_set cimport unordered_set

from .base cimport _Algorithm, Algorithm
from .dynamics cimport _GraphEvent, GraphEvent
from .graph cimport _Graph, Graph
from .structures cimport _Partition, Partition, count, index, node

cdef extern from "<networkit/components/ComponentDecomposition.hpp>":
	cdef cppclass _ComponentDecomposition "NetworKit::ComponentDecomposition"(_Algorithm):
		_ComponentDecomposition(_Graph G) except +
		count numberOfComponents() except +
		count componentOfNode(node query) except +
		_Partition getPartition() except +
		map[index, count] getComponentSizes() except +
		vector[vector[node]] getComponents() except +

cdef class ComponentDecomposition(Algorithm):
	cdef Graph _G

	def __init__(self, *args, **kwargs):
		if type(self) == ComponentDecomposition:
			raise RuntimeError("Error, you may not use ComponentDecomposition directly, use a sub-class instead")

	def getPartition(self):
		"""
		getPartition()

		Get a Partition that represents the components.

		Returns
		-------
		networkit.Partition
			A partition representing the found components.
		"""
		return Partition().setThis((<_ComponentDecomposition*>(self._this)).getPartition())

	def numberOfComponents(self):
		"""
		numberOfComponents()

		Get the number of connected components.

		Returns
		-------
		int
			The number of connected components.
		"""
		return (<_ComponentDecomposition*>(self._this)).numberOfComponents()

	def componentOfNode(self, v):
		"""
		componentOfNode(v)

		Get the the component in which node `v` is situated.

		Parameters
		----------
		v : int
			The node whose component is asked for.

		Returns
		-------
		int
			Component in which node `v` is situated.
		"""
		return (<_ComponentDecomposition*>(self._this)).componentOfNode(v)

	def getComponentSizes(self):
		"""
		getComponentSizes()

		Get the component sizes.

		Returns
		-------
		dict(int ``:`` int)
			A dict containing the component ids and their size.
		"""
		return (<_ComponentDecomposition*>(self._this)).getComponentSizes()

	def getComponents(self):
		"""
		getComponents()

		Get the connected components, each as a list of nodes.

		Returns
		-------
		list(int)
			The connected components.
		"""
		return (<_ComponentDecomposition*>(self._this)).getComponents()


cdef extern from "<networkit/components/ConnectedComponents.hpp>":

	cdef cppclass _ConnectedComponents "NetworKit::ConnectedComponents"(_ComponentDecomposition):
		_ConnectedComponents(_Graph G) except +
		@staticmethod
		_Graph extractLargestConnectedComponent(_Graph G, bool_t) nogil except +

cdef class ConnectedComponents(ComponentDecomposition):
	"""
	ConnectedComponents(G)

	Determines the connected components and associated values for an undirected graph.
	Create ConnectedComponents for Graph `G`.

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

	def __cinit__(self,  Graph G):
		self._this = new _ConnectedComponents(G._this)

	@staticmethod
	def extractLargestConnectedComponent(Graph graph, bool_t compactGraph = False):
		"""
		extractLargestConnectedComponent(graph, compactGraph=False)

		Constructs a new graph that contains only the nodes inside the
		largest connected component.

		Notes
		-----
		Available for undirected graphs only.

		Parameters
		----------
		graph : networkit.Graph
			The input graph.
		compactGraph : bool, optional
			If true, the node ids of the output graph will be compacted
			(i.e., re-numbered from 0 to n-1). If false, the node ids
			will not be changed. Default: False

		Returns
		-------
		networkit.Graph
			A graph that contains only the nodes inside the largest
			connected component.
		"""
		return Graph().setThis(_ConnectedComponents.extractLargestConnectedComponent(graph._this, compactGraph))

cdef extern from "<networkit/components/ParallelConnectedComponents.hpp>":

	cdef cppclass _ParallelConnectedComponents "NetworKit::ParallelConnectedComponents"(_ComponentDecomposition):
		_ParallelConnectedComponents(_Graph G, bool_t coarsening) except +

cdef class ParallelConnectedComponents(ComponentDecomposition):
	"""
	ParallelConnectedComponents(G, coarsening=True)

	Determines the connected components and associated values for
	an undirected graph.

	Parameters
	----------
	graph : networkit.Graph
		The input graph
	coarsening : bool, optional
		Specifies whether the main algorithm based on label propagation (LP)
		shall work recursively (true) or not (false) by coarsening/contracting
		an LP-computed clustering. Defaults to true since we saw positive effects
		in terms of running time for many networks. Beware of possible memory implications.
	"""

	def __cinit__(self,  Graph G, coarsening=True	):
		self._this = new _ParallelConnectedComponents(G._this, coarsening)

cdef extern from "<networkit/components/StronglyConnectedComponents.hpp>":

	cdef cppclass _StronglyConnectedComponents "NetworKit::StronglyConnectedComponents"(_ComponentDecomposition):
		_StronglyConnectedComponents(_Graph G) except +

cdef class StronglyConnectedComponents(ComponentDecomposition):
	"""
	StronglyConnectedComponents(G)

	Computes the strongly connected components of a directed graph.

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

	def __cinit__(self, Graph G):
		self._this = new _StronglyConnectedComponents(G._this)

cdef extern from "<networkit/components/WeaklyConnectedComponents.hpp>":

	cdef cppclass _WeaklyConnectedComponents "NetworKit::WeaklyConnectedComponents"(_ComponentDecomposition):
		_WeaklyConnectedComponents(_Graph G) except +

cdef class WeaklyConnectedComponents(ComponentDecomposition):
	"""
	WeaklyConnectedComponents(G)

	Determines the weakly connected components of a directed graph.

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

	def __cinit__(self, Graph G):
		self._this = new _WeaklyConnectedComponents(G._this)

cdef extern from "<networkit/components/BiconnectedComponents.hpp>":

	cdef cppclass _BiconnectedComponents "NetworKit::BiconnectedComponents"(_Algorithm):
		_BiconnectedComponents(_Graph G) except +
		count numberOfComponents() except +
		map[index, count] getComponentSizes() except +
		vector[vector[count]] getComponents() except +
		unordered_set[node] getComponentsOfNode(node u) except +

cdef class BiconnectedComponents(Algorithm):
	"""
	BiconnectedComponents()

	Determines the biconnected components of an undirected graph as defined in
	Tarjan, Robert. Depth-First Search and Linear Graph Algorithms. SIAM J.
	Comput. Vol 1, No. 2, June 1972.

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

	def __cinit__(self, Graph G):
		self._this = new _BiconnectedComponents(G._this)

	def numberOfComponents(self):
		"""
		numberOfComponents()
		
		Returns the number of components.

		Returns
		-------
		int
			The number of components.
		"""
		return (<_BiconnectedComponents*>(self._this)).numberOfComponents()

	def getComponentSizes(self):
		"""
		getComponentSizes()
		
		Returns the map from component id to size.

		Returns
		-------
		dict(int : int)
			A dict that maps each component id to its size.
		"""
		return (<_BiconnectedComponents*>(self._this)).getComponentSizes()

	def getComponents(self):
		"""
		getComponents()
		
		Returns all the components, each stored as (unordered) set of nodes.

		Returns
		-------
		vector[vector[node]]
			A vector of vectors. Each inner vector contains all the nodes inside the component.
		"""
		return (<_BiconnectedComponents*>(self._this)).getComponents()

	def getComponentsOfNode(self, node u):
		"""
		getComponentsOfNode(u)

		Get the components that contain node u.

		Parameters
		----------
		u : int
			The node.

		Returns
		-------
		set
			Components that contain node u.
		"""
		return (<_BiconnectedComponents*>(self._this)).getComponentsOfNode(u)

cdef extern from "<networkit/components/DynConnectedComponents.hpp>":

	cdef cppclass _DynConnectedComponents "NetworKit::DynConnectedComponents"(_ComponentDecomposition):
		_DynConnectedComponents(_Graph G) except +
		void update(_GraphEvent) except +
		void updateBatch(vector[_GraphEvent]) except +
		count numberOfComponents() except +
		count componentOfNode(node query) except +
		map[index, count] getComponentSizes() except +
		vector[vector[node]] getComponents() except +

cdef class DynConnectedComponents(ComponentDecomposition):
	"""
	DynConnectedComponents(G)

	Determines and updates the connected components of an undirected graph.

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

	def __cinit__(self, Graph G):
		self._this = new _DynConnectedComponents(G._this)

	def update(self, event):
		"""
		update(event)

		Updates the connected components after an edge insertion or
		deletion.

		Parameters
		----------
		event : networkit.dynamics.GraphEvent
			The event that happened (edge deletion or insertion).
		"""
		(<_DynConnectedComponents*>(self._this)).update(_GraphEvent(event.type, event.u, event.v, event.w))

	def updateBatch(self, batch):
		"""
		updateBatch(batch)

		Updates the connected components after a batch of edge insertions or
		deletions.

		Parameters
		----------
		batch : list(networkit.dynamics.GraphEvent)
			A list that contains a batch of edge insertions or deletions.
		"""
		cdef vector[_GraphEvent] _batch
		for event in batch:
			_batch.push_back(_GraphEvent(event.type, event.u, event.v, event.w))
		(<_DynConnectedComponents*>(self._this)).updateBatch(_batch)


cdef extern from "<networkit/components/DynWeaklyConnectedComponents.hpp>":

	cdef cppclass _DynWeaklyConnectedComponents "NetworKit::DynWeaklyConnectedComponents"(_ComponentDecomposition):
		_DynWeaklyConnectedComponents(_Graph G) except +
		void update(_GraphEvent) except +
		void updateBatch(vector[_GraphEvent]) except +

cdef class DynWeaklyConnectedComponents(ComponentDecomposition):
	"""
	DynWeaklyConnectedComponents(G)

	Determines and updates the weakly connected components of a directed graph.

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

	def __cinit__(self, Graph G):
		self._this = new _DynWeaklyConnectedComponents(G._this)

	def update(self, event):
		"""
		update(event)

		Updates the connected components after an edge insertion or
		deletion.

		Parameters
		----------
		event : networkit.dynamics.GraphEvent
			The event that happened (edge deletion or insertion).
		"""
		(<_DynWeaklyConnectedComponents*>(self._this)).update(_GraphEvent(event.type, event.u, event.v, event.w))

	def updateBatch(self, batch):
		"""
		updateBatch(batch)

		Updates the connected components after a batch of edge insertions or
		deletions.

		Parameters
		----------
		batch : list(networkit.dynamics.GraphEvent)
			A vector that contains a batch of edge insertions or deletions.
		"""
		cdef vector[_GraphEvent] _batch
		for event in batch:
			_batch.push_back(_GraphEvent(event.type, event.u, event.v, event.w))
		(<_DynWeaklyConnectedComponents*>(self._this)).updateBatch(_batch)