buckscivilwar.com

Tree and graphs

Trees and Graphs

Dab Hanrahan

Forest Drawing

Page 1

For what reason Trees?

Hierarchies

File devices and web sites

Organization charts

Categorical classifications

Similiarity and clustering

Branching processes

Genealogical and lineages

Phylogenetic trees

Decision procedures

Indices or search woods

Decision woods

Tournaments

Two Major Image Representations

Interconnection: Node / Link Layouts

Containment as well as Enclosure

F6

G6

H6

J36

U8

B10

C30

L7 M7

V12

O4 P4 Q4 R4 S4 T4

W8

Page 2

[Furbringer]

C. Elegans Cellular Lineage

[Sulston]

Page a few

Page 5

Page 5

Page six

Classic Shrub Drawing

Preorder or inorder traversal

Depth-InOrder Traversal

0

1

two

3

some

5

6th

7

0 1 2 3 4 5 6th 7 8 9 twelve 11 13 14 12-15

Similarly pertaining to pre-order, postorder

Note: width = n-1

Page six

Aesthetic Standards

1 .

Nodes at the same amounts should be lined up

2 .

Keep up with the relative purchasing of left and

correct subtrees

several.

Parent must be centered within the children

5.

A forest and its reflect image ought to be

drawn because reflections of each other

five.

A subtree should be attracted the same way

no matter where it arises in the tree

Rheingold-Tilford Algorithm

E. Rheingold, J. Tilford, Tidier pulling of trees, IEEE Trans. Software Architectural, SE-7(2), pp. 223-228. 81

Page eight

Rheingold-Tilford Algorithm

Left contour

Left threads

Right shape

Right threads

E. Rheingold, J. Tilford, Tidier drawing of trees and shrubs, IEEE Trans. Software Engineering, SE-7(2), pp. 223-228. 1981

Rheingold-Tilford Formula

Separation = 2

Electronic. Rheingold, L. Tilford, More tidy drawing of trees, IEEE Trans. Software Engineering, SE-7(2), pp. 223-228. 1981

Page 9

Rheingold-Tilford Algorithm

Translate by (sep+1)/2

E. Rheingold, J. Tilford, Tidier sketching of forest, IEEE Trans. Software Anatomist, SE-7(2), pp. 223-228. 1981

Rheingold-Tilford Criteria

T sama dengan min(h(TL), h(TR)

E. Rheingold, J. Tilford, Tidier sketching of woods, IEEE Trans. Software Architectural, SE-7(2), pp. 223-228. 1981

Page twelve

Rheingold-Tilford Algorithm

Total operating time: Rely

O( and – h(T))

E. Rheingold, J. Tilford, Tidier sketching of woods, IEEE Trans. Software Anatomist, SE-7(2), pp. 223-228. 81

Focus+Context: DOI Tree

http://davenation.com/doitree/doitree-avi-2002.htm

Page 14

Radial Designs

Bounded sand wedge

Aspect Proportion

Hierarchies are generally wide and shallow

http://cgm.cs.mcgill.ca/~luc/trees.html

Strategies:

Moving

Filtering, collapsing, expanding

Collection and aggregating

More space: Cone Tree, Hyperbolic

Browser

Target + circumstance

Page doze

Cone Woods

Cone Woods, Robertson, Greeting card, Mackinlay, 1991

Hyperbolic Woods

Demo about InXight

Page 13

Nested/Inclusion Trees

A

B

C

E

Deb

G

N

H

We

(A (B (C D) (E (G (H I)))))

Tree Maps [Schneiderman]

http://netscan.research.microsoft.com/treemap/

Page 13

Graph Pulling

Why Charts?

Relational directories with keys

Complex info structures

Internet sites

Citation networks

Link analysis

Computer systems

World wide web

File collections

Metabolic pathways

…

Page 12-15

Aesthetic Requirements

Minimize advantage crossings

Reduce area

Total edge length

Maximum edge length

Homogeneous edge duration

Total bends

Maximum bends

Angular bends

Aspect ratio

Symmetry

G. Di Battista, P. Eades, R. Tamassia, I. G. Tollis,

Graph Drawing, 99

Algorithms

Planar drawings

Split

Force-directed

Web page 16

Layered Drawing of Directed Charts

Sugiyama et al. 1981

Dot, Gamsden et ing. 1993

1 )

Layer assignment

2 .

Lessen edge crossings between layers

3.

Placement vertices flat

Additionally ,

5.

Cycle removing

5.

Path edges (fit splines)

shells. dot

Thompson -> Mashey;

Thompson -> Bourne;

Thompson -> csh;

csh -> tcsh;

Bourne -> ksh;

Bourne -> esh;

Bourne -> vsh;

Bourne -> " System-V";

Bourne -> v9sh;

v9sh -> radio controlled;

Bourne -> Bash;...

02.08.2019

Related

Essay in Environment

02.08.2019 What Do i need to Do to Protect Environment? Requirements: The writing ought to include the following aspects: 1 . In brief describe the latest severe environment in Shanghai/our…..