Библиотека Java с поддержкой проблемы изоморфизма подграфа?

Question

Я пытаюсь проанализировать использование "#include" в файлах C (что включено в первую очередь, зависимости ...).

Для этого я извлекаю из файла C "#include" и строю график. Я хотел бы определить общие закономерности на этом графике ...

Пока что я использую JGraphT в качестве графического движка (не уверен, что это правильное выражение) и JGraph для рендеринга (однако использование jgraph немного проблематично, поскольку макеты больше не включены в бесплатную версию).

Мне не удалось найти поддержку изоморфизма в jgrapht. Знаете ли вы какое-либо решение, обеспечивающее такую ​​поддержку (что-то вроде igraph, но для java) ..?

Я использую Java 1.5, и предлагаемое решение должно быть бесплатным ...

Answer 1

Вы смотрели на Parsemis ?

Это библиотека анализа графов Java, и (суб) изоморфизм графов является основополагающим для этого процесса, поэтому я предполагаю, что они каким-то образом решают эту проблему.

Хотя не уверен насчет лицензии, но я считаю, что это открытый исходный код, так как он был разработан для академических целей.

Answer 2

Не уверен, что один из них способен на изоморфизм, но я собрал пару ссылок на механизмы разметки графов в своем блоге: http://blog.pdark.de/2009/02/11/graph-layout-in-java/

Возможно, вы захотите взглянуть и на graphviz . Это не Java, но имеет очень мощный механизм компоновки.

Что касается изоморфизма: вам, вероятно, нужно проверять шаблоны только на уровне 0 (т. Е. Прямые включения), потому что все, что ниже, должно быть изоморфным по определению (все файлы, включенные некоторыми включаемыми файлами, всегда будут одинаковыми, если кто-то не использовал много #if магии в разделе включений).

Answer 3

Я точно не знаю конкретной библиотеки графов с кодом изоморфизма подграфа - поскольку она известна как NP-полная, вы ничего не можете сделать, кроме поиска в любом случае. Это часто проявляется в схемах переписывания графиков, поэтому AGG может помочь.

Answer 4

Похоже, что несколько месяцев назад в "экспериментальном" пакете JGraphT было упомянуто упоминание об изоморфизме , но, видимо, документации нет.

Сравнение изоморфизма является фундаментальным требованием в программном обеспечении для хеминформатики (технически это мономорфизм , который используется). Атомы являются «узлами», а связи - «ребрами». Молекулярные графики являются ненаправленными и могут быть циклическими. Доступно несколько библиотек хеминформатики с открытым исходным кодом, написанных на Java. Вы можете найти некоторые подсказки для решения вашей проблемы, посмотрев эти библиотеки.

Например, я написал лицензированную BSD библиотеку хеминформатики под названием MX , которая реализует алгоритм мономорфизма на основе VF . Я написал высокоуровневый обзор того, как был реализован алгоритм, и вы можете просмотреть исходный код для пакета сопоставления в моем репозитории GitHub. Большая часть работы выполняется в классе DefaultState .

MX также включает быстрый исчерпывающий детектор колец и другие графические манипуляции, которые могут быть применимы к вашей проблеме.

Answer 5

В последнее время я сам размышлял над этой проблемой (в моем случае я искал общие структуры разметки для преобразования JSP в теги).

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

• Я планировал исследовать метод, который математическое программное обеспечение использует для аналитической оценки интегралов в задачах исчисления. В этом случае существует множество известных структурных шаблонов, и рассматриваемая проблема должна соответствовать одному из известных шаблонов. Лучший способ сделать это не всегда очевиден, потому что это зависит от того, какие термины сгруппированы и т. Д.

• Алгоритмы, используемые в биологии для поиска соответствующих структур в двух сложных молекулах, также могут быть адаптированы к этой проблеме.