JUNG очень полнофункциональный, поэтому, если в JUNG нет алгоритма анализа графиков для того, что вам нужно, обычно есть веская теоретическая причина для этого.Для меня ваша проблема звучит как пример проблемы изоморфизма подграфа, которая является NP-Complete:
http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem
NP-Полнота может быть или не быть знакомой вам (потребовалосьмне 7 лет в колледже и степень магистра в области компьютерных наук, чтобы понять это!), поэтому я дам описание высокого уровня здесь.Определенные проблемы, такие как сортировка, могут быть решены за полиномиальное время относительно их входного размера.Например, если у меня есть список N элементов, я могу отсортировать его по времени O ( N log ( N )).Более конкретно, если я могу решить проблему за полиномиальное время, это означает, что я могу решить проблему, не исчерпывая все возможные решения.В случае сортировки я мог обойти каждую возможную перестановку списка и, если нашел перестановку списка, который был отсортирован, вернуть его.Это, очевидно, не самый быстрый способ решить проблему!Некоторые очень умные математики смогли довести его до теоретического минимума O ( N log ( N )), таким образом, мы можем довольно быстро отсортировать действительно большие списки вещей, используя компьютеры сегодня.
С другой стороны, проблемы NP-Complete считаются не имеющими решения за полиномиальное время (я говорю думал , потому что никто никогда не доказывал это, хотядоказательства убедительно свидетельствуют, что это так).В любом случае, это означает, что вы не можете окончательно решить проблему NP-Complete, не исчерпав заранее все возможные решения.Временная сложность задач NP-Complete всегда равна O ( c ^ N ) или хуже , где c - некоторая константа, большая чем1. Это означает, что время, необходимое для решения проблемы, растет экспоненциально с каждым постепенным увеличением размера проблемы.
Так, как это связано с моей проблемой ???
Я имею в виду, что если проблема изоморфизма подграфа является NP-полной, то единственный способ определить, является ли один граф подграфом другого графа, состоит в исчерпании всех возможныхрешение.Таким образом, вы можете решить эту проблему, но, вероятно, только до графов из нескольких узлов или около того (поскольку сложность времени задачи растет экспоненциально с каждым постепенным увеличением размера графа).Это означает, что вычислительно неосуществимо , чтобы вычислить решение для вашей проблемы, потому что, как только вы достигнете определенного размера графика, для поиска решения потребуется буквально целая вечность.
Более практично, если ваш босс просит вас сделать что-то, что доказуемо NP-Complete, вы можете просто сказать, что это невозможно, и ему придется выслушать вас.Если ваш профессор попросит вас сделать что-нибудь доказуемо NP-Complete, покажите ему, что это NP-Complete, и вы, вероятно, получите A за курс.Если вы пытаетесь сделать что-то NP-Complete по собственному желанию, лучше просто перейти к следующему проекту ...;)