diff options
Diffstat (limited to 'ml/dlib/dlib/graph_utils/graph_utils.h')
| -rw-r--r-- | ml/dlib/dlib/graph_utils/graph_utils.h | 1227 |
1 files changed, 0 insertions, 1227 deletions
diff --git a/ml/dlib/dlib/graph_utils/graph_utils.h b/ml/dlib/dlib/graph_utils/graph_utils.h deleted file mode 100644 index 81262b7f5..000000000 --- a/ml/dlib/dlib/graph_utils/graph_utils.h +++ /dev/null @@ -1,1227 +0,0 @@ -// 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_ - - |