内部参照と可能な循環参照を含む階層データ構造を解析する方法は？

Question

私はユーザーロールを設定するためのGUIを実装しています。ここで、アプリケーションの管理者は入れ子になったロールを定義することができます。この特定の場合のロールは、単純なキーと値のペア、ロールを識別するキー、および現在のロールが拡張する「子ロール」またはアプリケーションの一部へのパスのいずれかで定義されます。ここでは可能な構造のいくつかの任意の例は以下のとおりです。

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など）は高く評価されています（アルゴリズムが正しいとします）。

Answer 1

以下のコードはこのトリックを行う必要があります。単純なパーサを用意して、 '=>'記号の左と右の値を解析し、以下のFlatten.update()メソッドに渡す必要があります。

コードは2つの段階で動作します。「::パス」と宣言したパスのリストに各ロールのマッピングを作成します）

1として宣言親役割のリスト「拡張::」

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 => [] 
    } 
} 

希望上記のコードのための簡単なテストです。