all_distance_sketch Namespace Reference

Namespaces
	constants
	graph

Classes
class	Cover
	Cover extracted by the influence maximization algorithms. More...
class	GraphSketch
	Data structure for the graph sketch. More...
class	NodeIdDistanceData
	Container class to store node id and distance. More...
class	NodeSketch
	Single node sketch. More...
struct	SeedCover_t
	Single seed information. More...
class	TSkimReverseRank
	Infuelnce maximization based on reverse ranks. More...

Typedefs
typedef proto::NodeRanksGpb	NodeRanksGpb
typedef proto::NodeRankGpb	NodeRankGpb
typedef proto::SeedInfoGpb	SeedInfoGpb
typedef proto::CoverGpb	CoverGpb
typedef struct all_distance_sketch::SeedCover_t	SeedCover
	Single seed information. More...
typedef std::vector< NodeSketch >	NodesSketch
typedef NodesSketch::iterator	NodesSketchItr
typedef double	RandomId
	Type for random ids.
typedef proto::AllDistanceSketchGpb	AllDistanceSketchGpb
typedef proto::AllDistanceSketchGpb::NodeThresholdGpb	NodeThresholdGpb
typedef proto::SingleNodeSketchGpb	SingleNodeSketchGpb
typedef proto::SingleNodeSketchGpb::NodeSummaryDetailsGpb	NodeSummaryDetailsGpb
typedef proto::SingleNodeSketchGpb::ZValuesGpb	ZValuesGpb
typedef struct all_distance_sketch::NodeProb_t	NodeProb
typedef std::vector< Neighbourhood >	NeighbourhoodVector
typedef std::unordered_map< graph::EdgeWeight, NodeIdDistanceData >	ZValues
typedef std::vector< NodeIdDistanceData >	NodeIdDistanceVector
	Container for node id and distance.
typedef std::vector< NodeIdDistanceData >::iterator	NodeIdDistanceVectorItr
typedef std::vector< NodeDistanceIdRandomIdData >	NodeDistanceIdRandomIdDataVector
typedef std::vector< NodeDistanceIdRandomIdData >::iterator	NodeDistanceIdRandomIdDataVectorItr
typedef boost::minstd_rand	base_generator_type

Functions
template<class T >
static void	CalculateReverseRank (int source, graph::Graph< T > *graph, GraphSketch *graph_sketch, std::vector< int > *ranking)
	Calculates the reverse ranks of a single node. More...
template<class T , class CallBacks >
static void	CalculateReverseRank (int source, graph::Graph< T > *graph, GraphSketch *graph_sketch, std::vector< int > *ranking, CallBacks *call_backs)
	Calculates the reverse ranks of a single node. More...
static void	SaveRankingToGpb (int source_node_id, const std::vector< int > &ranking, NodeRanksGpb *node_ranks)
	saves the ranking to Gpb
static void	LoadRankingFromGpb (std::vector< int > *ranking, const NodeRanksGpb &node_ranks)
template<class T >
static void	CalculateGraphSketchMultiCore (graph::Graph< T > *graph, GraphSketch *graph_sketch, unsigned int num_threads=5, double increase_factor=1.1)
	Calculate the bottom K graph sketch in parallel This implementation is faster than the single threaded implementation but the cost is in memory. More...
template<class T >
static void	CalculateGraphSketch (graph::Graph< T > *graph, GraphSketch *graph_sketch)
	Calculate the bottom K single threaded. More...
int	random_gen_func (int i)
bool	cmp (const std::pair< int, int > &p1, const std::pair< int, int > &p2)

Detailed Description

project namespace

Typedef Documentation

typedef std::vector<NodeIdDistanceData>::iterator all_distance_sketch::NodeIdDistanceVectorItr

Iterator for vector

typedef std::vector<NodeSketch> all_distance_sketch::NodesSketch

Vector of NodeSketch objects

typedef NodesSketch::iterator all_distance_sketch::NodesSketchItr

Itertor

typedef struct all_distance_sketch::SeedCover_t all_distance_sketch::SeedCover

Single seed information.

Function Documentation

template<class T >

static void all_distance_sketch::CalculateGraphSketch ( graph::Graph< T > *  graph, GraphSketch *  graph_sketch  )

static

Calculate the bottom K single threaded.

Parameters

[in]	graph	- Graph data structure to calculate his sketch
[out]	graph_sketch	- The result graph sketch

See also

graph::Graph

GraphSketch

template<class T >

static void all_distance_sketch::CalculateGraphSketchMultiCore ( graph::Graph< T > *  graph, GraphSketch *  graph_sketch, unsigned int  num_threads = 5, double  increase_factor = 1.1  )

static

Calculate the bottom K graph sketch in parallel This implementation is faster than the single threaded implementation but the cost is in memory.

Parameters

[in]	graph	- Graph data structure to calculate his sketch
[out]	graph_sketch	- The result graph sketch
[in]	num_threads	- The number of threads to use in the calculation
[in]	increase_factor	- The calculation divides the work to batchs of increasing size. This factor will determine the size of each batch when the starting batch size is defined to be of size K received from the graph_sketch.

See also

graph::Graph

GraphSketch

template<class T >

all_distance_sketch::CalculateReverseRank ( int  source, graph::Graph< T > *  graph, GraphSketch *  graph_sketch, std::vector< int > *  ranking  )

static

Calculates the reverse ranks of a single node.

Parameters

[in]	source	- node id. for this node the algorithm will calculate how all the other nodes rank it.
[in]	graph	- The graph to run the calculation on.
[in]	graph_sketch	- See doc for more infromation.
[out]	ranking	- here the result of the calculation is stored. the ranking of j to source will be stored in (*ranking)[j] If there is not path between j and source then (*ranking)[j] == constants::UNREACHABLE The same goes for j such that j is not a node in the graph

See also

GraphSketch

graph::Graph

constants::UNREACHABLE

Examples:

examples/reverse_rank.cpp.

template<class T , class CallBacks >

all_distance_sketch::CalculateReverseRank ( int  source, graph::Graph< T > *  graph, GraphSketch *  graph_sketch, std::vector< int > *  ranking, CallBacks *  call_backs  )

static

Calculates the reverse ranks of a single node.

Parameters

[in]	source	- node id. for this node the algorithm will calculate how all the other nodes rank it.
[in]	graph	- The graph to run the calculation on.
[in]	graph_sketch	- See doc for more infromation.
[out]	ranking	- here the result of the calculation is stored. the ranking of j to source will be stored in (*ranking)[j]. If there is not path between j and source then (*ranking)[j] == constants::UNREACHABLE The same goes for j such that j is not a node in the graph
[in]	call_backs	- Call backs class with function that will be called in each major event. It can be used to stop the calucation once we reached all nodes that rank source up to a certain level e.g. stop when ranking[i] >= 100

See also

GraphSketch

graph::Graph

constants::UNREACHABLE