Я использую networkx (пакет для рисования графиков Python) http://networkx.lanl.gov/index.html для один из моих проектов. Хотя networkx довольно крут, функция отображения отстой из-за количества перекрестных краев. Есть ли способ минимизировать перекрестные ребра в графе? Я имею в виду алгоритм, который может сортировать узлы таким образом, чтобы минимизировать перекрестные ребра?
Минимизируйте перекрестные ребра на графике
comment
Вы пробовали Graphviz для рисования? Он может лучше свести к минимуму пересечения (особенно Dot, если у вас есть графы, которые он предпочитает). Какой у вас график (т. е. откуда он взялся)?
- person Jeremiah Willcock schedule 20.02.2011
comment
Я думал, что networkx использует graphviz для отображения (через pydot). Эти графики взяты из трасс сетей особого типа. Кольца больше всего пострадали :(
- person Anil Katti schedule 20.02.2011
comment
возможный дубликат планарных графических макетов
- person Dr. belisarius schedule 20.02.2011
comment
@belisarius: Вау! Я даже не помню такой...
- person schedule 20.02.2011
comment
Спасибо, Велизарий! Извините, я пропустил это.
- person Anil Katti schedule 20.02.2011
comment
@Придурок Ха! Я только сейчас понял, что вы ответили на оба :)
- person Dr. belisarius schedule 20.02.2011
Ответы (1)
Определение макета планарного графа, минимизирующего количество пересечений, является NP-трудным. См. вики-страницу номер пересечения.
Вы можете попробовать некоторые эвристики, я полагаю, что макет на основе силы довольно популярен (если я правильно помню, graphviz использует их).
Вы также можете попробовать некоторые алгоритмы приближения, вы должны найти ссылки на странице вики, на которую я ссылаюсь.
Надеюсь, это поможет.
person
Community
schedule
20.02.2011
