Class LayoutUtil

java.lang.Object
edu.cmu.tetrad.graph.LayoutUtil
public class LayoutUtil extends Object

LayoutUtil class.

Version:
$Id: $Id
Author:
josephramsey

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static enum 
    LayoutUtil.DefaultLayout
    The layouts that can serve as the default layout: the ones that need nothing but the graph.
    static final class 
    LayoutUtil.FruchtermanReingoldLayout
    Lays out a graph by linearly summing repulsive force between all nodes and attractive force between adjacent nodes.
    static final class 
    LayoutUtil.KamadaKawaiLayout
    Lays out a graph by placing springs between the nodes and letting the system settle (one node at a time).
    static interface 
    LayoutUtil.LayoutProgressListener
    Callback interface for reporting layout progress.
    static interface 
    LayoutUtil.NodeSize
    Supplies the rendered box size of each node, so a layout can space nodes by what they actually take up on screen.
    static class 
    LayoutUtil.NoOpProgressListener
    No-op listener for headless / non-GUI use.
    static class 
    LayoutUtil.SwingProgressListener
    Swing adapter that wraps a ProgressMonitor.

  • Constructor Summary

    Constructors
    Constructor
    Description
    LayoutUtil()
    Constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    static void
    arrangeByLayout(Graph graph, HashMap<String,PointXy> layout)
    arrangeByLayout.
    static boolean
    arrangeBySourceGraph(Graph resultGraph, Graph sourceGraph)
    Arranges the nodes in the result graph according to their positions in the source graph.
    static void
    circleLayout(Graph graph)
    Arranges the nodes in the graph in a circle, using an estimate of each node's rendered size.
    static void
    circleLayout(Graph graph, LayoutUtil.NodeSize size)
    Arranges the non-latent nodes in a circle just large enough that no two node boxes overlap and, for a circle of a few nodes, an edge between any two of them would be at least MIN_EDGE_LENGTH long from box to box (see MIN_EDGE_LENGTH_MAX_RADIUS), places each latent near its adjacent nodes without overlapping anything, and shifts the result so the bounding box of all node boxes sits at (LAYOUT_MARGIN, LAYOUT_MARGIN) — i.e.
    static void
    defaultLayout(Graph graph)
    Arranges the nodes in the graph by the default layout (see setDefaultLayout(DefaultLayout)), with estimated node sizes.
    static void
    defaultLayout(Graph graph, LayoutUtil.NodeSize size)
    Arranges the nodes in the graph by the default layout (see setDefaultLayout(DefaultLayout)), with the given node sizes for the layouts that use them.
    static void
    defaultLayoutConditional(Graph graph)
    Arranges the nodes using the default layout unless they all have positions already.
    static LayoutUtil.NodeSize
    estimatedNodeSize()
    A size estimate for use when no display sizes are available: about 8 px per character of the name plus padding, with the same 60 px floor and ~30 px height the workbench's measured node boxes use.
    static void
    fruchtermanReingoldLayout(Graph graph)
    fruchtermanReingoldLayout.
    static void
    fruchtermanReingoldLayout(Graph graph, double naturalEdgeLength)
    Fruchterman-Reingold with a chosen natural edge length: the distance at which the textbook pull along an edge and push between its two endpoints balance.
    static LayoutUtil.DefaultLayout
    getDefaultLayout()
    Returns the layout used for graphs that have not been laid out.
    static boolean
    isLaggedGraph(Graph graph)
    Returns true if the graph is a lagged (time-series) graph, i.e., at least one node has a positive lag index in its name.
    static void
    kamadaKawaiLayout(Graph graph, boolean randomlyInitialized, double naturalEdgeLength, double springConstant, double stopEnergy)
    kamadaKawaiLayout.
    static void
    kamadaKawaiLayout(Graph graph, boolean randomlyInitialized, double naturalEdgeLength, double springConstant, double stopEnergy, LayoutUtil.LayoutProgressListener listener)
    Overload that accepts an optional progress listener.
    static int
    lagIndex(String name)
    Returns the lag index encoded in a lagged variable name of the form base:k (as produced by TsUtils.createLagData), or 0 if the name carries no integer lag suffix.
    static void
    layoutByCausalOrder(Graph graph)
    Lays the graph out in rows by causal order, using an estimate of each node's rendered size.
    static void
    layoutByCausalOrder(Graph graph, LayoutUtil.NodeSize size)
    Lays the graph out in rows by causal order: the nodes with no parents in the top row, then the nodes all of whose parents are above, and so on down.
    static void
    layoutByKnowledgeIndices(Graph graph)
    Arranges the nodes of the given graph in tiers based on numerical indices derived from the node names, and positions them accordingly in a 2D layout.
    static void
    layoutByKnowledgeTiers(Graph graph, Knowledge knowledge)
    Arranges the nodes of the given graph in tiers based on their grouping as defined in the provided knowledge object.
    static void
    layoutInCenteredRows(List<List<Node>> tiers, LayoutUtil.NodeSize size)
    Places the given rows of nodes one under another, top row first, each row centered on the widest row.
    static List<List<Node>>
    orderRowsToReduceCrossings(Graph graph, List<List<Node>> rows)
    Orders the nodes within each of the given rows to reduce the crossings of the edges between rows, by the ordering step of Richard's layout (see orderTiers(Graph, List, List)).
    static void
    repositionLatents(Graph graph)
    Repositions latent nodes in the given graph based on their non-latent neighbors.
    static void
    repositionLatents(Graph graph, LayoutUtil.NodeSize size)
    Places each latent near its adjacent nodes without overlapping any other node's box.
    static void
    richardsLayout(Graph graph)
    Arranges the graph the way Richard lays out a graph for presentation: layered by causal depth, with each layer shifted a bit further right than the one above it, so that the flow reads down and to the right, and with within-layer orderings chosen by barycenter sweeps to reduce edge crossings.
    static void
    richardsLayout(Graph graph, LayoutUtil.NodeSize size)
    Richard's layout with the given node sizes and default spacing: a 30 px horizontal gap between node boxes, 90 px between layer centerlines, and a 50 px rightward shear per layer.
    static void
    richardsLayout(Graph graph, LayoutUtil.NodeSize size, double xGap, double yGap, double shearPerLayer)
    Richard's layout, fully parameterized.
    static void
    richardsLayout(Graph graph, LayoutUtil.NodeSize size, double xGap, double yGap, double shearPerLayer, boolean nudge)
    Richard's layout, with the nudge pass switchable.
    static void
    setDefaultLayout(LayoutUtil.DefaultLayout layout)
    Sets the layout used for graphs that have not been laid out, for this process.
    static void
    squareLayout(Graph graph)
    squareLayout.

    Methods inherited from class Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • LayoutUtil

      public LayoutUtil()
      Constructor.

  • Method Details

    • estimatedNodeSize

      public static LayoutUtil.NodeSize estimatedNodeSize()
      A size estimate for use when no display sizes are available: about 8 px per character of the name plus padding, with the same 60 px floor and ~30 px height the workbench's measured node boxes use.
      Returns:
      the estimate

    • layoutByKnowledgeTiers

      public static void layoutByKnowledgeTiers(Graph graph, Knowledge knowledge)
      Arranges the nodes of the given graph in tiers based on their grouping as defined in the provided knowledge object. Nodes not assigned to any tier are arranged first, followed by nodes in each tier, with both groups laid out in a 2D space with horizontal and vertical spacing. Latent nodes are repositioned after arranging other nodes.
      Parameters:
      graph - the graph whose nodes are to be arranged and positioned.
      knowledge - the knowledge object containing tier information and ungrouped variables for the graph nodes.

    • lagIndex

      public static int lagIndex(String name)
      Returns the lag index encoded in a lagged variable name of the form base:k (as produced by TsUtils.createLagData), or 0 if the name carries no integer lag suffix. Names whose suffix after the last colon is not a non-negative integer are treated as unlagged rather than throwing.
      Parameters:
      name - the variable name.
      Returns:
      the lag index, or 0.

    • isLaggedGraph

      public static boolean isLaggedGraph(Graph graph)
      Returns true if the graph is a lagged (time-series) graph, i.e., at least one node has a positive lag index in its name. Such graphs should be laid out by layoutByKnowledgeIndices(Graph), with the current time slice in the bottom row and each earlier lag in a row above, regardless of any knowledge tiers.
      Parameters:
      graph - the graph.
      Returns:
      true if some node name has a lag suffix :k with k > 0.

    • layoutByKnowledgeIndices

      public static void layoutByKnowledgeIndices(Graph graph)
      Arranges the nodes of the given graph in tiers based on numerical indices derived from the node names, and positions them accordingly in a 2D layout. The method processes the nodes to determine their tier, sorts them, and spaces them in both horizontal and vertical directions. Latent nodes are repositioned after arranging all other nodes.
      Parameters:
      graph - the graph whose nodes are to be arranged and positioned.

    • kamadaKawaiLayout

      public static void kamadaKawaiLayout(Graph graph, boolean randomlyInitialized, double naturalEdgeLength, double springConstant, double stopEnergy)

      kamadaKawaiLayout.

      Parameters:
      graph - a Graph object
      randomlyInitialized - a boolean
      naturalEdgeLength - a double
      springConstant - a double
      stopEnergy - a double

    • kamadaKawaiLayout

      public static void kamadaKawaiLayout(Graph graph, boolean randomlyInitialized, double naturalEdgeLength, double springConstant, double stopEnergy, LayoutUtil.LayoutProgressListener listener)
      Overload that accepts an optional progress listener.
      Parameters:
      graph - a Graph object
      randomlyInitialized - a boolean
      naturalEdgeLength - a double
      springConstant - a double
      stopEnergy - a double
      listener - a LayoutUtil.LayoutProgressListener, or null for Swing default

    • fruchtermanReingoldLayout

      public static void fruchtermanReingoldLayout(Graph graph)

      fruchtermanReingoldLayout.

      Parameters:
      graph - a Graph object

    • fruchtermanReingoldLayout

      public static void fruchtermanReingoldLayout(Graph graph, double naturalEdgeLength)
      Fruchterman-Reingold with a chosen natural edge length: the distance at which the textbook pull along an edge and push between its two endpoints balance. Because hubs here repel in proportion to the square root of their degree and overlapping node boxes are separated afterwards, edges settle to about twice this value in practice (a natural length of 80 gives mean edge lengths of 150 to 180 pixels on measurement models). Zero or less means automatic, 20 + 20 times the average degree; 40 to 60 keeps a latent measurement model compact.
      Parameters:
      graph - the graph.
      naturalEdgeLength - the natural edge length in pixels, or 0 for automatic.

    • arrangeByLayout

      public static void arrangeByLayout(Graph graph, HashMap<String,PointXy> layout)

      arrangeByLayout.

      Parameters:
      graph - a Graph object
      layout - a HashMap object

    • getDefaultLayout

      public static LayoutUtil.DefaultLayout getDefaultLayout()
      Returns the layout used for graphs that have not been laid out.
      Returns:
      the default layout.

    • setDefaultLayout

      public static void setDefaultLayout(LayoutUtil.DefaultLayout layout)
      Sets the layout used for graphs that have not been laid out, for this process. It starts as Richard's layout.
      Parameters:
      layout - the default layout; null for Richard's layout.

    • defaultLayoutConditional

      public static void defaultLayoutConditional(Graph graph)
      Arranges the nodes using the default layout unless they all have positions already.
      Parameters:
      graph - the graph to be arranged.

    • defaultLayout

      public static void defaultLayout(Graph graph)
      Arranges the nodes in the graph by the default layout (see setDefaultLayout(DefaultLayout)), with estimated node sizes.
      Parameters:
      graph - the graph to be arranged.

    • defaultLayout

      public static void defaultLayout(Graph graph, LayoutUtil.NodeSize size)
      Arranges the nodes in the graph by the default layout (see setDefaultLayout(DefaultLayout)), with the given node sizes for the layouts that use them.
      Parameters:
      graph - the graph to be arranged.
      size - supplies the rendered box size of each node.

    • circleLayout

      public static void circleLayout(Graph graph)
      Arranges the nodes in the graph in a circle, using an estimate of each node's rendered size. See circleLayout(Graph, NodeSize).
      Parameters:
      graph - the graph to be arranged.

    • circleLayout

      public static void circleLayout(Graph graph, LayoutUtil.NodeSize size)
      Arranges the non-latent nodes in a circle just large enough that no two node boxes overlap and, for a circle of a few nodes, an edge between any two of them would be at least MIN_EDGE_LENGTH long from box to box (see MIN_EDGE_LENGTH_MAX_RADIUS), places each latent near its adjacent nodes without overlapping anything, and shifts the result so the bounding box of all node boxes sits at (LAYOUT_MARGIN, LAYOUT_MARGIN) — i.e. comfortably in the top-left of the canvas.

      The radius is chosen from the node boxes: two boxes at angles a and b on a circle of radius r are separated by r|cos a − cos b| horizontally and r|sin a − sin b| vertically, and are apart if either separation exceeds the corresponding box extent plus the gap. The smallest such r is computed for every pair (not only neighbors — with wide labels and few nodes, the node across the circle is the binding one), and the radius is the largest of those.

      The edge between two nodes runs along the line between their centers, which are r times the unit-circle distance d between their angles apart, and the part of it inside a w by h box is the lesser of (w / 2) / |ux| and (h / 2) / |uy| for the line's unit direction (ux, uy). The direction does not depend on r, so the smallest r that leaves the edge the minimum length is (minimum + the two parts inside the boxes) / d.

      Parameters:
      graph - the graph to be arranged.
      size - supplies each node's rendered box size.

    • squareLayout

      public static void squareLayout(Graph graph)

      squareLayout.

      Parameters:
      graph - a Graph object

    • layoutByCausalOrder

      public static void layoutByCausalOrder(Graph graph)
      Lays the graph out in rows by causal order, using an estimate of each node's rendered size. See layoutByCausalOrder(Graph, NodeSize).
      Parameters:
      graph - a Graph object

    • layoutByCausalOrder

      public static void layoutByCausalOrder(Graph graph, LayoutUtil.NodeSize size)
      Lays the graph out in rows by causal order: the nodes with no parents in the top row, then the nodes all of whose parents are above, and so on down. The nodes within each row are ordered to reduce edge crossings, by the ordering step of Richard's layout. Each row is centered on the widest row. (The rows used to all start at the left margin, so that a row of one or two nodes sat at the far left above or below a wide row, and the edges between them ran at a long slant.)

      The nodes of a row are spaced by their own box widths, with CAUSAL_ORDER_X_GAP between neighbors, and the rows by the tallest box, with CAUSAL_ORDER_Y_GAP between rows. (Every node used to be allowed 80 pixels whatever its label, so that nodes with long names overlapped.) For boxes of the default size, 60 by 30, the spacing is what it was.

      Parameters:
      graph - a Graph object
      size - supplies each node's rendered box size.

    • layoutInCenteredRows

      public static void layoutInCenteredRows(List<List<Node>> tiers, LayoutUtil.NodeSize size)
      Places the given rows of nodes one under another, top row first, each row centered on the widest row. The nodes of a row are spaced by their own box widths, with CAUSAL_ORDER_X_GAP between neighbors, and the rows by the tallest box of all, with CAUSAL_ORDER_Y_GAP between rows; an empty row takes no space. This is the arrangement of the causal order layout, and of any other layout that sorts the nodes into rows (the workbench's distance-from-selected layout, for one).
      Parameters:
      tiers - the rows, top row first; nodes not in any row are not moved.
      size - supplies each node's rendered box size.

    • richardsLayout

      public static void richardsLayout(Graph graph)
      Arranges the graph the way Richard lays out a graph for presentation: layered by causal depth, with each layer shifted a bit further right than the one above it, so that the flow reads down and to the right, and with within-layer orderings chosen by barycenter sweeps to reduce edge crossings. Node sizes are estimated; see richardsLayout(Graph, NodeSize) to supply real display sizes.
      Parameters:
      graph - the graph to be arranged.

    • richardsLayout

      public static void richardsLayout(Graph graph, LayoutUtil.NodeSize size)
      Richard's layout with the given node sizes and default spacing: a 30 px horizontal gap between node boxes, 90 px between layer centerlines, and a 50 px rightward shear per layer.
      Parameters:
      graph - the graph to be arranged.
      size - supplies the rendered box size of each node.

    • richardsLayout

      public static void richardsLayout(Graph graph, LayoutUtil.NodeSize size, double xGap, double yGap, double shearPerLayer)
      Richard's layout, fully parameterized.

      The method is deterministic: the same graph in the same node order gives the same layout every time. It proceeds in four steps:

      1. Layering. Nodes are assigned to layers by causal depth using the directed structure only (each node goes in the first layer where all of the nodes with arrows into it are already placed). If the directed structure has cycles, one edge per cycle found by a depth-first search is set aside for the layering, so those edges, and only those, are drawn pointing up; everything downstream of a cycle is still layered by depth. For PAGs this means an edge like x o-> y places y below x, which matches the "y is not an ancestor of x" reading of the arrowhead.
      2. Crossing reduction. Alternating down and up barycenter sweeps reorder each layer by the mean position of its neighbors in the adjacent layer, and after each sweep every layer is walked and any two adjacent nodes whose exchange reduces the crossing count are exchanged, until no exchange helps (the transpose step of Gansner et al.), which removes the crossings the barycenter sort alone leaves behind. The barycenter of a node is the mean position of its neighbors in the sweep direction; all edge types vote here, including edges that span more than one layer. The ordering with the fewest straight-line crossings seen over all sweeps is kept. Crossings are counted here with every layer spread over the same width; after the coordinates are assigned and sheared, neighbors in a layer are exchanged once more wherever that reduces the crossings of the edges as actually placed, which matters for edges that span more than one layer; this is done before and again after the nudge described below.
      3. Coordinate assignment. Within each layer, nodes are packed by their actual box widths, then pulled toward the mean x of their neighbors over several relaxation passes, preserving the layer order and minimum separation, so children line up under their parents.
      4. Shear. Each layer is shifted right by shearPerLayer * layerIndex, so exogenous variables sit at the upper left and downstream variables render down and to the right.
      Parameters:
      graph - the graph to be arranged.
      size - supplies the rendered box size of each node.
      xGap - horizontal gap kept between node boxes in a layer.
      yGap - vertical distance between layer centerlines.
      shearPerLayer - rightward shift added per layer of depth.

    • richardsLayout

      public static void richardsLayout(Graph graph, LayoutUtil.NodeSize size, double xGap, double yGap, double shearPerLayer, boolean nudge)
      Richard's layout, with the nudge pass switchable. When nudge is false, the post-processing step that moves nodes sideways off the straight lines of long edges is skipped.
      Parameters:
      graph - the graph to be arranged.
      size - supplies the rendered box size of each node.
      xGap - horizontal gap kept between node boxes in a layer.
      yGap - vertical distance between layer centerlines.
      shearPerLayer - rightward shift added per layer of depth.
      nudge - whether to nudge nodes off long edge lines.

    • orderRowsToReduceCrossings

      public static List<List<Node>> orderRowsToReduceCrossings(Graph graph, List<List<Node>> rows)
      Orders the nodes within each of the given rows to reduce the crossings of the edges between rows, by the ordering step of Richard's layout (see orderTiers(Graph, List, List)). Edges within a row are not counted. The given lists are not changed.
      Parameters:
      graph - the graph; every node in the rows must be one of its nodes.
      rows - the rows, top first.
      Returns:
      the rows, reordered, as new lists.

    • arrangeBySourceGraph

      public static boolean arrangeBySourceGraph(Graph resultGraph, Graph sourceGraph)
      Arranges the nodes in the result graph according to their positions in the source graph.
      Parameters:
      resultGraph - a Graph object
      sourceGraph - a Graph object
      Returns:
      true if all the nodes were arranged, false if not.

    • repositionLatents

      public static void repositionLatents(Graph graph)
      Repositions latent nodes in the given graph based on their non-latent neighbors.
      Parameters:
      graph - the graph containing the nodes to be repositioned.

    • repositionLatents

      public static void repositionLatents(Graph graph, LayoutUtil.NodeSize size)
      Places each latent near its adjacent nodes without overlapping any other node's box. A latent is anchored at the centroid of its measured neighbors (falling back to all neighbors, then the graph center), and a ring search then finds the nearest point whose box clears every already-placed box by NODE_GAP. Ties are broken toward the outside of the graph so the latent floats just off its cluster rather than into the crowded interior. Latents with more measured neighbors are placed first, and each placed latent becomes an obstacle for the rest.
      Parameters:
      graph - the graph containing the nodes to be repositioned.
      size - supplies each node's rendered box size.