com.luciad.network.graph.numeric

Graph and Routing EngineClass TLcdNumericGraphEncoder

java.lang.Object

com.luciad.network.graph.numeric.TLcdNumericGraphEncoder

All Implemented Interfaces:

ILcdOutputStreamFactoryCapable

public class TLcdNumericGraphEncoder
extends Object
implements ILcdOutputStreamFactoryCapable

Encoder for exporting graphs to numeric graphs and saving numeric graphs after they have been modified.

Exporting graphs

Multi-leveled partitioned graphs can be converted into numerical graphs via this encoder. During the export phase, each partition, node and edge is mapped onto a numerical counterpart, computed by the encoder (see the documentation of TLcdNumericGraph for a description of how these numerical identifiers are computed).

The result will be written to disk incrementally, to allow processing of very large graphs which do not fit completely in memory.

All mappings are reported to the user via a ILcdNumericGraphMappingHandler callback.

If the graph is exported with an edge value function, the encoder will automatically encode the edge values and compute and encode the distance tables as well.

Saving graphs

The encoder allows saving numerical graphs to the location they were decoded from. Only the files that have changed (due to changes in the graph) will be saved. For optimal performance, it is important to split up very large graphs in multiple files.

File format

The following files are written to disk:

• *.ng: topology files, describing the topological structure of the graph - the partitions, nodes, edges and their connectivity.
• *.ngv: edge value files, containing the edge values for all edges in the topology files.
• *.ngd: distance table files, containing the distance tables for the topology+edge value files.

The Network developer guide contains a detailed description of the format of each of these file types.

Splitting files

The encoder allows splitting up the graph's data in multiple files. Splitting is done at partition level. Two mechanisms are provided to control the splitting process:

• Node split threshold: a partition is only saved in a separate file if it contains at least as many nodes as the node split threshold.
• Split levels: a partition is only saved in a separate file if its hierarchical level within the graph structure is one of the specified split levels.

Only if both the node split threshold and split level condition are fulfilled, a partition will be saved to a separate file. Both parameters can be configured via the API.

Value Encoding format

Edge value encoding takes up a considerable part of the graph's size on disk. The edge value encoding can therefore be configured to obtain smaller files. See the TLcdNumericGraphEncoder.EdgeValueEncoding documentation for more information on the available encodings.

Since:

9.1

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	TLcdNumericGraphEncoder.EdgeValueEncoding Enumeration describing the encoding of edge values.

Constructor Summary

Constructors

Constructor and Description
TLcdNumericGraphEncoder()

Method Summary

Modifier and Type	Method and Description
<N,E> void	exportEdgeValueFunction(ILcdGraph<N,E> aGraph, ILcdEdgeValueFunction<N,E> aEdgeValueFunction, String aTopologySourceName, String aEdgeValuesDestinationName) Exports the specified edge value function for the specified graph.
<N,E> void	exportGraph(ILcdGraph<N,E> aGraph, ILcdEdgeValueFunction<N,E> aEdgeValueFunction, ILcdNumericGraphMappingHandler<N,E> aMappingHandler, String aTopologyDestinationName, String aEdgeValuesDestinationName) Export the specified graph and edge value function to a numeric graph.
TLcdNumericGraphEncoder.EdgeValueEncoding	getEdgeValueEncoding() Returns the encoding mode for encoding edge values.
int	getExpansionSize() Returns the number of extra slots that is reserved in each partition for adding extra edges after the graph has been converted to a numeric graph.
int[]	getNodeSplitThresholds() Return for each level in the graph hierarchy the minimum number of nodes a partition should have before being encoded to a separate file.
ILcdOutputStreamFactory	getOutputStreamFactory() Returns the com.luciad.io.ILcdOutputStreamFactory which is used for creating output streams.
void	saveGraph(TLcdNumericGraph aGraph) Saves a numeric graph to the location it was decoded from.
void	setEdgeValueEncoding(TLcdNumericGraphEncoder.EdgeValueEncoding aValueEncoding) Sets the encoding mode for encoding edge values.
void	setExpansionSize(int aExpansionSize) Sets the number of extra slots to be reserved in each partition for adding extra edges after the graph has been converted to a numeric graph.
void	setNodeSplitThresholds(int[] aNodeSplitThresholds) Sets for each level in the graph hierarchy the minimum number of nodes a partition should have before being encoded to a separate file.
void	setOutputStreamFactory(ILcdOutputStreamFactory aOutputStreamFactory) Sets the com.luciad.io.ILcdOutputStreamFactory to be used for creating output streams.

Methods inherited from class java.lang.Object

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

Constructor Detail

TLcdNumericGraphEncoder

public TLcdNumericGraphEncoder()

Method Detail

setExpansionSize

public void setExpansionSize(int aExpansionSize)

Sets the number of extra slots to be reserved in each partition for adding extra edges after the graph has been converted to a numeric graph. The default value is 100. The higher this number, the more bits in the numerical id's will be reserved for future use by extra edges. If this number is set too high, the encoder might not be able to generate enough id's for all edges and nodes.

Parameters:

aExpansionSize - the number of extra slots to be reserved in each partition for adding extra edges after the graph has been converted to a numeric graph.

See Also:

getExpansionSize()

getExpansionSize

public int getExpansionSize()

Returns the number of extra slots that is reserved in each partition for adding extra edges after the graph has been converted to a numeric graph. The default value is 100.

Returns:

the number of extra slots to be reserved in each partition for adding extra edges after the graph has been converted to a numeric graph.

See Also:

getExpansionSize()

getEdgeValueEncoding

public TLcdNumericGraphEncoder.EdgeValueEncoding getEdgeValueEncoding()

Returns the encoding mode for encoding edge values.

Returns:

the encoding mode for encoding edge values.

See Also:

setEdgeValueEncoding(EdgeValueEncoding)

setEdgeValueEncoding

public void setEdgeValueEncoding(TLcdNumericGraphEncoder.EdgeValueEncoding aValueEncoding)

Sets the encoding mode for encoding edge values. The default is TLcdNumericGraphEncoder.EdgeValueEncoding.STANDARD.

Parameters:

aValueEncoding - the encoding mode for encoding edge values.

See Also:

getEdgeValueEncoding()

setNodeSplitThresholds

public void setNodeSplitThresholds(int[] aNodeSplitThresholds)

Sets for each level in the graph hierarchy the minimum number of nodes a partition should have before being encoded to a separate file. If a partition has a number of nodes larger than the specified threshold, the partition's data will be encoded to separate files. Hierarchical levels with value -1 or beyond the size of the specified array will never be split.

The default split configuration is {-1,1000} (partitions on the highest level will never be split, partitions on the second level will be split if the number of nodes is larger than 1000, lower level partitions will never be split).

Parameters:

aNodeSplitThresholds - the array with node split thresholds for which a file split should be considered.

See Also:

getNodeSplitThresholds()

getNodeSplitThresholds

public int[] getNodeSplitThresholds()

Return for each level in the graph hierarchy the minimum number of nodes a partition should have before being encoded to a separate file.

Returns:

the array with node split thresholds for which a file split should be considered.

See Also:

setNodeSplitThresholds(int[])

getOutputStreamFactory

public ILcdOutputStreamFactory getOutputStreamFactory()

Returns the com.luciad.io.ILcdOutputStreamFactory which is used for creating output streams.

Specified by:

getOutputStreamFactory in interface ILcdOutputStreamFactoryCapable

Returns:

the output stream factory which is used for creating output streams.

See Also:

setOutputStreamFactory(com.luciad.io.ILcdOutputStreamFactory)

setOutputStreamFactory

public void setOutputStreamFactory(ILcdOutputStreamFactory aOutputStreamFactory)

Sets the com.luciad.io.ILcdOutputStreamFactory to be used for creating output streams. By default, a com.luciad.io.TLcdFileOutputStreamFactory is used.

Specified by:

setOutputStreamFactory in interface ILcdOutputStreamFactoryCapable

Parameters:

aOutputStreamFactory - the factory to be used for creating output streams.

See Also:

getOutputStreamFactory()

exportGraph

public <N,E> void exportGraph(ILcdGraph<N,E> aGraph,
                              ILcdEdgeValueFunction<N,E> aEdgeValueFunction,
                              ILcdNumericGraphMappingHandler<N,E> aMappingHandler,
                              String aTopologyDestinationName,
                              String aEdgeValuesDestinationName)
                       throws IOException

Export the specified graph and edge value function to a numeric graph.

This method performs the following actions:

• It converts the specified graph to a numeric graph.
• It computes for each edge in the graph its forward and backward edge value using the specified edge value function.
• The topology (partitions, nodes, connecting edges) of the numeric graph, together with the edge values, are stored in one or more output streams.
• For each partition in the graph, the distance table is computed. If the graph is multileveled, the distance tables will be computed recursively for all levels.
• The distance tables are all stored using output streams.

Every mapping from a node or edge to a corresponding numeric identifier in the destination numeric graph is reported to the com.luciad.network.graph.numeric.ILcdNumericGraphMappingHandler that is specified.

Parameters:

aGraph - the graph to be converted to a numeric graph.

aEdgeValueFunction - the edge value function describing the weights of the edges in the graph.

aMappingHandler - the mapping handler to which all node and edge mappings should be reported.

aTopologyDestinationName - the destination name for the main graph file.

aEdgeValuesDestinationName - the destination name for the main graph values file.

Throws:

IOException - if an I/O exception occurs while exporting.

saveGraph

public void saveGraph(TLcdNumericGraph aGraph)
               throws IOException

Saves a numeric graph to the location it was decoded from. Only the files that have been changed will be overwritten.

Parameters:

aGraph - the graph to be saved.

Throws:

IOException - if an I/O exception occurs while saving.

exportEdgeValueFunction

public <N,E> void exportEdgeValueFunction(ILcdGraph<N,E> aGraph,
                                          ILcdEdgeValueFunction<N,E> aEdgeValueFunction,
                                          String aTopologySourceName,
                                          String aEdgeValuesDestinationName)
                                   throws IOException

Exports the specified edge value function for the specified graph. This can only be done if the graph has already been exported to a numeric graph in a previous step. The graph topology files will remain untouched.

Note that the specified graph should be the original graph, not the numeric graph resulting from a previous export! It is important that the getNodes(), getEdges() and getPartitions() methods return the same sequence (same order) of nodes/edges/partitions, as during the original encoding. Also, the encoding parameters (node split threshold, split levels and expansion size) should be identical to the ones used during the original encoding.

Parameters:

aGraph - the graph for which to export an edge value function.

aEdgeValueFunction - the edge value function to export.

aTopologySourceName - the location of the main graph topology file.

aEdgeValuesDestinationName - the location of the main edge value file where the values should be stored.

Throws:

IOException - if an I/O exception occurs while exporting.