#include <graph_wo_index.hpp>

Inheritance diagram for jubatus::core::graph::graph_wo_index:

Collaboration diagram for jubatus::core::graph::graph_wo_index:

Classes
struct	config

struct	diff_type

Public Member Functions
void	add_centrality_query (const preset_query &)

void	add_shortest_path_query (const preset_query &)

double	centrality (node_id_t id, centrality_type ct, const preset_query &) const

void	clear ()

void	create_edge (edge_id_t eid, node_id_t src, node_id_t tgt)

void	create_global_node (node_id_t id)

void	create_node (node_id_t id)

void	damping_factor (double a)

void	get_diff (diff_type &diff) const

void	get_edge (edge_id_t eid, edge_info &ret) const

void	get_node (node_id_t id, node_info &ret) const

void	get_status (std::map< std::string, std::string > &status) const

storage::version	get_version () const

	graph_wo_index (const config &config)

	graph_wo_index ()

void	mix (const diff_type &diff, diff_type &mixed)

	MSGPACK_DEFINE (local_nodes_, local_edges_, global_nodes_, eigen_scores_, spts_)

void	pack (framework::packer &packer) const

bool	put_diff (const diff_type &mixed)

void	remove_centrality_query (const preset_query &)

void	remove_edge (edge_id_t eid)

void	remove_global_node (node_id_t id)

void	remove_node (node_id_t id)

void	remove_shortest_path_query (const preset_query &)

void	shortest_path (node_id_t src, node_id_t tgt, uint64_t max_hop, std::vector< node_id_t > &ret, const preset_query &) const

std::string	type () const

void	unpack (msgpack::object o)

void	update_edge (edge_id_t eid, const property &p)

void	update_index ()

void	update_node (node_id_t id, const property &p)

	~graph_wo_index ()

Private Types
typedef jubatus::util::data::unordered_map< edge_id_t, edge_info >	edge_info_map

typedef jubatus::util::data::unordered_map< node_id_t, node_info >	node_info_map

Private Member Functions
void	get_diff_eigen_score (eigen_vector_query_diff &diff) const

void	get_diff_shortest_path_tree (spt_query_diff &diff) const

bool	is_node_matched_to_query (const preset_query &query, node_id_t id) const

void	may_set_landmark (node_id_t id)

void	put_diff_eigen_score (const eigen_vector_query_diff &mixed)

void	put_diff_shortest_path_tree (const spt_query_diff &mixed)

void	update_spt ()

void	update_spt_edges (const preset_query &query, spt_edges &se, node_id_t landmark, bool is_out)

void	update_spt_node (const preset_query &query, const std::vector< edge_id_t > &edges, spt_edges &se, bool is_out)

Static Private Member Functions
static void	mix (const eigen_vector_query_diff &diff, eigen_vector_query_diff &mixed)

static void	mix (const spt_query_diff &diff, spt_query_diff &mixed, size_t landmark_num)

static void	mix_spt (const shortest_path_tree &diff, shortest_path_tree &mixed)

static void	remove_by_swap (std::vector< edge_id_t > &edges, edge_id_t eid)

Private Attributes
config	config_

eigen_vector_query_diff	eigen_scores_

jubatus::util::data::unordered_map< node_id_t, uint8_t >	global_nodes_

edge_info_map	local_edges_

node_info_map	local_nodes_

spt_query_diff	spts_

Detailed Description

Definition at line 38 of file graph_wo_index.hpp.

Member Typedef Documentation

typedef jubatus::util::data::unordered_map<edge_id_t, edge_info> jubatus::core::graph::graph_wo_index::edge_info_map

private

Definition at line 132 of file graph_wo_index.hpp.

typedef jubatus::util::data::unordered_map<node_id_t, node_info> jubatus::core::graph::graph_wo_index::node_info_map

private

Definition at line 130 of file graph_wo_index.hpp.

Constructor & Destructor Documentation

jubatus::core::graph::graph_wo_index::graph_wo_index ( const config & config )

explicit

Definition at line 73 of file graph_wo_index.cpp.

References clear(), jubatus::core::graph::graph_wo_index::config::damping_factor, JUBATUS_EXCEPTION, and jubatus::core::graph::graph_wo_index::config::landmark_num.

     : config_(config) {
 
   if (!(0.0 < config.damping_factor && config.damping_factor < 1.0)) {
     throw JUBATUS_EXCEPTION(
         common::invalid_parameter("0.0 < damping_factor < 1.0"));
   }
 
   if (!(0 <= config.landmark_num)) {
     throw JUBATUS_EXCEPTION(
         common::invalid_parameter("0 <= landmark_num"));
   }
 
   clear();
 }

Here is the call graph for this function:

jubatus::core::graph::graph_wo_index::graph_wo_index ( )

Definition at line 89 of file graph_wo_index.cpp.

References clear().

                                {
   clear();
 }

Here is the call graph for this function:

jubatus::core::graph::graph_wo_index::~graph_wo_index ( )

Definition at line 93 of file graph_wo_index.cpp.

93 {

94 }

Member Function Documentation

void jubatus::core::graph::graph_wo_index::add_centrality_query ( const preset_query & query )

Definition at line 222 of file graph_wo_index.cpp.

References eigen_scores_.

                                                                    {
   eigen_scores_.insert(make_pair(query, eigen_vector_diff()));
 }

void jubatus::core::graph::graph_wo_index::add_shortest_path_query ( const preset_query & query )

Definition at line 226 of file graph_wo_index.cpp.

References spts_.

                                                                       {
   spts_.insert(make_pair(query, spt_diff()));
 }

double jubatus::core::graph::graph_wo_index::centrality	(	node_id_t	id,
		centrality_type	ct,
		const preset_query &	query
	)		const

Definition at line 238 of file graph_wo_index.cpp.

References eigen_scores_, jubatus::core::graph::EIGENSCORE, and JUBATUS_EXCEPTION.

                                      {
   if (ct == EIGENSCORE) {
     eigen_vector_query_diff::const_iterator model_it
         = eigen_scores_.find(query);
     if (model_it == eigen_scores_.end()) {
       throw JUBATUS_EXCEPTION(unknown_centrality_type(ct));
     }
     eigen_vector_diff::const_iterator it = model_it->second.find(id);
     if (it == model_it->second.end()) {
       throw JUBATUS_EXCEPTION(unknown_id("centrality", id));
     }
     return it->second.score;
   } else {
     throw JUBATUS_EXCEPTION(unknown_centrality_type(ct));
   }
 }

void jubatus::core::graph::graph_wo_index::clear ( )

Definition at line 100 of file graph_wo_index.cpp.

References eigen_scores_, global_nodes_, local_edges_, local_nodes_, and spts_.

Referenced by graph_wo_index().

                            {
   local_nodes_.clear();
   local_edges_.clear();
   global_nodes_.clear();
   eigen_scores_.clear();
   spts_.clear();
 }

Here is the caller graph for this function:

void jubatus::core::graph::graph_wo_index::create_edge	(	edge_id_t	eid,
		node_id_t	src,
		node_id_t	tgt
	)

Definition at line 170 of file graph_wo_index.cpp.

References JUBATUS_EXCEPTION, local_edges_, local_nodes_, jubatus::core::graph::edge_info::src, and jubatus::core::graph::edge_info::tgt.

                                                                             {
   if (local_nodes_.find(src) == local_nodes_.end()
       && local_nodes_.find(tgt) == local_nodes_.end()) {
     throw JUBATUS_EXCEPTION(
         unknown_id(
             string("graph_wo_index::create_edge unknown src id=")
             + lexical_cast<string>(src)
             + " tgt id=" + lexical_cast<string>(tgt),
             src));
   }
   if (local_edges_.count(eid) > 0) {
     throw JUBATUS_EXCEPTION(edge_exists(eid));
   }
 
   edge_info ei;
   ei.src = src;
   ei.tgt = tgt;
   local_edges_[eid] = ei;
   if (local_nodes_.count(src) > 0) {
     local_nodes_[src].out_edges.push_back(eid);
   }
   if (local_nodes_.count(tgt) > 0) {
     local_nodes_[tgt].in_edges.push_back(eid);
   }
 }

void jubatus::core::graph::graph_wo_index::create_global_node ( node_id_t id )

Definition at line 132 of file graph_wo_index.cpp.

References global_nodes_, and JUBATUS_EXCEPTION.

                                                     {
   if (global_nodes_.count(id) > 0) {
     throw JUBATUS_EXCEPTION(global_node_exists(id));
   }
   global_nodes_[id] = 0;
 }

void jubatus::core::graph::graph_wo_index::create_node ( node_id_t id )

Definition at line 108 of file graph_wo_index.cpp.

References JUBATUS_EXCEPTION, local_nodes_, and may_set_landmark().

                                              {
   if (local_nodes_.count(id) > 0) {
     throw JUBATUS_EXCEPTION(local_node_exists(id));
   }
   local_nodes_[id] = node_info();
   may_set_landmark(id);
 }

Here is the call graph for this function:

void jubatus::core::graph::graph_wo_index::damping_factor ( double a )

Definition at line 96 of file graph_wo_index.cpp.

References config_, and jubatus::core::graph::graph_wo_index::config::damping_factor.

                                             {
   config_.damping_factor = a;
 }

void jubatus::core::graph::graph_wo_index::get_diff ( diff_type & diff ) const

Definition at line 607 of file graph_wo_index.cpp.

References jubatus::core::graph::graph_wo_index::diff_type::eigen_vector_query, get_diff_eigen_score(), get_diff_shortest_path_tree(), jubatus::core::graph::graph_wo_index::diff_type::spt_query, and update_spt().

Referenced by update_index().

                                                    {
   // get_diff should be constant
   const_cast<graph_wo_index*>(this)->update_spt();
 
   get_diff_eigen_score(diff.eigen_vector_query);
   get_diff_shortest_path_tree(diff.spt_query);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::graph::graph_wo_index::get_diff_eigen_score ( eigen_vector_query_diff & diff ) const

private

Definition at line 372 of file graph_wo_index.cpp.

References config_, jubatus::core::graph::graph_wo_index::config::damping_factor, jubatus::core::clustering::dist(), jubatus::core::graph::preset_query::edge_query, eigen_scores_, is_node_matched_to_query(), local_edges_, local_nodes_, jubatus::core::graph::preset_query::node_query, jubatus::core::graph::eigen_vector_info::out_degree_num, jubatus::core::graph::edge_info::p, jubatus::core::graph::eigen_vector_info::score, and jubatus::core::graph::edge_info::tgt.

Referenced by get_diff().

                                                                              {
   diff.clear();  // tmp_diff + swap is better ?
 
   for (eigen_vector_query_diff::const_iterator query_it
            = eigen_scores_.begin();
        query_it != eigen_scores_.end(); ++query_it) {
     const preset_query& query = query_it->first;
     const eigen_vector_diff& model = query_it->second;
 
     double dist = 0;
     for (eigen_vector_diff::const_iterator it = model.begin();
          it != model.end(); ++it) {
       if (it->second.out_degree_num == 0) {
         dist += it->second.score;
       }
     }
 
     unordered_set<node_id_t> unmatched_nodes;
 
     uint64_t new_node_num = 0;
     double dist_from_new_node = 0;
     for (node_info_map::const_iterator node_it = local_nodes_.begin();
          node_it != local_nodes_.end(); ++node_it) {
       if (model.count(node_it->first) == 0) {
         if (!is_matched_to_query(query.node_query, node_it->second.property)) {
           unmatched_nodes.insert(node_it->first);
           continue;
         }
         dist_from_new_node += 1.0;
         ++new_node_num;
       }
     }
     dist += dist_from_new_node;
 
     if (model.size() + new_node_num > 0) {
       dist /= (model.size() + new_node_num);
     }
 
     eigen_vector_diff& qdiff = diff[query];
 
     for (node_info_map::const_iterator node_it = local_nodes_.begin();
          node_it != local_nodes_.end(); ++node_it) {
       if (unmatched_nodes.count(node_it->first)) {
         continue;
       }
       if (!is_matched_to_query(query.node_query, node_it->second.property)) {
         unmatched_nodes.insert(node_it->first);
         continue;
       }
 
       const std::vector<edge_id_t>& in_edges = node_it->second.in_edges;
       double score = 0;
       for (size_t i = 0; i < in_edges.size(); ++i) {
         if (unmatched_nodes.count(in_edges[i])) {
           continue;
         }
         edge_info_map::const_iterator edge_it = local_edges_.find(in_edges[i]);
         if (edge_it == local_edges_.end()) {
           continue;
         }
 
         const node_id_t src = edge_it->second.src;
         if (unmatched_nodes.count(src)) {
           continue;
         }
         if (!is_matched_to_query(query.edge_query, edge_it->second.p)) {
           continue;
         }
 
         eigen_vector_diff::const_iterator it = model.find(edge_it->second.src);
         if (it == model.end()) {
           continue;
         }
         if (it->second.out_degree_num != 0) {
           // TODO(beam2d) it->second.score > 0 should indicate
           // it->second.out_degree_num
           score += it->second.score / it->second.out_degree_num;
         }
       }
 
       eigen_vector_info ei;
       ei.score = config_.damping_factor * score + 1 - config_.damping_factor
           + config_.damping_factor * dist;
 
       if (is_empty_query(query)) {
         ei.out_degree_num = node_it->second.out_edges.size();
       } else {
         uint64_t out_degree = 0;
         for (size_t i = 0; i < node_it->second.out_edges.size(); ++i) {
           const edge_info_map::const_iterator edge_it
               = local_edges_.find(node_it->second.out_edges[i]);
           const edge_info& edge = edge_it->second;
           if (unmatched_nodes.count(edge.tgt)) {
             continue;
           }
           if (!is_node_matched_to_query(query, edge.tgt)) {
             unmatched_nodes.insert(edge.tgt);
             continue;
           }
           if (!is_matched_to_query(query.edge_query, edge.p)) {
             continue;
           }
           ++out_degree;
         }
         ei.out_degree_num = out_degree;
       }
 
       qdiff[node_it->first] = ei;
     }
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::graph::graph_wo_index::get_diff_shortest_path_tree ( spt_query_diff & diff ) const

private

Definition at line 567 of file graph_wo_index.cpp.

References jubatus::core::graph::shortest_path_tree::from_root, jubatus::core::graph::shortest_path_tree::landmark, local_nodes_, spts_, and jubatus::core::graph::shortest_path_tree::to_root.

Referenced by get_diff().

                                     {
   all_diff.clear();
 
   for (spt_query_diff::const_iterator it = spts_.begin(); it != spts_.end();
        ++it) {
     const spt_diff& mixed = it->second;
     spt_diff& diff = all_diff[it->first];
     diff.resize(mixed.size());
 
     for (uint64_t i = 0; i < mixed.size(); ++i) {
       const shortest_path_tree& spt = mixed[i];
       if (spt.landmark == LLONG_MAX) {
         continue;
       }
       diff[i].landmark = spt.landmark;
 
       for (node_info_map::const_iterator it = local_nodes_.begin();
            it != local_nodes_.end(); ++it) {
         const node_id_t id = it->first;
 
         spt_edges::const_iterator from_it = spt.from_root.find(id);
         if (from_it != spt.from_root.end()) {
           diff[i].from_root[id] = from_it->second;
         }
 
         spt_edges::const_iterator to_it = spt.to_root.find(id);
         if (to_it != spt.to_root.end()) {
           diff[i].to_root[id] = to_it->second;
         }
       }
     }
   }
 }

Here is the caller graph for this function:

void jubatus::core::graph::graph_wo_index::get_edge	(	edge_id_t	eid,
		edge_info &	ret
	)		const

Definition at line 345 of file graph_wo_index.cpp.

References JUBATUS_EXCEPTION, and local_edges_.

                                                                  {
   edge_info_map::const_iterator it = local_edges_.find(eid);
   if (it == local_edges_.end()) {
     throw JUBATUS_EXCEPTION(unknown_id("get_edge", eid));
   }
   ret = it->second;
 }

void jubatus::core::graph::graph_wo_index::get_node	(	node_id_t	id,
		node_info &	ret
	)		const

Definition at line 337 of file graph_wo_index.cpp.

References JUBATUS_EXCEPTION, and local_nodes_.

Referenced by remove_node().

                                                                 {
   node_info_map::const_iterator it = local_nodes_.find(id);
   if (it == local_nodes_.end()) {
     throw JUBATUS_EXCEPTION(unknown_id("get_node", id));
   }
   ret = it->second;
 }

Here is the caller graph for this function:

void jubatus::core::graph::graph_wo_index::get_status ( std::map< std::string, std::string > & status ) const

Definition at line 621 of file graph_wo_index.cpp.

References global_nodes_, local_edges_, and local_nodes_.

                                                                  {
   status["local_node_num"] = lexical_cast<string>(local_nodes_.size());
   status["global_node_num"] = lexical_cast<string>(global_nodes_.size());
   status["local_edge_num"] = lexical_cast<string>(local_edges_.size());
 }

storage::version jubatus::core::graph::graph_wo_index::get_version ( ) const

inline

Definition at line 117 of file graph_wo_index.hpp.

                                      {
     // TODO(kumagi): it should return correct version of model
     return storage::version();
   }

bool jubatus::core::graph::graph_wo_index::is_node_matched_to_query	(	const preset_query &	query,
		node_id_t	id
	)		const

private

Definition at line 546 of file graph_wo_index.cpp.

References local_nodes_, and jubatus::core::graph::preset_query::node_query.

Referenced by get_diff_eigen_score(), may_set_landmark(), and update_spt_node().

                         {
   node_info_map::const_iterator it = local_nodes_.find(id);
   if (it == local_nodes_.end()) {
     return true;
   }
   return is_matched_to_query(query.node_query, it->second.property);
 }

Here is the caller graph for this function:

void jubatus::core::graph::graph_wo_index::may_set_landmark ( node_id_t id )

private

Definition at line 116 of file graph_wo_index.cpp.

References config_, is_node_matched_to_query(), jubatus::core::graph::shortest_path_tree::landmark, jubatus::core::graph::graph_wo_index::config::landmark_num, and spts_.

Referenced by create_node(), and update_node().

                                                   {
   // Do we need it?
   // if (id > 1) return;
   for (spt_query_diff::iterator it = spts_.begin(); it != spts_.end(); ++it) {
     spt_diff& mixed = it->second;
     if (mixed.size() == static_cast<size_t>(config_.landmark_num)
         || !is_node_matched_to_query(it->first, id)) {
       return;
     }
 
     shortest_path_tree spt;
     spt.landmark = id;
     mixed.push_back(spt);
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::graph::graph_wo_index::mix	(	const diff_type &	diff,
		diff_type &	mixed
	)

Definition at line 627 of file graph_wo_index.cpp.

References config_, jubatus::core::graph::graph_wo_index::diff_type::eigen_vector_query, jubatus::core::graph::graph_wo_index::config::landmark_num, and jubatus::core::graph::graph_wo_index::diff_type::spt_query.

                                                                 {
   mix(diff.eigen_vector_query, mixed.eigen_vector_query);
   mix(diff.spt_query, mixed.spt_query, config_.landmark_num);
 }

void jubatus::core::graph::graph_wo_index::mix	(	const eigen_vector_query_diff &	diff,
		eigen_vector_query_diff &	mixed
	)

staticprivate

Definition at line 632 of file graph_wo_index.cpp.

                                     {
   for (eigen_vector_query_diff::const_iterator model_it = diff.begin();
       model_it != diff.end(); ++model_it) {
     eigen_vector_diff& evm = mixed[model_it->first];
     for (eigen_vector_diff::const_iterator it = model_it->second.begin();
          it != model_it->second.end(); ++it) {
       evm[it->first] = it->second;
     }
   }
 }

void jubatus::core::graph::graph_wo_index::mix	(	const spt_query_diff &	diff,
		spt_query_diff &	mixed,
		size_t	landmark_num
	)

staticprivate

Definition at line 659 of file graph_wo_index.cpp.

References mix_spt().

                          {
   for (spt_query_diff::const_iterator it = all_diff.begin();
        it != all_diff.end(); ++it) {
     const spt_diff& diff = it->second;
     spt_diff& mixed = all_mixed[it->first];
 
     map<node_id_t, uint64_t> diff_landmark2ind;
     for (uint64_t i = 0; i < diff.size(); ++i) {
       if (diff[i].landmark != LLONG_MAX) {
         diff_landmark2ind[diff[i].landmark] = i;
       }
     }
 
     map<node_id_t, uint64_t> mixed_landmark2ind;
     for (uint64_t i = 0; i < mixed.size(); ++i) {
       if (mixed[i].landmark != LLONG_MAX) {
         mixed_landmark2ind[mixed[i].landmark] = i;
       }
     }
 
     for (map<node_id_t, uint64_t>::const_iterator it
              = diff_landmark2ind.begin(); it != diff_landmark2ind.end(); ++it) {
       map<node_id_t, uint64_t>::iterator jt
           = mixed_landmark2ind.find(it->first);
       if (jt != mixed_landmark2ind.end()) {
         mix_spt(diff[it->second], mixed[jt->second]);
       } else if (mixed.size() < landmark_num) {
         mixed.push_back(diff[it->second]);
       }
     }
   }
 }

Here is the call graph for this function:

void jubatus::core::graph::graph_wo_index::mix_spt	(	const shortest_path_tree &	diff,
		shortest_path_tree &	mixed
	)

staticprivate

Definition at line 645 of file graph_wo_index.cpp.

References jubatus::core::graph::shortest_path_tree::from_root, and jubatus::core::graph::shortest_path_tree::to_root.

Referenced by mix().

                                {
   for (spt_edges::const_iterator it = diff.from_root.begin();
        it != diff.from_root.end(); ++it) {
     mixed.from_root[it->first] = it->second;
   }
 
   for (spt_edges::const_iterator it = diff.to_root.begin();
        it != diff.to_root.end(); ++it) {
     mixed.to_root[it->first] = it->second;
   }
 }

Here is the caller graph for this function:

jubatus::core::graph::graph_wo_index::MSGPACK_DEFINE	(	local_nodes_	,
		local_edges_	,
		global_nodes_	,
		eigen_scores_	,
		spts_
	)

void jubatus::core::graph::graph_wo_index::pack ( framework::packer & packer ) const

Definition at line 357 of file graph_wo_index.cpp.

                                                        {
   packer.pack(*this);
 }

bool jubatus::core::graph::graph_wo_index::put_diff ( const diff_type & mixed )

Definition at line 615 of file graph_wo_index.cpp.

References jubatus::core::graph::graph_wo_index::diff_type::eigen_vector_query, put_diff_eigen_score(), put_diff_shortest_path_tree(), and jubatus::core::graph::graph_wo_index::diff_type::spt_query.

Referenced by update_index().

                                                     {
   put_diff_eigen_score(mixed.eigen_vector_query);
   put_diff_shortest_path_tree(mixed.spt_query);
   return true;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::graph::graph_wo_index::put_diff_eigen_score ( const eigen_vector_query_diff & mixed )

private

Definition at line 484 of file graph_wo_index.cpp.

References eigen_scores_.

Referenced by put_diff().

                                           {
   eigen_scores_ = mixed;
   if (eigen_scores_.size() == 0) {
     return;
   }
 
   // normalize
   for (eigen_vector_query_diff::iterator model_it = eigen_scores_.begin();
        model_it != eigen_scores_.end(); ++model_it) {
     normalize(model_it->second);
   }
 }

Here is the caller graph for this function:

void jubatus::core::graph::graph_wo_index::put_diff_shortest_path_tree ( const spt_query_diff & mixed )

private

Definition at line 602 of file graph_wo_index.cpp.

References spts_.

Referenced by put_diff().

                                  {
   spts_ = mixed;
 }

Here is the caller graph for this function:

void jubatus::core::graph::graph_wo_index::remove_by_swap	(	std::vector< edge_id_t > &	edges,
		edge_id_t	eid
	)

staticprivate

Definition at line 695 of file graph_wo_index.cpp.

References jubatus::core::clustering::swap().

Referenced by remove_edge().

                    {
   for (size_t i = 0; i < edges.size(); ++i) {
     if (edges[i] == eid) {
       if (i + 1 < edges.size()) {
         swap(edges[i], edges.back());
       }
       edges.resize(edges.size() - 1);
       return;
     }
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::graph::graph_wo_index::remove_centrality_query ( const preset_query & query )

Definition at line 230 of file graph_wo_index.cpp.

References eigen_scores_.

                                                                       {
   eigen_scores_.erase(query);
 }

void jubatus::core::graph::graph_wo_index::remove_edge ( edge_id_t eid )

Definition at line 204 of file graph_wo_index.cpp.

References JUBATUS_EXCEPTION, local_edges_, local_nodes_, and remove_by_swap().

                                               {
   edge_info_map::iterator it = local_edges_.find(eid);
   if (it == local_edges_.end()) {
     throw JUBATUS_EXCEPTION(unknown_id("remove_edge:eid", eid));
   }
   node_id_t src = it->second.src;
   node_id_t tgt = it->second.tgt;
 
   if (local_nodes_.count(src) > 0) {
     remove_by_swap(local_nodes_[src].out_edges, eid);
   }
   if (local_nodes_.count(tgt) > 0) {
     remove_by_swap(local_nodes_[tgt].in_edges, eid);
   }
 
   local_edges_.erase(it);
 }

Here is the call graph for this function:

void jubatus::core::graph::graph_wo_index::remove_global_node ( node_id_t id )

Definition at line 139 of file graph_wo_index.cpp.

References global_nodes_, and JUBATUS_EXCEPTION.

                                                     {
   if (global_nodes_.count(id) == 0) {
     throw JUBATUS_EXCEPTION(unknown_id("remove_global_node", id));
   }
   global_nodes_.erase(id);
 }

void jubatus::core::graph::graph_wo_index::remove_node ( node_id_t id )

Definition at line 155 of file graph_wo_index.cpp.

References get_node(), jubatus::core::graph::node_info::in_edges, JUBATUS_EXCEPTION, local_nodes_, and jubatus::core::graph::node_info::out_edges.

                                              {
   node_info ni;
   try {
     get_node(id, ni);
   } catch (jubatus::core::common::exception::runtime_error&) {
     throw JUBATUS_EXCEPTION(unknown_id("remove_node", id));
   }
   if (ni.in_edges.size() > 0 || ni.out_edges.size() > 0) {
     throw JUBATUS_EXCEPTION(jubatus::core::common::exception::runtime_error(
         string("graph_wo_index::remove_node unknown id=")
         + lexical_cast<string>(id)));
   }
   local_nodes_.erase(id);
 }

Here is the call graph for this function:

void jubatus::core::graph::graph_wo_index::remove_shortest_path_query ( const preset_query & query )

Definition at line 234 of file graph_wo_index.cpp.

References spts_.

                                                                          {
   spts_.erase(query);
 }

void jubatus::core::graph::graph_wo_index::shortest_path	(	node_id_t	src,
		node_id_t	tgt,
		uint64_t	max_hop,
		std::vector< node_id_t > &	ret,
		const preset_query &	query
	)		const

Definition at line 258 of file graph_wo_index.cpp.

References config_, jubatus::core::graph::shortest_path_tree::from_root, global_nodes_, JUBATUS_EXCEPTION, jubatus::core::graph::graph_wo_index::config::landmark_num, spts_, and jubatus::core::graph::shortest_path_tree::to_root.

                                      {
   if (global_nodes_.count(src) == 0) {
     throw JUBATUS_EXCEPTION(unknown_id("shortest_path:src", src));
   }
   if (global_nodes_.count(tgt) == 0) {
     throw JUBATUS_EXCEPTION(unknown_id("shortest_path:tgt", tgt));
   }
   spt_query_diff::const_iterator model_it = spts_.find(query);
   if (model_it == spts_.end()) {
     throw JUBATUS_EXCEPTION(unknown_query(query));
   }
   const spt_diff& mixed = model_it->second;
   ret.clear();
   uint64_t min_score = ~uint64_t();
   uint64_t ind = ~uint64_t();
   for (uint64_t i = 0; i < mixed.size(); ++i) {
     const shortest_path_tree& spt = mixed[i];
     spt_edges::const_iterator src_it = spt.to_root.find(src);
     spt_edges::const_iterator tgt_it = spt.from_root.find(tgt);
     if (src_it == spt.to_root.end() || tgt_it == spt.from_root.end()) {
       continue;
     }
     uint64_t score = src_it->second.first + tgt_it->second.first;
     if (score < min_score) {
       min_score = score;
       ind = i;
     }
   }
 
   if (ind >= static_cast<uint64_t>(config_.landmark_num)) {
     return;
   }
 
   const spt_edges& to_root = mixed[ind].to_root;
   const spt_edges& from_root = mixed[ind].from_root;
   uint64_t landmark = mixed[ind].landmark;
 
   for (uint64_t cur = src; cur != landmark;) {
     if (ret.size() >= max_hop) {
       return;
     }
     spt_edges::const_iterator it = to_root.find(cur);
     if (it == to_root.end()) {
       ret.clear();
       return;
     }
     ret.push_back(cur);
     if (cur == tgt) {
       return;
     }
     cur = it->second.second;
   }
   ret.push_back(landmark);
 
   std::vector<node_id_t> from_root_path;
   for (uint64_t cur = tgt; cur != landmark;) {
     if (ret.size() + from_root_path.size() >= max_hop) {
       return;
     }
     spt_edges::const_iterator it = from_root.find(cur);
     if (it == from_root.end()) {
       ret.clear();
       return;
     }
     from_root_path.push_back(cur);
     cur = it->second.second;
   }
 
   for (vector<node_id_t>::const_reverse_iterator rit = from_root_path.rbegin();
        rit != from_root_path.rend(); ++rit) {
     ret.push_back(*rit);
   }
 }

string jubatus::core::graph::graph_wo_index::type ( ) const

Definition at line 353 of file graph_wo_index.cpp.

                                   {
   return string("graph_wo_index");
 }

void jubatus::core::graph::graph_wo_index::unpack ( msgpack::object o )

Definition at line 361 of file graph_wo_index.cpp.

                                            {
   o.convert(this);
 }

void jubatus::core::graph::graph_wo_index::update_edge	(	edge_id_t	eid,
		const property &	p
	)

Definition at line 196 of file graph_wo_index.cpp.

References JUBATUS_EXCEPTION, and local_edges_.

                                                                  {
   edge_info_map::iterator it = local_edges_.find(eid);
   if (it == local_edges_.end()) {
     throw JUBATUS_EXCEPTION(unknown_id("update_edge:eid", eid));
   }
   it->second.p = p;
 }

void jubatus::core::graph::graph_wo_index::update_index ( )

Definition at line 365 of file graph_wo_index.cpp.

References get_diff(), put_diff(), and update_spt().

                                   {
   update_spt();
   diff_type diff;
   get_diff(diff);
   put_diff(diff);
 }

Here is the call graph for this function:

void jubatus::core::graph::graph_wo_index::update_node	(	node_id_t	id,
		const property &	p
	)

Definition at line 146 of file graph_wo_index.cpp.

References JUBATUS_EXCEPTION, local_nodes_, and may_set_landmark().

                                                                 {
   node_info_map::iterator it = local_nodes_.find(id);
   if (it == local_nodes_.end()) {
     throw JUBATUS_EXCEPTION(unknown_id("update_node", id));
   }
   it->second.property = p;
   may_set_landmark(id);
 }

Here is the call graph for this function:

void jubatus::core::graph::graph_wo_index::update_spt ( )

private

Definition at line 556 of file graph_wo_index.cpp.

References jubatus::core::graph::shortest_path_tree::from_root, jubatus::core::graph::shortest_path_tree::landmark, spts_, jubatus::core::graph::shortest_path_tree::to_root, and update_spt_edges().

Referenced by get_diff(), and update_index().

                                 {
   for (spt_query_diff::iterator it = spts_.begin(); it != spts_.end(); ++it) {
     spt_diff& mixed = it->second;
     for (size_t i = 0; i < mixed.size(); ++i) {
       shortest_path_tree& spt = mixed[i];
       update_spt_edges(it->first, spt.to_root, spt.landmark, false);
       update_spt_edges(it->first, spt.from_root, spt.landmark, true);
     }
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::graph::graph_wo_index::update_spt_edges	(	const preset_query &	query,
		spt_edges &	se,
		node_id_t	landmark,
		bool	is_out
	)

private

Definition at line 498 of file graph_wo_index.cpp.

References local_nodes_, and update_spt_node().

Referenced by update_spt().

                  {
   se[landmark] = std::make_pair(0, landmark);
   for (node_info_map::const_iterator it = local_nodes_.begin();
        it != local_nodes_.end(); ++it) {
     if (!is_out) {
       update_spt_node(query, it->second.out_edges, se, is_out);
     } else {
       update_spt_node(query, it->second.in_edges, se, is_out);
     }
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::graph::graph_wo_index::update_spt_node	(	const preset_query &	query,
		const std::vector< edge_id_t > &	edges,
		spt_edges &	se,
		bool	is_out
	)

private

Definition at line 514 of file graph_wo_index.cpp.

References jubatus::core::clustering::dist(), jubatus::core::graph::preset_query::edge_query, is_node_matched_to_query(), local_edges_, jubatus::core::graph::edge_info::p, jubatus::core::graph::edge_info::src, and jubatus::core::graph::edge_info::tgt.

Referenced by update_spt_edges().

                  {
   for (size_t i = 0; i < edges.size(); ++i) {
     edge_info& edge = local_edges_[edges[i]];
     const node_id_t from = is_out ? edge.src : edge.tgt;
     const node_id_t to = is_out ? edge.tgt : edge.src;
 
     if (!is_matched_to_query(query.edge_query, edge.p)
         || !is_node_matched_to_query(query, from)
         || !is_node_matched_to_query(query, to)) {
       continue;
     }
 
     spt_edges::iterator tr_it = se.find(from);
     if (tr_it != se.end()) {
       uint64_t dist = tr_it->second.first + 1;
       spt_edges::iterator tr_jt = se.find(to);
       if (tr_jt != se.end()) {
         if (dist < tr_jt->second.first) {
           tr_jt->second.first = dist;
           tr_jt->second.second = from;
         }
       } else {
         se.insert(std::make_pair(to, std::make_pair(dist, from)));
       }
     }
   }
 }