|
|||
|
|
|
|||
|
|
Computes statistical information about a layout. More...
#include <ogdf/basic/LayoutStatistics.h>
Static Public Member Functions | |
| static ArrayBuffer< double > | angles (const GraphAttributes &ga, bool considerBends=true) |
Computes the angle for each pair of adjacent edge segments of the layout ga. | |
| static double | angularResolution (const GraphAttributes &ga) |
Computes Angular Resolution (AR) H of the nodes in the graph given, in ga. | |
| static double | aspectRatio (const GraphAttributes &ga) |
Computes Aspect Ratio (Asp) H of the layout/graph g. | |
| static double | averageFlow (const GraphAttributes &ga) |
| Calculates mean edge direction (vector) angle. | |
| static DPoint | centerOfMass (const GraphAttributes &ga) |
| Computes center of mass, where most nodes are. | |
| static double | closestPairOfPoints (const GraphAttributes &ga) |
| Computes Closest pair of points. | |
| static double | concentration (const GraphAttributes &ga) |
| Calculates the variance of node distances from the center of mass. | |
| static double | edgeLengthDeviation (const GraphAttributes &ga, EdgeArray< double > &out) |
Computes the edge length deviation H of the edges in the graph given, in ga. | |
| static EdgeArray< double > | edgeLengths (const GraphAttributes &ga, bool considerSelfLoops=false) |
Computes the edge length for each edge in the layout ga. | |
| static double | edgeOrthogonality (const GraphAttributes &ga) |
Computes Edge Orthogonality (EO) H of the graph g. | |
| static NodeArray< double > | gabrielRatio (const GraphAttributes &ga, Graph &gabrielGraphReference) |
Computes Gabriel Ratio H of the edges in the graph given, in ga and also returns new set of edges that fulfill Gabriel criteria. | |
| static double | graphArea (const GraphAttributes &ga) |
| Computes graph area (respecting node sizes), in coordinate length metric. | |
| static double | horizontalVerticalBalance (const GraphAttributes &ga, const bool vertical=false) |
| Computes horizontal node balance. | |
| static void | intersectionGraph (const GraphAttributes &ga, Graph &H, NodeArray< DPoint > &points, NodeArray< node > &origNode, EdgeArray< edge > &origEdge) |
Computes the intersection graph H of the line segments in the layout given by ga. | |
| static NodeArray< double > | neighbourhoodPreservation (const GraphAttributes &ga) |
Computes neighborhood preservation H of the edges in the graph given, in ga. | |
| static double | nodeOrthogonality (const GraphAttributes &ga, const double epsilon=1e-9) |
| Calculating percentage of nodes with integer coordinates. | |
| static double | nodeResolution (const GraphAttributes &ga) |
Computes Node Ratio H of the nodes in the graph given, in ga. | |
| static double | nodeUniformity (const GraphAttributes &ga, size_t gridWidth=10, size_t gridHeight=10) |
Computes Node Uniformity (NU) H of the graph g. | |
| static EdgeArray< size_t > | numberOfBends (const GraphAttributes &ga, bool considerSelfLoops=false) |
Computes the number of bends (i.e. bend-points) for each edge in the layout ga. | |
| static EdgeArray< size_t > | numberOfCrossings (const GraphAttributes &ga) |
Computes the number of edge crossings for each edge in the layout ga. | |
| static EdgeArray< size_t > | numberOfNodeCrossings (const GraphAttributes &ga) |
Computes the number of crossings through a non-incident node for each edge in the layout ga. | |
| static NodeArray< size_t > | numberOfNodeOverlaps (const GraphAttributes &ga) |
Computes the number of node overlaps for each node in the layout ga. | |
| static double | percentageCrossingVsMaxCrossings (const GraphAttributes &ga) |
Computes the percentage of crossings for each edge in the layout ga compared to the maximum number of crossings. | |
| static double | upwardsFlow (const GraphAttributes &ga) |
| Calculates percentage of edges that point upwards. | |
Computes statistical information about a layout.
Definition at line 49 of file LayoutStatistics.h.
|
static |
Computes the angle for each pair of adjacent edge segments of the layout ga.
Angles are given in radians.
| ga | Input layout. |
| considerBends | Determines whether bend points of edges shall be considered. |
|
static |
Computes Angular Resolution (AR) H of the nodes in the graph given, in ga.
def. Angular Resolution (AR): "After calculating the angular deviation of each edge from the ideal angle (based on degree), the AR metric calculates the mean over all nodes (excluding degree-1 nodes)." - https://www2.cs.arizona.edu/people/kobourov/gd-metrics2024.pdf
Returns a double of the angular resolution of the graph Returns 0.0 if there are no nodes with degree greater than 2, or if the graph has less than 3 nodes.
|
static |
Computes Aspect Ratio (Asp) H of the layout/graph g.
def. Aspect Ratio (Asp): "The Aspect Ratio is the ratio of the height of the drawing’s bounding box to its width (or vice versa, depending on which is greater)." - https://www2.cs.arizona.edu/people/kobourov/gd-metrics2024.pdf
Returns aspect ratio double (regarding node positions and sizes) Returns 0.0 if the graph has no nodes, or height or width of the bounding box are 0.
|
static |
Calculates mean edge direction (vector) angle.
For each edge, calculates angle of its directional vector, and returns the mean angle of all edges.
Returns degree of mean edge direction angle (as double). Returns -1.0 when graph is empty.
|
static |
Computes center of mass, where most nodes are.
def. Center Of Mass: Calculates mean position of all nodes.
Returns double pair containing center of mass coordinates. Returns a pair with (0.0, 0.0) if graph is empty. Returns a pair with (-1.0, -1.0) if graph has no nodes with valid (finite) coordinates.
|
static |
Computes Closest pair of points.
def. Closest pair of points: Finds the two nodes in the graph, that have the smallest euclidean distance to each other, and calculates their distance.
Returns euclidean distance double of two closest nodes. Returns -1.0 if graph is empty.
|
static |
Calculates the variance of node distances from the center of mass.
For each node, compute distance to center of mass, then calculate variance in all these distances.
Returns concentration nodes in graph. Returns -1.0 when graph is empty.
|
static |
Computes the edge length deviation H of the edges in the graph given, in ga.
Edge length deviation def.: The deviation of the actual edge length from the average edge length of the graph. Returns an array of edge deviations (of doubles) of all edges of the graph. Also generates a private variable with an edge length deviation average.
Source: https://www2.cs.arizona.edu/people/kobourov/gd-metrics2024.pdf
Returns an array of deviation values, of each edge (deviation of avg edge length) in the Graph
|
static |
Computes the edge length for each edge in the layout ga.
| ga | Input layout. |
| considerSelfLoops | Determines whether the lengths of self-loops are considered. |
|
static |
Computes Edge Orthogonality (EO) H of the graph g.
def. Edge Orthogonality (EO): Calculates mean of edge orthogonality deviation. "The Edge Orthogonality metric takes the mean of the angular deviation of all edges from the horizontal or vertical axis (whichever is closest)." - https://www2.cs.arizona.edu/people/kobourov/gd-metrics2024.pdf
Returns mean Edge Orthogonality of all edges
|
static |
Computes Gabriel Ratio H of the edges in the graph given, in ga and also returns new set of edges that fulfill Gabriel criteria.
Gabriel Ratio def.: The ratio of the distance between two nodes and the distance to the closest node to the edge between the two nodes, that is only allowed to contain the two nodes itself, not any other ones.
Source: https://www2.cs.arizona.edu/people/kobourov/gd-metrics2024.pdf
Returns an array of Gabriel Ratios (of doubles) of all nodes of the graph Also also assigns the reference graph (gabrielGraphReference) to the output gabriel graph
|
static |
Computes graph area (respecting node sizes), in coordinate length metric.
Uses GraphAttributes::boundingBox() as helper function, to get height and width of graph, to compute its area.
Returns graph area double value Returns 0 if graph has one or less nodes.
|
static |
Computes horizontal node balance.
def. Horizontal/Vertical node balance: Split nodes into two groups, left and right (or above or below) of the center, and divide it by total number of nodes.
Returns balance double value, where 0 is perfectly balanced and 1 is maximally unbalanced. Returns -1.0 if graph is empty.
|
static |
Computes the intersection graph H of the line segments in the layout given by ga.
The nodes of the intersection graph are all endpoints of segments in ga plus all intersection points. The edges correspond to edges in the input layout: If an edge connecting points v and w in H corresponds to an edge e in the input graph, then e contains a line segment s such that both v and w are endpoints or intersection points of s.
To put it more simple, we obtain graph H from ga by putting a dummy vertex on each crossing and bend point, and joining all nodes representing the same point in the plane.
| ga | Input layout. If it contains bend points, each segment of an edge's polyline is considered as a line segment. Otherwise, a straight-line drawing is assumed. |
| H | Is assigned the intersection graph. |
| points | Maps nodes in H to their geometric position in the layout. |
| origNode | Maps nodes in H to nodes in ga's graph. Points that are only intersection points of segments are mapped to nullptr. |
| origEdge | Maps edges in H to the corresponding edges in ga's graph. |
|
static |
Computes neighborhood preservation H of the edges in the graph given, in ga.
Neighborhood preservation def.: How many nodes in the graph are connected to the actually closest (least coordinative distance) nodes. Returns an array of neighbourhood preservations in percentile (of doubles from 0.0 for lowest preservation, to 1.0 for highest preservation) of all nodes of the graph. Neighborhood preservation def.: How many nodes in the graph are connected to the actually closest nodes (least coordinative distance. Also generates a private variable with an overall graph neighbourhood preservation average (also from 0.0 to 1.0 ).
Source: https://www2.cs.arizona.edu/people/kobourov/gd-metrics2024.pdf
Returns an array of preservation values, of each node in Graph mainGraph
|
static |
Calculating percentage of nodes with integer coordinates.
For each node, checks if its x- and y-coordinates are integers, and counts how many of them are. Can also receives epsilon value for tolerance of closeness to integer (default is 1e-9).
Returns percentage of nodes with integer coordinates (or within epsilon range). Returns -1.0 when graph is empty.
|
static |
Computes Node Ratio H of the nodes in the graph given, in ga.
Node Ratio def.: Node Resolution (NR) metric is the ratio between the smallest distance between two nodes and the largest distance between two nodes. Source: https://www2.cs.arizona.edu/people/kobourov/gd-metrics2024.pdf
Returns a double that gives the Node Ratio as output, which is: smallest_distance_between_2_nodes / biggest_distance_between_2_nodes
|
static |
Computes Node Uniformity (NU) H of the graph g.
def. Node Uniformity (NU): Calculates how well the node distribution is in the bounding box of the graph. "The Node Uniformity metric measures the distribution of nodes in the bounding box, by splitting it into grid cells based on the number of nodes in the graph, counting the number of nodes in each cell, and comparing them with an ideal distribution." - https://www2.cs.arizona.edu/people/kobourov/gd-metrics2024.pdf
Can also receive grid width and height as params, defaults to 10x10 grid.
Returns node uniformity metric between 1.0 and 0.0, where 1.0 is a perfect uniformity and 0.0 is the worst uniformity. Returns 0.0 if the graph has less than 2 nodes, or number of grid cells is 0 (e.g. gridWidth or/and gridHeight is 0).
|
static |
Computes the number of bends (i.e. bend-points) for each edge in the layout ga.
| ga | Input layout. |
| considerSelfLoops | Determines whether the bends of self-loops are considered. |
|
static |
Computes the number of edge crossings for each edge in the layout ga.
If several edge segments cross in the same point, this is counted as if all of these segments would cross pairwise. E.g., if three edge segments cross in a common points, this counts as two crossings for each of the edges.
| ga | Input layout. If it contains bend points, each segment of an edge's polyline is considered as a line segment. Otherwise, a straight-line drawing is assumed. |
|
static |
Computes the number of crossings through a non-incident node for each edge in the layout ga.
If several edge segments cross a node in the same point, one crossing per edge segment is counted. E.g., if three edge segments cross a node in a common point, this counts as three node crossings. Each node is treated as if it had the shape of the rectangle with the corresponding width and height given by ga.
| ga | Input layout. If it contains bend points, each segment of an edge's polyline is considered as a line segment. Otherwise, a straight-line drawing is assumed. |
|
static |
Computes the number of node overlaps for each node in the layout ga.
Each node is treated as if it had the shape of the rectangle with the corresponding width and height given by ga.
| ga | Input layout. |
|
static |
Computes the percentage of crossings for each edge in the layout ga compared to the maximum number of crossings.
The maximum number of crossings is defined as the number of crossings that would occur if all edges were straight lines and crossed at most once. This is computed by the numberOfCrossings() function.
|
static |
Calculates percentage of edges that point upwards.
For each edge, checks if its directional vector has a positive y-value, meaning that its direction points upwards.
Can also receives epsilon value for tolerance of closeness to integer (default is 1e-9).
Returns percentage of edges pointing upwards. Returns -1.0 when graph is empty, or undirected.
