<filename>toboggan/dp.py
#! /usr/bin/env python3
#
# This file is part of Toboggan, https://github.com/TheoryInPractice/Toboggan/,
# and is Copyright (C) North Carolina State University, 2017. It is licensed
# under the three-clause BSD license; see LICENSE.
#
# python libs
from collections import defaultdict, deque

# local imports
from toboggan.flow import Constr, SolvedConstr, PathConf


def solve(instance, silent=True, guessed_weights=None):
    """
    Find a feasible set of weights consistent with guessed_weights.

    guessed_weights is a sorted tuple of size k in which any of the entries
    might be None.  If guessed_weights is k integers, check whether this
    solution works.  If any entry of guessed_weights is None, check whether a
    solution exists with each None replaced by a integer that respects the
    sorted order of the tuple.
    """
    graph = instance.graph
    k = instance.k

    # The only constraint a priori is the total flow value
    globalconstr = Constr(instance)
    guessed_weights = [None]*k if not guessed_weights else guessed_weights

    assert len(guessed_weights) == k
    for index, guess in enumerate(guessed_weights):
        if guess is None:
            continue
        globalconstr = globalconstr.add_constraint([index], (0, guess))
        if globalconstr is None:
            return set()

    # Build first DP table
    old_table = defaultdict(set)
    allpaths = frozenset(range(k))
    # All k paths `end' at source
    old_table[PathConf(graph.source(), allpaths)] = set([globalconstr])
    if not silent:
        print("After processing edge into s, table is:")
        print(old_table)

    # run dynamic progamming
    for v in instance.ordering[:-1]:
        new_table = defaultdict(set)
        for paths, constraints in old_table.items():
            # Distribute paths incoming to i onto its neighbours
            if not silent:
                print("  Pushing {}".format(paths))
            for newpaths, dist in paths.push(v, graph.labeled_neighborhood(v)):
                # if not silent:
                    # print("  Candidate paths", newpaths)
                debug_counter = 0
                for constr in constraints:
                    # print("  Combining w/ constraints", constraints)
                    # Update constraint-set constr with new constraints imposed
                    # by our choice of pushing paths o..........es (as
                    # described by dist)
                    curr_constr = constr
                    try:
                        for e, p in dist:  # Paths p coincide on edge e
                            updated_constr = curr_constr.add_constraint(p, e)
                            if updated_constr is not None:
                                curr_constr = updated_constr
                            else:
                                break
                        else:
                            # WORRY ABOUT THIS EVENTUALLY
                            if constr.rank == curr_constr.rank or \
                                    not curr_constr.is_redundant():
                                # Add to DP table
                                new_table[newpaths].add(curr_constr)
                    except ValueError as err:
                        print("Problem while adding constraint", p, e)
                        raise err
        # replace tables
        old_table = new_table

    if not silent:
        print("\nDone.")
        print("Table is:")
        print(new_table)

    candidates = new_table[PathConf(graph.sink(), allpaths)]
    return candidates


def recover_paths(instance, weights, silent=True):
    """Recover the paths that correspond to the weights given."""
    graph = instance.graph
    k = instance.k

    if not silent:
        print(graph)

    # since we know all the weights, we can stored them as a solved constraint
    # system
    globalconstr = SolvedConstr(weights, instance)

    assert len(weights) == k
    allpaths = frozenset(range(k))

    # Build DP table, which will map path configurations to the path
    # configurations in the previous tables that yielded the specific entry
    # All k paths start at the source vertex
    initial_entries = {PathConf(graph.source(), allpaths): None}
    backptrs = [initial_entries]

    # Run DP
    for v in instance.ordering[:-1]:
        entries = {}
        for old_paths in backptrs[-1].keys():
            # Distribute paths incoming to i onto its neighbors
            if not silent:
                print("  Pushing {}".format(old_paths))
            for new_paths, dist in \
                    old_paths.push(v, graph.labeled_neighborhood(v)):
                # make sure the sets of paths that were pushed along each
                # edge sum to the proper flow value.  If not, don't create a
                # new table entry for this path set.
                for arc, pathset in dist:  # Paths pathset coincide on arc
                    success = globalconstr.add_constraint(pathset, arc)
                    if success is None:
                        break
                else:
                    if new_paths not in entries:
                        entries[new_paths] = old_paths

        # add the new entries to the list of backpointers
        backptrs.append(entries)

    if not silent:
        print("\nDone.")
        for bp in backptrs:
            print(bp)

    # recover the paths
    full_paths = [[deque(), weight] for weight in weights]
    try:
        # the "end" of the DP is all paths passing through the sink
        # conf = PathConf(graph.sink(), allpaths)
        conf = list(backptrs[-1].keys())[0]
        # iterate over the backpointer list in reverse
        for table in reversed(backptrs):
            for v in conf:
                # get the paths crossing this vertex
                incidence = conf[v]
                # vertices might repeat in consecutive table entries if an edge
                # is "long" wrt the topological ordering.  Don't add it twice
                # to the path lists in this case.
                for p in incidence:
                    arc_used = conf.arcs_used[p]
                    if arc_used == -1:
                        break
                    if len(full_paths[p][0]) == 0 or \
                            full_paths[p][0][0] != arc_used:
                        full_paths[p][0].appendleft(arc_used)
            # traverse the pointer backwards
            conf = table[conf]
    except KeyError as e:
        raise Exception("The set of weights is not a valid solution") from e

    return full_paths

<filename>toboggan/dp.py
#! /usr/bin/env python3
#
# This file is part of Toboggan, https://github.com/TheoryInPractice/Toboggan/,
# and is Copyright (C) North Carolina State University, 2017. It is licensed
# under the three-clause BSD license; see LICENSE.
#
# python libs
from collections import defaultdict, deque

# local imports
from toboggan.flow import Constr, SolvedConstr, PathConf


def solve(instance, silent=True, guessed_weights=None):
    """
    Find a feasible set of weights consistent with guessed_weights.

    guessed_weights is a sorted tuple of size k in which any of the entries
    might be None.  If guessed_weights is k integers, check whether this
    solution works.  If any entry of guessed_weights is None, check whether a
    solution exists with each None replaced by a integer that respects the
    sorted order of the tuple.
    """
    graph = instance.graph
    k = instance.k

    # The only constraint a priori is the total flow value
    globalconstr = Constr(instance)
    guessed_weights = [None]*k if not guessed_weights else guessed_weights

    assert len(guessed_weights) == k
    for index, guess in enumerate(guessed_weights):
        if guess is None:
            continue
        globalconstr = globalconstr.add_constraint([index], (0, guess))
        if globalconstr is None:
            return set()

    # Build first DP table
    old_table = defaultdict(set)
    allpaths = frozenset(range(k))
    # All k paths `end' at source
    old_table[PathConf(graph.source(), allpaths)] = set([globalconstr])
    if not silent:
        print("After processing edge into s, table is:")
        print(old_table)

    # run dynamic progamming
    for v in instance.ordering[:-1]:
        new_table = defaultdict(set)
        for paths, constraints in old_table.items():
            # Distribute paths incoming to i onto its neighbours
            if not silent:
                print("  Pushing {}".format(paths))
            for newpaths, dist in paths.push(v, graph.labeled_neighborhood(v)):
                # if not silent:
                    # print("  Candidate paths", newpaths)
                debug_counter = 0
                for constr in constraints:
                    # print("  Combining w/ constraints", constraints)
                    # Update constraint-set constr with new constraints imposed
                    # by our choice of pushing paths o..........es (as
                    # described by dist)
                    curr_constr = constr
                    try:
                        for e, p in dist:  # Paths p coincide on edge e
                            updated_constr = curr_constr.add_constraint(p, e)
                            if updated_constr is not None:
                                curr_constr = updated_constr
                            else:
                                break
                        else:
                            # WORRY ABOUT THIS EVENTUALLY
                            if constr.rank == curr_constr.rank or \
                                    not curr_constr.is_redundant():
                                # Add to DP table
                                new_table[newpaths].add(curr_constr)
                    except ValueError as err:
                        print("Problem while adding constraint", p, e)
                        raise err
        # replace tables
        old_table = new_table

    if not silent:
        print("\nDone.")
        print("Table is:")
        print(new_table)

    candidates = new_table[PathConf(graph.sink(), allpaths)]
    return candidates


def recover_paths(instance, weights, silent=True):
    """Recover the paths that correspond to the weights given."""
    graph = instance.graph
    k = instance.k

    if not silent:
        print(graph)

    # since we know all the weights, we can stored them as a solved constraint
    # system
    globalconstr = SolvedConstr(weights, instance)

    assert len(weights) == k
    allpaths = frozenset(range(k))

    # Build DP table, which will map path configurations to the path
    # configurations in the previous tables that yielded the specific entry
    # All k paths start at the source vertex
    initial_entries = {PathConf(graph.source(), allpaths): None}
    backptrs = [initial_entries]

    # Run DP
    for v in instance.ordering[:-1]:
        entries = {}
        for old_paths in backptrs[-1].keys():
            # Distribute paths incoming to i onto its neighbors
            if not silent:
                print("  Pushing {}".format(old_paths))
            for new_paths, dist in \
                    old_paths.push(v, graph.labeled_neighborhood(v)):
                # make sure the sets of paths that were pushed along each
                # edge sum to the proper flow value.  If not, don't create a
                # new table entry for this path set.
                for arc, pathset in dist:  # Paths pathset coincide on arc
                    success = globalconstr.add_constraint(pathset, arc)
                    if success is None:
                        break
                else:
                    if new_paths not in entries:
                        entries[new_paths] = old_paths

        # add the new entries to the list of backpointers
        backptrs.append(entries)

    if not silent:
        print("\nDone.")
        for bp in backptrs:
            print(bp)

    # recover the paths
    full_paths = [[deque(), weight] for weight in weights]
    try:
        # the "end" of the DP is all paths passing through the sink
        # conf = PathConf(graph.sink(), allpaths)
        conf = list(backptrs[-1].keys())[0]
        # iterate over the backpointer list in reverse
        for table in reversed(backptrs):
            for v in conf:
                # get the paths crossing this vertex
                incidence = conf[v]
                # vertices might repeat in consecutive table entries if an edge
                # is "long" wrt the topological ordering.  Don't add it twice
                # to the path lists in this case.
                for p in incidence:
                    arc_used = conf.arcs_used[p]
                    if arc_used == -1:
                        break
                    if len(full_paths[p][0]) == 0 or \
                            full_paths[p][0][0] != arc_used:
                        full_paths[p][0].appendleft(arc_used)
            # traverse the pointer backwards
            conf = table[conf]
    except KeyError as e:
        raise Exception("The set of weights is not a valid solution") from e

    return full_paths

#! /usr/bin/env python3 # # This file is part of Toboggan, https://github.com/TheoryInPractice/Toboggan/, # and is Copyright (C) North Carolina State University, 2017. It is licensed # under the three-clause BSD license; see LICENSE. # # python libs # local imports Find a feasible set of weights consistent with guessed_weights.      guessed_weights is a sorted tuple of size k in which any of the entries     might be None.  If guessed_weights is k integers, check whether this     solution works.  If any entry of guessed_weights is None, check whether a     solution exists with each None replaced by a integer that respects the     sorted order of the tuple. # The only constraint a priori is the total flow value # Build first DP table # All k paths `end' at source # run dynamic progamming # Distribute paths incoming to i onto its neighbours # if not silent: # print("  Candidate paths", newpaths) # print("  Combining w/ constraints", constraints) # Update constraint-set constr with new constraints imposed # by our choice of pushing paths o..........es (as # described by dist) # Paths p coincide on edge e # WORRY ABOUT THIS EVENTUALLY # Add to DP table # replace tables Recover the paths that correspond to the weights given. # since we know all the weights, we can stored them as a solved constraint # system # Build DP table, which will map path configurations to the path # configurations in the previous tables that yielded the specific entry # All k paths start at the source vertex # Run DP # Distribute paths incoming to i onto its neighbors # make sure the sets of paths that were pushed along each # edge sum to the proper flow value.  If not, don't create a # new table entry for this path set. # Paths pathset coincide on arc # add the new entries to the list of backpointers # recover the paths # the "end" of the DP is all paths passing through the sink # conf = PathConf(graph.sink(), allpaths) # iterate over the backpointer list in reverse # get the paths crossing this vertex # vertices might repeat in consecutive table entries if an edge # is "long" wrt the topological ordering.  Don't add it twice # to the path lists in this case. # traverse the pointer backwards