Root/monav/contractionhierarchies/compressedgraph.h

1/*
2Copyright 2010 Christian Vetter veaac.fdirct@gmail.com
3
4This file is part of MoNav.
5
6MoNav is free software: you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation, either version 3 of the License, or
9(at your option) any later version.
10
11MoNav is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with MoNav. If not, see <http://www.gnu.org/licenses/>.
18*/
19
20#ifndef COMPRESSEDGRAPH_H
21#define COMPRESSEDGRAPH_H
22
23#include "interfaces/irouter.h"
24#include "utils/coordinates.h"
25#include "utils/bithelpers.h"
26#include "blockcache.h"
27#include <QString>
28#include <QFile>
29#include <algorithm>
30#include <vector>
31
32class CompressedGraph {
33
34public :
35
36        typedef unsigned NodeIterator;
37
38protected:
39
40    //TYPES
41
42    struct Block {
43        struct Settings {
44            // adress blocks from the adjacent blocks array
45            unsigned char blockBits;
46            // address an entry in the adjacent blocks array
47            //unsigned char adjacentBlockBits; ==> can be computed from adjacentBlockcount bitsNeeded( count - 1 )
48            // address an internal node with a shortcut's middle
49            //unsigned char internalBits; ==> can be computed from nodeCount bitsNeeded( count - 1 );
50            // address an external node in another block
51            unsigned char externalBits;
52            // address the first edge of a node
53            unsigned char firstEdgeBits;
54            // bits used for the short weight class
55            unsigned char shortWeightBits;
56            // bits uses for the long weight class
57            unsigned char longWeightBits;
58            // bits used for the difference ( x - minX )
59            unsigned char xBits;
60            // bits used for the difference ( y - minY )
61            unsigned char yBits;
62            // minimal x value
63            unsigned minX;
64            // minimal y value
65            unsigned minY;
66            // #nodes => used for the size of firstEdges
67            unsigned nodeCount;
68            // #adjacent blocks => used for the size of adjacentBlocks
69            unsigned adjacentBlockCount;
70        } settings;
71
72        unsigned char adjacentBlockBits;
73        unsigned char internalBits;
74
75        unsigned edges;
76        unsigned adjacentBlocks;
77        unsigned firstEdges;
78        unsigned nodeCoordinates;
79
80        unsigned id;
81        const unsigned char* buffer;
82
83        void load( unsigned id, const unsigned char* buffer )
84        {
85            CompressedGraph::loadBlock( this, id, buffer );
86        }
87    };
88
89    struct PathBlock {
90
91        struct DataItem {
92            unsigned a;
93            unsigned b;
94
95            DataItem()
96            {
97                a = b = 0;
98            }
99
100            DataItem( const IRouter::Node& node )
101            {
102                assert( bits_needed( node.coordinate.x ) < 32 );
103                a = node.coordinate.x << 1;
104                a |= 1;
105                b = node.coordinate.y;
106            }
107
108            DataItem( const IRouter::Edge& description )
109            {
110                a = description.name;
111                a <<= 1;
112                a |= description.branchingPossible ? 1 : 0;
113                a <<= 1;
114                b = description.type;
115                b <<= 16;
116                b |= description.length;
117                b <<= 8;
118                b |= encode_integer< 4, 4 >( description.seconds );
119            }
120
121            bool isNode() const
122            {
123                return ( a & 1 ) == 1;
124            }
125
126            bool isEdge() const
127            {
128                return ( a & 1 ) == 0;
129            }
130
131            IRouter::Node toNode()
132            {
133                IRouter::Node node;
134                node.coordinate = UnsignedCoordinate( a >> 1, b );
135                return node;
136            }
137
138            IRouter::Edge toEdge()
139            {
140                IRouter::Edge edge;
141                edge.name = a >> 2;
142                edge.branchingPossible = ( a & 2 ) == 2;
143                edge.type = b >> 24;
144                edge.length = ( b >> 8 ) & ( ( 1u << 16 ) -1 );
145                edge.seconds = decode_integer< 4, 4 >( b & 255 );
146                return edge;
147            }
148        };
149
150        unsigned id;
151        const unsigned char* buffer;
152
153        void load( unsigned id, const unsigned char* buffer )
154        {
155            CompressedGraph::loadPathBlock( this, id, buffer );
156        }
157    };
158
159public:
160
161    // TYPES
162
163    struct Edge {
164        NodeIterator source;
165        NodeIterator target;
166        struct Data {
167            unsigned distance;
168            bool shortcut : 1;
169            bool forward : 1;
170            bool backward : 1;
171            bool unpacked : 1;
172            bool reversed : 1;
173            union {
174                NodeIterator middle;
175                unsigned id;
176            };
177            unsigned path;
178        } data;
179
180        bool operator<( const Edge& right ) const {
181            if ( source != right.source )
182                return source < right.source;
183            int l = ( data.forward ? -1 : 0 ) + ( data.backward ? 1 : 0 );
184            int r = ( right.data.forward ? -1 : 0 ) + ( right.data.backward ? 1 : 0 );
185            if ( l != r )
186                return l < r;
187            if ( target != right.target )
188                return target < right.target;
189            return data.distance < right.data.distance;
190        }
191
192    };
193
194    class EdgeIterator {
195
196        friend class CompressedGraph;
197
198    public:
199
200        EdgeIterator()
201        {
202        }
203
204        bool hasEdgesLeft()
205        {
206            return m_position < m_end;
207        }
208
209        NodeIterator target() const { return m_target; }
210        bool forward() const { return m_data.forward; }
211        bool backward() const { return m_data.backward; }
212        bool shortcut() const { return m_data.shortcut; }
213        bool unpacked() const { return m_data.unpacked; }
214        NodeIterator middle() const { return m_data.middle; }
215        unsigned distance() const { return m_data.distance; }
216        IRouter::Edge description() const { return IRouter::Edge( m_data.description.nameID, m_data.description.branchingPossible, m_data.description.type, 1, ( m_data.distance + 5 ) / 10 ); }
217#ifdef NDEBUG
218    private:
219#endif
220
221        EdgeIterator( unsigned source, const Block& block, unsigned position, unsigned end ) :
222                m_block( &block ), m_source( source ), m_position( position ), m_end( end )
223        {
224        }
225
226        const Block* m_block;
227        NodeIterator m_target;
228        NodeIterator m_source;
229        unsigned m_position;
230        unsigned m_end;
231
232        struct EdgeData {
233            unsigned distance;
234            bool shortcut : 1;
235            bool forward : 1;
236            bool backward : 1;
237            bool unpacked : 1;
238            bool reversed : 1;
239            union {
240                NodeIterator middle;
241                struct {
242                    unsigned nameID : 30;
243                    bool branchingPossible : 1;
244                    unsigned type;
245                } description;
246            };
247            unsigned path;
248        } m_data;
249    };
250
251    // FUNCTIONS
252
253    CompressedGraph()
254    {
255        m_loaded = false;
256    }
257
258    ~CompressedGraph()
259    {
260        if ( m_loaded )
261            unloadGraph();
262    }
263
264    bool loadGraph( QString filename, unsigned cacheSize )
265    {
266        if ( m_loaded )
267            unloadGraph();
268        QFile settingsFile( filename + "_config" );
269        if ( !settingsFile.open( QIODevice::ReadOnly ) ) {
270            qCritical() << "failed to open file:" << settingsFile.fileName();
271            return false;
272        }
273        m_settings.read( settingsFile );
274        if ( !m_blockCache.load( filename + "_edges", cacheSize / m_settings.blockSize / 2 + 1, m_settings.blockSize ) )
275            return false;
276        if ( !m_pathCache.load( filename + "_paths", cacheSize / m_settings.blockSize / 2 + 1, m_settings.blockSize ) )
277            return false;
278        m_loaded = true;
279        return true;
280    }
281
282    EdgeIterator edges( NodeIterator node )
283    {
284        unsigned blockID = nodeToBlock( node );
285        unsigned internal = nodeToInternal( node );
286        const Block* block = getBlock( blockID );
287        return unpackFirstEdges( *block, internal );
288    }
289
290    EdgeIterator findEdge( NodeIterator source, NodeIterator target, unsigned id )
291    {
292        if ( source < target )
293            std::swap( source, target );
294        EdgeIterator e = edges( source );
295        while ( e.hasEdgesLeft() ) {
296            unpackNextEdge( &e );
297            if ( e.target() != target )
298                continue;
299            if ( e.shortcut() )
300                continue;
301            if ( id != 0 ) {
302                id--;
303                continue;
304            }
305
306            return e;
307        }
308        assert( false );
309        return e;
310    }
311
312    void unpackNextEdge( EdgeIterator* edge )
313    {
314        const Block& block = *edge->m_block;
315        EdgeIterator::EdgeData& edgeData = edge->m_data;
316        const unsigned char* buffer = block.buffer + ( edge->m_position >> 3 );
317        int offset = edge->m_position & 7;
318
319        // forward + backward flag
320        bool forwardAndBackward = read_unaligned_unsigned( &buffer, 1, &offset ) != 0;
321        if ( forwardAndBackward ) {
322            edgeData.forward = true;
323            edgeData.backward = true;
324        } else {
325            edgeData.forward = read_unaligned_unsigned( &buffer, 1, &offset ) != 0;
326            edgeData.backward = !edgeData.forward;
327        }
328
329        // target
330        bool internalTarget = read_unaligned_unsigned( &buffer, 1, &offset ) != 0;
331        if ( internalTarget ) {
332            unsigned target = read_unaligned_unsigned( &buffer, bits_needed( edge->m_source ), &offset );
333            edge->m_target = nodeFromDescriptor( block.id, target );
334        } else {
335            unsigned adjacentBlock = read_unaligned_unsigned( &buffer, block.adjacentBlockBits, &offset );
336            unsigned target = read_unaligned_unsigned( &buffer, block.settings.externalBits, &offset );
337            unsigned adjacentBlockPosition = block.adjacentBlocks + adjacentBlock * block.settings.blockBits;
338            unsigned targetBlock = read_unaligned_unsigned( block.buffer + ( adjacentBlockPosition >> 3 ), block.settings.blockBits, adjacentBlockPosition & 7 );
339            edge->m_target = nodeFromDescriptor( targetBlock, target );
340        }
341
342        // weight
343        bool longWeight = block.settings.shortWeightBits == block.settings.longWeightBits;
344        if ( !longWeight )
345            longWeight = read_unaligned_unsigned( &buffer, 1, &offset ) != 0;
346        edgeData.distance = read_unaligned_unsigned( &buffer, longWeight ? block.settings.longWeightBits : block.settings.shortWeightBits, &offset );
347
348        // unpacked
349        edgeData.unpacked = read_unaligned_unsigned( &buffer, 1, &offset ) != 0;
350        if ( edgeData.unpacked ) {
351            if ( forwardAndBackward )
352                edgeData.reversed = read_unaligned_unsigned( &buffer, 1, &offset ) != 0;
353            else
354                edgeData.reversed = edgeData.backward;
355            edgeData.path = read_unaligned_unsigned( &buffer, m_settings.pathBits, &offset );
356        }
357
358        // shortcut
359        edgeData.shortcut = read_unaligned_unsigned( &buffer, 1, &offset ) != 0;
360        if ( edgeData.shortcut ) {
361            if ( !edgeData.unpacked ) {
362                unsigned middle = read_unaligned_unsigned( &buffer, block.internalBits, &offset );
363                edgeData.middle = nodeFromDescriptor( block.id, middle );
364            }
365        }
366
367        // edge description
368        if ( !edgeData.shortcut && !edgeData.unpacked ) {
369            edgeData.description.type = read_unaligned_unsigned( &buffer, m_settings.typeBits, &offset );
370            edgeData.description.nameID = read_unaligned_unsigned( &buffer, m_settings.nameBits, &offset );
371            edgeData.description.branchingPossible = read_unaligned_unsigned( &buffer, 1, &offset );
372        }
373
374        edge->m_position = ( buffer - block.buffer ) * 8 + offset;
375    }
376
377    IRouter::Node node( NodeIterator node )
378    {
379        unsigned blockID = nodeToBlock( node );
380        unsigned internal = nodeToInternal( node );
381        const Block* block = getBlock( blockID );
382        IRouter::Node result;
383        unpackCoordinates( *block, internal, &result.coordinate );
384        return result;
385    }
386
387    unsigned numberOfNodes() const
388    {
389        return m_settings.numberOfNodes;
390    }
391
392    unsigned numberOfEdges() const
393    {
394        return m_settings.numberOfEdges;
395    }
396
397    template< class T, class S >
398    void path( const EdgeIterator& edge, T path, S edges, bool forward )
399    {
400        assert( edge.unpacked() );
401        unsigned pathBegin = path->size();
402        unsigned edgesBegin = edges->size();
403        int increase = edge.m_data.reversed ? -1 : 1;
404
405        IRouter::Node targetNode = node( edge.target() );
406        unsigned pathID = edge.m_data.path;
407
408        if ( !forward ) {
409            PathBlock::DataItem data = unpackPath( pathID );
410            assert( data.isNode() );
411            path->push_back( data.toNode().coordinate );
412        }
413
414        pathID += increase;
415
416        while( true ) {
417            PathBlock::DataItem data = unpackPath( pathID );
418            if ( data.isEdge() ) {
419                edges->push_back( data.toEdge() );
420                pathID += increase;
421                continue;
422            }
423            assert( data.isNode() );
424            IRouter::Node node = data.toNode();
425            if ( node.coordinate.x == targetNode.coordinate.x && node.coordinate.y == targetNode.coordinate.y )
426                break;
427            path->push_back( node.coordinate );
428            pathID += increase;
429        }
430
431        if ( forward ) {
432            path->push_back( targetNode.coordinate );
433        } else {
434            std::reverse( path->begin() + pathBegin, path->end() );
435            std::reverse( edges->begin() + edgesBegin, edges->end() );
436        }
437
438        assert( edges->size() != ( int ) edgesBegin ); // at least one edge description has to be present
439    }
440
441protected:
442
443    // TYPES
444
445    struct GlobalSettings {
446        unsigned blockSize;
447        unsigned char internalBits;
448        unsigned char pathBits;
449        unsigned char typeBits;
450        unsigned char nameBits;
451        unsigned numberOfNodes;
452        unsigned numberOfEdges;
453
454        void read( QFile& in )
455        {
456            in.read( ( char* ) &blockSize, sizeof( blockSize ) );
457            in.read( ( char* ) &internalBits, sizeof( internalBits ) );
458            in.read( ( char* ) &pathBits, sizeof( pathBits ) );
459            in.read( ( char* ) &typeBits, sizeof( typeBits ) );
460            in.read( ( char* ) &nameBits, sizeof( nameBits ) );
461            in.read( ( char* ) &numberOfNodes, sizeof( numberOfNodes ) );
462            in.read( ( char* ) &numberOfEdges, sizeof( numberOfEdges ) );
463        }
464
465        void write( QFile& out )
466        {
467            out.write( ( const char* ) &blockSize, sizeof( blockSize ) );
468            out.write( ( const char* ) &internalBits, sizeof( internalBits ) );
469            out.write( ( const char* ) &pathBits, sizeof( pathBits ) );
470            out.write( ( const char* ) &typeBits, sizeof( typeBits ) );
471            out.write( ( const char* ) &nameBits, sizeof( nameBits ) );
472            out.write( ( const char* ) &numberOfNodes, sizeof( numberOfNodes ) );
473            out.write( ( const char* ) &numberOfEdges, sizeof( numberOfEdges ) );
474        }
475    };
476
477    struct nodeDescriptor {
478        unsigned block;
479        unsigned node;
480    };
481
482    // FUNCTIONS
483
484    PathBlock::DataItem unpackPath( unsigned position ) {
485        unsigned blockID = position / ( m_settings.blockSize / 8 );
486        unsigned internal = ( position % ( m_settings.blockSize / 8 ) ) * 8;
487        const PathBlock* block = getPathBlock( blockID );
488        PathBlock::DataItem data;
489        data.a = *( ( unsigned* ) ( block->buffer + internal ) );
490        data.b = *( ( unsigned* ) ( block->buffer + internal + 4 ) );
491        return data;
492    }
493
494    void unpackCoordinates( const Block& block, unsigned node, UnsignedCoordinate* result )
495    {
496        unsigned position = block.nodeCoordinates + ( block.settings.xBits + block.settings.yBits ) * node;
497        const unsigned char* buffer = block.buffer + ( position >> 3 );
498        int offset = position & 7;
499        result->x = read_unaligned_unsigned( &buffer, block.settings.xBits, &offset ) + block.settings.minX;
500        result->y = read_unaligned_unsigned( buffer, block.settings.yBits, offset ) + block.settings.minY;
501    }
502
503    EdgeIterator unpackFirstEdges( const Block& block, unsigned node )
504    {
505        unsigned position = block.firstEdges + block.settings.firstEdgeBits * node;
506        const unsigned char* buffer = block.buffer + ( position >> 3 );
507        int offset = position & 7;
508        unsigned begin = read_unaligned_unsigned( &buffer, block.settings.firstEdgeBits, &offset );
509        unsigned end = read_unaligned_unsigned( buffer, block.settings.firstEdgeBits, offset );
510        return EdgeIterator( node, block, begin + block.edges, end + block.edges );
511    }
512
513    const Block* getBlock( unsigned block )
514    {
515        return m_blockCache.getBlock( block );
516    }
517
518    const PathBlock* getPathBlock( unsigned block )
519    {
520        return m_pathCache.getBlock( block );
521    }
522
523    unsigned nodeToBlock( NodeIterator node )
524    {
525        return node >> m_settings.internalBits;
526    }
527
528    unsigned nodeToInternal( NodeIterator node )
529    {
530        return read_bits( node, m_settings.internalBits );
531    }
532
533    NodeIterator nodeFromDescriptor( nodeDescriptor node )
534    {
535        NodeIterator result = ( node.block << m_settings.internalBits ) | node.node;
536        assert( nodeToBlock( result ) == node.block );
537        assert( nodeToInternal( result ) == node.node );
538        return result;
539    }
540
541    NodeIterator nodeFromDescriptor( unsigned block, unsigned node )
542    {
543        NodeIterator result = ( block << m_settings.internalBits ) | node;
544        assert( nodeToBlock( result ) == block );
545        assert( nodeToInternal( result ) == node );
546        return result;
547    }
548
549    static void loadBlock( Block* block, unsigned blockID, const unsigned char* blockBuffer )
550    {
551        const unsigned char* buffer = blockBuffer;
552        int offset = 0;
553
554        // read settings
555        block->settings.blockBits = read_unaligned_unsigned( &buffer, 8, &offset );
556        block->settings.externalBits = read_unaligned_unsigned( &buffer, 8, &offset );
557        block->settings.firstEdgeBits = read_unaligned_unsigned( &buffer, 8, &offset );
558        block->settings.shortWeightBits = read_unaligned_unsigned( &buffer, 8, &offset );
559        block->settings.longWeightBits = read_unaligned_unsigned( &buffer, 8, &offset );
560        block->settings.xBits = read_unaligned_unsigned( &buffer, 8, &offset );
561        block->settings.yBits = read_unaligned_unsigned( &buffer, 8, &offset );
562        block->settings.minX = read_unaligned_unsigned( &buffer, 32, &offset );
563        block->settings.minY = read_unaligned_unsigned( &buffer, 32, &offset );
564        block->settings.nodeCount = read_unaligned_unsigned( &buffer, 32, &offset );
565        block->settings.adjacentBlockCount = read_unaligned_unsigned( &buffer, 32, &offset );
566
567        // set other values
568        block->internalBits = bits_needed( block->settings.nodeCount - 1 );
569        block->adjacentBlockBits = bits_needed( block->settings.adjacentBlockCount - 1 );
570        block->id = blockID;
571        block->buffer = blockBuffer;
572
573        // compute offsets
574        block->nodeCoordinates = ( buffer - blockBuffer ) * 8 + offset;
575        block->adjacentBlocks = block->nodeCoordinates + ( block->settings.xBits + block->settings.yBits ) * block->settings.nodeCount;
576        block->firstEdges = block->adjacentBlocks + block->settings.blockBits * block->settings.adjacentBlockCount;
577        block->edges = block->firstEdges + block->settings.firstEdgeBits * ( block->settings.nodeCount + 1 );
578    }
579
580    static void loadPathBlock( PathBlock* block, unsigned blockID, const unsigned char* blockBuffer )
581    {
582        block->id = blockID;
583        block->buffer = blockBuffer;
584    }
585
586    void unloadGraph()
587    {
588        m_blockCache.unload();
589        m_pathCache.unload();
590    }
591
592    // VARIABLES
593
594    GlobalSettings m_settings;
595    BlockCache< Block > m_blockCache;
596    BlockCache< PathBlock > m_pathCache;
597    bool m_loaded;
598};
599
600#endif // COMPRESSEDGRAPH_H
601

Archive Download this file

Branches:
master



interactive