treebolic.model.graph
Class Graph

java.lang.Object
  treebolic.model.graph.Graph

Direct Known Subclasses:

MutableGraph

public class Graph
extends java.lang.Object

Graph

Author:

Bernard Bou

Field Summary

(package private) static boolean	dfs
protected java.util.Set<GraphEdge>	theEdges The set of edges
protected java.util.Set<GraphNode>	theNodes The set of nodes.

Constructor Summary

protected

Graph() Constructor

Method Summary

java.util.Collection<GraphEdge>	getEdges() Returns a unmodifiable Collection of all the edges of this graph.
java.util.Collection<GraphEdge>	getEdges(GraphNode thisNode) Gets an unmodifiable collection of all edges adjacent to thisNode.
java.util.Collection<GraphNode>	getNodes() Returns a unmodifiable Collection of all nodes of this graph.
java.util.Map<GraphNode,java.util.Collection<GraphEdge>>	getNodeToEdgesMap() Returns a unmodifiable Map of all edges of this graph.
GraphNode	getNodeWithMinimumIncomingDegree() Determines a node with the minimal incoming degree.
java.util.Collection<GraphEdge>	getNonTreeEdges(GraphNode thisNode) Gets an unmodifiable collection of all edges adjacent to thisNode that has been marked as tree.
java.util.Collection<GraphEdge>	getTreeEdges(GraphNode thisNode) Gets an unmodifiable collection of all edges adjacent to thisNode that has been marked as tree.
Tree	makeSpanningTree() Returns a spanning tree of the graph.
private void	processSpanningTreeBFS(Graph thisSpanningTree, GraphNode thisRoot) Populate breadth-first search
private void	processSpanningTreeDFS(Graph thisSpanningTree, GraphNode thisRoot) Populate depth-first search
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

dfs

static final boolean dfs

See Also:

Constant Field Values

theNodes

protected java.util.Set<GraphNode> theNodes

The set of nodes.

theEdges

protected java.util.Set<GraphEdge> theEdges

The set of edges

Constructor Detail

Graph

protected Graph()

Constructor

Method Detail

getNodes

public java.util.Collection<GraphNode> getNodes()

Returns a unmodifiable Collection of all nodes of this graph. The result is unmodifiable because any deletions in the collection would leave the graph in an undefined state. To delete or add a node, the methods in this class must be used.

Returns:

the nodes of the graph.

getEdges

public java.util.Collection<GraphEdge> getEdges()

Returns a unmodifiable Collection of all the edges of this graph. The result is unmodifiable because any deletions in the collection would leave the graph in an undefined state. To delete or add an edge, the methods in this class must be used.

Returns:

the edges of the graph.

getTreeEdges

public java.util.Collection<GraphEdge> getTreeEdges(GraphNode thisNode)

Gets an unmodifiable collection of all edges adjacent to thisNode that has been marked as tree. This method ignores the direction of the edges.

Parameters:

thisNode - node.

Returns:

set of adjacent tree edges.

getNonTreeEdges

public java.util.Collection<GraphEdge> getNonTreeEdges(GraphNode thisNode)

Gets an unmodifiable collection of all edges adjacent to thisNode that has been marked as tree. This method ignores the direction of the edges.

Parameters:

thisNode - node.

Returns:

set of adjacent tree edges.

getEdges

public java.util.Collection<GraphEdge> getEdges(GraphNode thisNode)

Gets an unmodifiable collection of all edges adjacent to thisNode. This method ignores the direction of the theEdges.

Parameters:

thisNode - node.

Returns:

set of adjacent edges.

getNodeToEdgesMap

public java.util.Map<GraphNode,java.util.Collection<GraphEdge>> getNodeToEdgesMap()

Returns a unmodifiable Map of all edges of this graph. The result is unmodifiable because any deletions in the collection would leave the graph in an undefined state. To delete or add an edge, the methods in this class must be used.

Returns:

the edges of the graph.

makeSpanningTree

public Tree makeSpanningTree()

Returns a spanning tree of the graph. The spanning tree is a new instance of Tree, the nodes of the original graph and the spanning tree are shared and the edges are either shared or the spanning tree uses the reverse edges. The root of the spanning tree is the node that is returned by getNodeWithMinimumIncomingDegree(), i.e. a node with minimal incoming degree. The spanning tree is directed, i.e. the direction of all the edges is as it is expected for trees.

Returns:

A spanning tree of the graph.

processSpanningTreeDFS

private void processSpanningTreeDFS(Graph thisSpanningTree,
                                    GraphNode thisRoot)

Populate depth-first search

Parameters:

thisSpanningTree - spanning tree (stub)

thisRoot - starting node

processSpanningTreeBFS

private void processSpanningTreeBFS(Graph thisSpanningTree,
                                    GraphNode thisRoot)

Populate breadth-first search

Parameters:

thisSpanningTree - spanning tree (stub)

thisRoot - starting node

getNodeWithMinimumIncomingDegree

public GraphNode getNodeWithMinimumIncomingDegree()

Determines a node with the minimal incoming degree. Often there are several such nodes, this method returns any of these, it is not guaranteed that two seperate calls return the same node.

Returns:

A node with the minimal incoming degree.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object