souffle::ram::analysis::MaxMatching Class Reference

#include <Index.h>

Inheritance diagram for souffle::ram::analysis::MaxMatching:

Collaboration diagram for souffle::ram::analysis::MaxMatching:

Public Types
using	Distance = int
using	Matchings = std::unordered_map< Node, Node >
	Matching represent a solution of the matching, i.e., which node in the bi-partite graph maps to another node. More...
using	Node = uint32_t
using	Nodes = std::unordered_set< Node >

Public Member Functions
void	addEdge (Node u, Node v)
	@Brief add an edge to the bi-partite graph More...
int	getNumMatchings () const
	@Brief get number of matches in the solution More...
const Matchings &	solve ()
	@Brief solve the maximum matching problem More...

Data Fields
const Distance	InfiniteDistance = -1
const Node	NullVertex = 0

Protected Member Functions
bool	bfSearch ()
	@Brief perform a breadth first search in the graph More...
bool	dfSearch (Node u)
	@Brief perform a depth first search in the graph More...
Distance	getDistance (Node v)
	@Brief get distance of a node More...
Node	getMatch (Node v)
	@Brief get match for a search signature More...

Private Types
using	DistanceMap = std::map< Node, Distance >
	distance function of nodes More...
using	Edges = std::unordered_set< Node >
	Edges in the bi-partite graph. More...
using	Graph = std::unordered_map< Node, Edges >
	Bi-partite graph of instance. More...

Private Attributes
DistanceMap	distance
Graph	graph
Matchings	match

Detailed Description

@Brief Computes a maximum matching with Hopcroft-Karp algorithm

This class is a helper class for RamIndex.

This implements a standard maximum matching algorithm for a bi-partite graph also known as a marriage problem. Given a set of edges in a bi-partite graph select a subset of edges that each node in the bi-partite graph has at most one adjacent edge associated with.

The nodes of the bi-partite graph represent index-signatures stemming from RAM operations and RAM existence checks for a relation. A relation between two nodes represent whether an index operation subsumes another operation.

Source: http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm#Pseudocode

Definition at line 112 of file Index.h.

Member Typedef Documentation

Distance

using souffle::ram::analysis::MaxMatching::Distance = int

Definition at line 118 of file Index.h.

DistanceMap

using souffle::ram::analysis::MaxMatching::DistanceMap = std::map<Node, Distance>

private

distance function of nodes

Definition at line 188 of file Index.h.

Edges

using souffle::ram::analysis::MaxMatching::Edges = std::unordered_set<Node>

private

Edges in the bi-partite graph.

Definition at line 180 of file Index.h.

Graph

using souffle::ram::analysis::MaxMatching::Graph = std::unordered_map<Node, Edges>

private

Bi-partite graph of instance.

Definition at line 184 of file Index.h.

Matchings

using souffle::ram::analysis::MaxMatching::Matchings = std::unordered_map<Node, Node>

Matching represent a solution of the matching, i.e., which node in the bi-partite graph maps to another node.

If no map exist for a node, there is no adjacent edge exists for that node.

Definition at line 124 of file Index.h.

Node

using souffle::ram::analysis::MaxMatching::Node = uint32_t

Definition at line 114 of file Index.h.

Nodes

using souffle::ram::analysis::MaxMatching::Nodes = std::unordered_set<Node>

Definition at line 116 of file Index.h.

Member Function Documentation

addEdge()

void souffle::ram::analysis::MaxMatching::addEdge	(	Node	u,
		Node	v
	)

@Brief add an edge to the bi-partite graph

Parameters

u	search signature
v	subsuming search signature

Definition at line 170 of file Index.cpp.

           {
        graph[u].insert(v);
    }
}
 
MaxMatching::Node MaxMatching::getMatch(Node v) {
    auto it = match.find(v);
    if (it == match.end()) {
        return NullVertex;
    }

bfSearch()

bool souffle::ram::analysis::MaxMatching::bfSearch ( )

protected

@Brief perform a breadth first search in the graph

Definition at line 197 of file Index.cpp.

               {
            distance[it.first] = InfiniteDistance;
        }
    }
 
    distance[NullVertex] = InfiniteDistance;
    while (!bfQueue.empty()) {
        u = bfQueue.front();
        bfQueue.pop();
        assert(u != NullVertex);
        const Edges& children = graph[u];
        for (auto it : children) {
            Node mv = getMatch(it);
            if (getDistance(mv) == InfiniteDistance) {
                distance[mv] = getDistance(u) + 1;
                if (mv != NullVertex) {
                    bfQueue.push(mv);
                }
            }
        }
    }
    return (getDistance(NullVertex) != InfiniteDistance);
}
 
bool MaxMatching::dfSearch(Node u) {
    if (u != 0) {
        Edges& children = graph[u];
        for (auto v : children) {
            if (getDistance(getMatch(v)) == getDistance(u) + 1) {

dfSearch()

bool souffle::ram::analysis::MaxMatching::dfSearch ( Node  u )

protected

@Brief perform a depth first search in the graph

Parameters

u	search signature

Definition at line 229 of file Index.cpp.

                                               {
    while (bfSearch()) {
        std::vector<Node> keys(graph.size());
        for (auto& it : graph) {
            keys.push_back(it.first);

Referenced by solve().

getDistance()

MaxMatching::Distance souffle::ram::analysis::MaxMatching::getDistance ( Node  v )

protected

@Brief get distance of a node

Definition at line 189 of file Index.cpp.

                           {
    Node u;
    std::queue<Node> bfQueue;
    // Build layers
    for (auto& it : graph) {

getMatch()

MaxMatching::Node souffle::ram::analysis::MaxMatching::getMatch ( Node  v )

protected

@Brief get match for a search signature

Parameters

v	search signature

Definition at line 181 of file Index.cpp.

                                                   {
    auto it = distance.find(v);
    if (it == distance.end()) {
        return InfiniteDistance;
    }

Referenced by solve().

getNumMatchings()

int souffle::ram::analysis::MaxMatching::getNumMatchings ( ) const

inline

@Brief get number of matches in the solution

Returns

number of matches

Definition at line 142 of file Index.h.

                                {
        return match.size() / 2;
    }

References match.

solve()

const MaxMatching::Matchings & souffle::ram::analysis::MaxMatching::solve

(

)

@Brief solve the maximum matching problem

Returns

returns the matching

Definition at line 248 of file Index.cpp.

                       : keys) {
            if (getMatch(node) == NullVertex) {
                dfSearch(node);
            }
        }
    }
    return match;
}
 
void MinIndexSelection::solve() {
    // map the keys in the key set to lexicographical order
    if (searches.empty()) {
        return;
    }

References dfSearch(), getMatch(), and NullVertex.

Here is the call graph for this function:

Field Documentation

distance

DistanceMap souffle::ram::analysis::MaxMatching::distance

private

Definition at line 192 of file Index.h.

graph

Graph souffle::ram::analysis::MaxMatching::graph

private

Definition at line 191 of file Index.h.

InfiniteDistance

const Distance souffle::ram::analysis::MaxMatching::InfiniteDistance = -1

Definition at line 130 of file Index.h.

match

Matchings souffle::ram::analysis::MaxMatching::match

private

Definition at line 190 of file Index.h.

Referenced by getNumMatchings().

NullVertex

const Node souffle::ram::analysis::MaxMatching::NullVertex = 0

Definition at line 127 of file Index.h.

Referenced by solve().

---

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

• ram/analysis/Index.h
• ram/analysis/Index.cpp