skcriteria.utils.dag_rank module

DAG conversion and ranking-reconstruction utilities.

This module provides utilities for converting a directed graph (typically a pairwise dominance graph / tournament) into a Directed Acyclic Graph, and for reconstructing a ranking from it.

as_condensed_reduced_dag() collapses each strongly connected component (dominance cycle) into a single supernode via graph condensation, which is always exact and acyclic – no heuristic or arbitrary cycle-breaking choice is involved. ranking_from_generations() then builds a ranking from that DAG, where every alternative that was part of the same dominance cycle ends up tied at the same rank.

Key Features

  • Exact, deterministic cycle handling via strongly connected components

  • No approximation or arbitrary choices: every dominance cycle in the original graph is reported as an explicit tie in the resulting ranking

skcriteria.utils.dag_rank.as_condensed_reduced_dag(graph)[source]

Collapse every strongly connected component into a single node.

Produces a DAG where each node represents either a single alternative or, if it was part of a dominance cycle (a strongly connected component of size greater than one), the whole group of alternatives tied together by that cycle. The condensation is then transitively reduced, dropping edges implied by other paths so only the minimal set of edges needed to preserve reachability remains.

Graph condensation is a direct mathematical construction, always exact and always acyclic, with no heuristic involved and no arbitrary choice to make about which edge to remove to break a cycle. Use this when the goal is to report where the pairwise comparisons fail to determine a strict order, instead of forcing one anyway.

Parameters:

graph (networkx.DiGraph) – The (possibly cyclic) graph to condense.

Returns:

  • dag (networkx.DiGraph) – The transitive reduction of the condensation of graph: one node per strongly connected component, with an edge between two supernodes only where required to preserve the reachability relation implied by the original graph.

  • members (dict) – Maps each node of dag to the set of original alternatives it represents. Nodes coming from a size-one component map to a singleton set; nodes coming from a dominance cycle map to all the alternatives tied together by that cycle. Meant to be passed as the members argument of ranking_from_generations().

Notes

nx.transitive_reduction does not preserve node attributes, so the members mapping has to be rebuilt after calling it – this is handled internally, callers do not need to worry about it.

skcriteria.utils.dag_rank.max_posible_ranks(dag, members)[source]

Total number of rankings obtainable from the condensed DAG.

Counts every strict ordering consistent with dag: for each topological generation, the alternatives tied together (grouped by supernode via members) can be permuted freely among themselves, contributing a factorial of their combined size; the total is the product of these factorials across all generations. Meant to size or bound generate_rankings_with_cycle_permutations() (e.g. deciding whether max_rankings is needed) without materializing the rankings.

Parameters:
Returns:

Maximum number of distinct rankings derivable from dag.

Return type:

int

skcriteria.utils.dag_rank.ranking_from_generations(alternatives, dag, members)[source]

Generate a ranking based on topological generations.

Creates a single ranking where alternatives in the same topological generation (incomparable elements) share the same rank. This provides a compact representation when ties are acceptable.

Meant to be used with the condensed DAG from as_condensed_reduced_dag(), where a node may represent several alternatives tied together by a dominance cycle.

Parameters:

  • alternatives (array-like) – Array of alternative names/identifiers in their original order. This defines the order in which ranks are returned in the ranking.

  • dag (networkx.DiGraph) – A directed acyclic graph representing preference relations, as returned by as_condensed_reduced_dag().

  • members (dict) – Maps each node of dag to the set of alternatives it represents, as returned by as_condensed_reduced_dag().

Returns:

A 1-indexed NumPy array where the i-th element is the rank of the i-th alternative. Alternatives in the same generation (i.e. in the same dominance cycle) share the same rank. Lower ranks indicate better alternatives.

Return type:

np.ndarray

skcriteria.utils.dag_rank.generate_rankings_with_cycle_permutations(alternatives, dag, members, *, max_rankings=None)[source]

Generate rankings by permuting the alternatives within each cycle.

Unlike a ranking that ties together every alternative belonging to the same dominance cycle, this function enumerates every possible internal ordering of each cycle’s members as a separate candidate ranking. Inside a genuine dominance cycle no internal order is more justified than another – every ordering violates at least one pairwise comparison – so instead of hiding that ambiguity behind a tie, this exposes every equally plausible strict ranking for the decision-maker to inspect.

This relies on dag being the condensation of a tournament (see as_condensed_reduced_dag): for a tournament, the condensation is always a strict total order of its supernodes (no two supernodes are ever incomparable), which means every topological generation contains exactly one supernode. That is what lets this function iterate nx.topological_generations directly instead of enumerating every topological sort – there is only one order between supernodes to begin with, so all the combinatorial variation comes exclusively from permuting the members within each cycle.

Parameters:

  • alternatives (array-like) – Array of alternative names/identifiers in their original order. This defines the order in which ranks are returned in each ranking.

  • dag (networkx.DiGraph) – The condensation of a tournament, as returned by as_condensed_dag.

  • members (dict) – Maps each node of dag to the set of alternatives it represents, as returned by as_condensed_dag.

  • max_rankings (int, optional) – Maximum number of rankings to generate. If None (default), all possible rankings are generated.

Yields:

np.ndarray – A 1-indexed NumPy array where the i-th element is the rank (position) of the i-th alternative. Every yielded ranking is a strict total order – no ties.

Notes

The total number of rankings generated is the product, over every supernode with more than one member, of the factorial of its size (e.g. a single cycle of 3 alternatives yields 3! = 6 rankings). This grows very fast with cycle size, so max_ranks is worth setting for anything but small cycles.