Как правильно определить решение графа зависимостей

Question

Я создал класс, который берет ориентированный граф, вершину этого графа и выводит приемлемую последовательность вершин, ведущую к этой вершине.

например.

• А-> В
• A-> C
• B-> D
• C-> D

Две возможные последовательности для вершины D:

• A-> B-> C-> D
• A-> C-> B-> D

Теперь мне нужно разработать тест, чтобы определить, является ли решение, которое дает моя программа, правильным.

Есть идеи?

Answer 1

Вы можете использовать алгоритм, основанный на Cyclomatic Complexity , чтобы вычислить количество путей, которые должны быть найдены, что было бы хорошей проверкой работоспособности - особенно если у вас очень большой график, получая точно правильный количество путей было бы обнадеживающим (хотя это и не является гарантией правильности самих путей!). В общем, количество ребер минус количество узлов - вы увидите нюансы на этой странице википедии.

Answer 2

Ваша проблема довольно распространена.По сути, есть два похожих и простых способа справиться с этим:

• поместить последовательности узлов в набор и проверить размер набора и содержит ли он все последовательности

• сортирует последовательности в соответствии с некоторым известным алгоритмом (например, сравнивая один узел за другим).Теперь порядок всегда один и тот же.

В Java это будет означать:

• реализовать equals и hashCode для последовательностиузлы (если это что-то вроде List<Node>, вместо них реализуйте equals и hashCode для Node) и поместите их в HashSet.Затем просто проверьте, имеет ли набор правильный размер и содержит ли они оба пути.

• составляют последовательность узлов Comparable и сортируйте их.Тогда порядок всегда известен и фиксирован.В вашем случае просто сравните соответствующие узлы один за другим.