With the new module LEDA graph isomorphisms you receive efficient algorithms for your subgraph testing problems. Read the paper Graph Isomorphism Implementation in LEDA 5.1 for more details, have a look in the 5.1 manual and play around with the demo program demo/graph_iso/gw_isomorphism.cpp (part of your LEDA package).

Overview:

• r_circle_polygon and r_circle_gen_polygon: Polygons, consisting of straight line segments as well as circular segments; all polygon operations supported.
• r_circle_segment (and sweep): considerable speed-up
• data type real: significant speed-up

The LEDA types polygon and gen_polygon allow only straight line edges. Several of our customers have to compute with polygons where at least some edges are circular arcs. Often approximating such an edge by several straight line segments is not appropriate.

With version 5.0 LEDA provides two new data types called r_circle_polygon and r_circle_gen_polygon that can handle polygons having straight line segments as well as circular arcs.

With version 5.1 some of our exact computation with circular arcs are now about 10 times faster than before. And approximated computation (= input and output data contain curved segments, only the computation uses straight line approximations) of boolean operations is now as fast as in the case of straight line segments.

The type r_circle_gen_polygon allows to model polygons with holes. All the usual polygon operations are provided.

In particular, we offer the following boolean operations:

• intersection,
• union,
• difference and
• symmetric difference.

We want to point out that all these computations are exact, i.e. no rounding errors can occur.

Documentation:
Read the manual page on r_circle_gen_polygon.
Read the manual page on r_circle_polygon.

Overview:

• decoding_i(f)stream: new, supports random access seeks on compressed files
• BlockCoder<C>: new, provides blockwise encoding/decoding which speeds up seeks
• DeflateCoder: considerable speed-up for both encoding and decoding
• A0Coder: new order0-model implementation, yields speed-up
• AdaptiveHuffmanCoder: new coder
• BWTCoder: new implementation, twice as fast and uses 40% less space
• checksummers: supports seek in decode mode in constant time
• PPMIICoder: new, outperforms bzip2 with respect to compression ration as well as speed
• MTF2Coder: new, sometimes better results than MTFCoder
• RLE0Coder: new, to be used in combination with MTF2

LEDA provides several coders for the compression of your data.

Highlights:

• Our PPMIICoder outperforms bzip2 with respect to compression rates and speed.
  
• BWTCoder and DeflateCoder are much faster now.

Suppose you have a large compressed data base and you want to retrieve only some selected records without decompressing the whole file: Then you can benefit from the new LEDA class BlockCoder which speeds up random access reading of encoded files. Reading and seeking on encoded files does not differ from unencoded files.

Convince yourself how easy it is: Have a look at an example. More examples in the package.

Documentation: Read the manual page.

• Symmetric encryption and authentification
• CipherKey: key generation from passphrase (and optionally salt)
• Blowfish, Twofish, Rijndael (=AES): block ciphers to be plugged into the following coders
• ECBCoder, CBCCoder, CFBCoder, OFBCoder: coders for symmetric key encryption/decryption (block cipher modes as stream ciphers)
• OMACCoder: symmetric key authentication (based on a block cipher)
• SHACoder: new checksummer, implements SHA-1 hash algorithm
• CryptAutoDecoder: like AutoDecoder, but allows the user to specify keys
• secure_socket_streambuf: supports easy and secure internet connections based on leda_socket

You want to protect your data with cryptography? LEDA offers all the tools you need:

• Key Generation:
  derive keys from easy-to-remember human-readable passphrases.
  
• Encryption / Decryption:
  make sure that nobody else can read your secret data.
  
• Authentication:
  verify that nobody (in particular no virus) has tampered with your sensitive data.

Enhancing your application with cryptography is simple. Have a look at an example.

It also shows you how seamlessly cryptography integrates with compression.

Some technical details:

block ciphers: Rijndael(=AES), Blowfish, Twofish

block cipher modes: ECB, CBC, CFB, OFB (for encryption) and OMAC (for authentication)

new checksummer: SHA-1 hashing

Documentation: Read the manual page.

« click figure at the left to see details »

Most graph algorithms do not change the underlying graph, they work on a constant or static graph. A static graph consists of a fixed sequence of nodes and edges. In many cases static graphs are much more efficient (time as well as space efficient) than other graph implementations. LEDA improves the time efficiency of flow algorithms significantly.

What are Static Graphs?

Most graph algorithms do not change the underlying graph, they work on a constant or static graph. A static graph consists of a fixed sequence of nodes and edges. New nodes or edges can be appended only in a construction phase which has to be started by calling G.start_construction() and terminated by G.finish_construction(). After the construction phase both sequences V and E are fixed.

There are different models of static graphs; the class is parameterized by the so called graph category. There are directed graphs, bidirectional graphs, opposite graphs, bidirected graphs and undirected graphs. Currently, the first three are available.

See the manual page for a definition.

Finally static graphs support several efficient ways - efficient compared to using node_arrays, edge_arrays, node_maps, and edge_maps - to associate data with the edges and nodes of the graph.

The manual page explains the details.

Why should you use Static Graphs?

In many cases static graphs are much more efficient (time as well as space efficient) than other graph implementations.

In our experiments, running maxflow algorithms on networks produced by the ak-generator of Cherkassy and Goldberg, we received the following results:

Table of results.

The running time improvement is up to 65% (or even up to 75% if we compare static graphs using static slots with L E D A graphs using external arrays), the space savings are up to 62%.

LEDA 5.1 brings new implementations, the time efficiency of several flow algorithms improved even more.

Samples: Have a look at an example.

Documentation: Read the manual page.