Defined in File LocalCommunity.hpp
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
Initialize an empty community for the given graph.
G – The graph.
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.
u – The node to add.
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.
u – The node to add.
Check if a given node u is in the community.
u – The node to check.
If u is in the community.
Return the community as a std::set<node>.
The community as std::set<node>
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.
callback – The callback to call.
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.
callback – The callback to call.
Get the size of the community.
The size of the community.
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.
The internal edge weight of the community.
Get the cut of the community.
The cut of the community.
Public Functions
Calculate how much the boundary size would change if the node was removed from the community.
Public Members
Number of neighbors in the community.
Number of neighbors outside the community.
The only neighbor outside the community if there is only one.
The number of neighbors that have no internal neighbors.
Public Functions
Public Functions
Public Functions
Calculate how much the boundary size would change if the node was added to the community.
Public Members
Number of neighbors in the community.
Number of neighbors outside the community.
Number of nodes in the boundary whose only outside neighbor is this node.