dlib C++ Library - graph_utils.h
// 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
!*/
{
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
!*/
{
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 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 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;
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_