1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
/*=========================================================================
Program: Visualization Toolkit
Module: vtkSpanTreeLayoutStrategy.h
Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
All rights reserved.
See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
This software is distributed WITHOUT ANY WARRANTY; without even
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the above copyright notice for more information.
=========================================================================*/
//-------------------------------------------------------------------------
//Copyright 2008 Sandia Corporation.
//Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
//the U.S. Government retains certain rights in this software.
//-------------------------------------------------------------------------
// .NAME vtkSpanTreeLayoutStrategy
// .SECTION Description
// vtkSpanTreeLayout is a strategy for drawing directed graphs that
// works by first extracting a spanning tree (more accurately, a
// spanning forest), and using this both to position graph vertices
// and to plan the placement of non-tree edges. The latter are drawn
// with the aid of edge points to produce a tidy drawing.
//
// The approach is best suited to "quasi-trees", graphs where the number
// of edges is of the same order as the number of nodes; it is less well
// suited to denser graphs. The boolean flag DepthFirstSpanningTree
// determines whether a depth-first or breadth-first strategy is used to
// construct the underlying forest, and the choice of strategy affects
// the output layout significantly. Informal experiments suggest that
// the breadth-first strategy is better for denser graphs.
//
// Different layouts could also be produced by plugging in alternative
// tree layout strategies. To work with the method of routing non-tree
// edges, any strategy should draw a tree so that levels are equally
// spaced along the z-axis, precluding for example the use of a radial
// or balloon layout.
//
// vtkSpanTreeLayout is based on an approach to 3D graph layout first
// developed as part of the "tulip" tool by Dr. David Auber at LaBRI,
// U.Bordeaux: see www.tulip-software.org
//
// This implementation departs from the original version in that:
// (a) it is reconstructed to use Titan/VTK data structures;
// (b) it uses a faster method for dealing with non-tree edges,
// requiring at most two edge points per edge
// (c) allows for plugging in different tree layout methods
// (d) allows selection of two different strategies for building
// the underlying layout tree, which can yield significantly
// different results depending on the data.
//
// .SECTION Thanks
// Thanks to David Duke from the University of Leeds for providing this
// implementation.
#ifndef vtkSpanTreeLayoutStrategy_h
#define vtkSpanTreeLayoutStrategy_h
#include "vtkInfovisLayoutModule.h" // For export macro
#include "vtkGraphLayoutStrategy.h"
class VTKINFOVISLAYOUT_EXPORT vtkSpanTreeLayoutStrategy : public vtkGraphLayoutStrategy
{
public:
static vtkSpanTreeLayoutStrategy *New();
vtkTypeMacro(vtkSpanTreeLayoutStrategy, vtkGraphLayoutStrategy);
void PrintSelf(ostream& os, vtkIndent indent);
// Description:
// If set, base the layout on a depth-first spanning tree,
// rather than the default breadth-first spanning tree.
// Switching between DFT and BFT may significantly change
// the layout, and choice must be made on a per-graph basis.
// Default value is off.
vtkSetMacro(DepthFirstSpanningTree, bool);
vtkGetMacro(DepthFirstSpanningTree, bool);
vtkBooleanMacro(DepthFirstSpanningTree, bool);
// Description:
// Perform the layout.
void Layout();
protected:
vtkSpanTreeLayoutStrategy();
~vtkSpanTreeLayoutStrategy();
vtkGraphLayoutStrategy *TreeLayout;
bool DepthFirstSpanningTree;
private:
vtkSpanTreeLayoutStrategy(const vtkSpanTreeLayoutStrategy&); // Not implemented.
void operator=(const vtkSpanTreeLayoutStrategy&); // Not implemented.
};
#endif
|
