ノードにグラフデータ構造内に複数の入力があるかどうかを調べる方法は？

Question

私はStrings変調のための簡単なネットワークを作成しようとしています。

アイデアは、ネットワークの出力は、最後の実行モジュールの出力です。
モジュールは何らかの方法で配置できます。モジュールを入力として接続する必要がある場合は、入力を合計する必要があります（文字列の連結）。

これを実装するには、グラフのデータ構造としてネットワークを表現することを考えています。

モジュールが入力として2つの接続を持っていると判断する方法は何ですか（結果として入力する前に2つの出力を合計することができます）。

グラフをトラバースするためにどのようなアルゴリズムを使用しますか？幅優先？

ネットワークを表す優れたソリューションはありますか？ [疑似コードが高く評価されました]

Answer 1

隣接関係リスト（「このノードはこれらのノードを指しています）」としてグラフを保存している場合は、隣接リストを繰り返してA→B （ "このノードはこれらのノードによってポイントされています）"という逆隣接リストを作成します。

さらに詳しい情報：this article

EDIT：

あなたの図から、隣接リストは次のようになります。

A -> [B, C] 
B -> [D] 
C -> [D] 
D -> [] 

これはMap<Node, Collection<Node>>として表すことができます。ペアをとってマップを更新するメソッドを書くには、connectと呼んでください。構造体を構築するには、connect(A, B)、connect(A, C)、connect(B, D)、connect(C, D)と呼ぶでしょう。

反転するには、反転構造を保持する新しいマップを作成します。マップ内の各キーを繰り返し、リスト内の各値を反復し、引数が逆の逆構造のconnectを呼び出します。

Answer 2

これは、幅優先と深さ優先の両方で実装できます。私は深さ優先のアルゴリズムを投稿します：

public class Node { 

    private List<Node> parents = new ArrayList<Node>(); 
    private List<Node> children = new ArrayList<Node>(); 
    private Map<Node, String> receivedMessages = new HashMap<Node, String>(); 
    private String id = ""; 

    public Node(String id) { 
     this.id = id; 
    } 

    void processMessage(Node sender, String message) { 
     if (parents.contains(sender)) 
      receivedMessages.put(sender, message); 

     // if all the parents sent the message 
     if (receivedMessages.size() == parents.size()) { 
      String newMessage = composeNewMessage(receivedMessages); 

      if (children.size() == 0) // if end node or "leaf" 
       ouputResult(this, newMessage); 
      else { 
       for (Node child : children) { 
        child.processMessage(this, newMessage); 
       } 
      } 
     } 
    } 

    public void addParent(Node parent) { 
     if (parent != null) 
      parents.add(parent); 
     parent.children.add(this); 
    } 

    public void addChild(Node child) { 
     if (child != null) 
      children.add(child); 
     child.parents.add(this); 
    } 

    private void ouputResult(Node node, String newMessage) { 
     // TODO: implement 
    } 

    private String composeNewMessage(Map<Node, String> receivedMessages2) { 
     // TODO: implement 
     return ""; 
    } 

    public static void main(String[] args) { 
     Node A = new Node("A"); 
     Node B = new Node("B"); 
     Node C = new Node("C"); 
     Node D = new Node("D"); 
     Node start = new Node("start"); 
     Node end = new Node("end"); 
     A.addParent(start); 
     B.addParent(A); 
     C.addParent(A); 
     D.addParent(B); 
     D.addParent(C); 
     end.addParent(D); 
     A.processMessage(start, "Message"); 
    } 
}