Ticket #7863: graphing.cpp

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>


class Op
{
        const char *mName;
public:
        Op( const char *s ) : mName(s) {}
        const char* name() const { return mName; }
};

struct OpMapper
{
        Op *op;
        OpMapper( Op *o = NULL ) : op(o) {}
};

namespace boost { namespace graph {

        template <typename T>
        struct vertex_name_extractor
        {
                typedef T   type;
                typedef Op* result_type;
                const result_type operator() ( const T& v ) const
                {
                        return v.me;
                }
        };

        template<typename VertexProperty>
        struct vertex_info_constructor
        {
                typedef VertexProperty return_type;
                typedef typename vertex_name_extractor<VertexProperty>::result_type argument_type;
                return_type operator()( argument_type n )
                {
                        return VertexProperty(n);
                }
        };

        template<> struct internal_vertex_name<OpMapper>
        { typedef multi_index::member<OpMapper, Op*, &OpMapper::op> type; };

        template<> struct internal_vertex_constructor<OpMapper>
        { typedef vertex_info_constructor<OpMapper> type; };

} }


class BoostGraph
{
        typedef boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, OpMapper> graph_t;
        typedef boost::graph_traits<graph_t>::vertex_descriptor Vertex;
        typedef boost::graph_traits<graph_t>::edge_descriptor   Edge;
        typedef boost::graph_traits<graph_t>::in_edge_iterator  Iterator;

        graph_t mGraph;

        bool removeVertexIfEmpty( const Vertex &v )
        {
                if ( boost::degree(v, mGraph)==0 && boost::out_degree(v, mGraph)==0 )
                {
                        OpMapper &op = mGraph[v];
                        printf("removeVert: %s (%p,%lu)\n", op.op->name(), op.op, v);
                        boost::clear_vertex(v, mGraph);
                        boost::remove_vertex(v, mGraph);
                        return true;
                }
                return false;
        }

        void _printInputs( const Vertex &v )
        {
                Op *dst = mGraph[v].op;
                Iterator vi, ve;
                for ( boost::tie(vi,ve) = boost::in_edges(v, mGraph); vi != ve; ++vi )
                {
                        const Vertex dv = source(*vi, mGraph);
                        Op *src = mGraph[dv].op;
                        printf("inedge: %s (%p,%lu) -> %s (%p,%lu)\n", src->name(), src, size_t(v), dst?dst->name():"!NULL!", dst, size_t(dv));
                }
        }

        void printInputs( const Vertex &v )
        {
                _printInputs(v);
                printf("---------------------------------\n");
        }

public:
        void connect( Op &from, Op &to )
        {
                const Vertex u = boost::graph::add_vertex(&from, mGraph), v = boost::graph::add_vertex(&to, mGraph);
                if ( boost::edge(u, v, mGraph).second==false )
                {
                        boost::add_edge(u, v, mGraph);
                        printInputs(v);
                }
        }

        void disconnect( Op &from, Op &to )
        {
                boost::optional<Vertex> fv = boost::graph::find_vertex(&from, mGraph);
                if ( fv )
                {
                        const boost::optional<Vertex> tv = boost::graph::find_vertex(&to, mGraph);
                        if ( tv )
                        {
                                printf("disconnect: %s (%p,%lu) -> %s (%p,%lu)\n", from.name(), &from, *fv, to.name(), &to, *tv);
                                boost::remove_edge(*fv, *tv, mGraph);
                                if ( removeVertexIfEmpty(*tv) )
                                {
                                        // fv invalid now ?
                                        fv = boost::graph::find_vertex(&from, mGraph);
                                        if ( fv ) removeVertexIfEmpty(*fv);

                                        printInputs(*tv);
                                        return;
                                }
                                printInputs(*tv);
                        }
                        removeVertexIfEmpty(*fv);
                }
        }

        void dumpInputs( const Vertex &v )
        {
                Iterator vi, ve;
                for ( boost::tie(vi,ve) = boost::in_edges(v, mGraph); vi != ve; ++vi )
                        dumpInputs( source(*vi, mGraph) );

                _printInputs(v);
        }

        void printInputs( Op &op )
        {
                printf("-------------- tree -------------------\n");
                dumpInputs( *boost::graph::find_vertex(&op, mGraph) );
        }
};

extern "C" int main( int argc, const char **argv )
{
        Op a("a"), b("b"), c("c"), d("d");
        BoostGraph bg;

        bg.connect(c, d);

        // Swapping these two lines should have no affect...but it does
        // BoostGraph::connect calling boost::graph::add_vertex is giving bad vertex ids
        bg.connect(a, b);
        bg.disconnect(c, d);

        bg.connect(c, b);
        bg.connect(b, d);

        bg.printInputs(d);

        return 0;
}