All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | Protected Member Functions | Protected Attributes | Friends | List of all members
NetworKit::PubWebGenerator Class Reference

Generates a static graph that resembles an assumed geometric distribution of nodes in a P2P network. More...

#include <PubWebGenerator.h>

Public Member Functions

 PubWebGenerator ()
 
 PubWebGenerator (count numNodes, count numberOfDenseAreas, float neighborhoodRadius, count maxNumberOfNeighbors)
 
virtual Graph generate ()
 
- Public Member Functions inherited from NetworKit::StaticGraphGenerator
virtual ~StaticGraphGenerator ()=default
 Default destructor. More...
 

Protected Member Functions

void determineNeighbors (Graph &g)
 
void moveNodeIntoUnitSquare (float &x, float &y)
 
float squaredDistanceInUnitTorus (float x1, float y1, float x2, float y2)
 
void chooseDenseAreaSizes ()
 
void fillDenseAreas (Graph &g)
 
void spreadRemainingNodes (Graph &g)
 
void chooseClusterSizes ()
 
void addNodesToArea (index area, count num, Graph &g)
 
bool isValidEdge (Graph &g, node u, node v, edgeweight &ew)
 
void addNode (Graph &g)
 Adds nodes randomly, distribution respects original one. More...
 
void removeRandomNode (Graph &g)
 Removes random node, uniform distribution. More...
 

Protected Attributes

count n
 number of nodes More...
 
count numDenseAreas
 number of areas with more nodes (denser) More...
 
float neighRad
 neighborhood radius More...
 
count maxNeigh
 maximum number of neighbors More...
 
std::vector< circledenseAreaXYR
 position of each circular dense area More...
 
std::vector< countnumPerArea
 number of points in each circular area More...
 

Friends

class DynamicPubWebGenerator
 

Detailed Description

Generates a static graph that resembles an assumed geometric distribution of nodes in a P2P network.

The basic structure is to distribute points randomly in the unit torus and to connect vertices close to each other (at most neighRad distance and none of them already has maxNeigh neighbors). The distribution is chosen to get some areas with high density and others with low density. There are numDenseAreas dense areas, which can overlap. Each area is circular, has a certain position and radius and number of points. These values are strored in denseAreaXYR and numPerArea, respectively.

Used and described in more detail in J. Gehweiler, H. Meyerhenke: A Distributed Diffusive Heuristic for Clustering a Virtual P2P Supercomputer. In Proc. 7th High-Performance Grid Computing Workshop (HPGC'10), in conjunction with 24th IEEE Internatl. Parallel and Distributed Processing Symposium (IPDPS'10), IEEE, 2010.

Reasonable parameters for constructor:

Constructor & Destructor Documentation

NetworKit::PubWebGenerator::PubWebGenerator ( )
inline
NetworKit::PubWebGenerator::PubWebGenerator ( count  numNodes,
count  numberOfDenseAreas,
float  neighborhoodRadius,
count  maxNumberOfNeighbors 
)

Member Function Documentation

void NetworKit::PubWebGenerator::addNode ( Graph g)
protected

Adds nodes randomly, distribution respects original one.

void NetworKit::PubWebGenerator::addNodesToArea ( index  area,
count  num,
Graph g 
)
protected
void NetworKit::PubWebGenerator::chooseClusterSizes ( )
protected
void NetworKit::PubWebGenerator::chooseDenseAreaSizes ( )
protected
void NetworKit::PubWebGenerator::determineNeighbors ( Graph g)
protected
void NetworKit::PubWebGenerator::fillDenseAreas ( Graph g)
protected
Graph NetworKit::PubWebGenerator::generate ( )
virtual
bool NetworKit::PubWebGenerator::isValidEdge ( Graph g,
node  u,
node  v,
edgeweight ew 
)
protected
void NetworKit::PubWebGenerator::moveNodeIntoUnitSquare ( float &  x,
float &  y 
)
protected
void NetworKit::PubWebGenerator::removeRandomNode ( Graph g)
protected

Removes random node, uniform distribution.

void NetworKit::PubWebGenerator::spreadRemainingNodes ( Graph g)
protected
float NetworKit::PubWebGenerator::squaredDistanceInUnitTorus ( float  x1,
float  y1,
float  x2,
float  y2 
)
protected

Friends And Related Function Documentation

friend class DynamicPubWebGenerator
friend

Member Data Documentation

std::vector<circle> NetworKit::PubWebGenerator::denseAreaXYR
protected

position of each circular dense area

count NetworKit::PubWebGenerator::maxNeigh
protected

maximum number of neighbors

count NetworKit::PubWebGenerator::n
protected

number of nodes

float NetworKit::PubWebGenerator::neighRad
protected

neighborhood radius

count NetworKit::PubWebGenerator::numDenseAreas
protected

number of areas with more nodes (denser)

std::vector<count> NetworKit::PubWebGenerator::numPerArea
protected

number of points in each circular area


The documentation for this class was generated from the following files: