EPIC: Support loop edges

[john-boyer-phd]

Support the addition of a loop edge, i.e., an edge of the form (v, v). This is particularly important for many directed graph use cases.

• Both arcs of the loop edge should be added to the adjacency list of v and both would indicate v as the neighbor. The loop edge should be added as a directed edge so that only one is added to the in-degree and to the out-degree results for v.

• Amend the arc capacity limit imposed by gp_DynamicAddEdge() and gp_DynamicInsertEdge() so that the maximum capacity is N*N (assuming multiple edges are not supported or are supported using a counter rather than multiple arc pairs to represent the multiple instances of an edge between the same endpoint vertices).

• Amend various reader methods to support adding loop edges if the format supports it (such as the adjacency list format, the LEDA format, and the digraph6 format).

• Add a graph structure data member to count the number of loop edges added to the graph. The counter should be incremented upon addition by gp_AddEdge() or gp_InsertEdge() of a loop edge (which will implicitly include adding of loop edges by supporting reader methods).

• Check, with a debugger, that gp_DeleteEdge() works when deleting a loop edge as well as decrementing the loop edge counter when gp_DeleteEdge() deletes a loop edge.

• Add a new public function gp_GetLoopEdgeCount() that returns the loop edge counter value.

• Amend graph writers to issue an ErrorMessage() and return NOTOK if the format being written does not support loop edges and gp_GetLoopEdgeCount() returns a non-zero value, such as the adjacency matrix format and the graph6 format.

• Add a new public method gp_RemoveLoopEdges() that deletes all loop edges in a graph.

• Amend gp_Embed() to invoke gp_RemoveLoopEdges() if an invocation of gp_GetLoopEdgeCount() returns a value greater than 0. This should be done in the preprocessing, before embedding initialization.

• Add a smoke test that creates a planar embedding for an adjacency list formatted file to which loop edges have been added.

• Check, with a debugger, that all other methods in graphUtils and graphDFSUtils work correctly, if they need to do so, on graphs that contain loop edges, such as the methods for edge contraction and vertex identification and depth first search.