Как проанализировать иерархическую структуру данных, содержащую внутренние ссылки и возможные циклические ссылки? - PullRequest
Новая
       9

Как проанализировать иерархическую структуру данных, содержащую внутренние ссылки и возможные циклические ссылки?

0 голосов
/ 30 декабря 2010

Я реализую графический интерфейс для настройки пользовательских ролей, где администратор приложения имеет возможность определять вложенные роли. Роли в этом конкретном случае определяются простыми парами ключ-значение, ключом, идентифицирующим роль, и значением является либо «дочерняя роль», которую расширяет текущая роль, либо путь к некоторой части приложения. Вот несколько произвольных примеров возможных структур: 

user => path::/articles/read
user => path::/settings/edit/my

moderator => extend::user
moderator => path::/articles/edit

siteadmin => extend::moderator
siteadmin => extend::some-other-role
siteadmin => path::/user/ban

Как видите, роли могут быть вложенными, и одна роль может расширять несколько ролей.

Моя цель -

  • обнаружить и предупредить о круговом ссылки, вызванные расширением ролей
  • выравнивает всю структуру данных, так что правила будут содержать только «путь» определения типов.

Как бы вы подошли к этой проблеме? Я реализую это в php, но приветствуется любое решение (псевдокод, java и т. Д.) (Если алгоритм правильный).

1 Ответ

1 голос
/ 30 декабря 2010

Код ниже должен помочь. Вам нужно будет предоставить простой синтаксический анализатор для разбора значений слева и справа от знака '=>' и передать его методу Flatten.update() ниже.

Код работает в два этапа:

1) Создание сопоставления для каждой роли со списком путей, объявленных с помощью «path ::», и списком родительских ролей, объявленных с помощью «exte ::»

2) Выровняйте все пути для каждой роли, обходя отображение, сохраняя карту всех посещенных родительских узлов, чтобы избежать циклических зависимостей. 

class ChildValue {
    Set<String> paths = new HashSet<String>();
    Set<String> extend = new HashSet<String>();
}

/*
 * Logic to flatten interpret and flatten out
 * roles data
 */
class Flatten {
    // logical mapping store
    Map<String, ChildValue> mapping = new HashMap<String, ChildValue>();

    // Stage 1. Build logical mappin
    //
    // Call this method for every "role" => "path::/path" or "extend::role" pair
    void update(String roleName, String value) {
        ChildValue child = mapping.get(roleName);
        if (null == child) {
            // create new child node
            child = new ChildValue();
            mapping.put(roleName, child);
        }

        if (value.startsWith("path::")) {
            String path = value.substring(6);
            child.paths.add(path);
        } else {// assume "extend::"
            String extend = value.substring(8);
            child.extend.add(extend);
        }
    }

    // Stage 2.
    // After the mapping is build, call this method to
    // find all flattened paths for the role you need
    Set<String> getPathsFor(String roleName) {
        Set<String> visited = new HashSet<String>();
        return getPathsFor(roleName, visited);
    }

    // this method is called recursively
    private Set<String> getPathsFor(String roleName, Set<String> visited) {
        Set<String> paths = new HashSet<String>();
        ChildValue child = mapping.get(roleName);
        if (child != null) {
            // first add all paths directly declared with "path::"
            paths.addAll(child.paths);
            // then add all transitive paths
            for (String extendedRole : child.extend) {
                // check if parent node has not yet been visited
                // to avoid circular dependencies
                if (!visited.contains(extendedRole)) {
                    // not yet visited here, add all extended paths
                    visited.add(extendedRole);
                    paths.addAll(getPathsFor(extendedRole, visited));
                }else{
                        // node already visited, seems like we
                        // we have a circular dependency
                        throw new RuntimeException("Detected circular dep");
                }
            }
        }
        return paths;
    }
}

Вот простой тест для кода выше 

public class Roles {
    public static void main(String[] args) {
        Flatten ft = new Flatten();
        ft.update("user", "path::/path1");
        ft.update("user", "path::/path2");
        ft.update("user", "extend::parent");

        ft.update("parent", "path::/parent/path1");
        ft.update("parent", "path::/parent/path2");
        ft.update("parent", "extend::user");// circular dep

        System.out.println("paths for user => " + ft.getPathsFor("user"));
        System.out.println("paths for parent => " + ft.getPathsFor("parent"));
        System.out.println("paths for unknown => " + ft.getPathsFor("unknown"));

            //will print
            // paths for user => [/path2, /path1, /parent/path2, /parent/path1]
            // paths for parent => [/path2, /path1, /parent/path2, /parent/path1]
            // paths for unknown => []
    }
}

Надеюсь, что это отражает общую идею.

...