namespace primitive

Overview

Functions for generating primitive rings. More…

namespace primitive {
 
// structs
 
struct Graph;
struct Vertex;
 
// classes
 
class RingUpdater;
 
} // namespace primitive

Detailed Documentation

Functions for generating primitive rings.

This namespace contains struct definitions and functions that are used for generating primitive (shortest-path) rings (directed cyclic graphs).

The Vertex object is a collection of elements for each point, required for graph traversal. The Graph object is an object for the whole frame, containing the information of all vertices, and a row-ordered vector of vector of the rings generated.

The Franzblau shortest-path criterion has been used. The SP (shortest-path) criterion is midway between the least restrictive and most restrictive criteria in the hierarchy.

The following is the procedure for finding primitive rings:

  1. All possible rings (including non-SP) rings are found, in the primitive::countAllRingsFromIndex function, using the backtracking algorithm. This is a recursive algorithm.

  2. The non-SP rings are then removed from the list of all rings, using the Franzblau shortest path criterion (primitive::removeNonSPrings), answered by a hop-bounded breadth-first sweep per vertex.

Changelog