geometry.object
Class SkeletonGraph

java.lang.Object
  geometry.object.SkeletonGraph

public class SkeletonGraph
extends java.lang.Object

A skeleton graph is a reduction of the skeleton to only end nodes and junction nodes. The vertices of the graph are the end nodes and junction nodes, respectively. Two vertices in the skeleton graph are connected if there exists a skeleton branch (see SkeletonBranch) between them. The edge weight is given by the length of the corresponding skeleton part. This data structure is needed mostly for searching the shortest paths in the skeleton to create the skeleton paths.

Field Summary

private org.jgrapht.graph.SimpleDirectedWeightedGraph<SkeletonNode,SkeletonBranch>	graph the "real" skeleton graph
private org.apache.log4j.Logger	logger logger instance

Constructor Summary

SkeletonGraph()
constructor.

Method Summary

boolean	addEdge(SkeletonBranch part) add the specified edge (defined by the SkeletonBranch to the graph.
boolean	addVertex(SkeletonNode node) Add a new vertex to the graph.
void	deleteUnconnectedComponents() If the skeleton graph is not connected, the unconnected parts are deleted.
java.util.List<SkeletonNode>	getAllVertexNeighbors(SkeletonNode node) Get all vertices in the graph directly connected to the specified vertex.
java.util.Set<SkeletonNode>	getAllVertices() Get all vertices in this graph.
java.util.Set<SkeletonBranch>	getOutgoingEdges(SkeletonNode node) return the edges emanating from the specified node
SkeletonPath	getShortestPath(SkeletonNode start, SkeletonNode end) Get the shortest path in the graph from the specified start node to the specified end node.
boolean	removeVertex(SkeletonNode node)

Methods inherited from class java.lang.Object

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

Field Detail

graph

private final org.jgrapht.graph.SimpleDirectedWeightedGraph<SkeletonNode,SkeletonBranch> graph

the "real" skeleton graph

logger

private final org.apache.log4j.Logger logger

logger instance

Constructor Detail

SkeletonGraph

public SkeletonGraph()

constructor. Directly create an empty graph to avoid null pointers

Method Detail

addVertex

public boolean addVertex(SkeletonNode node)

Add a new vertex to the graph. Duplicates are not allowed. If the vertex already exists, the graph remains unchanged.

Parameters:

node - - the vertex to be added

Returns:

true if the vertex could be added, false if not.

removeVertex

public boolean removeVertex(SkeletonNode node)

addEdge

public boolean addEdge(SkeletonBranch part)

add the specified edge (defined by the SkeletonBranch to the graph. Start and end vertex of the edge are extracted from the specified skeleton part.

Parameters:

part - the edge to be added

Returns:

true if the edge could be created, false if not

getAllVertexNeighbors

public java.util.List<SkeletonNode> getAllVertexNeighbors(SkeletonNode node)

Get all vertices in the graph directly connected to the specified vertex.

Parameters:

node - - the vertex to get the neighbor for

Returns:

a list of all vertices directly connected to the specified node

deleteUnconnectedComponents

public void deleteUnconnectedComponents()

If the skeleton graph is not connected, the unconnected parts are deleted.

First, the "main skeleton graph" is found: The biggest connected graph component is seen as "main skeleton". Then, all vertices that are not connected to the main skeleton, and therewith all connected edges with these vertices are deleted.

getAllVertices

public java.util.Set<SkeletonNode> getAllVertices()

Get all vertices in this graph.

Returns:

set of all vertices

getShortestPath

public SkeletonPath getShortestPath(SkeletonNode start,
                                    SkeletonNode end)

Get the shortest path in the graph from the specified start node to the specified end node.

Parameters:

start - the start node

end - the end node

Returns:

the shortest SkeletonPath from start to end

getOutgoingEdges

public java.util.Set<SkeletonBranch> getOutgoingEdges(SkeletonNode node)

return the edges emanating from the specified node

Parameters:

node -

Returns:

get all edges (=SkeletonBranches) emanating from the specified node