Common and useful Graph functions?

Question

Hi,

I'm implementing a simple Graph library for my uni project and since this is the first time I'm dealing with graphs, I would like to know which functions you guys consider to be most common and useful for Graph implementations...

So far, I have this:

• graphInitialize()
• graphInsertVertex()
• graphRemoveVertex()
• graphGetVertex()
• graphGetVertexValue() (not implemented yet, not sure if I'll need it)
• graphInsertEdge()
• graphRemoveEdge()
• graphLinkVertices() (this calls graphInsertEdge twice for bidirectional graph)
• graphUnlinkVertices() (this calls graphRemoveEdge twice for bidirectional graph)
• graphDestroy()

I know I'm missing a function do determine the shortest path, but I'm leaving that for last...

Do you think I'm missing any common/useful function?

Answer 1

In general:

• getVertexCount
• getEdgeCount
• transposeGraph (reverse all edges)
• getEdgeWeight
• setEdgeWeight

More algorithmic stuff:

• countConnectedComponents
• countStronglyConnectedComponents
• computeAllPairsShortestPath
• computeShortestPath(source, sink)
• computeSingleSourceShortestPath(source)
• computeMaxFlow(source, sink)
• isTree
• isBipartite
• isAcyclic
• topologicSort
• getDiameter
• getPrincipleVertex

... this could go on forever.

Answer 2

A few other things to consider:

• Adding attributes to a node or edge, such as a weighting.
• What type of graph are you creating? Directed, undirected etc...
• Maybe methods to give you some general information about the graph? Node count, edge count etc
• Can i get the degree of a node easily?
• Can you check if a node or edge are already in the graph?

I would recommend taking a look at some other graph libraries. Here are a few:

• JUNG - Java
• Networkx - Python
• Boost Graph Library - C++

Answer 3

As a side note, if you're writing your library in an OOP style, then you can drop the "graph" prefix on all of your methods as it would be redundant. Otherwise, if this is a procedural library, then you may want to define a namespace.

Answer 4

What you may find useful entierly depends on what you're going to use the library for...

A few more things you might find useful-

• a function which returns all of the edges which touch a vertex
• a function which returns all of the vertices which are connected to a vertex with one edge
• dikjstra algorithm

Some applications require that every edge or vertex would have a certain property such as distance or weight. Ofcourse you can always add more and more members to your Edge and Vertex class but there are ways to do it generically without cluttering your classes with stuff you might not need to use.