Move layers functionality to rustworkx-core

[mtreinish]

The layers() function is only exposed via a Python interface currently:

rustworkx/src/dag_algo/mod.rs

Lines 227 to 345 in ab93329

	/// Return a list of layers
	///
	/// A layer is a subgraph whose nodes are disjoint, i.e.,
	/// a layer has depth 1. The layers are constructed using a greedy algorithm.
	///
	/// :param PyDiGraph graph: The DAG to get the layers from
	/// :param list first_layer: A list of node ids for the first layer. This
	/// will be the first layer in the output
	/// :param bool index_output: When set to to ``True`` the output layers will be
	/// a list of integer node indices.
	///
	/// :returns: A list of layers, each layer is a list of node data, or if
	/// ``index_output`` is ``True`` each layer is a list of node indices.
	/// :rtype: list
	///
	/// :raises InvalidNode: If a node index in ``first_layer`` is not in the graph
	#[pyfunction]
	#[pyo3(
	signature=(dag, first_layer, index_output=false),
	text_signature = "(dag, first_layer, /, index_output=False)"
	)]
	pub fn layers(
	py: Python,
	dag: &digraph::PyDiGraph,
	first_layer: Vec<usize>,
	index_output: bool,
	) -> PyResult<PyObject> {
	let mut output_indices: Vec<Vec<usize>> = Vec::new();
	let mut output: Vec<Vec<&PyObject>> = Vec::new();
	// Convert usize to NodeIndex
	let mut first_layer_index: Vec<NodeIndex> = Vec::new();
	for index in first_layer {
	first_layer_index.push(NodeIndex::new(index));
	}
	let mut cur_layer = first_layer_index;
	let mut next_layer: Vec<NodeIndex> = Vec::new();
	let mut predecessor_count: HashMap<NodeIndex, usize> = HashMap::new();
	let mut layer_node_data: Vec<&PyObject> = Vec::new();
	if !index_output {
	for layer_node in &cur_layer {
	let node_data = match dag.graph.node_weight(*layer_node) {
	Some(data) => data,
	None => {
	return Err(InvalidNode::new_err(format!(
	"An index input in 'first_layer' {} is not a valid node index in the graph",
	layer_node.index()
	)))
	}
	};
	layer_node_data.push(node_data);
	}
	output.push(layer_node_data);
	} else {
	for layer_node in &cur_layer {
	if !dag.graph.contains_node(*layer_node) {
	return Err(InvalidNode::new_err(format!(
	"An index input in 'first_layer' {} is not a valid node index in the graph",
	layer_node.index()
	)));
	}
	}
	output_indices.push(cur_layer.iter().map(|x| x.index()).collect());
	}
	// Iterate until there are no more
	while !cur_layer.is_empty() {
	for node in &cur_layer {
	let children = dag
	.graph
	.neighbors_directed(*node, petgraph::Direction::Outgoing);
	let mut used_indices: HashSet<NodeIndex> = HashSet::new();
	for succ in children {
	// Skip duplicate successors
	if used_indices.contains(&succ) {
	continue;
	}
	used_indices.insert(succ);
	let mut multiplicity: usize = 0;
	let raw_edges = dag
	.graph
	.edges_directed(*node, petgraph::Direction::Outgoing);
	for edge in raw_edges {
	if edge.target() == succ {
	multiplicity += 1;
	}
	}
	predecessor_count
	.entry(succ)
	.and_modify(|e| *e -= multiplicity)
	.or_insert(dag.in_degree(succ.index()) - multiplicity);
	if *predecessor_count.get(&succ).unwrap() == 0 {
	next_layer.push(succ);
	predecessor_count.remove(&succ);
	}
	}
	}
	if !index_output {
	let mut layer_node_data: Vec<&PyObject> = Vec::new();
	for layer_node in &next_layer {
	layer_node_data.push(&dag.graph[*layer_node]);
	}
	if !layer_node_data.is_empty() {
	output.push(layer_node_data);
	}
	} else if !next_layer.is_empty() {
	output_indices.push(next_layer.iter().map(|x| x.index()).collect());
	}
	cur_layer = next_layer;
	next_layer = Vec::new();
	}
	if !index_output {
	Ok(PyList::new_bound(py, output).into())
	} else {
	Ok(PyList::new_bound(py, output_indices).into())
	}
	}

We should port it to rustworkx-core, so that rust users can leverage the function.

One tweak that probably makes sense for the rustworkx-core version is that instead of returning a PyList for a Vec of Vecs of node weights we should have it return of an iterator of Vecs of node ids. This would be more flexible and performant for rust space users and for the python side of rustworkx we can just collect the iterator to a pylist (for backwards compatibility).

[raynelfss]

Can I be assigned to this?