edge_num.h

Go to the documentation of this file.

//
// This program can be freely used in an academic environment
// ONLY for research purposes, subject to the following restrictions:
//
// 1. The origin of this software must not be misrepresented; you must not
//    claim that you wrote the original software. If you use this software
//    an acknowledgment in the product documentation is required.
// 2. Altered source versions must be plainly marked as such, and must not be
//    misrepresented as being the original software.
// 3. This notice may not be removed or altered from any source distribution.
//
// Any other use is strictly prohibited by the author, without an explicit 
// permission.
//
// Note that this program uses the LEDA library, which is NOT free. For more 
// details visit Algorithmic Solutions at http://www.algorithmic-solutions.com/
// There is also a free version of LEDA 6.0 or newer.
//
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// ! Any commercial use of this software is strictly !
// ! prohibited without explicit permission by the   !
// ! author.                                         !
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
//
// This software is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
//
// Copyright (C) 2004-2008 - Dimitrios Michail <dimitrios.michail@gmail.com>
//

#ifndef EDGE_NUM_H
#define EDGE_NUM_H

#include <LEP/mcb/config.h>
#include <vector>
#ifdef LEDA_GE_V5
#include <LEDA/graph/graph.h>
#include <LEDA/graph/edge_array.h>
#include <LEDA/graph/node_set.h>
#include <LEDA/core/b_queue.h>
#else
#include <LEDA/graph.h>
#include <LEDA/edge_array.h>
#include <LEDA/node_set.h>
#include <LEDA/b_queue.h>
#endif

namespace mcb { 


    class edge_num
    {

        private:
            // variables:
            int n; 
            int m;
            int k;
            std::vector< leda::edge > index;
            leda::edge_array<int> rindex;
            // methods:
            void create_numbering( const leda::graph& );
            int construct_tree( const leda::graph&, leda::edge_array<bool>& tree );
            
        public:
            edge_num();

            explicit edge_num ( const leda::graph& G );

            edge_num ( const edge_num& );

            ~edge_num (void);

            edge_num& operator=( const edge_num& );

            inline int operator()(leda::edge e) const { 
                return rindex[e];
            }

            inline leda::edge operator()(int i) const { 
#if ! defined(LEDA_CHECKING_OFF)
                if ( i < 0 || i > m-1 )
                    leda::error_handler(999,"edge_num: illegal number requested");
#endif
                return index[ i ];
            }

            bool tree( leda::edge e ) const { 
                return ( rindex[e] >= m - n + k );
            }

            int dim_cycle_space() const {
                return m - n + k;
            }

            int num_weak_connected_comp() const {
                return k;
            }
    };


} // end namespace mcb

#endif

/* ex: set ts=4 sw=4 sts=4 et: */