vtkGraphLayoutFilter.cxx 8.2 KB
Newer Older
1 2 3 4 5
/*=========================================================================

  Program:   Visualization Toolkit
  Module:    vtkGraphLayoutFilter.cxx

6
  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7 8
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
9

10 11
     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12
     PURPOSE.  See the above copyright notice for more information.
13 14 15

=========================================================================*/
#include "vtkGraphLayoutFilter.h"
16

17 18
#include "vtkCellArray.h"
#include "vtkCellData.h"
19
#include "vtkMath.h"
20 21
#include "vtkInformation.h"
#include "vtkInformationVector.h"
22
#include "vtkObjectFactory.h"
23
#include "vtkPointData.h"
24
#include "vtkPolyData.h"
25

Brad King's avatar
Brad King committed
26
vtkStandardNewMacro(vtkGraphLayoutFilter);
27 28 29 30 31

vtkGraphLayoutFilter::vtkGraphLayoutFilter()
{
  this->GraphBounds[0] = this->GraphBounds[2] = this->GraphBounds[4] = -0.5;
  this->GraphBounds[1] = this->GraphBounds[3] = this->GraphBounds[5] =  0.5;
32
  this->MaxNumberOfIterations = 50;
33 34 35 36 37 38 39 40
  this->CoolDownRate = 10.0;
  this->AutomaticBoundsComputation = 1;
  this->ThreeDimensionalLayout = 1;
}

// A vertex contains a position and a displacement.
typedef struct _vtkLayoutVertex
{
41 42
  double x[3];
  double d[3];
43 44 45 46 47 48 49 50 51 52 53
} vtkLayoutVertex;

// An edge consists of two vertices joined together.
// This struct acts as a "pointer" to those two vertices.
typedef struct _vtkLayoutEdge
{
  int t;
  int u;
} vtkLayoutEdge;

// Cool-down function.
54 55 56
static inline double CoolDown(double t, double r)
{
  return t-(t/r);
57 58
}

59 60 61
static inline double forceAttract(double x, double k)
{
  return (x * x) / k;
62 63
}

64
static inline double forceRepulse(double x, double k)
65 66
{
  if (x != 0.0)
67
  {
68
    return k * k / x;
69
  }
70
  else
71
  {
72
    return VTK_DOUBLE_MAX;
73
  }
74 75
}

76 77 78 79
int vtkGraphLayoutFilter::RequestData(
  vtkInformation *vtkNotUsed(request),
  vtkInformationVector **inputVector,
  vtkInformationVector *outputVector)
80
{
81 82 83 84
  // get the info objects
  vtkInformation *inInfo = inputVector[0]->GetInformationObject(0);
  vtkInformation *outInfo = outputVector->GetInformationObject(0);

85
  // get the input and output
86 87 88 89 90
  vtkPolyData *input = vtkPolyData::SafeDownCast(
    inInfo->Get(vtkDataObject::DATA_OBJECT()));
  vtkPolyData *output = vtkPolyData::SafeDownCast(
    outInfo->Get(vtkDataObject::DATA_OBJECT()));

91 92 93 94
  vtkPoints *pts = input->GetPoints();
  vtkCellArray *lines = input->GetLines();
  int numLines = lines->GetNumberOfCells();  //Number of lines/edges.
  int numPts = input->GetNumberOfPoints();  //Number of points/vertices.
95
  double diff[3], len;  //The difference vector.
96
  int i, j, l;  //Iteration variables.
97
  vtkIdType npts = 0;
98
  vtkIdType *cellPts = nullptr;
99
  double fa, fr, minimum;
100 101 102 103

  vtkDebugMacro(<<"Drawing graph");

  if ( numPts <= 0 || numLines <= 0)
104
  {
105
    vtkErrorMacro(<<"No input");
106
    return 1;
107
  }
108

109 110
  // Generate bounds automatically if necessary. It's the same
  // as the input bounds.
111
  if ( this->AutomaticBoundsComputation )
112
  {
113
    pts->GetBounds(this->GraphBounds);
114
  }
115 116

  for (i=0; i<3; i++)
117
  {
118
    if ( this->GraphBounds[2*i+1] <= this->GraphBounds[2*i] )
119
    {
120 121
      this->GraphBounds[2*i+1] = this->GraphBounds[2*i] + 1;
    }
122
  }
123

124 125 126
  // Allocate memory for structures. Break polylines into line segments.
  numLines=0;
  for (i=0, lines->InitTraversal(); lines->GetNextCell(npts, cellPts); i++)
127
  {
128
    numLines += npts - 1;
129
  }
130

131 132
  vtkLayoutVertex *v = new vtkLayoutVertex [numPts];
  vtkLayoutEdge *e = new vtkLayoutEdge [numLines];
133

134 135
  // Get the points, either x,y,0 or x,y,z
  for (i=0; i<numPts; i++)
136
  {
137 138
    pts->GetPoint(i,v[i].x);
    if ( ! this->ThreeDimensionalLayout )
139
    {
140 141
      v[i].x[2] = 0;
    }
142
  }
143 144 145 146

  // Get the edges
  numLines=0;
  for (i=0, lines->InitTraversal(); lines->GetNextCell(npts, cellPts); i++)
147
  {
148
    for (j=0; j<npts-1; j++)
149
    {
150 151 152
      e[numLines].t = cellPts[j];
      e[numLines++].u = cellPts[j+1];
    }
153
  }
154 155

  // More variable definitions:
156
  double volume = (this->GraphBounds[1] - this->GraphBounds[0]) *
157 158
    (this->GraphBounds[3] - this->GraphBounds[2]) *
    (this->GraphBounds[5] - this->GraphBounds[4]);
159
  double temp = sqrt( (this->GraphBounds[1]-this->GraphBounds[0])*
160 161 162 163 164
                     (this->GraphBounds[1]-this->GraphBounds[0]) +
                     (this->GraphBounds[3]-this->GraphBounds[2])*
                     (this->GraphBounds[3]-this->GraphBounds[2]) +
                     (this->GraphBounds[5]-this->GraphBounds[4])*
                     (this->GraphBounds[5]-this->GraphBounds[4]) );
165
  // The optimal distance between vertices.
166
  double k = pow(volume/numPts,0.33333);
167 168

  // Begin iterations.
169
  double norm;
170
  for(i=0; i<this->MaxNumberOfIterations; i++)
171
  {
172 173
    // Calculate the repulsive forces.
    for(j=0; j<numPts; j++)
174
    {
175 176 177 178
      v[j].d[0] = 0.0;
      v[j].d[1] = 0.0;
      v[j].d[2] = 0.0;
      for(l=0; l<numPts; l++)
179
      {
180
        if (j != l)
181
        {
182 183 184 185 186 187 188 189 190 191
          diff[0] = v[j].x[0] - v[l].x[0];
          diff[1] = v[j].x[1] - v[l].x[1];
          diff[2] = v[j].x[2] - v[l].x[2];
          norm = vtkMath::Normalize(diff);
          fr = forceRepulse(norm,k);
          v[j].d[0] += diff[0] * fr;
          v[j].d[1] += diff[1] * fr;
          v[j].d[2] += diff[2] * fr;
        }
      }
192
    }
193 194 195

    // Calculate the attractive forces.
    for (j=0; j<numLines; j++)
196
    {
197 198 199 200 201 202 203 204 205 206 207
      diff[0] = v[e[j].u].x[0] - v[e[j].t].x[0];
      diff[1] = v[e[j].u].x[1] - v[e[j].t].x[1];
      diff[2] = v[e[j].u].x[2] - v[e[j].t].x[2];
      norm = vtkMath::Normalize(diff);
      fa = forceAttract(norm,k);
      v[e[j].u].d[0] -= diff[0] * fa;
      v[e[j].u].d[1] -= diff[1] * fa;
      v[e[j].u].d[2] -= diff[2] * fa;
      v[e[j].t].d[0] += diff[0] * fa;
      v[e[j].t].d[1] += diff[1] * fa;
      v[e[j].t].d[2] += diff[2] * fa;
208
    }
209 210 211

    // Combine the forces for a new configuration
    for (j=0; j<numPts; j++)
212
    {
213 214 215 216 217
      norm = vtkMath::Normalize(v[j].d);
      minimum = (norm < temp ? norm : temp);
      v[j].x[0] += v[j].d[0] * minimum;
      v[j].x[1] += v[j].d[1] * minimum;
      v[j].x[2] += v[j].d[2] * minimum;
218
    }
219 220 221

    // Reduce temperature as layout approaches a better configuration.
    temp = CoolDown(temp, this->CoolDownRate);
222
  }
223 224 225 226 227 228

  // Get the bounds of the graph and scale and translate to
  // bring them within the bounds specified.
  vtkPoints *newPts = vtkPoints::New();
  newPts->SetNumberOfPoints(numPts);
  for (i=0; i<numPts; i++)
229
  {
230
    newPts->SetPoint(i,v[i].x);
231
  }
232 233
  double bounds[6], sf[3], x[3], xNew[3];
  double center[3], graphCenter[3];
234 235
  newPts->GetBounds(bounds);
  for (i=0; i<3; i++)
236
  {
237
    if ( (len=(bounds[2*i+1] - bounds[2*i])) == 0.0 )
238
    {
239
      len = 1.0;
240
    }
241 242 243
    sf[i] = (this->GraphBounds[2*i+1] - this->GraphBounds[2*i]) / len;
    center[i] = (bounds[2*i+1] + bounds[2*i])/2.0;
    graphCenter[i] = (this->GraphBounds[2*i+1] + this->GraphBounds[2*i])/2.0;
244
  }
245

246
  double scale = sf[0];
247 248 249
  scale = (scale < sf[1] ? scale : sf[1]);
  scale = (scale < sf[2] ? scale : sf[2]);

250
  for (i=0; i<numPts; i++)
251
  {
252
    newPts->GetPoint(i, x);
253
    for (j=0; j<3; j++)
254
    {
255
      xNew[j] = graphCenter[j] + scale*(x[j]-center[j]);
256
    }
257 258
    newPts->SetPoint(i,xNew);
  }
259 260 261 262 263 264 265 266 267 268 269

  // Send the data to output.
  output->SetPoints(newPts);
  output->SetLines(lines);
  output->GetPointData()->PassData(input->GetPointData());
  output->GetCellData()->PassData(input->GetCellData());

  // Clean up.
  newPts->Delete();
  delete [] v;
  delete [] e;
270 271

  return 1;
272 273 274 275
}

void vtkGraphLayoutFilter::PrintSelf(ostream& os, vtkIndent indent)
{
Brad King's avatar
Brad King committed
276
  this->Superclass::PrintSelf(os,indent);
277

278
  os << indent << "AutomaticBoundsComputation: "
279 280 281
     << (this->AutomaticBoundsComputation ? "On\n" : "Off\n");

  os << indent << "GraphBounds: \n";
282
  os << indent << "  Xmin,Xmax: (" << this->GraphBounds[0] << ", "
283
     << this->GraphBounds[1] << ")\n";
284
  os << indent << "  Ymin,Ymax: (" << this->GraphBounds[2] << ", "
285
     << this->GraphBounds[3] << ")\n";
286
  os << indent << "  Zmin,Zmax: (" << this->GraphBounds[4] << ", "
287 288
     << this->GraphBounds[5] << ")\n";

289
  os << indent << "MaxNumberOfIterations: "
290 291
     << this->MaxNumberOfIterations << endl;

292
  os << indent << "CoolDownRate: "
293 294
     << this->CoolDownRate << endl;

295
  os << indent << "Three Dimensional Layout: "
296 297
     << (this->ThreeDimensionalLayout ? "On\n" : "Off\n");
}