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< Graph > | buildGraphFromTglf (std::istream &in) |
| Build a Graph object from TGLF. More... | |
| std::shared_ptr< Graph > | buildGraphFromTglf (std::string &s) |
| Build a Graph object from TGLF. More... | |
| std::shared_ptr< Graph > | buildGraphFromTglfFile (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
|
strong |
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
|
strong |
◆ 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
|
strong |
Control how much processing should be done on connector routes by the RoutingAdapter.
◆ SepDir
|
strong |
◆ SepTransform
|
strong |
◆ SepType
|
strong |
◆ TreeRoutingType
|
strong |
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] in An istream containing TGLF.
- Returns
- A Graph built on the given TGLF.
Referenced by buildGraphFromTglf().
◆ buildGraphFromTglf() [2/2]
| Graph_SP dialect::buildGraphFromTglf | ( | std::string & | s | ) |
Build a Graph object from TGLF.
- Parameters
-
[in] in A string containing TGLF.
- Returns
- A Graph built on the given TGLF.
References buildGraphFromTglf().
◆ buildGraphFromTglfFile()
| std::shared_ptr<Graph> dialect::buildGraphFromTglfFile | ( | const std::string & | filepath | ) |
◆ 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] G The Graph to be laid out. Node positions are updated in-place. Constraints are set in the Graph's SepMatrix. [in] opts Options controlling the layout. [out] logger Optional 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().
◆ doHOLA() [2/2]
| void dialect::doHOLA | ( | dialect::Graph & | G | ) |
◆ 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] graph The Graph whose nodes are to be aligned, and in whose SepMatrix alignments should be recorded when made. [in,out] atab An AlignmentTable for the given Graph. [in] opts HolaOpts object to set parameters for the process. [in] reattempt Set 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().
◆ 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().
◆ logically_equal()
|
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] A The left anchor Node of the Chain. [in] d0 The CardinalDir in which the chain departs from Node A. [in] Z The right anchor Node of the Chain. [in] d1 The 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().
◆ 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] q like p, only for the second quadrant [in] r like p, only for the third quadrant [in] s like p, only for the fourth quadrant [in] c binary 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().
◆ partition()
| 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] items The vector of objects of type T that are to be partitioned. [in] key A function returning a floating point key value on objects of type T. [in] tolerance If 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().
◆ shapeOfLink()
| LinkShape dialect::shapeOfLink | ( | Node_SP | link | ) |
Determine the LinkShape for a given Node of degree 2.
- Parameters
-
[in] link The link whose shape is to be determined.
- Returns
- The LinkShape for the given node.
- Exceptions
-
Runtime error if the given node is not of degree 2.
Referenced by dialect::Chain::Chain().
◆ string_format()
| std::string dialect::string_format | ( | const std::string & | format, |
| Args ... | args | ||
| ) |
String formatting.
- Note
- Thanks to: https://stackoverflow.com/a/26221725
Referenced by doHOLA(), dialect::OrthoHubLayout::layout(), reattachTrees(), dialect::BoundingBox::repr(), dialect::LeaflessOrthoRouter::route(), dialect::Assignment::toString(), dialect::Edge::writePolylineConnectorData(), dialect::Edge::writeRoundedOrthoConnectorData(), dialect::Graph::writeSvg(), and dialect::Node::writeSvg().
◆ writeStringToFile()
| void dialect::writeStringToFile | ( | const std::string & | s, |
| const std::string & | filepath | ||
| ) |
Write a string to a file.
- Parameters
-
[in] s the string to be written [in] filepath full filesystem path to the file to be written
Variable Documentation
◆ applyBendToDir
| const map< LinkShape, map< CardinalDir, CardinalDir > > dialect::applyBendToDir |
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 |
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] |
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().
