Ignore:
Timestamp:
09/07/16 15:20:29 (5 years ago)
Author:
bburlacu
Message:

#2288: Clean up code and add comments in the ConstrainedForceDirectedLayout class. Minor changes to view and directed graph chart. Introduced an INetworkNode interface for more flexibility. Updated cola and adaptagrams dlls with latest changes from upstream.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.VariableInteractionNetworks/HeuristicLab.VariableInteractionNetworks.Views/3.3/Layout/ConstrainedForceDirectedLayout.cs

    r13893 r14275  
    2626using Cola;
    2727using HeuristicLab.Core;
    28 using HeuristicLab.Random;
    2928using Point = Cola.Point;
    3029
    3130namespace HeuristicLab.VariableInteractionNetworks.Views {
    3231  public class ConstrainedForceDirectedLayout {
     32    #region edge routing modes
    3333    public enum EdgeRouting : uint {
    3434      None,
     
    3636      Orthogonal
    3737    }
    38     private ConstrainedFDLayout layoutEngine;
     38    #endregion
     39
     40    #region layout-related private members
     41    private ConstrainedFDLayout alg;
     42    // graph and constraint definitions
    3943    private TopologyNodePtrs topologyNodes;
    4044    private TopologyEdgePtrs topologyRoutes;
     45    private RectanglePtrs rectangles;
     46    private ColaEdges edges;
    4147    private Cola.Doubles edgeLengths;
    4248    private int topologyNodeCount;
    43     private readonly IRandom random = new MersenneTwister();
    4449    private Dictionary<uint, uint> idMap;
    4550    private Dictionary<IVertex, int> indexMap;
     51    #endregion
     52
     53    #region public properties
    4654    public double IdealEdgeLength { get; set; }
    4755    public double DefaultEdgeLength { get; set; }
     
    8088      }
    8189    }
     90    #endregion
    8291
    8392    public ConstrainedForceDirectedLayout() {
     
    8796      LayoutWidth = 800;
    8897      LayoutHeight = 600;
    89       PerformEdgeRouting = true;
    9098      MinHorizontalSpacing = 0;
    9199      MinVerticalSpacing = 0;
     
    93101    }
    94102
     103    /// <summary>
     104    /// This method accepts a dictionary mapping each vertex to a rectangular shape, so that the layout is aware of each node's width and height
     105    /// </summary>
     106    /// <param name="nodeShapes">The dictionary mapping graph vertices to rectangular shapes.</param>
    95107    public void Run(Dictionary<IVertex, RectangleF> nodeShapes) {
    96108      if (nodeShapes.Count == 0) return;
     109      // map vertices to node indices required by cola
    97110      indexMap = new Dictionary<IVertex, int>();
    98111      idMap = new Dictionary<uint, uint>();
    99       var rectangles = new Cola.RectanglePtrs();
     112      rectangles = new Cola.RectanglePtrs();
    100113      int i = 0;
    101114      arcs = new List<IArc>();
     115      topologyNodes = new TopologyNodePtrs();
    102116      foreach (var pair in nodeShapes) {
    103117        var v = pair.Key;
    104118        arcs.AddRange(v.InArcs);
    105119        var p = pair.Value;
    106 
    107         var width = p.Size.Width;
    108         var height = p.Size.Height;
    109 
    110         var x = random.NextDouble() * (LayoutWidth - width);
    111         var y = random.NextDouble() * (LayoutHeight - height);
    112         // randomize coordinates before passing them to the layout engine
    113         var rect = new Cola.Rectangle(x, x + width, y, y + height);
     120        var rect = new Cola.Rectangle(p.X, p.X + p.Width, p.Y, p.Y + p.Height);
    114121        rectangles.Add(rect);
    115122
    116123        indexMap[v] = i;
     124        topologyNodes.Add(new Cola.Node((uint)i, rect));
     125
    117126        ++i;
    118127      }
    119128      topologyNodeCount = i;
    120       var edges = new ColaEdges(arcs.Select(x => new ColaEdge((uint)indexMap[x.Source], (uint)indexMap[x.Target])).ToList());
     129      edges = new ColaEdges(arcs.Select(x => new ColaEdge((uint)indexMap[x.Source], (uint)indexMap[x.Target])).ToList());
    121130      edgeLengths = new Cola.Doubles(Enumerable.Range(0, edges.Count).Select(x => DefaultEdgeLength).ToList());
    122131
    123       layoutEngine = new ConstrainedFDLayout(rectangles, edges, IdealEdgeLength, PreventOverlaps, edgeLengths);
     132      // initialize the layout engine using the rectangles, edges, and desired settings
     133      alg = new ConstrainedFDLayout(rectangles, edges, IdealEdgeLength, edgeLengths);
     134      alg.setAvoidNodeOverlaps(PreventOverlaps); // prevent overlap of node shapes
     135
     136      // identify clusters and configure cluster hierarchy
    124137      var clusters = IdentifyClusters(rectangles, edges).ToList();
    125138      if (clusters.Count > 1) {
     
    128141          rootCluster.addChildCluster(cluster);
    129142        }
    130         layoutEngine.setClusterHierarchy(rootCluster);
    131       }
    132       var ccs = new CompoundConstraintPtrs();
    133       for (i = 0; i < rectangles.Count - 1; ++i) {
    134         for (int j = i + 1; j < rectangles.Count; ++j) {
    135           if (MinHorizontalSpacing > 0)
    136             ccs.Add(new SeparationConstraint(Dim.XDIM, (uint)i, (uint)j, MinHorizontalSpacing, false));
    137           if (MinVerticalSpacing > 0)
    138             ccs.Add(new SeparationConstraint(Dim.YDIM, (uint)i, (uint)j, MinVerticalSpacing, false));
    139         }
    140       }
    141       if (ccs.Any()) layoutEngine.setConstraints(ccs);
     143        alg.setClusterHierarchy(rootCluster);
     144      }
     145
    142146      var topology = new ColaTopologyAddon();
    143       layoutEngine.setTopology(topology);
    144       layoutEngine.makeFeasible();
    145       // store topology after makeFeasible()
    146       topology = ColaTopologyAddon.CastToConcreteType(layoutEngine.getTopology());
    147       layoutEngine.run();
    148 
    149       topologyNodes = topology.topologyNodes;
    150       topologyRoutes = topology.topologyRoutes;
    151 
    152       if (PerformEdgeRouting) {
    153         RouteEdges(edges);
    154       } else {
    155         int id = topologyNodeCount;
    156         foreach (var edge in edges) {
    157           var eps = new TopologyEdgePointPtrs();
    158           var src = topologyNodes[(int)edge.first];
    159           var dst = topologyNodes[(int)edge.second];
    160           eps.Add(new EdgePoint(src, EdgePoint.RectIntersect.CENTRE));
    161           eps.Add(new EdgePoint(dst, EdgePoint.RectIntersect.CENTRE));
    162           topologyRoutes.Add(new Edge((uint)id++, IdealEdgeLength, eps));
    163         }
    164       }
    165     }
    166 
     147      alg.setTopology(topology);
     148      alg.makeFeasible();
     149      var newTopology = ColaTopologyAddon.CastToConcreteType(alg.getTopology()); // store topology after makeFeasible()
     150
     151      topologyNodes = newTopology.topologyNodes;
     152      topologyRoutes = newTopology.topologyRoutes;
     153
     154      RouteEdges();
     155      // finally, run the layout engine (the positions of the rectangles will be updated)
     156      alg.run();
     157    }
     158
     159    public void Run(bool preserveTopology = true) {
     160      if (preserveTopology) {
     161        RouteEdges();
     162        var topology = new ColaTopologyAddon(topologyNodes, topologyRoutes);
     163        alg.setTopology(topology);
     164      }
     165      alg.run();
     166    }
     167
     168    /// <summary>
     169    /// This method is used internally by the @IdentifyClusters method to separate vertices by color
     170    /// (vertices of the same subgraph will have the same color)
     171    /// </summary>
     172    /// <param name="v">The starting vertex from which all adjacent vertices will be colored.</param>
    167173    private static void ColourNeighbours(IVertex v) {
    168174      foreach (var arc in v.InArcs) {
     
    178184    }
    179185
     186    /// <summary>
     187    /// Method used to identify the disconnected components of the graph, so that they can be layouted separately and placed in non-overlapping areas of the drawing region.
     188    /// </summary>
     189    /// <param name="rectangles">The rectangles corresponding to the graph nodes.</param>
     190    /// <param name="edges">The edges connecting the rectangles.</param>
     191    /// <returns>A list of clusters representing the disconnected components.</returns>
    180192    private static IEnumerable<Cluster> IdentifyClusters(RectanglePtrs rectangles, ColaEdges edges) {
    181193      // build a graph using the rectangles and the edges
     
    205217    }
    206218
    207     private void RouteEdges(ColaEdges edges) {
     219    /// <summary>
     220    /// This method performs edge routing, meaning that edges are moved such that they go around the nodes.
     221    /// Routing can produce polyline or orthogonal graph edges .
     222    /// </summary>
     223    private void RouteEdges() {
     224      topologyRoutes = new TopologyEdgePtrs();
    208225      // after the layout is done, we need to use a router to route edges
    209226      RouterFlag rf;
     
    216233          break;
    217234        default:
    218           rf = RouterFlag.PolyLineRouting;
    219           break;
     235          var id = topologyNodeCount;
     236          foreach (var edge in edges) {
     237            var eps = new TopologyEdgePointPtrs();
     238            var src = topologyNodes[(int)edge.first];
     239            var dst = topologyNodes[(int)edge.second];
     240            eps.Add(new EdgePoint(src, EdgePoint.RectIntersect.CENTRE));
     241            eps.Add(new EdgePoint(dst, EdgePoint.RectIntersect.CENTRE));
     242            topologyRoutes.Add(new Edge((uint)id++, IdealEdgeLength, eps));
     243          }
     244          return;
    220245      }
    221246      var router = new Router((uint)rf);
     247      // set the minimal distance by which nodes should be avoided by the router
    222248      router.setRoutingParameter(RoutingParameter.shapeBufferDistance, 5);
    223       //router.setRoutingParameter(RoutingParameter.idealNudgingDistance, 0);
    224249      router.UseLeesAlgorithm = true;
    225250      router.InvisibilityGrph = false;
    226       //router.RubberBandRouting = true;
    227       var shapes = new List<ShapeRef>();
    228251      // consider topology routes only for the topologyNodes associated with our objects (the rectangles)
    229 
    230252      for (int i = 0; i < topologyNodeCount; ++i) {
    231253        var r = topologyNodes[i].rect;
     
    242264        var shapeRef = new ShapeRef(router, poly);
    243265        idMap[shapeRef.id()] = (uint)i;
    244         shapes.Add(shapeRef);
    245266      }
    246267      router.processTransaction();
    247268
    248       var connRefs = new List<ConnRef>();
    249269      for (int i = 0; i < edges.Count; ++i) {
    250270        var edge = edges[i];
     
    271291            var id = router.newObjectId();
    272292            var node = new Node(id, new Cola.Rectangle(p.x, p.x + 1, p.y, p.y + 1));
    273             //topologyNodes.Add(node);
    274293            idMap[id] = id;
    275294            eps.Add(new EdgePoint(node, ri));
     
    278297        eps.Add(new EdgePoint(dst, EdgePoint.RectIntersect.CENTRE));
    279298        topologyRoutes.Add(new Edge((uint)i, IdealEdgeLength, eps));
    280         connRefs.Add(connRef);
    281       }
    282     }
    283 
    284     public void Run() { }
    285 
    286     public void UpdateNodePosition(IVertex v, PointF point) {
    287       var node = topologyNodes[indexMap[v]];
     299      }
     300    }
     301
     302    public void OutputInstanceToSVG(string path) {
     303      alg.outputInstanceToSVG(path);
    288304    }
    289305
Note: See TracChangeset for help on using the changeset viewer.