Я ищу функцию java, которая минимизирует количество пересечений кромок в графе.java function, которая находит граф с минимальными пересечениями края
Ввод должен быть графиком G (E [], V []), где V [] - массив всех узлов, а E [] - массив всех ребер. Выход должен представлять собой 2D-массив краевых элементов (E [] []), который содержит все пары ребер, пересекающих друг друга.
См., Например, раздел https://www.ads.tuwien.ac.at/research/graphDrawing.html «Сведение к минимуму». На рис. 3a и 3b показаны различные представления одного и того же графика. Но рис. 3b имеет минимальное количество перекрестных пересечений. Поэтому в этом конкретном случае функции outputarray должны иметь длину [1] [2] с элементами [0] [0] = «Node Green Yellow» и [0] [1] = «Node Pink Orange»
I уже посмотрел на JUNG, но я не смог найти встроенную функцию для минимизации. Большинство библиотек, выполняющих минимизацию, являются коммерческими и полностью перегружены. Я не ищу графический вывод. Мне нужно только минимальное количество перекрестных пересечений и задействованных краев.
Пожалуйста, разместите более наглядный пример того, что вы хотите – Argote
Если это взвешенный, связанный граф, то минимальное связующее дерево даст вам дерево со всеми вершинами, все еще связанными и не имеющими пересекающихся границ. Это справедливо для всех плоских графов. Если вы хотите представить непланарные графы, это немного сложнее и требует, чтобы вы находили регионы, в которые вы можете встраивать ребра (если они могут быть перемещены) или возможные области, какие края использовать на основе стоимости плохого количества, сколько регионов они пяди. –
Я должен держать все узлы и обычно не иметь планарных графов. Я реализую фермионную тензорную сеть и должен добавлять дополнительные тензоры при пересечениях линий. Поэтому я хочу добавить как можно меньше тензоров ... Это не часть вопроса, а мотивация, почему мне это нужно. – user1324005