Как определить, имеет ли узел более одного входа в структуре данных графа?

Question

Я пытаюсь создать простую сеть для строковой модуляции.

Идея состоит в том, что вывод сети - это вывод последнего выполненного модуля.
Модули могутбыть организованы любым способом, и если модуль должен подключаться как вход, вход должен быть суммирован (конкатенация строк).

Чтобы реализовать это, я думаю представить сеть в виде структуры данных графа.

Что меня сейчас блокирует, так это то, как определить, что модуль имеет два соединения в качестве входа (поэтому я смогу суммировать два выхода до подачи результата в качестве входа)?

Какой алгоритм использовать для обхода графа?в ширину?

Есть ли лучшее решение для представления сети?[псевдокод высоко ценится]

Answer 1

Вы можете реализовать это как в ширину, так и в глубину.Я опубликую алгоритм глубины:

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");
    }
}

Answer 2

Если вы храните график в виде списка смежности («Этот узел указывает на эти узлы»), то вы можете просто перебрать список смежности и поменять местами пары A -> B на B -> A, создавсписок обратной смежности («На этот узел указывают эти узлы»).

Подробнее в этой статье .

РЕДАКТИРОВАТЬ:

На вашей диаграмме список смежности будет:

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 в инвертированной структуре с обратными аргументами.