topological.py

# -*- coding: utf-8 -*-
from __future__ import unicode_literals
from itertools import chain


AGGREGATES_DEPENDENCIES = {
    "revenuePerUser": ["sumRevenue", "visits"],
    "ctr": ["clicks", "shows"],
    "cpc": ["budget", "clicks"],
    "GoalsMetrics.cpa": ["budget", "sumGoalReachesAny"],
    "GoalsMetrics.conversion": ["sumGoalReachesAny", "visits"]
}

CALCULATED_FIELDS = [
    "revenuePerUser", "ctr", "cpc", "shows",
]

from itertools import chain


def dfs(start_node, get_adj_func, visited=None):
    '''
    Обход в глубину. Генератор вершин.

    Args:
        start_node: начальная вершина
        get_adj_func: (node) -> list of nodes -- функция, выдающая список
            соседних с нодой вершин
    '''

    if visited is None:
        visited = set()

    def visit_recur(node, visited):
        if node in visited:
            return
        yield node
        visited.add(node)
        for node in get_adj_func(node):
            if node not in visited:
                for other_node in visit_recur(node, visited):
                    yield other_node
    for node in visit_recur(start_node, visited):
        yield node


def get_deps(column, deps_map):
    '''
    Возвращает список зависимостей колонки
    '''
    return deps_map.get(column, [])


def resolve_dependencies(columns, deps_map, dfs_func=dfs):
    '''
    Возвращает список колонок с добавленными зависимостями.

    Не следит за циклами в графе зависимостей. Предполагает, что их нет

    Args:
        columns: ['col1', 'col2']
        deps_map: {
            'col1': ['col2', 'col3']
        }
    Returns:
        ['col1', 'col2', 'col3']
    '''
    get_adj_func = lambda node: get_deps(node, deps_map)
    seen = set()
    return list(chain.from_iterable(
        dfs_func(col, get_adj_func, seen) for col in columns))


def resolve_deps_with_toposort(columns, deps_map):
    '''
    Возвращает список колонок с добавленными зависимостями в
    порядке топологической сортировки. Чуть медленее, чем без сортировки.

    Не следит за циклами в графе зависимостей. Предполагает, что их нет

    Args:
        columns: ['col1', 'col2']
        deps_map: {
            'col1': ['col2', 'col3']
        }
    Returns:
        ['col3', 'col2', 'col1']
    '''

    reverse_dfs = lambda *args, **kwargs: reversed(list(dfs(*args, **kwargs)))
    return resolve_dependencies(columns, deps_map, reverse_dfs)

columns = [1, 7]

deps = {
    1: [2, 3],
    2: [3, 4],
    3: [4, 5, 6],
    4: [5, 6],
    6: [10006],
    7: [101, 102],
    102: [1]}

if __name__ == '__main__':
    # columns = resolve_dependencies(CALCULATED_FIELDS, AGGREGATES_DEPENDENCIES)
    # print list(topological_sort(columns, AGGREGATES_DEPENDENCIES))
    print resolve_deps_with_toposort(CALCULATED_FIELDS, AGGREGATES_DEPENDENCIES)