dlib C++ Library - graph_utils.h

    // Copyright (C) 2007  Davis E. King (davisking@users.sourceforge.net)
    // License: Boost Software License   See LICENSE.txt for the full license.
    #ifndef DLIB_GRAPH_UTILs_
    #define DLIB_GRAPH_UTILs_

    #include "../algs.h"
    #include <vector>
    #include "graph_utils_abstract.h"
    #include "../is_kind.h"
    #include "../enable_if.h"
    #include <algorithm>
    #include "../set.h"
    #include "../memory_manager.h"
    #include "../set_utils.h"

    namespace dlib
    {

    // ----------------------------------------------------------------------------------------

        template <typename T>
        typename T::edge_type& edge(
            T& g,
            unsigned long idx,
            unsigned long n
        )
        {
            // make sure requires clause is not broken
            DLIB_ASSERT(g.has_edge(idx,n) == true,
                "\tT::edge_type& edge(g, i, j)"
                << "\n\tyou have requested an invalid edge"
                << "\n\ti: " << idx
                << "\n\tj: " << n
                );

            for (unsigned long i = 0; i < g.node(idx).number_of_neighbors(); ++i)
            {
                if (g.node(idx).neighbor(i).index() == n)
                    return g.node(idx).edge(i);
            }

            // put this here just so compilers don't complain about a lack of
            // a return here
            DLIB_CASSERT(false,
                "\tT::edge_type& edge(g, i, j)"
                << "\n\tyou have requested an invalid edge"
                << "\n\ti: " << idx
                << "\n\tj: " << n
                );
        }

        template <typename T>
        const typename T::edge_type& edge(
            const T& g,
            unsigned long idx,
            unsigned long n
        )
        {
            // make sure requires clause is not broken
            DLIB_ASSERT(g.has_edge(idx,n) == true,
                "\tT::edge_type& edge(g, i, j)"
                << "\n\tyou have requested an invalid edge"
                << "\n\ti: " << idx
                << "\n\tj: " << n
                );

            for (unsigned long i = 0; i < g.node(idx).number_of_neighbors(); ++i)
            {
                if (g.node(idx).neighbor(i).index() == n)
                    return g.node(idx).edge(i);
            }

            // put this here just so compilers don't complain about a lack of
            // a return here
            DLIB_CASSERT(false,
                "\tT::edge_type& edge(g, i, j)"
                << "\n\tyou have requested an invalid edge"
                << "\n\ti: " << idx
                << "\n\tj: " << n
                );
        }

    // ----------------------------------------------------------------------------------------

        namespace graph_helpers
        {
            template <typename T, typename U>
            inline bool is_same_object (
                const T& a,
                const U& b
            )
            {
                if (is_same_type<const T,const U>::value == false)
                    return false;
                if ((void*)&a == (void*)&b)
                    return true;
                else
                    return false;
            }

            template <
                typename T
                >
            bool search_for_directed_cycles (
                const T& node,
                std::vector<bool>& visited,
                std::vector<bool>& temp
            )
            /*!
                requires
                    - visited.size() >= number of nodes in the graph that contains the given node
                    - temp.size() >= number of nodes in the graph that contains the given node
                    - for all i in temp:
                        - temp[i] == false
                ensures
                    - checks the connected subgraph containing the given node for directed cycles
                      and returns true if any are found and false otherwise.
                    - for all nodes N in the connected subgraph containing the given node:
                        - #visited[N.index()] == true
                    - for all i in temp:
                        - #temp[i] == false
            !*/
            {
                if (temp[node.index()] == true)
                    return true;

                visited[node.index()] = true;
                temp[node.index()] = true;

                for (unsigned long i = 0; i < node.number_of_children(); ++i)
                {
                    if (search_for_directed_cycles(node.child(i), visited, temp))
                        return true;
                }

                temp[node.index()] = false;

                return false;
            }

        // ------------------------------------------------------------------------------------

            template <
                typename T
                >
            typename enable_if<is_directed_graph<typename T::graph_type>,bool>::type search_for_undirected_cycles (
                const T& node,
                std::vector<bool>& visited,
                unsigned long prev = std::numeric_limits<unsigned long>::max()
            )
            /*!
                requires
                    - visited.size() >= number of nodes in the graph that contains the given node
                    - for all nodes N in the connected subgraph containing the given node:
                        - visited[N.index] == false
                ensures
                    - checks the connected subgraph containing the given node for directed cycles
                      and returns true if any are found and false otherwise.
                    - for all nodes N in the connected subgraph containing the given node:
                        - #visited[N.index()] == true
            !*/
            {
                using namespace std;
                if (visited[node.index()] == true)
                    return true;

                visited[node.index()] = true;

                for (unsigned long i = 0; i < node.number_of_children(); ++i)
                {
                    if (node.child(i).index() != prev &&
                        search_for_undirected_cycles(node.child(i), visited, node.index()))
                        return true;
                }

                for (unsigned long i = 0; i < node.number_of_parents(); ++i)
                {
                    if (node.parent(i).index() != prev &&
                        search_for_undirected_cycles(node.parent(i), visited, node.index()))
                        return true;
                }

                return false;
            }

        // ------------------------------------------------------------------------------------

            template <
                typename T
                >
            typename enable_if<is_graph<typename T::graph_type>,bool>::type search_for_undirected_cycles (
                const T& node,
                std::vector<bool>& visited,
                unsigned long prev = std::numeric_limits<unsigned long>::max()
            )
            /*!
                requires
                    - visited.size() >= number of nodes in the graph that contains the given node
                    - for all nodes N in the connected subgraph containing the given node:
                        - visited[N.index] == false
                ensures
                    - checks the connected subgraph containing the given node for directed cycles
                      and returns true if any are found and false otherwise.
                    - for all nodes N in the connected subgraph containing the given node:
                        - #visited[N.index()] == true
            !*/
            {
                using namespace std;
                if (visited[node.index()] == true)
                    return true;

                visited[node.index()] = true;

                for (unsigned long i = 0; i < node.number_of_neighbors(); ++i)
                {
                    if (node.neighbor(i).index() != prev &&
                        search_for_undirected_cycles(node.neighbor(i), visited, node.index()))
                        return true;
                }

                return false;
            }

        }

    // ------------------------------------------------------------------------------------

        template <
            typename graph_type1,
            typename graph_type2
            >
        typename enable_if<is_graph<graph_type1> >::type copy_graph_structure (
            const graph_type1& src,
            graph_type2& dest
        )
        {
            COMPILE_TIME_ASSERT(is_graph<graph_type1>::value);
            COMPILE_TIME_ASSERT(is_graph<graph_type2>::value);
            if (graph_helpers::is_same_object(src,dest))
                return;

            dest.clear();
            dest.set_number_of_nodes(src.number_of_nodes());

            // copy all the edges from src into dest
            for (unsigned long i = 0; i < src.number_of_nodes(); ++i)
            {
                for (unsigned long j = 0; j < src.node(i).number_of_neighbors(); ++j)
                {
                    const unsigned long nidx = src.node(i).neighbor(j).index();
                    if (nidx >= i)
                    {
                        dest.add_edge(i,nidx);
                    }
                }
            }
        }

        template <
            typename graph_type1,
            typename graph_type2
            >
        typename enable_if<is_directed_graph<graph_type1> >::type copy_graph_structure (
            const graph_type1& src,
            graph_type2& dest
        )
        {
            COMPILE_TIME_ASSERT(is_directed_graph<graph_type1>::value);
            COMPILE_TIME_ASSERT(is_directed_graph<graph_type2>::value || is_graph<graph_type2>::value );
            if (graph_helpers::is_same_object(src,dest))
                return;

            dest.clear();
            dest.set_number_of_nodes(src.number_of_nodes());

            // copy all the edges from src into dest
            for (unsigned long i = 0; i < src.number_of_nodes(); ++i)
            {
                for (unsigned long j = 0; j < src.node(i).number_of_children(); ++j)
                {
                    const unsigned long nidx = src.node(i).child(j).index();
                    if (dest.has_edge(i,nidx) == false)
                    {
                        dest.add_edge(i,nidx);
                    }
                }
            }
        }

    // ----------------------------------------------------------------------------------------

        template <
            typename T,
            typename S
            >
        typename enable_if<is_graph<typename T::graph_type> >::type find_connected_nodes (
        const T& n,
        S& visited
        )
        {
            if (visited.is_member(n.index()) == false)
            {
                unsigned long temp = n.index();
                visited.add(temp);

                for (unsigned long i = 0; i < n.number_of_neighbors(); ++i)
                    find_connected_nodes(n.neighbor(i), visited);
            }
        }

        template <
            typename T,
            typename S
            >
        typename enable_if<is_directed_graph<typename T::graph_type> >::type find_connected_nodes (
        const T& n,
        S& visited
        )
        {
            if (visited.is_member(n.index()) == false)
            {
                unsigned long temp = n.index();
                visited.add(temp);

                for (unsigned long i = 0; i < n.number_of_parents(); ++i)
                    find_connected_nodes(n.parent(i), visited);
                for (unsigned long i = 0; i < n.number_of_children(); ++i)
                    find_connected_nodes(n.child(i), visited);
            }
        }

    // ----------------------------------------------------------------------------------------

        template <
            typename T
            >
        bool graph_is_connected (
            const T& g
        )
        {
            if (g.number_of_nodes() == 0)
                return true;

            set<unsigned long>::kernel_1b_c visited;
            find_connected_nodes(g.node(0), visited);
            return (visited.size() == g.number_of_nodes());
        }

    // ----------------------------------------------------------------------------------------

        template <
            typename T
            >
        bool graph_contains_directed_cycle (
            const T& graph
        )
        {
            using namespace std;
            using namespace graph_helpers;
            std::vector<bool> visited(graph.number_of_nodes(), false);
            std::vector<bool> temp(graph.number_of_nodes(), false);

            while (true)
            {
                // find the first node that hasn't been visited yet
                unsigned long i;
                for (i = 0; i < visited.size(); ++i)
                {
                    if (visited[i] == false)
                        break;
                }

                // if we didn't find any non-visited nodes then we are done
                if (i == visited.size())
                    return false;

                if (search_for_directed_cycles(graph.node(i), visited, temp))
                    return true;
            }
        }

    // ----------------------------------------------------------------------------------------

        template <
            typename T
            >
        bool graph_contains_undirected_cycle (
            const T& graph
        )
        {
            using namespace std;
            using namespace graph_helpers;
            std::vector<bool> visited(graph.number_of_nodes(), false);

            while (true)
            {
                // find the first node that hasn't been visited yet
                unsigned long i;
                for (i = 0; i < visited.size(); ++i)
                {
                    if (visited[i] == false)
                        break;
                }

                // if we didn't find any non-visited nodes then we are done
                if (i == visited.size())
                    return false;

                if (search_for_undirected_cycles(graph.node(i), visited))
                    return true;
            }
        }

    // ----------------------------------------------------------------------------------------

        template <
            typename directed_graph_type,
            typename graph_type
            >
        void create_moral_graph (
            const directed_graph_type& g,
            graph_type& moral_graph
        )
        {
            // make sure requires clause is not broken
            DLIB_ASSERT(graph_contains_directed_cycle(g) == false,
                "\tvoid create_moral_graph(g, moral_graph)"
                << "\n\tYou can only make moral graphs if g doesn't have directed cycles"
                );
            COMPILE_TIME_ASSERT(is_graph<graph_type>::value);
            COMPILE_TIME_ASSERT(is_directed_graph<directed_graph_type>::value);

            copy_graph_structure(g, moral_graph);

            // now marry all the parents (i.e. add edges between parent nodes)
            for (unsigned long i = 0; i < g.number_of_nodes(); ++i)
            {
                // loop over all combinations of parents of g.node(i)
                for (unsigned long j = 0; j < g.node(i).number_of_parents(); ++j)
                {
                    for (unsigned long k = 0; k < g.node(i).number_of_parents(); ++k)
                    {
                        const unsigned long p1 = g.node(i).parent(j).index();
                        const unsigned long p2 = g.node(i).parent(k).index();
                        if (p1 == p2)
                            continue;

                        if (moral_graph.has_edge(p1,p2) == false)
                            moral_graph.add_edge(p1,p2);
                    }
                }
            }
        }

    // ----------------------------------------------------------------------------------------

        template <
            typename graph_type,
            typename sets_of_int
            >
        bool is_clique (
            const graph_type& g,
            const sets_of_int& clique
        )
        {
            // make sure requires clause is not broken
            DLIB_ASSERT(graph_contains_length_one_cycle(g) == false,
                "\tvoid is_clique(g, clique)"
                << "\n\tinvalid graph"
                );
    #ifdef ENABLE_ASSERTS
            clique.reset();
            while (clique.move_next())
            {
                const unsigned long x = clique.element();
                DLIB_ASSERT( x < g.number_of_nodes(),
                    "\tvoid is_clique(g, clique)"
                    << "\n\tthe clique set contained an invalid node index"
                    << "\n\tx:                   " << x
                    << "\n\tg.number_of_nodes(): " << g.number_of_nodes()
                    );
            }
    #endif

            COMPILE_TIME_ASSERT(is_graph<graph_type>::value);

            std::vector<unsigned long> v;
            v.reserve(clique.size());
            clique.reset();
            while (clique.move_next())
            {
                v.push_back(clique.element());
            }

            for (unsigned long i = 0; i < v.size(); ++i)
            {
                for (unsigned long j = 0; j < v.size(); ++j)
                {
                    if (v[i] == v[j])
                        continue;
                    if (g.has_edge(v[i], v[j]) == false)
                        return false;
                }
            }

            return true;
        }

    // ----------------------------------------------------------------------------------------

        template <
            typename graph_type,
            typename sets_of_int
            >
        bool is_maximal_clique (
            const graph_type& g,
            const sets_of_int& clique
        )
        {
            // make sure requires clause is not broken
            DLIB_ASSERT(graph_contains_length_one_cycle(g) == false,
                "\tvoid is_maximal_clique(g, clique)"
                << "\n\tinvalid graph"
                );
            DLIB_ASSERT(is_clique(g,clique) == true,
                "\tvoid is_maximal_clique(g, clique)"
                << "\n\tinvalid graph"
                );
    #ifdef ENABLE_ASSERTS
            clique.reset();
            while (clique.move_next())
            {
                const unsigned long x = clique.element();
                DLIB_ASSERT( x < g.number_of_nodes(),
                    "\tvoid is_maximal_clique(g, clique)"
                    << "\n\tthe clique set contained an invalid node index"
                    << "\n\tx:                   " << x
                    << "\n\tg.number_of_nodes(): " << g.number_of_nodes()
                    );
            }
    #endif

            COMPILE_TIME_ASSERT(is_graph<graph_type>::value);

            if (clique.size() == 0)
                return true;

            // get an element in the clique and make sure that
            // none of its neighbors that aren't in the clique are connected
            // to all the elements of the clique.
            clique.reset();
            clique.move_next();
            const unsigned long idx = clique.element();

            for (unsigned long i = 0; i < g.node(idx).number_of_neighbors(); ++i)
            {
                const unsigned long n = g.node(idx).neighbor(i).index();
                if (clique.is_member(n))
                    continue;

                // now loop over all the clique members and make sure they don't all
                // share an edge with node n
                bool all_share_edge = true;
                clique.reset();
                while (clique.move_next())
                {
                    if (g.has_edge(clique.element(), n) == false)
                    {
                        all_share_edge = false;
                        break;
                    }
                }

                if (all_share_edge == true)
                    return false;
            }

            return true;
        }

    // ----------------------------------------------------------------------------------------

        template <
            typename T
            >
        typename enable_if<is_directed_graph<T>,bool>::type graph_contains_length_one_cycle (
            const T& graph
        )
        {
            for (unsigned long i = 0; i < graph.number_of_nodes(); ++i)
            {
                // make sure none of this guys children are actually itself
                for (unsigned long n = 0; n < graph.node(i).number_of_children(); ++n)
                {
                    if (graph.node(i).child(n).index() == i)
                        return true;
                }
            }

            return false;
        }

    // ----------------------------------------------------------------------------------------

        template <
            typename T
            >
        typename enable_if<is_graph<T>,bool>::type graph_contains_length_one_cycle (
            const T& graph
        )
        {
            for (unsigned long i = 0; i < graph.number_of_nodes(); ++i)
            {
                // make sure none of this guys neighbors are actually itself
                for (unsigned long n = 0; n < graph.node(i).number_of_neighbors(); ++n)
                {
                    if (graph.node(i).neighbor(n).index() == i)
                        return true;
                }
            }

            return false;
        }

    // ----------------------------------------------------------------------------------------

        namespace graph_helpers
        {
            struct pair
            {
                unsigned long index;
                unsigned long num_neighbors;

                bool operator< (const pair& p) const { return num_neighbors < p.num_neighbors; }
            };

            template <
                typename T,
                typename S,
                typename V
                >
            void search_graph_for_triangulate (
                const T& n,
                S& visited,
                V& order_visited
            )
            {
                // base case of recursion.  stop when we hit a node we have
                // already visited.
                if (visited.is_member(n.index()))
                    return;

                // record that we have visited this node
                order_visited.push_back(n.index());
                unsigned long temp = n.index();
                visited.add(temp);

                // we want to visit all the neighbors of this node but do
                // so by visiting the nodes with the most neighbors first.  So
                // lets make a vector that lists the nodes in the order we
                // want to visit them
                std::vector<pair> neighbors;
                for (unsigned long i = 0; i < n.number_of_neighbors(); ++i)
                {
                    pair p;
                    p.index = i;
                    p.num_neighbors = n.neighbor(i).number_of_neighbors();
                    neighbors.push_back(p);
                }

                // now sort the neighbors array so that the neighbors with the
                // most neighbors come first.
                std::sort(neighbors.rbegin(), neighbors.rend());

                // now visit all the nodes
                for (unsigned long i = 0; i < neighbors.size(); ++i)
                {
                    search_graph_for_triangulate(n.neighbor(neighbors[i].index), visited, order_visited);
                }
            }
        } // end namespace graph_helpers

        template <
            typename graph_type,
            typename set_of_sets_of_int
            >
        void triangulate_graph_and_find_cliques (
            graph_type& g,
            set_of_sets_of_int& cliques
        )
        {

            // make sure requires clause is not broken
            DLIB_ASSERT(graph_contains_length_one_cycle(g) == false,
                "\tvoid triangulate_graph_and_find_cliques(g, cliques)"
                << "\n\tInvalid graph"
                );
            DLIB_ASSERT(graph_is_connected(g) == true,
                "\tvoid triangulate_graph_and_find_cliques(g, cliques)"
                << "\n\tInvalid graph"
                );

            COMPILE_TIME_ASSERT(is_graph<graph_type>::value);

            using namespace graph_helpers;
            using namespace std;
            typedef typename set_of_sets_of_int::type set_of_int;

            cliques.clear();

            // first we find the node with the most neighbors
            unsigned long max_index = 0;
            unsigned long num_neighbors = 0;
            for (unsigned long i = 0; i < g.number_of_nodes(); ++i)
            {
                if (g.node(i).number_of_neighbors() > num_neighbors)
                {
                    max_index = i;
                    num_neighbors = g.node(i).number_of_neighbors();
                }
            }

            // now we do a depth first search of the entire graph starting
            // with the node we just found.  We record the order in which
            // we visit each node in the vector order_visited.
            std::vector<unsigned long> order_visited;
            set_of_int visited;
            search_graph_for_triangulate(g.node(max_index), visited, order_visited);

            set_of_int clique;

            // now add edges to the graph to make it triangulated
            while (visited.size() > 0)
            {
                // we are going to enumerate over the nodes in the reverse of the
                // order in which they were visited.  So get the last node out.
                const unsigned long idx = order_visited.back();
                order_visited.pop_back();
                visited.destroy(idx);

                // as a start add this node to our current clique
                unsigned long temp = idx;
                clique.clear();
                clique.add(temp);

                // now we want to make a clique that contains node g.node(idx) and
                // all of its neighbors that are still recorded in the visited set
                // (except for neighbors that have only one edge).
                for (unsigned long i = 0; i < g.node(idx).number_of_neighbors(); ++i)
                {
                    // get the index of the i'th neighbor
                    unsigned long nidx = g.node(idx).neighbor(i).index();

                    // add it to the clique if it is still in visited and it isn't
                    // a node with only one neighbor
                    if (visited.is_member(nidx) == true &&
                        g.node(nidx).number_of_neighbors() != 1)
                    {
                        // add edges between this new node and all the nodes
                        // that are already in the clique
                        clique.reset();
                        while (clique.move_next())
                        {
                            if (g.has_edge(nidx, clique.element()) == false)
                                g.add_edge(nidx, clique.element());
                        }

                        // now also record that we added this node to the clique
                        clique.add(nidx);
                    }
                }

                if (cliques.is_member(clique) == false && is_maximal_clique(g,clique) )
                {
                    cliques.add(clique);
                }

                // now it is possible that we are missing some cliques of size 2 since
                // above we didn't add nodes with only one edge to any of our cliques.
                // Now lets make sure all these nodes are accounted for
                for (unsigned long i = 0; i < g.number_of_nodes(); ++i)
                {
                    clique.clear();
                    if (g.node(i).number_of_neighbors() == 1)
                    {
                        unsigned long temp = i;
                        clique.add(temp);
                        temp = g.node(i).neighbor(0).index();
                        clique.add(temp);

                        if (cliques.is_member(clique) == false)
                            cliques.add(clique);
                    }
                }
            }

        }

    // ----------------------------------------------------------------------------------------

        template <
            typename graph_type,
            typename join_tree_type
            >
        void create_join_tree (
            const graph_type& g,
            join_tree_type& join_tree
        )
        {
            // make sure requires clause is not broken
            DLIB_ASSERT(graph_contains_length_one_cycle(g) == false,
                "\tvoid create_join_tree(g, join_tree)"
                << "\n\tInvalid graph"
                );
            DLIB_ASSERT(graph_is_connected(g) == true,
                "\tvoid create_join_tree(g, join_tree)"
                << "\n\tInvalid graph"
                );

            COMPILE_TIME_ASSERT(is_graph<graph_type>::value);
            COMPILE_TIME_ASSERT(is_graph<join_tree_type>::value);

            typedef typename join_tree_type::type set_of_int;
            typedef typename join_tree_type::edge_type set_of_int_edge;
            typedef typename set<set_of_int>::kernel_1b_c set_of_sets_of_int;

            copy_graph_structure(g, join_tree);

            // don't even bother in this case
            if (g.number_of_nodes() == 0)
                return;

            set_of_sets_of_int cliques;
            set_of_int s;

            triangulate_graph_and_find_cliques(join_tree, cliques);

            join_tree.set_number_of_nodes(cliques.size());

            // copy the cliques into each of the nodes of tree
            for (unsigned long i = 0; i < join_tree.number_of_nodes(); ++i)
            {
                cliques.remove_any(s);
                s.swap(join_tree.node(i).data);
            }

            set_of_int_edge e;

            // add all possible edges to the join_tree
            for (unsigned long i = 0; i < join_tree.number_of_nodes(); ++i)
            {
                for (unsigned long j = i+1; j < join_tree.number_of_nodes(); ++j)
                {
                    set_intersection(
                        join_tree.node(i).data,
                        join_tree.node(j).data,
                        e);

                    if (e.size() > 0)
                    {
                        join_tree.add_edge(i,j);
                        edge(join_tree,i,j).swap(e);
                    }
                }
            }

            // now we just need to remove the unnecessary edges so that we get a
            // proper join tree
            s.clear();
            set_of_int& good = s; // rename s to something slightly more meaningful
            // good will contain nodes that have been "approved"
            unsigned long n = 0;
            good.add(n);

            std::vector<unsigned long> vtemp;

            while (good.size() < join_tree.number_of_nodes())
            {
                // figure out which of the neighbors of nodes in good has the best edge
                unsigned long best_bad_idx = 0;
                unsigned long best_good_idx = 0;
                unsigned long best_overlap = 0;
                good.reset();
                while (good.move_next())
                {
                    // loop over all the neighbors of the current node in good
                    for (unsigned long i = 0; i < join_tree.node(good.element()).number_of_neighbors(); ++i)
                    {
                        const unsigned long idx = join_tree.node(good.element()).neighbor(i).index();
                        if (!good.is_member(idx))
                        {
                            const unsigned long overlap = join_tree.node(good.element()).edge(i).size();

                            if (overlap > best_overlap)
                            {
                                best_overlap = overlap;
                                best_bad_idx = idx;
                                best_good_idx = good.element();
                            }
                        }
                    }
                }

                // now remove all the edges from best_bad_idx to the nodes in good except for the
                // edge to best_good_idx.
                for (unsigned long i = 0; i < join_tree.node(best_bad_idx).number_of_neighbors(); ++i)
                {
                    const unsigned long idx = join_tree.node(best_bad_idx).neighbor(i).index();
                    if (idx != best_good_idx && good.is_member(idx))
                    {
                        vtemp.push_back(idx);
                    }
                }

                for (unsigned long i = 0; i < vtemp.size(); ++i)
                    join_tree.remove_edge(vtemp[i], best_bad_idx);

                vtemp.clear();

                // and finally add this bad index into the good set
                good.add(best_bad_idx);
            }
        }

    // ----------------------------------------------------------------------------------------

        namespace graph_helpers
        {
            template <
                typename T,
                typename U
                >
            bool validate_join_tree (
                const T& n,
                U& deads,
                unsigned long parent = 0xffffffff
            )
            /*!
                this function makes sure that a join tree satisfies the following criterion for paths starting at the given node:
                    - for all valid i and j such that i and j are both < #join_tree.number_of_nodes()
                        - let X be the set of numbers that is contained in both #join_tree.node(i).data
                          and #join_tree.node(j).data
                        - It is the case that all nodes on the unique path between #join_tree.node(i)
                          and #join_tree.node(j) contain the numbers from X in their sets.

                returns true if validation passed and false if there is a problem with the tree
            !*/
            {
                n.data.reset();
                while (n.data.move_next())
                {
                    if (deads.is_member(n.data.element()))
                        return false;
                }

                for (unsigned long i = 0; i < n.number_of_neighbors(); ++i)
                {
                    if (n.neighbor(i).index() == parent)
                        continue;

                    // add anything to dead stuff
                    n.data.reset();
                    while (n.data.move_next())
                    {
                        if (n.neighbor(i).data.is_member(n.data.element()) == false)
                        {
                            unsigned long temp = n.data.element();
                            deads.add(temp);
                        }
                    }

                    if (validate_join_tree(n.neighbor(i), deads, n.index()) == false)
                        return false;

                    // remove this nodes stuff from dead stuff
                    n.data.reset();
                    while (n.data.move_next())
                    {
                        if (n.neighbor(i).data.is_member(n.data.element()) == false)
                        {
                            unsigned long temp = n.data.element();
                            deads.destroy(temp);
                        }
                    }
                }

                return true;
            }
        }

        template <
            typename graph_type,
            typename join_tree_type
            >
        bool is_join_tree (
            const graph_type& g,
            const join_tree_type& join_tree
        )
        {

            // make sure requires clause is not broken
            DLIB_ASSERT(graph_contains_length_one_cycle(g) == false,
                "\tvoid create_join_tree(g, join_tree)"
                << "\n\tInvalid graph"
                );
            DLIB_ASSERT(graph_is_connected(g) == true,
                "\tvoid create_join_tree(g, join_tree)"
                << "\n\tInvalid graph"
                );

            COMPILE_TIME_ASSERT(is_graph<graph_type>::value || is_directed_graph<graph_type>::value);
            COMPILE_TIME_ASSERT(is_graph<join_tree_type>::value);

            if (graph_contains_undirected_cycle(join_tree))
                return false;

            if (graph_is_connected(join_tree) == false)
                return false;

            // verify that the path condition of the join tree is valid
            for (unsigned long i = 0; i < join_tree.number_of_nodes(); ++i)
            {
                typename join_tree_type::type deads;
                if (graph_helpers::validate_join_tree(join_tree.node(i), deads) == false)
                    return false;
            }

            typename join_tree_type::edge_type e;
            typename join_tree_type::edge_type all;
            // now make sure that the edges contain correct intersections
            for (unsigned long i = 0; i < join_tree.number_of_nodes(); ++i)
            {
                set_union(all,join_tree.node(i).data, all);
                for (unsigned long j = 0; j < join_tree.node(i).number_of_neighbors(); ++j)
                {
                    set_intersection(join_tree.node(i).data,
                                     join_tree.node(i).neighbor(j).data,
                                     e);

                    if (!(e == join_tree.node(i).edge(j)))
                        return false;
                }
            }

            // and finally check that all the nodes in g show up in the join tree
            if (all.size() != g.number_of_nodes())
                return false;
            all.reset();
            while (all.move_next())
            {
                if (all.element() >= g.number_of_nodes())
                    return false;
            }

            return true;
        }

    // ----------------------------------------------------------------------------------------

    }

    #endif // DLIB_GRAPH_UTILs_