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

#include <Matching.h>

Public Member Functions

 Matching (count z=0)
 Construct new Matching. More...
 
void match (node u, node v)
 Set two nodes u and v as each others matching partners. More...
 
void unmatch (node u, node v)
 Reset the two nodes u and v to unmatched. More...
 
bool isMatched (node u) const
 Check if node is matched. More...
 
bool areMatched (node u, node v) const
 Check if the two nodes u and v are matched together. More...
 
bool isProper (const Graph &G) const
 Check whether this is a proper matching in the graph, i.e. More...
 
count size (const Graph &G) const
 Get the number of edges in this matching. More...
 
index mate (node v) const
 Get the matched neighbor of v if it exists, otherwise none. More...
 
edgeweight weight (const Graph &G) const
 Get total weight of edges in this matching. More...
 
Partition toPartition (const Graph &G) const
 Convert matching to a Partition object where matched nodes belong to the same subset and unmatched nodes belong to a singleton subset. More...
 
std::vector< nodegetVector () const
 Get the actual vector storing the data. More...
 

Protected Attributes

std::vector< nodedata
 storage of matching nodes More...
 

Constructor & Destructor Documentation

NetworKit::Matching::Matching ( count  z = 0)

Construct new Matching.

Parameters
[in]zMaximum number of nodes.

Member Function Documentation

bool NetworKit::Matching::areMatched ( node  u,
node  v 
) const

Check if the two nodes u and v are matched together.

Parameters
[in]unode.
[in]vnode.
std::vector< node > NetworKit::Matching::getVector ( ) const

Get the actual vector storing the data.

Returns
vector
bool NetworKit::Matching::isMatched ( node  u) const

Check if node is matched.

Parameters
[in]unode.
Returns
true if u is matched.
bool NetworKit::Matching::isProper ( const Graph G) const

Check whether this is a proper matching in the graph, i.e.

no two matched edges are adjacent.

[in] G A graph.

Parameters
[out]@ctrue if this is a proper matching.

The content of this data structure represents a matching iff (for all v in V: M[v] = v or M[M[v]] = v) and (for all (u,v) in M): (u,v) in E

void NetworKit::Matching::match ( node  u,
node  v 
)

Set two nodes u and v as each others matching partners.

Parameters
[in]unode.
[in]vnode.
index NetworKit::Matching::mate ( node  v) const

Get the matched neighbor of v if it exists, otherwise none.

Parameters
[in]vnode.
Returns
Mate of v if it exists, otherwise none.
count NetworKit::Matching::size ( const Graph G) const

Get the number of edges in this matching.

Returns
Number of edges in matching.
Partition NetworKit::Matching::toPartition ( const Graph G) const

Convert matching to a Partition object where matched nodes belong to the same subset and unmatched nodes belong to a singleton subset.

Returns
Partition
void NetworKit::Matching::unmatch ( node  u,
node  v 
)

Reset the two nodes u and v to unmatched.

Parameters
[in]unode.
[in]vnode.
edgeweight NetworKit::Matching::weight ( const Graph G) const

Get total weight of edges in this matching.

Parameters
[in]gThe corresponding graph.
Returns
Total weight of edges in this matching.

Member Data Documentation

std::vector<node> NetworKit::Matching::data
protected

storage of matching nodes


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