// Copyright (C) 2007 Davis E. King (davis@dlib.net)
// License: Boost Software License See LICENSE.txt for the full license.
#ifndef DLIB_GRAPH_KERNEl_1_
#define DLIB_GRAPH_KERNEl_1_
#include <memory>
#include <vector>
#include "../serialize.h"
#include "../noncopyable.h"
#include "../std_allocator.h"
#include "../algs.h"
#include "graph_kernel_abstract.h"
#include "../is_kind.h"
namespace dlib
{
// ----------------------------------------------------------------------------------------
template <typename node_type, typename graph, bool is_checked>
struct graph_checker_helper
{
/*!
This object is used to check preconditions based on the value of is_checked
!*/
static void check_neighbor (
unsigned long edge_index,
const node_type& self
)
{
// make sure requires clause is not broken
DLIB_CASSERT(edge_index < self.number_of_neighbors(),
"\tnode_type& graph::node_type::neighbor(edge_index)"
<< "\n\tYou have specified an invalid index"
<< "\n\tedge_index: " << edge_index
<< "\n\tnumber_of_neighbors(): " << self.number_of_neighbors()
<< "\n\tthis: " << &self
);
}
static void check_edge (
unsigned long edge_index,
const node_type& self
)
{
// make sure requires clause is not broken
DLIB_CASSERT(edge_index < self.number_of_neighbors(),
"\tE& graph::node_type::edge(edge_index)"
<< "\n\tYou have specified an invalid index"
<< "\n\tedge_index: " << edge_index
<< "\n\tnumber_of_neighbors(): " << self.number_of_neighbors()
<< "\n\tthis: " << &self
);
}
static void check_node (
unsigned long index,
const graph& self
)
{
// make sure requires clause is not broken
DLIB_CASSERT(index < self.number_of_nodes(),
"\tnode_type& graph::node(index)"
<< "\n\tYou have specified an invalid index"
<< "\n\tindex: " << index
<< "\n\tnumber_of_nodes(): " << self.number_of_nodes()
<< "\n\tthis: " << &self
);
}
static void check_has_edge (
unsigned long node_index1,
unsigned long node_index2,
const graph& self
)
{
// make sure requires clause is not broken
DLIB_CASSERT(node_index1 < self.number_of_nodes() &&
node_index2 < self.number_of_nodes(),
"\tvoid graph::has_edge(node_index1, node_index2)"
<< "\n\tYou have specified an invalid index"
<< "\n\tnode_index1: " << node_index1
<< "\n\tnode_index2: " << node_index2
<< "\n\tnumber_of_nodes(): " << self.number_of_nodes()
<< "\n\tthis: " << &self
);
}
static void check_add_edge (
unsigned long node_index1,
unsigned long node_index2,
const graph& self
)
{
DLIB_CASSERT(node_index1 < self.number_of_nodes() &&
node_index2 < self.number_of_nodes(),
"\tvoid graph::add_edge(node_index1, node_index2)"
<< "\n\tYou have specified an invalid index"
<< "\n\tnode_index1: " << node_index1
<< "\n\tnode_index2: " << node_index2
<< "\n\tnumber_of_nodes(): " << self.number_of_nodes()
<< "\n\tthis: " << &self
);
DLIB_CASSERT( self.has_edge(node_index1, node_index2) == false,
"\tvoid graph::add_edge(node_index1, node_index2)"
<< "\n\tYou can't add an edge if it already exists in the graph"
<< "\n\tnode_index1: " << node_index1
<< "\n\tnode_index2: " << node_index2
<< "\n\tnumber_of_nodes(): " << self.number_of_nodes()
<< "\n\tthis: " << &self
);
}
static void check_remove_edge (
unsigned long node_index1,
unsigned long node_index2,
const graph& self
)
{
DLIB_CASSERT(node_index1 < self.number_of_nodes() &&
node_index2 < self.number_of_nodes(),
"\tvoid graph::remove_edge(node_index1, node_index2)"
<< "\n\tYou have specified an invalid index"
<< "\n\tnode_index1: " << node_index1
<< "\n\tnode_index2: " << node_index2
<< "\n\tnumber_of_nodes(): " << self.number_of_nodes()
<< "\n\tthis: " << &self
);
DLIB_CASSERT( self.has_edge(node_index1, node_index2) == true,
"\tvoid graph::remove_edge(node_index1, node_index2)"
<< "\n\tYou can't remove an edge if it isn't in the graph"
<< "\n\tnode_index1: " << node_index1
<< "\n\tnode_index2: " << node_index2
<< "\n\tnumber_of_nodes(): " << self.number_of_nodes()
<< "\n\tthis: " << &self
);
}
static void check_remove_node (
unsigned long index,
const graph& self
)
{
// make sure requires clause is not broken
DLIB_CASSERT(index < self.number_of_nodes(),
"\tvoid graph::remove_node(index)"
<< "\n\tYou have specified an invalid index"
<< "\n\tindex: " << index
<< "\n\tnumber_of_nodes(): " << self.number_of_nodes()
<< "\n\tthis: " << &self
);
}
};
template <typename node_type, typename graph>
struct graph_checker_helper <node_type, graph, false>
{
static inline void check_edge ( unsigned long , const node_type& ) { }
static inline void check_neighbor ( unsigned long , const node_type& ) { }
static inline void check_node ( unsigned long , const graph& ) { }
static inline void check_has_edge ( unsigned long , unsigned long , const graph& ) { }
static inline void check_add_edge ( unsigned long , unsigned long , const graph& ) { }
static inline void check_remove_edge ( unsigned long , unsigned long , const graph& ) { }
static inline void check_remove_node ( unsigned long , const graph& ) { }
};
// ----------------------------------------------------------------------------------------
template <
typename T,
typename E = char,
typename mem_manager = default_memory_manager,
bool is_checked = true
>
class graph_kernel_1 : noncopyable
{
/*!
INITIAL VALUE
- nodes.size() == 0
CONVENTION
- nodes.size() == number_of_nodes()
- for all valid i:
- *nodes[i] == node(i)
- nodes[i]->neighbors.size() == nodes[i]->number_of_neighbors(i)
- nodes[i]->idx == i == nodes[i]->index()
- for all valid n:
- nodes[i]->neighbors[n] == pointer to the n'th parent node of i
- *nodes[i]->neighbors[n] == node(i).neighbor(n)
- *nodes[i]->edges[n] == node(i).edge(n)
!*/
public:
struct node_type;
private:
typedef graph_checker_helper<node_type, graph_kernel_1, is_checked> checker;
public:
typedef T type;
typedef E edge_type;
typedef mem_manager mem_manager_type;
graph_kernel_1(
) {}
virtual ~graph_kernel_1(
) {}
void clear(
) { nodes.clear(); }
void set_number_of_nodes (
unsigned long new_size
);
unsigned long number_of_nodes (
) const { return nodes.size(); }
node_type& node (
unsigned long index
) { checker::check_node(index,*this); return *nodes[index]; }
const node_type& node (
unsigned long index
) const { checker::check_node(index,*this); return *nodes[index]; }
bool has_edge (
unsigned long node_index1,
unsigned long node_index2
) const;
void add_edge (
unsigned long node_index1,
unsigned long node_index2
);
void remove_edge (
unsigned long node_index1,
unsigned long node_index2
);
unsigned long add_node (
);
void remove_node (
unsigned long index
);
void swap (
graph_kernel_1& item
) { nodes.swap(item.nodes); }
public:
struct node_type
{
T data;
typedef graph_kernel_1 graph_type;
unsigned long index(
) const { return idx; }
unsigned long number_of_neighbors (
) const { return neighbors.size(); }
const node_type& neighbor (
unsigned long edge_index
) const { checker::check_neighbor(edge_index,*this); return *neighbors[edge_index]; }
node_type& neighbor (
unsigned long edge_index
) { checker::check_neighbor(edge_index,*this); return *neighbors[edge_index]; }
const E& edge (
unsigned long edge_index
) const { checker::check_edge(edge_index,*this); return *edges[edge_index]; }
E& edge (
unsigned long edge_index
) { checker::check_edge(edge_index,*this); return *edges[edge_index]; }
private:
friend class graph_kernel_1;
typedef std_allocator<node_type*,mem_manager> alloc_type;
typedef std_allocator<std::shared_ptr<E>,mem_manager> alloc_edge_type;
std::vector<node_type*,alloc_type> neighbors;
std::vector<std::shared_ptr<E>,alloc_edge_type> edges;
unsigned long idx;
};
private:
typedef std_allocator<std::shared_ptr<node_type>,mem_manager> alloc_type;
typedef std::vector<std::shared_ptr<node_type>, alloc_type> vector_type;
vector_type nodes;
};
// ----------------------------------------------------------------------------------------
template <
typename T,
typename E,
typename mem_manager,
bool is_checked
>
inline void swap (
graph_kernel_1<T,E,mem_manager,is_checked>& a,
graph_kernel_1<T,E,mem_manager,is_checked>& b
) { a.swap(b); }
// ----------------------------------------------------------------------------------------
template <
typename T,
typename E,
typename mem_manager,
bool is_checked
>
struct is_graph<graph_kernel_1<T,E,mem_manager, is_checked> >
{
static const bool value = true;
};
// ----------------------------------------------------------------------------------------
template <
typename T,
typename E,
typename mem_manager,
bool is_checked
>
void serialize (
const graph_kernel_1<T,E,mem_manager,is_checked>& item,
std::ostream& out
)
{
try
{
serialize(item.number_of_nodes(), out);
// serialize each node
for (unsigned long i = 0; i < item.number_of_nodes(); ++i)
{
serialize(item.node(i).data, out);
// serialize all the edges
for (unsigned long n = 0; n < item.node(i).number_of_neighbors(); ++n)
{
// only serialize edges that we haven't already serialized
if (item.node(i).neighbor(n).index() >= i)
{
serialize(item.node(i).neighbor(n).index(), out);
serialize(item.node(i).edge(n), out);
}
}
const unsigned long stop_mark = 0xFFFFFFFF;
serialize(stop_mark, out);
}
}
catch (serialization_error& e)
{
throw serialization_error(e.info + "\n while serializing object of type graph_kernel_1");
}
}
// ----------------------------------------------------------------------------------------
template <
typename T,
typename E,
typename mem_manager,
bool is_checked
>
void deserialize (
graph_kernel_1<T,E,mem_manager,is_checked>& item,
std::istream& in
)
{
try
{
unsigned long size;
deserialize(size, in);
item.clear();
item.set_number_of_nodes(size);
// deserialize each node
for (unsigned long i = 0; i < item.number_of_nodes(); ++i)
{
deserialize(item.node(i).data, in);
const unsigned long stop_mark = 0xFFFFFFFF;
// Add all the edges going to this node's neighbors
unsigned long index;
deserialize(index, in);
while (index != stop_mark)
{
item.add_edge(i, index);
// find the edge
unsigned long j = 0;
for (j = 0; j < item.node(i).number_of_neighbors(); ++j)
if (item.node(i).neighbor(j).index() == index)
break;
deserialize(item.node(i).edge(j), in);
deserialize(index, in);
}
}
}
catch (serialization_error& e)
{
throw serialization_error(e.info + "\n while deserializing object of type graph_kernel_1");
}
}
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
// member function definitions
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
template <
typename T,
typename E,
typename mem_manager,
bool is_checked
>
void graph_kernel_1<T,E,mem_manager,is_checked>::
set_number_of_nodes (
unsigned long new_size
)
{
try
{
nodes.resize(new_size);
for (unsigned long i = 0; i < nodes.size(); ++i)
{
nodes[i].reset(new node_type);
nodes[i]->idx = i;
}
}
catch (...)
{
clear();
throw;
}
}
// ----------------------------------------------------------------------------------------
template <
typename T,
typename E,
typename mem_manager,
bool is_checked
>
bool graph_kernel_1<T,E,mem_manager,is_checked>::
has_edge (
unsigned long node_index1,
unsigned long node_index2
) const
{
checker::check_has_edge(node_index1, node_index2, *this);
node_type& n = *nodes[node_index1];
// search all the child nodes to see if there is a link to the right node
for (unsigned long i = 0; i < n.neighbors.size(); ++i)
{
if (n.neighbors[i]->idx == node_index2)
return true;
}
return false;
}
// ----------------------------------------------------------------------------------------
template <
typename T,
typename E,
typename mem_manager,
bool is_checked
>
void graph_kernel_1<T,E,mem_manager,is_checked>::
add_edge (
unsigned long node_index1,
unsigned long node_index2
)
{
checker::check_add_edge(node_index1, node_index2, *this);
try
{
node_type& n1 = *nodes[node_index1];
node_type& n2 = *nodes[node_index2];
n1.neighbors.push_back(&n2);
std::shared_ptr<E> e(new E);
n1.edges.push_back(e);
// don't add this twice if this is an edge from node_index1 back to itself
if (node_index1 != node_index2)
{
n2.neighbors.push_back(&n1);
n2.edges.push_back(e);
}
}
catch (...)
{
clear();
throw;
}
}
// ----------------------------------------------------------------------------------------
template <
typename T,
typename E,
typename mem_manager,
bool is_checked
>
void graph_kernel_1<T,E,mem_manager,is_checked>::
remove_edge (
unsigned long node_index1,
unsigned long node_index2
)
{
checker::check_remove_edge(node_index1, node_index2, *this);
node_type& n1 = *nodes[node_index1];
node_type& n2 = *nodes[node_index2];
// remove the record of the link from n1
unsigned long pos = static_cast<unsigned long>(find(n1.neighbors.begin(), n1.neighbors.end(), &n2) - n1.neighbors.begin());
n1.neighbors.erase(n1.neighbors.begin() + pos);
n1.edges.erase(n1.edges.begin() + pos);
// check if this is an edge that goes from node_index1 back to itself
if (node_index1 != node_index2)
{
// remove the record of the link from n2
unsigned long pos = static_cast<unsigned long>(find(n2.neighbors.begin(), n2.neighbors.end(), &n1) - n2.neighbors.begin());
n2.neighbors.erase(n2.neighbors.begin() + pos);
n2.edges.erase(n2.edges.begin() + pos);
}
}
// ----------------------------------------------------------------------------------------
template <
typename T,
typename E,
typename mem_manager,
bool is_checked
>
unsigned long graph_kernel_1<T,E,mem_manager,is_checked>::
add_node (
)
{
try
{
std::shared_ptr<node_type> n(new node_type);
n->idx = nodes.size();
nodes.push_back(n);
return n->idx;
}
catch (...)
{
clear();
throw;
}
}
// ----------------------------------------------------------------------------------------
template <
typename T,
typename E,
typename mem_manager,
bool is_checked
>
void graph_kernel_1<T,E,mem_manager,is_checked>::
remove_node (
unsigned long index
)
{
checker::check_remove_node(index,*this);
node_type& n = *nodes[index];
// remove all edges pointing to this node from its neighbors
for (unsigned long i = 0; i < n.neighbors.size(); ++i)
{
// remove the edge from this specific parent
unsigned long pos = static_cast<unsigned long>(find(n.neighbors[i]->neighbors.begin(), n.neighbors[i]->neighbors.end(), &n) -
n.neighbors[i]->neighbors.begin());
n.neighbors[i]->neighbors.erase(n.neighbors[i]->neighbors.begin() + pos);
n.neighbors[i]->edges.erase(n.neighbors[i]->edges.begin() + pos);
}
// now remove this node by replacing it with the last node in the nodes vector
nodes[index] = nodes[nodes.size()-1];
// update the index for the node we just moved
nodes[index]->idx = index;
// now remove the duplicated node at the end of the vector
nodes.pop_back();
}
// ----------------------------------------------------------------------------------------
}
#endif // DLIB_GRAPH_KERNEl_1_