Adaptagrams
Classes | Enumerations | Functions | Variables
dialect Namespace Reference

libdialect: A library for computing human-like orthogonal network (DiAlEcT) layouts. More...

Classes

class  ACALayout
 Implements the Adaptive Constrained Alignment (ACA) algorithm. More...
 
struct  AestheticBend
 A bend point deliberately added to a connector route, for aesthetic reasons. More...
 
struct  Arrangement
 Represents the arrangement of all Nbrs around a centre node. More...
 
struct  Assignment
 Represents an assignment of nbrs to semiaxes, and records the cost of this assignment. More...
 
struct  BendSequence
 A data structure for managing sequences of bend types, points at which these bends should occur (in a given Chain), cost of such a sequence of bends (for a given Chain), and incoming and outgoing Compass directions, for non-cycles. More...
 
struct  BoundingBox
 A bounding box, given by the extreme coordinates. More...
 
class  Chain
 A Chain is a sequence of degree-2 Nodes, possibly forming a cycle. More...
 
struct  ColaGraphRep
 Bundles those data structures required in order to represent a Graph in libcola, and to map infomration between the libcola and libdialect representations. More...
 
struct  ColaOptions
 Provides a simple way to set any or all of the various optional arguments to libcola layout methods. More...
 
class  Edge
 The Edge class represents edges in a graph. More...
 
struct  EdgeSegment
 Represents an axis-aligned segment of an orthogonal connector route. More...
 
class  ExpansionGoal
 The ExpansionGoal class. More...
 
class  ExpansionManager
 The ExpansionManager class. More...
 
class  Face
 Represents a single face of a 4-planar, orthogonal layout. More...
 
class  FaceSet
 
class  GhostNode
 A GhostNode represents another Node. More...
 
class  Graph
 The Graph class represents graphs consisting of nodes and edges. More...
 
class  LeaflessOrthoRouter
 Does a special orthogonal routing in a graph having no leaves, ensuring that at least two distinct sides of every node are used as connection points. This is useful if we later wish to planarise the layout, since it ensures that no node will become a leaf in that process. More...
 
struct  Matrix2d
 Dense 2d array, with integer indices. More...
 
struct  Nbr
 Represents a neighbouring node to a central node. More...
 
class  NearbyObjectFinder
 
class  Nexus
 
class  Node
 The Node class represents nodes in a graph. More...
 
struct  NodeBuckets
 
struct  NodeIdCmp
 Useful for set operations on Node lookups. More...
 
class  OrthoHubLayout
 A layout object that tries to orthogonalise hubs. This means it visits nodes of degrees 3 or higher, and tries to set their neighbours in cardinal compass directions from it. More...
 
struct  OrthoHubLayoutOptions
 Options to control OrthoHubLayout. More...
 
class  OrthoPlanariser
 
class  PeeledNode
 A PeeledNode is a type of GhostNode, used in the peeling process. More...
 
struct  Projection
 
class  ProjSeq
 
struct  Quad
 Represents a quadrant, relative to a central node. More...
 
struct  RoutingAdapter
 Adapter to easily apply libavoid::Routers to libdialect::Graphs. More...
 
struct  SepCo
 
struct  SepPairSubConstraintInfo
 
class  Side
 A side of a Face. E.g. a rectangular Face has four Sides: north, south, east, and west. More...
 
struct  Stem
 Represents a leaf node, along with its one edge and neighbour. More...
 
class  TreePlacement
 

Enumerations

enum  LinkShape
 
enum  GapType { GapType::CENTRE, GapType::BDRY }
 
enum  SepDir { SepDir::EAST , SepDir::RIGHT }
 
enum  SepType { SepType::NONE, SepType::EQ, SepType::INEQ }
 
enum  SepTransform {
  SepTransform::ROTATE90CW, SepTransform::ROTATE90ACW, SepTransform::ROTATE180, SepTransform::FLIPV,
  SepTransform::FLIPH, SepTransform::FLIPMD, SepTransform::FLIPOD
}
 
enum  TreeRoutingType
 
enum  ExpansionEstimateMethod
 
enum  RouteProcessing { RouteProcessing::NONE, RouteProcessing::RECORD, RouteProcessing::REFINE_AND_RECORD }
 Control how much processing should be done on connector routes by the RoutingAdapter. More...
 

Functions

LinkShapes bentLinkShapeCwFromStartingPt (LinkShape start)
 Get the bent LinkShapes, in clockwise order, starting from a given one.
 
std::vector< std::vector< LinkShape > > lookupMinimalBendSeqs (Node_SP A, CardinalDir d0, Node_SP Z, CardinalDir d1)
 Look up the minimal bend sequences for a Chain. More...
 
CardinalDirs possibleCardinalDirections (Node_SP node1, Node_SP node2)
 List the possible cardinal directions from node1 to node2, if they were to be aligned non-aggressively.
 
LinkShape shapeOfLink (Node_SP link)
 Determine the LinkShape for a given Node of degree 2. More...
 
Chains buildAllChainsInGraph (std::shared_ptr< dialect::Graph > graph)
 Convenience method to build all the chains and cycles in a graph.
 
void doHOLA (dialect::Graph &G, const dialect::HolaOpts &holaOpts, dialect::Logger *logger=nullptr)
 Apply the HOLA layout algorithm to the given Graph. See Steve Kieffer, Tim Dwyer, Kim Marriott, and Michael Wybrow. HOLA: Human-like Orthogonal Network Layout. IEEE Transactions on Visualization and Computer Graphics 22, no. 1 (2016): 349-358. More...
 
void doHOLA (dialect::Graph &G)
 Convenience function to do HOLA layout with default options. More...
 
std::shared_ptr< GraphbuildGraphFromTglf (std::istream &in)
 Build a Graph object from TGLF. More...
 
std::shared_ptr< GraphbuildGraphFromTglf (std::string &s)
 Build a Graph object from TGLF. More...
 
std::shared_ptr< GraphbuildGraphFromTglfFile (const std::string &filepath)
 Build a Graph object from a file containing TGLF. More...
 
void writeStringToFile (const std::string &s, const std::string &filepath)
 Write a string to a file. More...
 
AlignmentFlag operator & (AlignmentFlag a, AlignmentFlag b)
 Thanks to https://stackoverflow.com/a/1448478.
 
double manhattan (Node_SP u, Node_SP v)
 Report the "Manhattan distance" between two nodes.
 
size_t doNearAlignments (dialect::Graph &graph, dialect::AlignmentTable &atab, dialect::NodesById &ignore, const dialect::HolaOpts &opts, bool reattempt=false)
 Look for nodes that are nearly aligned, and try to align them. More...
 
PeeledNode_SP identifyRootNode (const Graph &graph)
 Mark as "root" the PeeledNode having largest serial number. More...
 
std::vector< Stem_SP > makeStemsFromLeaves (const NodesById &leaves)
 Make a Stem object to represent each leaf.
 
Trees peel (Graph &G)
 Perform the "peeling" process, in which the exterior trees are removed from the given Graph. More...
 
bool CompareActiveEvents (Event *a, Event *b)
 
std::vector< std::string > lookupQuadActions (size_t p, size_t q, size_t r, size_t s, size_t c)
 Look up legal quad actions. More...
 
FaceSet_SP reattachTrees (Graph_SP core, Trees trees, HolaOpts opts, Logger *logger=nullptr)
 Given a planar orthogonal core, and the corresponding Trees (as resulting from the peeling process), choose Faces of the core in which to place the Trees, generate constraints to expand those Faces, and insert large Nodes to represent the bounding boxes of the Trees.
 
TreePlacement_SP chooseBestPlacement (TreePlacements tps, HolaOpts opts)
 Choose the best TreePlacement from among a list of alternatives.
 
bool logically_equal (double a, double b, double error_factor=1.0)
 Tolerant equality test for doubles. Generates principled value for tolerance. More...
 
bool approx_equal (double a, double b, double tol=0.000001)
 Tolerant equality test for doubles. Uses arbitrary tolerance.
 
template<typename ... Args>
std::string string_format (const std::string &format, Args ... args)
 String formatting. More...
 
template<typename T >
std::vector< std::vector< T > > partition (std::vector< T > items, std::function< double(T)> key, double tolerance=0)
 Partition a vector of items according to a key value. More...
 

Variables

const LinkShapes bentLinkShapeCw
 The bent LinkShapes, in clockwise order:
 
const std::map< LinkShape, std::map< CardinalDir, CardinalDir > > applyBendToDir
 
const std::map< LinkShape, CardinalDir > cwIncomingDirForBend
 
const std::map< CompassDir, std::map< CardinalDir, std::map< CardinalDir, std::vector< std::vector< LinkShape > > > > > minimalBendSeqs
 
const std::vector< unsigned > SEMIAXIS_SETS_BY_CARDINALITY [5]
 

Detailed Description

libdialect: A library for computing human-like orthogonal network (DiAlEcT) layouts.

This header defines tools for working with the "chains", i.e. maximal subgraphs composed entirely of "links" (nodes of degree 2), in 4-planar orthogonal layouts.

Enumeration Type Documentation

◆ ExpansionEstimateMethod

When expanding faces in order to make room to place the trees, there are different ways to estimate which is the best dimension in which to operate first.

SPACE: Look at the available space in each dimension. CONSTRAINTS: Compute the separation constraints you would use in each dimension, and sum their violations.

◆ GapType

enum dialect::GapType
strong
Enumerator
CENTRE 

Gap between the centres of two nodes:

BDRY 

Gap between the opposite boundaries of two nodes:

◆ LinkShape

enum dialect::LinkShape
strong

In a 4-planar orthogonal layout, a link has one of six possible shapes, depending on which two of its four sides are the ones where its edges meet it. For example, if one edge enters from the south, and the other from the east, then this link is shaped like the top-left corner of a box. This enum names the six possible configurations.

◆ RouteProcessing

Control how much processing should be done on connector routes by the RoutingAdapter.

Enumerator
NONE 

Don't do anything.

RECORD 

Record the connector routes in the Edges, exactly as returned by the Router.

REFINE_AND_RECORD 

Record the connector routes in the Edges after first doing post-processing to remove extremely small S-bends.

◆ SepDir

enum dialect::SepDir
strong
Enumerator
EAST 

Cardinal constraints imply both a separation and an alignment:

RIGHT 

Lateral constraints imply only a separation:

◆ SepTransform

enum dialect::SepTransform
strong
Enumerator
ROTATE90CW 

Rotate 90 degrees clockwise.

ROTATE90ACW 

Rotate 90 degrees anticlockwise.

ROTATE180 

Rotate 180 degrees.

FLIPV 

Flip over vertical axis.

FLIPH 

Flip over horizontal axis.

FLIPMD 

Flip over the "main diagonal" i.e. the axis whose slope is positive in the graphics plane. This goes from upper left to lower right, since in the graphics plane the positive y-axis points downward.

FLIPOD 

Flip over the "off diagonal".

◆ SepType

enum dialect::SepType
strong
Enumerator
NONE 

No constraint:

EQ 

An exact separation:

INEQ 

A minimal separation:

◆ TreeRoutingType

When routing connectors for Trees, the set of allowed connection directions depends on the application.

In, for example, a NORTH-growing tree, an edge between ranks i and i + 1 will always be allowed to connect only to the south (S) port of a node in rank i + 1.

The TreeRoutingType controls the directions allowed for connection to nodes in rank i, as follows:

STRICT: only N is allowed. CORE_ATTACHMENT: N, E, W are allowed for the root node if it has exactly one child and is transversely displaced from its one child; otherwise only N. MONOTONIC: N, E, W are allowed for all nodes on rank i.

Function Documentation

◆ buildGraphFromTglf() [1/2]

std::shared_ptr<Graph> dialect::buildGraphFromTglf ( std::istream &  in)

Build a Graph object from TGLF.

Parameters
[in]inAn istream containing TGLF.
Returns
A Graph built on the given TGLF.

Referenced by buildGraphFromTglf().

Here is the caller graph for this function:

◆ buildGraphFromTglf() [2/2]

Graph_SP dialect::buildGraphFromTglf ( std::string &  s)

Build a Graph object from TGLF.

Parameters
[in]inA string containing TGLF.
Returns
A Graph built on the given TGLF.

References buildGraphFromTglf().

Here is the call graph for this function:

◆ buildGraphFromTglfFile()

std::shared_ptr<Graph> dialect::buildGraphFromTglfFile ( const std::string &  filepath)

Build a Graph object from a file containing TGLF.

Parameters
[in]filepathFull filesystem path to a file containing TGLF.
Returns
A Graph built on the given TGLF.

◆ CompareActiveEvents()

bool dialect::CompareActiveEvents ( Event *  a,
Event *  b 
)

We need a special function for comparing Events, using a positive tolerance. Here's why. Suppose vertical segment A has its south end at (0, 0), and horizontal segment B has its east end at (0, -0.00000000001). This means that /technically/ A and B intersect. However (http://xkcd.com/1475/) you probably don't actually want to treat this as an intersection. The comparison function is designed so that, when the list of active events is sorted, the "close" event for segment A will come /before/ the "sustain" event for segment B, instead of the other way around, as dictated by their exact y-coordinates. This way we will /not/ detect an intersection between A and B.

◆ doHOLA() [1/2]

void dialect::doHOLA ( dialect::Graph G,
const dialect::HolaOpts &  holaOpts,
dialect::Logger *  logger = nullptr 
)

Apply the HOLA layout algorithm to the given Graph. See Steve Kieffer, Tim Dwyer, Kim Marriott, and Michael Wybrow. HOLA: Human-like Orthogonal Network Layout. IEEE Transactions on Visualization and Computer Graphics 22, no. 1 (2016): 349-358.

Parameters
[in,out]GThe Graph to be laid out. Node positions are updated in-place. Constraints are set in the Graph's SepMatrix.
[in]optsOptions controlling the layout.
[out]loggerOptional pointer to a Logger in which to record TGLF for various stages of the layout process. Useful for debugging.

References dialect::OrthoHubLayoutOptions::avoidFlatTriangles, buildAllChainsInGraph(), dialect::ACALayout::createAlignments(), doNearAlignments(), dialect::Graph::getIEL(), dialect::Graph::getNumEdges(), dialect::Graph::getNumNodes(), dialect::BoundingBox::h(), dialect::OrthoHubLayout::layout(), dialect::ColaOptions::logger, dialect::ColaOptions::nodeClusters, Avoid::nudgeOrthogonalSegmentsConnectedToShapes, Avoid::nudgeSharedPathsWithCommonEndPoint, Avoid::OrthogonalRouting, dialect::Graph::padAllNodes(), peel(), dialect::OrthoPlanariser::planarise(), dialect::ColaOptions::preventOverlaps, reattachTrees(), dialect::RoutingAdapter::route(), dialect::LeaflessOrthoRouter::route(), dialect::RoutingAdapter::router, Avoid::Router::setRoutingOption(), dialect::ColaOptions::solidEdgeExemptions, dialect::ColaOptions::solidifyAlignedEdges, string_format(), dialect::ACALayout::updateGraph(), dialect::ColaOptions::useMajorization, dialect::ColaOptions::useNeighbourStress, dialect::BoundingBox::w(), vpsc::XDIM, and vpsc::YDIM.

Referenced by doHOLA().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ doHOLA() [2/2]

void dialect::doHOLA ( dialect::Graph G)

Convenience function to do HOLA layout with default options.

Parameters
[in,out]GThe Graph to be laid out. Node positions are updated in-place. Constraints are set in the Graph's SepMatrix.

References doHOLA().

Here is the call graph for this function:

◆ doNearAlignments()

size_t dialect::doNearAlignments ( dialect::Graph graph,
dialect::AlignmentTable &  atab,
dialect::NodesById &  ignore,
const dialect::HolaOpts &  opts,
bool  reattempt = false 
)

Look for nodes that are nearly aligned, and try to align them.

Parameters
[in,out]graphThe Graph whose nodes are to be aligned, and in whose SepMatrix alignments should be recorded when made.
[in,out]atabAn AlignmentTable for the given Graph.
[in]optsHolaOpts object to set parameters for the process.
[in]reattemptSet true for a more aggressive process that reattempts alignments even after they have been marked infeasible (in case other changes in the meantime might have made them now feasible). Default: false.
Returns
Number of successful alignments.

References vpsc::XDIM, and vpsc::YDIM.

Referenced by doHOLA().

Here is the caller graph for this function:

◆ identifyRootNode()

PeeledNode_SP dialect::identifyRootNode ( const Graph graph)

Mark as "root" the PeeledNode having largest serial number.

Note
The Graph must contain only PeeledNodes.
Returns
The PeeledNode identified as root.

References dialect::Graph::getNode(), dialect::Graph::getNodeLookup(), and dialect::Node::setIsRoot().

Referenced by peel().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ logically_equal()

bool dialect::logically_equal ( double  a,
double  b,
double  error_factor = 1.0 
)
inline

Tolerant equality test for doubles. Generates principled value for tolerance.

Note
Thanks to: https://stackoverflow.com/a/4010279

◆ lookupMinimalBendSeqs()

std::vector< std::vector< LinkShape > > dialect::lookupMinimalBendSeqs ( Node_SP  A,
CardinalDir  d0,
Node_SP  Z,
CardinalDir  d1 
)

Look up the minimal bend sequences for a Chain.

Parameters
[in]AThe left anchor Node of the Chain.
[in]d0The CardinalDir in which the chain departs from Node A.
[in]ZThe right anchor Node of the Chain.
[in]d1The CardinalDir in which the chain enters Node Z (i.e. the CardinalDir from the last Node of the Chain toward the right anchor Node).
Returns
Vector of vectors of LinkShapes, giving all possible minimal bend sequences for this Chain.
Note
This does work correctly even for the case of a chain in which the left and right anchor nodes are the same (as, e.g., in a figure-8 network).

References minimalBendSeqs.

Referenced by dialect::Chain::computePossibleBendSequences().

Here is the caller graph for this function:

◆ lookupQuadActions()

vector< string > dialect::lookupQuadActions ( size_t  p,
size_t  q,
size_t  r,
size_t  s,
size_t  c 
)

Look up legal quad actions.

Parameters
[in]p= 0, 1, or 2, indicating whether there are 0, 1, or >= 2 nodes in the first quadrant
[in]qlike p, only for the second quadrant
[in]rlike p, only for the third quadrant
[in]slike p, only for the fourth quadrant
[in]cbinary coded representation of which semiaxes are to be used: 1's bit: 1 if EAST is to be used; else 0 2's bit: 1 if SOUTH is to be used; else 0 4's bit: 1 if WEST is to be used; else 0 8's bit: 1 if NORTH is to be used; else 0
Returns
vector of strings, naming the legal quad actions

Referenced by dialect::Arrangement::computeNAssignments().

Here is the caller graph for this function:

◆ partition()

template<typename T >
std::vector<std::vector<T> > dialect::partition ( std::vector< T >  items,
std::function< double(T)>  key,
double  tolerance = 0 
)

Partition a vector of items according to a key value.

Parameters
[in]itemsThe vector of objects of type T that are to be partitioned.
[in]keyA function returning a floating point key value on objects of type T.
[in]toleranceIf positive, put items into the same part provided their key is within tolerance of a running average key value for that part.
Note
As a by-product, each part will be sorted in ascending order according to the given key function.
Returns
vector of vectors of objects of type T.

◆ peel()

Trees dialect::peel ( Graph G)

Perform the "peeling" process, in which the exterior trees are removed from the given Graph.

Note
See Abello, James, Frank Van Ham, and Neeraj Krishnan. "Ask-graphview: A large scale graph visualization system." IEEE transactions on visualization and computer graphics 12 no. 5 (2006): 669-676.
The given Graph is modiifed in place. It will be pared down to its own /core/ – i.e. all that remains after the trees have been peeled away.

Each tree includes a root node which is a copy of a node that remains in the core.

The underlying Graphs of the created Trees consist of PeeledNodes.

In the case that the given Graph is itself a tree, the remaining core will consist only of the tree's root node. Meanwhile the one Tree will be a copy of the entire original graph.

Returns
The trees.

References dialect::Graph::getNode(), identifyRootNode(), dialect::Graph::isEmpty(), makeStemsFromLeaves(), dialect::NodeBuckets::severNodes(), and dialect::NodeBuckets::takeLeaves().

Referenced by doHOLA().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ shapeOfLink()

LinkShape dialect::shapeOfLink ( Node_SP  link)

Determine the LinkShape for a given Node of degree 2.

Parameters
[in]linkThe link whose shape is to be determined.
Returns
The LinkShape for the given node.
Exceptions
Runtimeerror if the given node is not of degree 2.

Referenced by dialect::Chain::Chain().

Here is the caller graph for this function:

◆ string_format()

template<typename ... Args>
std::string dialect::string_format ( const std::string &  format,
Args ...  args 
)

◆ writeStringToFile()

void dialect::writeStringToFile ( const std::string &  s,
const std::string &  filepath 
)

Write a string to a file.

Parameters
[in]sthe string to be written
[in]filepathfull filesystem path to the file to be written

Variable Documentation

◆ applyBendToDir

const map< LinkShape, map< CardinalDir, CardinalDir > > dialect::applyBendToDir
Initial value:
{
{LinkShape::TLC, { {CardinalDir::NORTH, CardinalDir::EAST}, {CardinalDir::WEST, CardinalDir::SOUTH} }},
{LinkShape::TRC, { {CardinalDir::NORTH, CardinalDir::WEST}, {CardinalDir::EAST, CardinalDir::SOUTH} }},
{LinkShape::BRC, { {CardinalDir::SOUTH, CardinalDir::WEST}, {CardinalDir::EAST, CardinalDir::NORTH} }},
{LinkShape::BLC, { {CardinalDir::SOUTH, CardinalDir::EAST}, {CardinalDir::WEST, CardinalDir::NORTH} }}
}

Lookup table: Given one of the four bent LinkShapes b, and a CardinalDir d, return the CardinalDir you would be going if you came into bend b going in direction d, and then followed the bend.

Referenced by dialect::Chain::writeConfigSeq().

◆ cwIncomingDirForBend

const map< LinkShape, CardinalDir > dialect::cwIncomingDirForBend
Initial value:
{
{LinkShape::TLC, CardinalDir::NORTH},
{LinkShape::TRC, CardinalDir::EAST},
{LinkShape::BRC, CardinalDir::SOUTH},
{LinkShape::BLC, CardinalDir::WEST}
}

Lookup table: For any of the four bent LinkShapes, return its clockwise incoming CardinalDir. In other words, if you were going clockwise around a box, which direction would you be going when you entered this bend?

Referenced by dialect::Chain::writeConfigSeq().

◆ minimalBendSeqs

const map< CompassDir, map< CardinalDir, map< CardinalDir, vector< vector< LinkShape > > > > > dialect::minimalBendSeqs

Lookup table: Suppose you have a chain starting at node A and ending at node Z. Let c be the CompassDir from Z to A (which will be cardinal if A and Z are aligned, else ordinal). Suppose as we traverse the chain from A toward Z we must depart A going in CardinalDir d0, and must enter Z going in CardinalDir d1. Then by looking up (c, d0, d1) in this table, we get a vector of vectors of LinkShapes, giving all possible minimal bend sequences for this chain.

Note: Whereas d0 gives both the direction from which we depart node A AND the side of A from which we depart, d1 is the direction we travel as we enter node Z (and therefore is the OPPOSITE of the side of Z at which we enter). For example d1 = EAST means we are traveling east as we enter node Z (but we enter it on its west side).

Referenced by lookupMinimalBendSeqs().

◆ SEMIAXIS_SETS_BY_CARDINALITY

const std::vector<unsigned> dialect::SEMIAXIS_SETS_BY_CARDINALITY[5]
Initial value:
= {
{0},
{1, 2, 4, 8},
{3, 5, 9, 6, 10, 12},
{14, 13, 11, 7},
{15}
}

Using the binary coding for vacant semiaxes described in the doctext for the lookupQuadActions function, each integer 0, 1, ..., 15 describes a subset of the set of all semiaxes. It is useful to have these subset codes sorted by cardinality of the set.

Referenced by dialect::Arrangement::computeNAssignments().