Общие и полезные функции Graph?

Question

Я реализую простую библиотеку Graph для своего универа, и так как я впервые имею дело с графиками, я хотел бы знать, какие функции вы, ребята, считаете наиболее распространенными и полезными для реализаций Graph ... .

Пока у меня есть это:

• graphInitialize ()
• graphInsertVertex ()
• graphRemoveVertex ()
• graphGetVertex ()
• graphGetVertexValue () (еще не реализовано, не уверен, понадобится ли мне это)
• graphInsertEdge ()
• graphRemoveEdge ()
• graphLinkVertices () (это вызывает graphInsertEdge дважды для двунаправленного графа) * ​​1020 *
• graphUnlinkVertices () (это вызывает graphRemoveEdge дважды для двунаправленного графа) * ​​1022 *
• graphDestroy ()

Я знаю, что мне не хватает функции, определяющей кратчайший путь, но я оставляю ее насовсем ...

Как вы думаете, я пропускаю какую-либо общую / полезную функцию?

Answer 1

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

Еще несколько вещей, которые вы можете найти полезными-

• функция, которая возвращает все ребра, которые касаются вершины
• функция, которая возвращает все вершины, которые связаны с вершиной одним ребром
• алгоритм Дикжстры

В некоторых приложениях требуется, чтобы у каждого ребра или вершины было определенное свойство, например distance или weight. Конечно, вы всегда можете добавить все больше и больше членов в ваш класс Edge и Vertex, но есть способы сделать это в общем, не загромождая ваши классы вещами, которые вам, возможно, не понадобятся.

Answer 2

Несколько других вещей для рассмотрения:

• Добавление атрибутов к узлу или ребру, например, взвешивание.
• Какой тип графика вы создаете? Направленные, ненаправленные и т.д ...
• Может быть, методы, чтобы дать вам некоторую общую информацию о графике? Количество узлов, число ребер и т. Д.
• Могу ли я легко получить степень узла?
• Можете ли вы проверить, есть ли узел или ребро на графике?

Я бы рекомендовал взглянуть на некоторые другие библиотеки графов. Вот некоторые из них:

• JUNG - Java
• Сетьx - Python
• Библиотека графов повышения - C ++

Answer 3

В целом:

• getVertexCount
• getEdgeCount
• transposeGraph (перевернуть все края)
• getEdgeWeight
• setEdgeWeight

Больше алгоритмических вещей:

• countConnectedComponents
• countStronglyConnectedComponents
• computeAllPairsShortestPath
• computeShortestPath (источник, приемник)
• computeSingleSourceShortestPath (источник)
• computeMaxFlow (источник, приемник)
• isTree
• isBipartite
• isAcyclic
• topologicSort
• getDiameter
• getPrincipleVertex

... это может продолжаться вечно.

Answer 4

В качестве примечания: если вы пишете свою библиотеку в стиле ООП, то вы можете удалить префикс «graph» во всех ваших методах, так как он будет избыточным. В противном случае, если это процедурная библиотека, вы можете определить пространство имен.