petgraph::algo::matching

Function greedy_matching

Source 
pub fn greedy_matching<G>(graph: G) -> Matching<G>
where
    G: Visitable + IntoNodeIdentifiers + NodeIndexable + IntoNeighbors,
    G::NodeId: Eq + Hash,
    G::EdgeId: Eq + Hash,
Expand description

[Generic] Compute a matching using a greedy heuristic.

The input graph is treated as if undirected. The underlying heuristic is unspecified, but is guaranteed to be bounded by O(|V| + |E|). No guarantees about the output are given other than that it is a valid matching.

If you require a maximum matching, use maximum_matching function instead.

§Arguments

  • graph: an undirected graph.

§Returns

  • Matching calculated using greedy heuristic.

§Complexity

  • Time complexity: O(|V| + |E|).
  • Auxiliary space: O(|V|).

where |V| is the number of nodes and |E| is the number of edges.