Minimum-Paths Minimum Discordant Nodes in General Graphs

This model optimizes the number of walks for the k-Minimum Discordant Nodes objective in directed graphs with cycles. It wraps NumPathsOptimization with:

model_type = kMinDiscordantNodesCycles
stop_on_delta_abs = 0

Thus, it iterates over increasing values of \(k\) and stops when the discordant-node objective reaches a plateau.

1. Definition

Given a directed graph (possibly cyclic) with node flow values, this model returns weighted walks minimizing discordant nodes while selecting \(k\) automatically.

The search starts from a valid lower bound and increases \(k\) up to max_num_paths (or until time limit), stopping at the first non-improving objective value under the absolute-delta rule.

2. Solving the problem

import flowpaths as fp
import networkx as nx

G = nx.DiGraph()
G.add_node("s", flow=5)
G.add_node("a", flow=5)
G.add_node("b", flow=5)
G.add_node("t", flow=5)
G.add_edge("s", "a")
G.add_edge("a", "b")
G.add_edge("b", "a")
G.add_edge("b", "t")

model = fp.MinPathsMinDiscordantNodesCycles(
    G=G,
    flow_attr="flow",
    discordance_tolerance=0.1,
    min_num_paths=1,
    max_num_paths=10,
)
model.solve()

if model.is_solved():
    sol = model.get_solution(remove_empty_paths=True)
    print(model.model.k)  # selected k
    print(sol["walks"])
    print(sol["weights"])
    print(sol["discordant_nodes"])

Example search flow:

flowchart LR
    start([Start at k0]) --> solvek[Solve k-MinDiscordantNodesCycles at k]
    solvek --> feasible{Solved?}
    feasible -- no --> nextk[Increase k]
    feasible -- yes --> plateau{Objective plateau?}
    plateau -- no --> nextk
    plateau -- yes --> stop([Return previous feasible model])
    nextk --> solvek

3. References

Jin Zhao, Haodi Feng, Daming Zhu, Yu Lin, MultiTrans: An Algorithm for Path Extraction Through Mixed Integer Linear Programming for Transcriptome Assembly, IEEE/ACM Transactions on Computational Biology and Bioinformatics 19(1), 48-56, 2022.
See also flowpaths References.

MinPathsMinDiscordantNodesCycles

MinPathsMinDiscordantNodesCycles(
    G: DiGraph,
    flow_attr: str,
    weight_type: type = float,
    discordance_tolerance: float = 0.1,
    subset_constraints: list = None,
    additional_starts: list = None,
    additional_ends: list = None,
    optimization_options: dict = None,
    solver_options: dict = None,
    min_num_paths: int = 1,
    max_num_paths: int = 2
    ** 64,
    time_limit: float = float(
        "inf"
    ),
)

Bases: NumPathsOptimization

Find a minimum number of walks for k-MinDiscordantNodes on cyclic graphs by iterating over k.

This class is a thin wrapper around NumPathsOptimization with: - model_type fixed to kMinDiscordantNodesCycles - stop_on_delta_abs fixed to 0

Therefore, the search stops at the first k where the objective value does not improve in absolute value compared to the reference used by NumPathsOptimization.

Source code in flowpaths/minpathsmindiscordantnodescycles.py

def __init__(
    self,
    G: nx.DiGraph,
    flow_attr: str,
    weight_type: type = float,
    discordance_tolerance: float = 0.1,
    subset_constraints: list = None,
    additional_starts: list = None,
    additional_ends: list = None,
    optimization_options: dict = None,
    solver_options: dict = None,
    min_num_paths: int = 1,
    max_num_paths: int = 2**64,
    time_limit: float = float("inf"),
):
    super().__init__(
        model_type=kmindiscordantnodescycles.kMinDiscordantNodesCycles,
        stop_on_delta_abs=0,
        min_num_paths=min_num_paths,
        max_num_paths=max_num_paths,
        time_limit=time_limit,
        G=G,
        flow_attr=flow_attr,
        weight_type=weight_type,
        discordance_tolerance=discordance_tolerance,
        subset_constraints=subset_constraints or [],
        additional_starts=additional_starts or [],
        additional_ends=additional_ends or [],
        optimization_options=optimization_options,
        solver_options=solver_options or {},
    )