Merging upstream version 1.44.3.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1227 insertions, 0 deletions

diff --git a/ml/dlib/dlib/graph_utils/graph_utils.h b/ml/dlib/dlib/graph_utils/graph_utils.h
new file mode 100644
index 000000000..81262b7f5
--- /dev/null
+++ b/ml/dlib/dlib/graph_utils/graph_utils.h
@@ -0,0 +1,1227 @@
+// Copyright (C) 2007  Davis E. King (davis@dlib.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 enable_if<is_graph<T>,typename T::edge_type>::type& edge(
+        T& g, 
+        unsigned long idx_i, 
+        unsigned long idx_j
+    )
+    {
+        // make sure requires clause is not broken
+        DLIB_ASSERT(g.has_edge(idx_i,idx_j) == true,
+            "\tT::edge_type& edge(g, idx_i, idx_j)"
+            << "\n\t you have requested an invalid edge"
+            << "\n\t idx_i: " << idx_i
+            << "\n\t idx_j: " << idx_j 
+            );
+
+        for (unsigned long i = 0; i < g.node(idx_i).number_of_neighbors(); ++i)
+        {
+            if (g.node(idx_i).neighbor(i).index() == idx_j)
+                return g.node(idx_i).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, idx_i, idx_j)"
+            << "\n\t you have requested an invalid edge"
+            << "\n\t idx_i: " << idx_i
+            << "\n\t idx_j: " << idx_j 
+            );
+    }
+
+    template <typename T>
+    const typename enable_if<is_graph<T>,typename T::edge_type>::type& edge(
+        const T& g,  
+        unsigned long idx_i,
+        unsigned long idx_j
+    )
+    {
+        // make sure requires clause is not broken
+        DLIB_ASSERT(g.has_edge(idx_i,idx_j) == true,
+            "\tT::edge_type& edge(g, idx_i, idx_j)"
+            << "\n\t you have requested an invalid edge"
+            << "\n\t idx_i: " << idx_i
+            << "\n\t idx_j: " << idx_j 
+            );
+
+        for (unsigned long i = 0; i < g.node(idx_i).number_of_neighbors(); ++i)
+        {
+            if (g.node(idx_i).neighbor(i).index() == idx_j)
+                return g.node(idx_i).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, idx_i, idx_j)"
+            << "\n\t you have requested an invalid edge"
+            << "\n\t idx_i: " << idx_i
+            << "\n\t idx_j: " << idx_j 
+            );
+    }
+
+// ----------------------------------------------------------------------------------------
+    
+    template <typename T>
+    typename enable_if<is_directed_graph<T>,typename T::edge_type>::type& edge(
+        T& g, 
+        unsigned long parent_idx, 
+        unsigned long child_idx 
+    )
+    {
+        // make sure requires clause is not broken
+        DLIB_ASSERT(g.has_edge(parent_idx,child_idx) == true,
+            "\t T::edge_type& edge(g, parent_idx, child_idx)"
+            << "\n\t you have requested an invalid edge"
+            << "\n\t parent_idx: " << parent_idx
+            << "\n\t child_idx: " << child_idx 
+            );
+
+        for (unsigned long i = 0; i < g.node(parent_idx).number_of_children(); ++i)
+        {
+            if (g.node(parent_idx).child(i).index() == child_idx)
+                return g.node(parent_idx).child_edge(i);
+        }
+
+        // put this here just so compilers don't complain about a lack of
+        // a return here
+        DLIB_CASSERT(false,
+            "\t T::edge_type& edge(g, parent_idx, child_idx)"
+            << "\n\t you have requested an invalid edge"
+            << "\n\t parent_idx: " << parent_idx
+            << "\n\t child_idx: " << child_idx 
+            );
+    }
+
+    template <typename T>
+    const typename enable_if<is_directed_graph<T>,typename T::edge_type>::type& edge(
+        const T& g,  
+        unsigned long parent_idx, 
+        unsigned long child_idx 
+    )
+    {
+        // make sure requires clause is not broken
+        DLIB_ASSERT(g.has_edge(parent_idx,child_idx) == true,
+            "\t T::edge_type& edge(g, parent_idx, child_idx)"
+            << "\n\t you have requested an invalid edge"
+            << "\n\t parent_idx: " << parent_idx
+            << "\n\t child_idx: " << child_idx 
+            );
+
+        for (unsigned long i = 0; i < g.node(parent_idx).number_of_children(); ++i)
+        {
+            if (g.node(parent_idx).child(i).index() == child_idx)
+                return g.node(parent_idx).child_edge(i);
+        }
+
+        // put this here just so compilers don't complain about a lack of
+        // a return here
+        DLIB_ASSERT(false,
+            "\t T::edge_type& edge(g, parent_idx, child_idx)"
+            << "\n\t you have requested an invalid edge"
+            << "\n\t parent_idx: " << parent_idx
+            << "\n\t child_idx: " << child_idx 
+            );
+    }
+
+// ----------------------------------------------------------------------------------------
+    
+    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 graph_type1,
+        typename graph_type2
+        >
+    typename enable_if<is_graph<graph_type1> >::type copy_graph (
+        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;
+
+        copy_graph_structure(src,dest);
+
+        // copy all the node and edge content 
+        for (unsigned long i = 0; i < src.number_of_nodes(); ++i)
+        {
+            dest.node(i).data = src.node(i).data;
+
+            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.node(i).edge(j) = src.node(i).edge(j);
+                }
+            }
+        }
+    }
+
+    template <
+        typename graph_type1,
+        typename graph_type2
+        >
+    typename enable_if<is_directed_graph<graph_type1> >::type copy_graph (
+        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);
+        if (graph_helpers::is_same_object(src,dest))
+            return;
+
+        copy_graph_structure(src,dest);
+
+        // copy all the node and edge content 
+        for (unsigned long i = 0; i < src.number_of_nodes(); ++i)
+        {
+            dest.node(i).data = src.node(i).data;
+            for (unsigned long j = 0; j < src.node(i).number_of_children(); ++j)
+            {
+                dest.node(i).child_edge(j) = src.node(i).child_edge(j);
+            }
+        }
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    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_has_symmetric_edges (
+        const T& graph
+    )
+    {
+        for (unsigned long i = 0; i < graph.number_of_nodes(); ++i)
+        {
+            for (unsigned long j = 0; j < graph.node(i).number_of_children(); ++j)
+            {
+                const unsigned long jj = graph.node(i).child(j).index();
+                // make sure every edge from a parent to a child has an edge linking back
+                if (graph.has_edge(jj,i) == false)
+                    return false;
+            }
+
+            for (unsigned long j = 0; j < graph.node(i).number_of_parents(); ++j)
+            {
+                const unsigned long jj = graph.node(i).parent(j).index();
+                // make sure every edge from a child to a parent has an edge linking back
+                if (graph.has_edge(i,jj) == false)
+                    return false;
+            }
+        }
+
+        return true;
+    }
+
+// ----------------------------------------------------------------------------------------
+    
+    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_
+
+