wt.epm.retriever.graph
Class AbstractGraph

java.lang.Object
  wt.epm.retriever.graph.AbstractGraph

Direct Known Subclasses:

ResultGraph

public abstract class AbstractGraph

extends Object

Represents a graph of objects (nodes) interconnected by various links (edges). Allows fast traversing of the network, as well as building other high-performance graph algorithms. GraphNode and/or GraphLink classes can be overwritten to allow graph nodes and links to carry any additional information.

Nested Class Summary

private class

AbstractGraph.GraphAnalyzer Auxiliary inner class to eliminate some code reduplication while initializing the graph.

Field Summary

protected boolean	has_cycles Graph has cycles
protected boolean	is_forest Graph is a tree or a set of trees
protected boolean	is_inverted Graph built on "inverted" BinaryLinks
protected GraphEdge[]	links Edges (links) of the graph
static int	LNK_INVERT Inverted direction: creates a cycle in the graph
static int	LNK_JOINT Joint link (between tree branches)
static int	LNK_TREE Link belongs to spanning tree/forest
static int	LNK_UNKNOWN Not initialized yet - probably an error in the initialization code
private static Log	log
protected GraphNode[]	nodes Nodes of the graph
protected GraphNode[]	rootNodes Roots of the spanning forest

Constructor Summary

AbstractGraph()
Creates a non-inverted graph.

AbstractGraph(boolean isInverted)
Creates a graph with given direction of links.

Method Summary

protected void	analyseGraph() Build the spanning tree (or forest) of this graph.
GraphEdge[]	getGraphEdges() An array of all the GraphLink objects.
GraphNode[]	getGraphNodes() An array of all the GraphNode objects.
int	getLinkCount() Number of links (edges) in the graph.
int	getNodeCount() Number of nodes in the graph.
GraphNode[]	getRootGraphNodes() An array of nodes - roots of the spanning forest.
GraphNode	getTreeRootNode() The top node of the tree.
boolean	hasCycles() Graph is not a DAG (Directed Acyclic Graph).
boolean	isEmpty() Shortcut for getNodeCount() == 0.
boolean	isForest() Graph is a set of one or more trees.
boolean	isInverted() Graph has been built for "inverted" order of BinaryLinks: traversing from "parents" to "children" will mean moving from role B toward role A.
boolean	isTree() Graph is a tree.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

log

private static Log log

LNK_UNKNOWN

public static final int LNK_UNKNOWN

Not initialized yet - probably an error in the initialization code

See Also:

Constant Field Values

LNK_TREE

public static final int LNK_TREE

Link belongs to spanning tree/forest

See Also:

Constant Field Values

LNK_JOINT

public static final int LNK_JOINT

Joint link (between tree branches)

See Also:

Constant Field Values

LNK_INVERT

public static final int LNK_INVERT

Inverted direction: creates a cycle in the graph

See Also:

Constant Field Values

nodes

protected GraphNode[] nodes

Nodes of the graph

links

protected GraphEdge[] links

Edges (links) of the graph

rootNodes

protected GraphNode[] rootNodes

Roots of the spanning forest

is_inverted

protected boolean is_inverted

Graph built on "inverted" BinaryLinks

is_forest

protected boolean is_forest

Graph is a tree or a set of trees

has_cycles

protected boolean has_cycles

Graph has cycles

Constructor Detail

AbstractGraph

public AbstractGraph()

Creates a non-inverted graph.

AbstractGraph

public AbstractGraph(boolean isInverted)

Creates a graph with given direction of links.

Parameters:

isInverted - link from roleB to RoleA

Method Detail

analyseGraph

protected final void analyseGraph()

Build the spanning tree (or forest) of this graph. Initialize rootNodes array. Perform classification of all links regarding the structure of the graph.

getGraphNodes

public final GraphNode[] getGraphNodes()

An array of all the GraphNode objects.

Returns:

GraphNode[] never null, but may be empty

getGraphEdges

public final GraphEdge[] getGraphEdges()

An array of all the GraphLink objects.

Returns:

GraphLink[] never null, but may be empty

getRootGraphNodes

public final GraphNode[] getRootGraphNodes()

An array of nodes - roots of the spanning forest.

Returns:

GraphNode[] - has at least one element

getTreeRootNode

public final GraphNode getTreeRootNode()

The top node of the tree. If the graph actually has more than one connectivity component, just returns the root of the first of them, so check isTree() for more information.

Returns:

GraphNode getRootNodes()[0], never null

isInverted

public final boolean isInverted()

Graph has been built for "inverted" order of BinaryLinks: traversing from "parents" to "children" will mean moving from role B toward role A.

Returns:

boolean

isEmpty

public final boolean isEmpty()

Shortcut for getNodeCount() == 0.

Returns:

boolean

getNodeCount

public final int getNodeCount()

Number of nodes in the graph.

Returns:

int

getLinkCount

public final int getLinkCount()

Number of links (edges) in the graph.

Returns:

int

isTree

public final boolean isTree()

Graph is a tree. All links are of type LNK_TREE.

Returns:

boolean

isForest

public final boolean isForest()

Graph is a set of one or more trees. All links are of type LNK_TREE.

Returns:

boolean

hasCycles

public boolean hasCycles()

Graph is not a DAG (Directed Acyclic Graph). There are some links with GraphLink.getType() == LNK_INVERT, so careless traversing may result in the infinite cycle.

Returns:

boolean