Skip to content

Home

Jump to bottom
John M. Boyer edited this page Mar 1, 2022 · 24 revisions

Introduction

This source code project provides a library for implementing graph algorithms as well as implementations of several planarity-related graph algorithms. The origin of this project is the reference implementation for the Edge Addition Planarity Algorithm, which is now the fastest and simplest linear-time method for planar graph embedding and planarity obstruction isolation (i.e. Kuratowski subgraph isolation). This project includes implementations of:

There has been successful technology transfer into other projects of this project's code or algorithms, including:

Software Component and Source Code Overview

Wrapper Application

The planarity.exe application provides menu and command-line methods to simplify accessing the functionality of the planarity-related algorithms offered by the APIs of this source code project. It includes the following components and files:

  • Main Program & Menu User Interface (planarity.c, planarity.h)
  • Command-Line Interface (planarityCommandLine.c)
  • Randomly Generate and Process Graphs (planarityRandomGraphs.c)
  • Read and Process a Specific Graph (planritySpecificGraph.c)
  • Low-Level Application Utilities & Definitions (planarityUtils.c, platformTime.h)

Core Planarity Algorithms

The core edge addition planarity algorithm is provided by the following components and source files:

  • Planar & Outerplanar Graph Embedders (graphEmbed.c)
  • Planarity & Outerplanarity Obstruction Detection and Isolation (graphNonplanar.c, graphIsolator.c, graphOuterplanarObstructions.c)
  • Planarity Preprocessing Algorithms (graphDFSUtils.c)

Ancillary Algorithm Modules

There are a number of supporting data structures and methods, as follows:

  • Public API Declarations, Graph Data Structure Definitions, Basic Graph Operations (graph.h, graphStructures.h, appconst.h, graphUtils.c)
  • Graph Reading/Writing (graphIO.c)
  • List Collection Data Structure (listcoll.c, listcoll.h)
  • Stack Data Structure (stack.c, stack.h)
  • String Buffer Data Structure (strbuf.c, strbuf.h)
  • Check Correctness of Core and Extension Algorithm Outputs (graphTests.c)
  • Extension Mechanism (graphExtensions.c, graphExtensions.h, graphExtensions.private.h, graphFunctionTable.h)

Extension Algorithms

The core planarity algorithm can be augmented to solve several planarity-related problems. Based on the extension mechanism, the following additional algorithms are implemented:

  • Planar Graph Drawing (graphDrawPlanar_Extensions.c, graphDrawPlanar.c, graphDrawPlanar.h, graphDrawPlanar.private.h)
  • Search for Subgraphs Homeomorphic to K2,3 (graphK23Search_Extensions.c, graphK23Search.c, graphK23Search.h, graphK23Search.private.h)
  • Search for Subgraphs Homeomorphic to K4 (graphK4Search_Extensions.c, graphK4Search.c, graphK4Search.h, graphK4Search.private.h)
  • Search for Subgraphs Homeomorphic to K3,3 (graphK33Search_Extensions.c, graphK33Search.c, graphK33Search.h, graphK33Search.private.h)

Compile-Time Parameters of the Library

Public API Methods and Definitions (versus Non-Public Methods)

The convention used in the source code to indicate a public API method is to prefix its name with gp (graph public) and then an underscore (see graph.h). Non-public methods have a leading underscore but not the gp prefix. To optimize performance, several public API methods that perform low-level graph operations are defined to be inline (see graphStructure.h).

Speed Macros

By default, several public API methods are provided as inline definitions in release mode compilation and as function calls in the debug compilation. This enables optimal performance in release mode and facilitates isolating and stepping into the code with a debugger. This behavior can be changed by amending the SPEED_MACROS definition in appconst.h.

Optimization of 1-Based Array Indexing

The graph data structure in this implementation uses arrays to store information about vertices and edges. In the default configuration of the source code, 1-based array indexing is used rather than the implementation language's normal 0-based array indexing. In the code, the constant NIL is used like a null pointer to set the initial value of an array index variable when it isn't yet indicating any particular vertex or edge. The original implementation used 0-based indexing, but several frequently used, low-level methods are more efficient if NIL is defined to be 0. Since NIL is 0, vertex and edge information is stored in arrays at positions greater than 0, not at position 0.

Before this implementation was optimized with 1-based array indexing, an earlier version used 0-based array indexing. To test the code with 0-based array indexing, uncomment the 0-based array indexing definitions of NIL and NIL_CHAR in appconst.h.

When the source code is compiled in the default 1-based configuration, input text files containing graphs in the adjacency list format can use both 1-based and the older 0-based numbering for vertices. The samples directory contains several input test files in both formats, such as Petersen.txt (1-based) and Petersen.0-based.txt. The application method runSpecificGraphTests() in planarityCommandLine.c is invoked in response to the command-line planarity.exe -test, and it runs the quick regression tests on both the 1-based and the 0-based test files in the samples directory when the source code is compiled in the default 1-based configuration.

The graph API includes methods that immunize vertex and edge iteration loops from changes between 1-based and 0-based array indexing. See Introduction to the Graph API below for further details.

The Default Edge Limit and How to Change It

As a default that is easy to override at compile-time and at run-time, a graph with N vertices may have up to 3N edges. This ensures that, by default, planarity-related algorithms operate in O(N) time even on dense graphs with more than O(N) edges. For other graph algorithms, a different edge limit may be preferred. At compile-time, an alternative factor of N other than 3 can be set by changing the constant DEFAULT_EDGE_LIMIT in graphStructures.h. However, it is easier to set any alternative edge limit (not just a factor of N) at run-time by using gp_EnsureArcCapacity(). The term arc is used because each edge is represented by two arc records, one in each of the adjacency lists of each of the two vertices incident with the edge. For example, the arc limit can be set so that all edges of a complete graph on N vertices can be fully represented.

Introduction to the Graph API

Creating and Reading or Building a Graph

To begin working with graphs, create an instance of the graph data structure using gp_New(), like this:

#include "graph.h"
...
graphP theGraph = gp_New();

As an optional step, you can configure the newly allocated graph structure with a maximum number of edges higher than the default of 3N edges, where N is the number of vertices. If you know the maximum number of edges M that you would like to set, and then pass 2*M to gp_EnsureArcCapacity(). The number is double because each edge is represented by two arcs, one for each endpoint vertex of the edge. It is more efficient to set a higher limit before using gp_InitGraph() or gp_Read() because the limit is changed without having to copy anything to larger arrays.

The last step in getting a graph ready to process is to either use gp_Read() to read vertices and edges from a file or use gp_InitGraph() to make an empty graph with N vertices and then use invocations of methods such as gp_AddEdge() to add edges. For an example of using gp_Read(), see the implementation of SpecificGraph() in planaritySpecificGraph.c. For an example of using gp_AddEdge(), see the implementation of gp_CreateRandomGraph() in graphUtils.c.

Vertex Array Iteration

After a graph has been created and then built or read from a file, your program will have a reference to the in-memory graph instance with a variable, such as theGraph variable above. The code sample below shows the preferred method for iterating through the vertices sequentially to do some processing. As a simple example of vertex array iteration, this code sums across all vertices all of the outbound edges leading away from all vertices. This excludes edges that are inbound only and includes directed edges that lead away from a vertex as well as undirected edges that are inbound and outbound:

sumOutDegrees = 0;
for (v = gp_GetFirstVertex(theGraph); gp_VertexInRange(theGraph, v); v++) {
    sumOutDegrees += gp_GetVertexOutDegree(theGraph, v);
}

The API methods gp_GetFirstVertex() and gp_VertexInRange() help to immunize the loop from changes between 1-based versus 0-based array indexing.

The main vertex array V in the graph data structure is created to contain 2N vertex records, N for representing the vertices of the graph, and an additional N vertex records to represent virtual vertices. Virtual vertices are used to create extra copies of vertices for algorithm-specific purposes. For example, the planarity-related algorithms in this project use virtual vertices to help represent cut vertices in the multiple biconnected components that contain them. The iteration pattern above loops through the first N non-virtual vertices of the graph. The iteration pattern for processing virtual vertices is the same, except you would instead use gp_GetFirstVirtualVertex() and gp_VirtualVertexInRange(). For an easy code sample that shows both iteration loops, please see _ClearVertexVisitedFlags() in graphUtils.c.

Edge Array Iteration and Adjacency List Iteration

Each edge of a graph is represented by a pair of arc records stored consecutively in edge array E in the graph data structure. By using array indices as pointers, the arcs are arranged into doubly linked lists called adjacency lists, which are are associated with vertices in a manner described below. Since an edge (v, w) has endpoints v and w, the adjacency list of vertex v contains an arc record indicating vertex w, and the adjacency list of w contains the twin arc that indicates the index of vertex v.

To process all edges incident to a vertex v, a loop can be used to iterate v's adjacency list. To continue the example in the prior example, we can take a look at the loop construct in the implementation of gp_GetVertexOutDegree() that is in graphUtils.c:

degree = 0;
e = gp_GetFirstArc(theGraph, v);
while (gp_IsArc(e))
{
     if (gp_GetDirection(theGraph, e) != EDGEFLAG_DIRECTION_INONLY)
         degree++;
     e = gp_GetNextArc(theGraph, e);
}

Each vertex record contains pointers to (indices of) the first and last arcs in its adjacency list. The loop initialization uses gp_GetFirstArc() to obtain the first arc pointing to a neighbor of a vertex v. The while loop body is performed if the index e indicates a valid arc in the edge array, and the end of the loop body uses gp_GetNextArc() to enable iteration through each arc in the adjacency list. The method returns NIL as the next arc after the last arc in the adjacency list of v, at which point the loop terminates. The method gp_GetDirection() is used to ensure that each edge adds to the outward degree count if it is either undirected or directed outward from v, but not if it is an inward edge that only leads into v from a neighbor vertex w.

To process all edges (pairs of arcs) in the edge array, the following iteration pattern should be used:

EsizeOccupied = gp_EdgeInUseIndexBound(theGraph);
for (e = gp_GetFirstEdge(theGraph); e < EsizeOccupied; e+=2)
{
    if (gp_EdgeInUse(theGraph, e)) {
        // Process arc e and its twin returned by gp_GetTwinArc(theGraph, e)
    }
}

Since the allocated edge array may be larger than needed for the number of edges in the graph, the variable EsizeOccupied is used to store the calculated result of the inline method that returns the index boundary for edge records that are in use. The gp_GetFirstEdge() and gp_EdgeInUseIndexBound() methods help to immunize loops to changes between 1-based versus 0-based array indexing. The gp_EdgeInUse() method helps the loop to skip edge records that are not in use, which can occur if gp_DeleteEdge() has been used. Processing an edge may involve doing work on both a given arc e and its twin arc, which is obtained using gp_GetTwinArc().

Undirected versus Directed Graphs

The current graph API supports input, representation, and output of both undirected and directed graphs, even though the original uses cases of the planarity-related algorithm require only undirected graphs. Digraph input is supported by gp_Read() in the adjacency list format. When reading the adjacency list of a vertex v, the occurrence of a vertex index w is interpreted as an outward directed edge from v to w, so v's adjacency list receives an arc containing w's index that is flagged with EDGEFLAG_DIRECTION_OUTONLY, and w's adjacency list receives an arc containing v's index that is flagged with EDGEFLAG_DIRECTION_INONLY. If, in a later reading of the adjacency list of w, there appears the index of v, then the direction flags on both arcs are cleared to indicate that the edge is undirected. Therefore, in terms of representation, it is legitimate to traverse an edge from v to w if the arc containing w has no direction flag setting or if it is set to EDGEFLAG_DIRECTION_OUTONLY, but not if the direction flag is set to EDGEFLAG_DIRECTION_INONLY. Digraph output is supported by gp_Write() in the adjacency list format in a manner consistent with edge traversal. When outputting the adjacency list for a vertex v, the method gp_Write() will output w for an arc containing w if the arc has no direction flag set or if the flag is set to EDGEFLAG_DIRECTION_OUTONLY.

The Planarity-Related Algorithm Pattern

The high-level pattern for planarity-related algorithms is as follows:

  • Create an empty graph data structure with gp_New(),
  • Read a graph with gp_Read() or build it with gp_InitGraph() and gp_AddEdge() as described in the section above,
  • Call gp_Embed() with the embedding flags for the desired planarity-related algorithms,
    • Process the OK (embeddable) or NONEMBEDDABLE return result
    • Optional: Process and output the modified graph with gp_SortVertices() and gp_Write()
  • Release the graph data structure with gp_Free(), or reuse it by calling gp_ReinitializeGraph()

The gp_Embed() method processes an input graph as if it is undirected because the decision about whether edges will cross in an embedding is unrelated to their direction. Although it is possible to read or build a digraph, the implementation of gp_Embed() just ignores the edge direction flags. This includes underlying planarity pre-processing methods such as gp_CreateDFSTree(). When writing other graph applications that are not planarity-related, some utility methods such as gp_CreateDFSTree() are public because they may be still useful, but in these cases the application author may need to write their own similar implementation if alternative behavior is required. For example, depth first search on an undirected graph is provided by gp_CreateDFSTree(), but a similar alternative implementation would be required for depth first search on a digraph.

A set of embedding flags is available to help control the specific planarity-related algorithm that gp_Embed() executes. See GetEmbedFlags() in planarityUtils.c for various flags that you can currently use, including the following:

  • EMBEDFLAGS_PLANAR for planarity testing, embedding, and obstruction isolation;
  • EMBEDFLAGS_OUTERPLANAR for outerplanarity testing, embedding, and obstruction isolation;
  • EMBEDFLAGS_DRAWPLANAR to execute an extension function set that enables gp_Embed() to calculate a visibility representation and a textual rendering of a planar graph;
  • EMBEDFLAGS_SEARCHFORK23 to execute an extension function set that enables gp_Embed() to determine if a graph contains a subgraph homeomorphic to K2,3 and, if so, returns it;
  • EMBEDFLAGS_SEARCHFORK4 to enable an extension that enables gp_Embed() to determine if a graph contains a subgraph homeomorphic to K4 and, if so, returns it; and
  • EMBEDFLAGS_SEARCHFORK33 to execute an extension function set that enables gp_Embed() to determine if a graph contains a subgraph homeomorphic to K3,3 and, if so, returns it.

The method SpecificGraph() in planaritySpecificGraph.c expresses a variation of this high-level pattern with a few notable differences:

  • After creating the empty graph data structure with gp_New(), if an extension function set for a planarity-related algorithm is to be used, then an appropriate extension function set is attached dynamically to the graph data structure;
  • After a graph is read from a file with gp_Read(), it is duplicated using gp_DupGraph() so that the graph modifications made by gp_Embed() can be tested for correctness;
  • The modifications to the graph made by gp_Embed() are tested for correctness using gp_TestEmbedResultIntegrity(). The tests performed are specific to the algorithm executed and the embedding result.
  • During pre-processing steps within gp_Embed(), the method gp_CreateDFSTree() is invoked, followed by invoking gp_SortVertices() to convert the graph from its original index order into order by depth first search indices. Within the implementation pattern of SpecificGraph() in planaritySpecificGraph.c, the method gp_SortVertices() is called again, just prior to invoking gp_Write(), to convert the graph back to the original index order. This makes it easier to compare the contents of the input and output files.

Developing Graph Algorithms Using Extensions

The Graph API in this project offers an extension mechanism to enable the development of graph algorithms that require additional data to be associated each vertex, each edge, and the graph. This includes general graph algorithms as well as planarity-related algorithms, including those that augment the core edge addition planarity algorithm. Several extensions for planarity-related algorithms are included in this project. By convention, an extension consists of four components:

  • graphExtensionName.h: public declarations of methods called outside of the extension code. This includes any new public API methods as well as the methods that attach and detach the algorithm extension data structure and function overload methods to and from the core graph data structure. As illustrated in SpecificGraph() in planaritySpecificGraph.c, the attach method is called just after invoking gp_New() if the application needs to use the extension algorithm, and the detach method is called automatically by gp_Free().
  • graphExtensionName_Extensions.c: implementations of the extension attachment and detachment methods as well as function overloads that extend core graph processing and core planarity methods.
  • graphExtensionName.private.h: private, extension-specific data structure and method declarations
  • graphExtensionName.c: extension-specific method implementations. This may include private that are called from the extension's function overloads of core graph processing and core planarity methods as well as additional public methods directly callable by applications. An extension may have no additional public methods if it is only augmenting the behavior of an existing graph API method, such as gp_Embed().

The K3,3 search extension can be examined as an example of the four components above. The graphK33Search.h header file declares the attachment and detachment methods and no other public methods because the extension extends the behaviors of the existing API method gp_Embed(). In the implementation of gp_AttachK33Search() in graphK33Search_Extension.c, the K3,3 context data structure is created and associated with the graph data structure using gp_AddExtension(). The virtual function pointer table of the K3,3 context is also initialized to point to overload methods for several non-public methods invoked by gp_Embed() to perform parts of the core planarity algorithm processing model. There are also a few more overloads that help ensure that other public APIs for initialization and reinitialization of a graph’s vertex and edge information also include initializing or reinitializing of the additional information associated with vertices and edges by the K3,3 search extension.

Implementations of several function overloads appear directly in graphK33Search_Extension.c, but the main behavior of K3,3 search as distinct from and an extension of the core edge addition planarity algorithm appears in graphK33Search.c. The main extension behavior is rooted by the _SearchForK33InBicomp() method, which is declared in graphK33Search.private.h so it can be included in graphK33Search_Extension.c and invoked from the overload method _K33Search_HandledBlockedBicomp().

The method _K33Search_HandledBlockedBicomp() is invoked by gp_Embed() when it calls the method pointed to by the function table’s fpHandleBlockedBicomp pointer, which was initialized to point to _K33Search_HandledBlockedBicomp() in gp_AttachK33Search(). The method simply invokes _SearchForK33InBicomp() if gp_Embed() has received the algorithm flag indicating that it should search for a subgraph homeomorphic to K3,3. During execution of the core planarity algorithm by gp_Embed(), there is obviously no subgraph homeomorphic to K3,3 as long as the graph remains planar as edges are added. However, when the edge addition planarity algorithm is blocked from embedding an edge due to information stored in the external face vertices of a biconnected component (bicomp), then the core planarity algorithm has found an obstruction to planarity. The obstruction is a subgraph homeomorphic to either K3,3 or K5, as these are the two obstructions to planarity (Kuratowski’s theorem). The extension behavior in _SearchForK33InBicomp() either isolates the subgraph homeomorphic to either K3,3, if found, or it unblocks the biconnected component if it only contains a subgraph homeomorphic to K5 so that the extended planarity algorithm can continue embedding edges. The extended algorithm continues embedding edges and unblocking any subgraphs homeomorphic to K5 either until a subgraph homeomorphic to K3,3 is found or until all edges of the original graph has been embedded without finding a subgraph homeomorphic to K3,3.

Clone this wiki locally