Skip to content

Home

Jump to bottom
John M. Boyer edited this page Sep 30, 2020 · 29 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 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)
  • 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

Speed Macros

By default, the source code is configured to provide several public API methods as inline (i.e. speed macros) in release mode compilation and as function calls in the debug compilation. 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 nodes, 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 node 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.
  • 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; and

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.
Clone this wiki locally