Template Class LocalCommunity¶

Nested Relationships¶

Class Documentation¶

template<bool ShellMaintainsExtDeg, bool MaintainBoundary = false, bool AllowRemoval = false>
class LocalCommunity¶

Class for maintaining some measures for a local community while expanding it.

Depending on the template parameters, different values are maintained. By default, it stores the shell of the community (i.e., all external neighbors) and the volume and cut of the community. Further, for every node in the shell, the number of internal neighbors is maintained. Optionally, also the number of external neighbors can be maintained for every node in the shell (ShellMaintainsExtDeg). Additionally, also the boundary, i.e., all nodes in the community that have a neighbor in the shell are maintained (MaintainBoundary).

Public Functions

LocalCommunity(const Graph &G)¶

Initialize an empty community for the given graph.

Parameters:

G – The graph.

void addNode(node u)¶

Add the given node to the community.

This needs O(deg(u)) time in expectation. If the boundary is maintained, the complexity can be higher but this is amortized if nodes are only added to the community.

Parameters:

u – The node to add.

void removeNode(node u)¶

Removes the given node form the community

This needs O(deg(u)) time in expectation. If the boundary is maintained, the complexity can be higher but this is amortized if nodes are only added to the community.

Parameters:

u – The node to add.

bool contains(node u) const¶

Check if a given node u is in the community.

Parameters:

u – The node to check.

Returns:

If u is in the community.

std::set<node> toSet() const¶

Return the community as a std::set<node>.

Returns:

The community as std::set<node>

template<typename F>
inline void forShellNodes(F callback)¶

Execute a callback for every node in the shell.

The complexity is linear in the size of the shell. The callback should accept a node and a ShellInfo object as parameters. Note that only the enabled properties of the ShellInfo object may be accessed.

Parameters:

callback – The callback to call.

template<typename F>
inline void forCommunityNodes(F callback)¶

Execute a callback for every node in the community.

The complexity is linear in the size of the community. The callback should accept a node and a CommunityInfo object as parameters. Note that only the enabled properties of the CommunityInfo object may be accessed.

Note that unless AllowRemoval is set, the CommunityInfo object is empty.

Parameters:

callback – The callback to call.

inline size_t size() const¶

Get the size of the community.

Returns:

The size of the community.

inline double internalEdgeWeight() const¶

Get the internal edge weight. This is the sum of the weights of all internal edges, i.e., the weight of every internal edge is counted once.

Returns:

The internal edge weight of the community.

inline double cut() const¶

Get the cut of the community.

Returns:

The cut of the community.

inline count boundarySize() const¶

Get the size of the boundary of the community.

Returns:

The size of the boundary.

struct CommunityInfo¶

Public Functions

inline int64_t boundaryChange() const¶

Calculate how much the boundary size would change if the node was removed from the community.

inline CommunityInfo()¶

Public Members

OptionalValue<double, AllowRemoval> intDeg¶

Number of neighbors in the community.

OptionalValue<double, ShellMaintainsExtDeg && AllowRemoval> extDeg¶

Number of neighbors outside the community.

OptionalValue<node, MaintainBoundary && AllowRemoval> exclusiveOutsideNeighbor¶

The only neighbor outside the community if there is only one.

OptionalValue<count, MaintainBoundary && AllowRemoval> numFullyInternalNeighbors¶

The number of neighbors that have no internal neighbors.

template<typename ValueType, bool used>
struct OptionalValue¶

Public Functions

inline ValueType &get()¶

inline const ValueType &get() const¶

inline ValueType &operator*()¶

inline const ValueType &operator*() const¶

inline ValueType *operator->()¶

inline const ValueType *operator->() const¶

inline void set(ValueType)¶

inline OptionalValue &operator+=(ValueType)¶

inline OptionalValue &operator-=(ValueType)¶

inline OptionalValue(const ValueType&)¶

inline OptionalValue()¶

template<typename ValueType>
struct OptionalValue<ValueType, true>¶

Public Functions

inline ValueType &get()¶

inline const ValueType &get() const¶

inline ValueType &operator*()¶

inline const ValueType &operator*() const¶

inline ValueType *operator->()¶

inline const ValueType *operator->() const¶

inline void set(ValueType v)¶

template<typename SecondValue, typename std::enable_if<std::is_scalar<SecondValue>::value, int>::type = 0>
inline OptionalValue &operator+=(SecondValue v)¶

template<typename SecondValue, typename std::enable_if<std::is_scalar<SecondValue>::value, int>::type = 0>
inline OptionalValue &operator-=(SecondValue v)¶

inline OptionalValue(const ValueType &v)¶

inline OptionalValue()¶

Public Members

ValueType value¶

struct ShellInfo¶

Public Functions

inline int64_t boundaryChange() const¶

Calculate how much the boundary size would change if the node was added to the community.

inline ShellInfo()¶

Public Members

OptionalValue<double, true> intDeg¶

Number of neighbors in the community.

OptionalValue<double, ShellMaintainsExtDeg> extDeg¶

Number of neighbors outside the community.

OptionalValue<count, MaintainBoundary> numExclusiveBoundaryMembers¶

Number of nodes in the boundary whose only outside neighbor is this node.