com.jgraph.layout.hierarchical.model

Class JGraphHierarchyModel

public class JGraphHierarchyModel extends Object

Internal model of a hierarchical graph. This model stores nodes and edges equivalent to the real graph nodes and edges, but also stores the rank of the cells, the order within the ranks and the new candidate locations of cells. The internal model also reverses edge direction were appropriate , ignores self-loop and groups parallels together under one edge object.
Field Summary
protected booleandeterministic
Whether or not cells are ordered according to the order in the graph model.
protected intdfsCount
Count of the number of times the ancestor dfs has been used
protected MapedgeMapper
Map from graph edges to internal model edges
intmaxRank
Stores the largest rank number allocated
Mapranks
Mapping from rank number to actual rank
Object[]roots
Store of roots of this hierarchy model, these are real graph cells, not internal cells
protected booleanscanRanksFromSinks
Whether the rank assignment is done from the sinks or sources.
protected MapvertexMapper
Map from graph vertices to internal model nodes
Constructor Summary
JGraphHierarchyModel(JGraphFacade facade)
Constructor with no parameters creates a default model
JGraphHierarchyModel(JGraphFacade facade, Object[] vertices, boolean ordered, boolean deterministic, boolean scanRanksFromSinks)
Creates an internal ordered graph model using the vertices passed in.
Method Summary
protected voidcreateInternalCells(JGraphFacade facade, Object[] vertices, JGraphHierarchyNode[] internalVertices)
Creates all edges in the internal model
voiddfs(JGraphFacade.CellVisitor visitor, Object[] dfsRoots, boolean trackAncestors, Set seenNodes)
A depth first search through the internal heirarchy model
voiddfs(JGraphHierarchyNode parent, JGraphHierarchyNode root, JGraphHierarchyEdge connectingEdge, JGraphFacade.CellVisitor visitor, Set seen, int layer)
Performs a depth first search on the internal hierarchy model
voiddfs(JGraphHierarchyNode parent, JGraphHierarchyNode root, JGraphHierarchyEdge connectingEdge, JGraphFacade.CellVisitor visitor, Set seen, int[] ancestors, int childHash, int layer)
Performs a depth first search on the internal hierarchy model.
voidfixRanks()
Fixes the layer assignments to the values stored in the nodes.
voidformOrderedHierarchy(JGraphFacade facade, Object[] vertices)
Creates an internal ordered graph model using the vertices passed in.
intgetDfsCount()
MapgetEdgeMapper()
MapgetVertexMapping()
voidinitialRank()
Basic determination of minimum layer ranking by working from from sources or sinks and working through each node in the relevant edge direction.
booleanisDeterministic()
booleanisSinksAtLayerZero()
voidsetDeterministic(boolean deterministic)
voidsetDfsCount(int dfsCount)
voidsetEdgeMapper(Map edgeMapper)
voidsetSinksAtLayerZero(boolean sinksAtLayerZero)
voidsetVertexMapping(Map vertexMapping)

Field Detail

deterministic

protected boolean deterministic
Whether or not cells are ordered according to the order in the graph model. Defaults to false since sorting usually produces quadratic performance. Note that since JGraph 6 returns edges in a deterministic order, it might be that this layout is always deterministic using that JGraph regardless of this flag setting (i.e. leave it false in that case)

dfsCount

protected int dfsCount
Count of the number of times the ancestor dfs has been used

edgeMapper

protected Map edgeMapper
Map from graph edges to internal model edges

maxRank

public int maxRank
Stores the largest rank number allocated

ranks

public Map ranks
Mapping from rank number to actual rank

roots

public Object[] roots
Store of roots of this hierarchy model, these are real graph cells, not internal cells

scanRanksFromSinks

protected boolean scanRanksFromSinks
Whether the rank assignment is done from the sinks or sources.

vertexMapper

protected Map vertexMapper
Map from graph vertices to internal model nodes

Constructor Detail

JGraphHierarchyModel

public JGraphHierarchyModel(JGraphFacade facade)
Constructor with no parameters creates a default model

Parameters: facade the facade of the graph to be laid out

JGraphHierarchyModel

public JGraphHierarchyModel(JGraphFacade facade, Object[] vertices, boolean ordered, boolean deterministic, boolean scanRanksFromSinks)
Creates an internal ordered graph model using the vertices passed in. If there are any, leftward edge need to be inverted in the internal model

Parameters: facade the facade describing the graph to be operated on vertices the vertices for this hierarchy ordered whether or not the vertices are already ordered deterministic whether or not this layout should be deterministic on each usage scanRanksFromSinks Whether the rank assignment is done from the sinks or sources.

Method Detail

createInternalCells

protected void createInternalCells(JGraphFacade facade, Object[] vertices, JGraphHierarchyNode[] internalVertices)
Creates all edges in the internal model

Parameters: facade the facade desrcibing the graph to be laid out vertices the vertices whom are to have an internal representation created internalVertices the blank internal vertices to have their information filled in using the real vertices

dfs

public void dfs(JGraphFacade.CellVisitor visitor, Object[] dfsRoots, boolean trackAncestors, Set seenNodes)
A depth first search through the internal heirarchy model

Parameters: visitor the visitor pattern to be called for each node trackAncestors whether or not the search is to keep track all nodes directly above this one in the search path

dfs

public void dfs(JGraphHierarchyNode parent, JGraphHierarchyNode root, JGraphHierarchyEdge connectingEdge, JGraphFacade.CellVisitor visitor, Set seen, int layer)
Performs a depth first search on the internal hierarchy model

Parameters: parent the parent internal node of the current internal node root the current internal node connectingEdge the internal edge connecting the internal node and the parent internal node, if any visitor the visitor pattern to be called for each node seen a set of all nodes seen by this dfs a set of all of the ancestor node of the current node layer the layer on the dfs tree ( not the same as the model ranks )

dfs

public void dfs(JGraphHierarchyNode parent, JGraphHierarchyNode root, JGraphHierarchyEdge connectingEdge, JGraphFacade.CellVisitor visitor, Set seen, int[] ancestors, int childHash, int layer)
Performs a depth first search on the internal hierarchy model. This dfs extends the default version by keeping track of cells ancestors, but it should be only used when necessary because of it can be computationally intensive for deep searches.

Parameters: parent the parent internal node of the current internal node root the current internal node connectingEdge the internal edge connecting the internal node and the parent internal node, if any visitor the visitor pattern to be called for each node seen a set of all nodes seen by this dfs ancestors the parent hash code childHash the new hash code for this node layer the layer on the dfs tree ( not the same as the model ranks )

fixRanks

public void fixRanks()
Fixes the layer assignments to the values stored in the nodes. Also needs to create dummy nodes for edges that cross layers.

formOrderedHierarchy

public void formOrderedHierarchy(JGraphFacade facade, Object[] vertices)
Creates an internal ordered graph model using the vertices passed in. If there are any, leftward edge need to be inverted in the internal model

Parameters: facade the facade describing the graph to be operated on vertices the vertices to be laid out

getDfsCount

public int getDfsCount()

Returns: Returns the dfsCount.

getEdgeMapper

public Map getEdgeMapper()

Returns: Returns the edgeMapper.

getVertexMapping

public Map getVertexMapping()

Returns: Returns the vertexMapping.

initialRank

public void initialRank()
Basic determination of minimum layer ranking by working from from sources or sinks and working through each node in the relevant edge direction. Starting at the sinks is basically a longest path layering algorithm.

isDeterministic

public boolean isDeterministic()

Returns: Returns the deterministic.

isSinksAtLayerZero

public boolean isSinksAtLayerZero()

setDeterministic

public void setDeterministic(boolean deterministic)

Parameters: deterministic The deterministic to set.

setDfsCount

public void setDfsCount(int dfsCount)

Parameters: dfsCount The dfsCount to set.

setEdgeMapper

public void setEdgeMapper(Map edgeMapper)

Parameters: edgeMapper The edgeMapper to set.

setSinksAtLayerZero

public void setSinksAtLayerZero(boolean sinksAtLayerZero)

setVertexMapping

public void setVertexMapping(Map vertexMapping)

Parameters: vertexMapping The vertexMapping to set.

Copyright (C) 2001-2009 JGraph Ltd. All rights reserved.