#include <NodeIDAllocator.h>

Static Public Member Functions
static std::vector< NodeID >	cluster (BVDataPTAImpl *pta, const std::vector< std::pair< NodeID, unsigned > > keys, std::vector< std::pair< hclust_fast_methods, std::vector< NodeID > > > &candidates, std::string evalSubtitle="")

static std::vector< NodeID >	getReverseNodeMapping (const std::vector< NodeID > &nodeMapping)

static void	evaluate (const std::vector< NodeID > &nodeMap, const Map< PointsTo, unsigned > pointsToSets, Map< std::string, std::string > &stats, bool accountForOcc)
	Fills in *NumWords statistics in stats..

static void	printStats (std::string title, Map< std::string, std::string > &stats)

Private Types
typedef Map< NodePair, std::pair< unsigned, unsigned > >	DistOccMap

Static Private Member Functions
static size_t	condensedIndex (size_t n, size_t i, size_t j)

static unsigned	requiredBits (const PointsTo &pts)
	Returns the minimum number of bits required to represent pts in a perfect world.

static unsigned	requiredBits (const size_t n)
	Returns the minimum number of bits required to represent n items in a perfect world.

static double *	getDistanceMatrix (const std::vector< std::pair< const PointsTo *, unsigned > > pointsToSets, const size_t numObjects, const Map< NodeID, unsigned > &nodeMap, double &distanceMatrixTime)

static void	traverseDendrogram (std::vector< NodeID > &nodeMap, const int *dendrogram, const size_t numObjects, unsigned &allocCounter, Set< int > &visited, const int index, const std::vector< NodeID > &regionNodeMap)

static std::vector< unsigned >	regionObjects (const Map< NodeID, Set< NodeID > > &graph, size_t numObjects, size_t &numLabels)

static std::pair< hclust_fast_methods, std::vector< NodeID > >	determineBestMapping (const std::vector< std::pair< hclust_fast_methods, std::vector< NodeID > > > &candidates, Map< PointsTo, unsigned > pointsToSets, const std::string &evalSubtitle, double &evalTime)

Static Private Attributes

static const std::string	NumObjects = "NumObjects"

static const std::string	RegioningTime = "RegioningTime"

static const std::string	DistanceMatrixTime = "DistanceMatrixTime"

static const std::string	FastClusterTime = "FastClusterTime"

static const std::string	DendrogramTraversalTime = "DendrogramTravTime"

static const std::string	EvalTime = "EvalTime"

static const std::string	TotalTime = "TotalTime"

static const std::string	TheoreticalNumWords = "TheoreticalWords"

static const std::string	OriginalBvNumWords = "OriginalBvWords"

static const std::string	OriginalSbvNumWords = "OriginalSbvWords"

static const std::string	NewBvNumWords = "NewBvWords"

static const std::string	NewSbvNumWords = "NewSbvWords"

static const std::string	NumRegions = "NumRegions"

static const std::string	NumGtIntRegions = "NumGtIntRegions"

static const std::string	LargestRegion = "LargestRegion"

static const std::string	BestCandidate = "BestCandidate"

static const std::string	NumNonTrivialRegionObjects = "NumNonTrivObj"

Detailed Description

Perform clustering given points-to sets with nodes allocated according to the DENSE strategy.

Definition at line 117 of file NodeIDAllocator.h.

Member Typedef Documentation

◆ DistOccMap

typedef Map<NodePair, std::pair<unsigned, unsigned> > SVF::NodeIDAllocator::Clusterer::DistOccMap

private

Maps a pair of nodes to their (minimum) distance and the number of times that distance occurs in a set of unique points-to sets.

Definition at line 122 of file NodeIDAllocator.h.

Member Function Documentation

◆ cluster()

std::vector< NodeID > SVF::NodeIDAllocator::Clusterer::cluster	(	BVDataPTAImpl *	pta,
		const std::vector< std::pair< NodeID, unsigned > >	keys,
		std::vector< std::pair< hclust_fast_methods, std::vector< NodeID > > > &	candidates,
		std::string	evalSubtitle = `""`
	)

static

Returns vector mapping previously allocated node IDs to a smarter allocation based on the points-to sets in pta accessed through keys. The second part of the keys pairs are the number of (potential) occurrences of that points-to set or a subset, depending on the client's wish. TODO: interfaces are getting unwieldy, an initialised object may be better. TODO: kind of sucks pta can't be const here because getPts isn't.

Definition at line 187 of file NodeIDAllocator.cpp.

{
    assert(pta != nullptr && "Clusterer::cluster: given null BVDataPTAImpl");
    assert(Options::NodeAllocStrat() == Strategy::DENSE && "Clusterer::cluster: only dense allocation clustering currently supported");
 
    Map<std::string, std::string> overallStats;
    double fastClusterTime = 0.0;
    double distanceMatrixTime = 0.0;
    double dendrogramTraversalTime = 0.0;
    double regioningTime = 0.0;
    double evalTime = 0.0;
 
    // Pair of nodes to their (minimum) distance and the number of occurrences of that distance.
    Map<std::pair<NodeID, NodeID>, std::pair<unsigned, unsigned>> distances;
 
    double clkStart = PTAStat::getClk(true);
 
    // Map points-to sets to occurrences.
    Map<PointsTo, unsigned> pointsToSets;
 
    // Objects each object shares at least a points-to set with.
    Map<NodeID, Set<NodeID>> coPointeeGraph;
    for (const std::pair<NodeID, unsigned> &keyOcc : keys)
    {
        const PointsTo &pts = pta->getPts(keyOcc.first);
        const size_t oldSize = pointsToSets.size();
        pointsToSets[pts] += keyOcc.second;;
 
        // Edges in this graph have no weight or uniqueness, so we only need to
        // do this for each points-to set once.
        if (oldSize != pointsToSets.size())
        {
            NodeID firstO = !pts.empty() ? *(pts.begin()) : 0;
            Set<NodeID> &firstOsNeighbours = coPointeeGraph[firstO];
            for (const NodeID o : pts)
            {
                if (o != firstO)
                {
                    firstOsNeighbours.insert(o);
                    coPointeeGraph[o].insert(firstO);
                }
            }
        }
    }
 
    size_t numObjects = NodeIDAllocator::get()->numObjects;
    overallStats[NumObjects] = std::to_string(numObjects);
 
    size_t numRegions = 0;
    std::vector<unsigned> objectsRegion;
    if (Options::RegionedClustering())
    {
        objectsRegion = regionObjects(coPointeeGraph, numObjects, numRegions);
    }
    else
    {
        // Just a single big region (0).
        objectsRegion.insert(objectsRegion.end(), numObjects, 0);
        numRegions = 1;
    }
 
    // Set needs to be ordered because getDistanceMatrix, in its n^2 iteration, expects
    // sets to be ordered (we are building a condensed matrix, not a full matrix, so it
    // matters). In getDistanceMatrix, doing regionReverseMapping for oi and oj, where
    // oi < oj, and getting a result moi > moj gives incorrect results.
    // In the condensed matrix, [b][a] where b >= a, is incorrect.
    std::vector<OrderedSet<NodeID>> regionsObjects(numRegions);
    for (NodeID o = 0; o < numObjects; ++o) regionsObjects[objectsRegion[o]].insert(o);
 
    // Size of the return node mapping. It is potentially larger than the number of
    // objects because we align each region to NATIVE_INT_SIZE.
    // size_t numMappings = 0;
 
    // Maps a region to a mapping which maps 0 to n to all objects
    // in that region.
    std::vector<std::vector<NodeID>> regionMappings(numRegions);
    // The reverse: region to mapping of objects to a 0 to n from above.
    std::vector<Map<NodeID, unsigned>> regionReverseMappings(numRegions);
    // We can thus use 0 to n for each region to create smaller distance matrices.
    for (unsigned region = 0; region < numRegions; ++region)
    {
        size_t curr = 0;
        // With the OrderedSet above, o1 < o2 => map[o1] < map[o2].
        for (NodeID o : regionsObjects[region])
        {
            // push_back here is just like p...[region][curr] = o.
            regionMappings[region].push_back(o);
            regionReverseMappings[region][o] = curr++;
        }
 
        // curr is the number of objects. A region with no objects makes no sense.
        assert(curr != 0);
 
        // Number of bits needed for this region if we were
        // to start assigning from 0 rounded up to the fewest needed
        // native ints. This is added to the number of mappings since
        // we align each region to a native int.
        // numMappings += requiredBits(regionsObjects[region].size());
    }
 
    // Points-to sets which are relevant to a region, i.e., those whose elements
    // belong to that region. Pair is for occurrences.
    std::vector<std::vector<std::pair<const PointsTo *, unsigned>>> regionsPointsTos(numRegions);
    for (const Map<PointsTo, unsigned>::value_type &ptocc : pointsToSets)
    {
        const PointsTo &pt = ptocc.first;
        const unsigned occ = ptocc.second;
        if (pt.empty()) continue;
        // Guaranteed that begin() != end() because of the continue above. All objects in pt
        // will be relevant to the same region.
        unsigned region = objectsRegion[*(pt.begin())];
        // In our "graph", objects in the same points-to set have an edge between them,
        // so they are all in the same connected component/region.
        regionsPointsTos[region].push_back(std::make_pair(&pt, occ));
    }
 
    double clkEnd = PTAStat::getClk(true);
    regioningTime = (clkEnd - clkStart) / TIMEINTERVAL;
    overallStats[RegioningTime] = std::to_string(regioningTime);
    overallStats[NumRegions] = std::to_string(numRegions);
 
    std::vector<hclust_fast_methods> methods;
    if ((enum hclust_fast_methods)Options::ClusterMethod() == HCLUST_METHOD_SVF_BEST)
    {
        methods.push_back(HCLUST_METHOD_SINGLE);
        methods.push_back(HCLUST_METHOD_COMPLETE);
        methods.push_back(HCLUST_METHOD_AVERAGE);
    }
    else
    {
        methods.push_back((enum hclust_fast_methods)Options::ClusterMethod());
    }
 
    for (const hclust_fast_methods method : methods)
    {
        std::vector<NodeID> nodeMap(numObjects, UINT_MAX);
 
        unsigned numGtIntRegions = 0;
        unsigned largestRegion = 0;
        unsigned nonTrivialRegionObjects = 0;
        unsigned allocCounter = 0;
        for (unsigned region = 0; region < numRegions; ++region)
        {
            const size_t regionNumObjects = regionsObjects[region].size();
            // Round up to next Word: ceiling of current allocation to get how
            // many words and multiply to get the number of bits; if we're aligning.
            if (Options::RegionAlign())
            {
                allocCounter =
                    ((allocCounter + NATIVE_INT_SIZE - 1) / NATIVE_INT_SIZE) * NATIVE_INT_SIZE;
            }
 
            if (regionNumObjects > largestRegion) largestRegion = regionNumObjects;
 
            // For regions with fewer than 64 objects, we can just allocate them
            // however as they will be in the one int regardless..
            if (regionNumObjects < NATIVE_INT_SIZE)
            {
                for (NodeID o : regionsObjects[region]) nodeMap[o] = allocCounter++;
                continue;
            }
 
            ++numGtIntRegions;
            nonTrivialRegionObjects += regionNumObjects;
 
            double *distMatrix = getDistanceMatrix(regionsPointsTos[region], regionNumObjects,
                                                   regionReverseMappings[region], distanceMatrixTime);
 
            clkStart = PTAStat::getClk(true);
            int *dendrogram = new int[2 * (regionNumObjects - 1)];
            double *height = new double[regionNumObjects - 1];
            hclust_fast(regionNumObjects, distMatrix, method, dendrogram, height);
            delete[] distMatrix;
            delete[] height;
            clkEnd = PTAStat::getClk(true);
            fastClusterTime += (clkEnd - clkStart) / TIMEINTERVAL;
 
            clkStart = PTAStat::getClk(true);
            Set<int> visited;
            traverseDendrogram(nodeMap, dendrogram, regionNumObjects, allocCounter,
                               visited, regionNumObjects - 1, regionMappings[region]);
            delete[] dendrogram;
            clkEnd = PTAStat::getClk(true);
            dendrogramTraversalTime += (clkEnd - clkStart) / TIMEINTERVAL;
        }
 
        candidates.push_back(std::make_pair(method, nodeMap));
 
        // Though we "update" these in the loop, they will be the same every iteration.
        overallStats[NumGtIntRegions] = std::to_string(numGtIntRegions);
        overallStats[LargestRegion] = std::to_string(largestRegion);
        overallStats[NumNonTrivialRegionObjects] = std::to_string(nonTrivialRegionObjects);
    }
 
    // Work out which of the mappings we generated looks best.
    std::pair<hclust_fast_methods, std::vector<NodeID>> bestMapping = determineBestMapping(candidates, pointsToSets,
            evalSubtitle, evalTime);
 
    overallStats[DistanceMatrixTime] = std::to_string(distanceMatrixTime);
    overallStats[DendrogramTraversalTime] = std::to_string(dendrogramTraversalTime);
    overallStats[FastClusterTime] = std::to_string(fastClusterTime);
    overallStats[EvalTime] = std::to_string(evalTime);
    overallStats[TotalTime] = std::to_string(distanceMatrixTime + dendrogramTraversalTime + fastClusterTime + regioningTime + evalTime);
 
    overallStats[BestCandidate] = SVFUtil::hclustMethodToString(bestMapping.first);
    printStats(evalSubtitle + ": overall", overallStats);
 
    return bestMapping.second;
}

◆ condensedIndex()

size_t SVF::NodeIDAllocator::Clusterer::condensedIndex	(	size_t	n,
		size_t	i,
		size_t	j
	)

inlinestaticprivate

Returns an index into a condensed matrix (upper triangle, excluding diagonals) corresponding to an nxn matrix.

Definition at line 411 of file NodeIDAllocator.cpp.

{
    // From https://stackoverflow.com/a/14839010
    return n*(n-1)/2 - (n-i)*(n-i-1)/2 + j - i - 1;
}

◆ determineBestMapping()

std::pair< hclust_fast_methods, std::vector< NodeID > > SVF::NodeIDAllocator::Clusterer::determineBestMapping	(	const std::vector< std::pair< hclust_fast_methods, std::vector< NodeID > > > &	candidates,
		Map< PointsTo, unsigned >	pointsToSets,
		const std::string &	evalSubtitle,
		double &	evalTime
	)

inlinestaticprivate

Definition at line 650 of file NodeIDAllocator.cpp.

{
    // In case we're not comparing anything, set to first "candidate".
    std::pair<hclust_fast_methods, std::vector<NodeID>> bestMapping = candidates[0];
    // Number of bits required for the best candidate.
    size_t bestWords = std::numeric_limits<size_t>::max();
    if (evalSubtitle != "" || (enum hclust_fast_methods)Options::ClusterMethod() == HCLUST_METHOD_SVF_BEST)
    {
        for (const std::pair<hclust_fast_methods, std::vector<NodeID>> &candidate : candidates)
        {
            Map<std::string, std::string> candidateStats;
            hclust_fast_methods candidateMethod = candidate.first;
            std::string candidateMethodName = SVFUtil::hclustMethodToString(candidateMethod);
            std::vector<NodeID> candidateMapping = candidate.second;
 
            // TODO: parameterise final arg.
            const double clkStart = PTAStat::getClk(true);
            evaluate(candidateMapping, pointsToSets, candidateStats, true);
            const double clkEnd = PTAStat::getClk(true);
            evalTime += (clkEnd - clkStart) / TIMEINTERVAL;
            printStats(evalSubtitle + ": candidate " + candidateMethodName, candidateStats);
 
            size_t candidateWords = 0;
            if (Options::PtType() == PointsTo::SBV) candidateWords = std::stoull(candidateStats[NewSbvNumWords]);
            else if (Options::PtType() == PointsTo::CBV) candidateWords = std::stoull(candidateStats[NewBvNumWords]);
            else assert(false && "Clusterer::cluster: unsupported BV type for clustering.");
 
            if (candidateWords < bestWords)
            {
                bestWords = candidateWords;
                bestMapping = candidate;
            }
        }
    }
 
    return bestMapping;
}

◆ evaluate()

void SVF::NodeIDAllocator::Clusterer::evaluate	(	const std::vector< NodeID > &	nodeMap,
		const Map< PointsTo, unsigned >	pointsToSets,
		Map< std::string, std::string > &	stats,
		bool	accountForOcc
	)

static

Fills in *NumWords statistics in stats..

Definition at line 572 of file NodeIDAllocator.cpp.

{
    u64_t totalTheoretical = 0;
    u64_t totalOriginalSbv = 0;
    u64_t totalOriginalBv = 0;
    u64_t totalNewSbv = 0;
    u64_t totalNewBv = 0;
 
    for (const Map<PointsTo, unsigned>::value_type &ptsOcc : pointsToSets)
    {
        const PointsTo &pts = ptsOcc.first;
        const unsigned occ = ptsOcc.second;
        if (pts.count() == 0) continue;
 
        u64_t theoretical = requiredBits(pts) / NATIVE_INT_SIZE;
        if (accountForOcc) theoretical *= occ;
 
        // Check number of words for original SBV.
        Set<unsigned> words;
        // TODO: nasty hardcoding.
        for (const NodeID o : pts) words.insert(o / 128);
        u64_t originalSbv = words.size() * 2;
        if (accountForOcc) originalSbv *= occ;
 
        // Check number of words for original BV.
        NodeID min = UINT_MAX;
        NodeID max = 0;
        for (NodeID o : pts)
        {
            if (o < min) min = o;
            if (o > max) max = o;
        }
        words.clear();
        for (NodeID b = min; b <= max; ++b)
        {
            words.insert(b / NATIVE_INT_SIZE);
        }
        u64_t originalBv = words.size();
        if (accountForOcc) originalBv *= occ;
 
        // Check number of words for new SBV.
        words.clear();
        // TODO: nasty hardcoding.
        for (const NodeID o : pts) words.insert(nodeMap[o] / 128);
        u64_t newSbv = words.size() * 2;
        if (accountForOcc) newSbv *= occ;
 
        // Check number of words for new BV.
        min = UINT_MAX;
        max = 0;
        for (const NodeID o : pts)
        {
            const NodeID mappedO = nodeMap[o];
            if (mappedO < min) min = mappedO;
            if (mappedO > max) max = mappedO;
        }
 
        words.clear();
        // No nodeMap[b] because min and max and from nodeMap.
        for (NodeID b = min; b <= max; ++b) words.insert(b / NATIVE_INT_SIZE);
        u64_t newBv = words.size();
        if (accountForOcc) newBv *= occ;
 
        totalTheoretical += theoretical;
        totalOriginalSbv += originalSbv;
        totalOriginalBv += originalBv;
        totalNewSbv += newSbv;
        totalNewBv += newBv;
    }
 
    stats[TheoreticalNumWords] = std::to_string(totalTheoretical);
    stats[OriginalSbvNumWords] = std::to_string(totalOriginalSbv);
    stats[OriginalBvNumWords] = std::to_string(totalOriginalBv);
    stats[NewSbvNumWords] = std::to_string(totalNewSbv);
    stats[NewBvNumWords] = std::to_string(totalNewBv);
}

◆ getDistanceMatrix()

double * SVF::NodeIDAllocator::Clusterer::getDistanceMatrix	(	const std::vector< std::pair< const PointsTo *, unsigned > >	pointsToSets,
		const size_t	numObjects,
		const Map< NodeID, unsigned > &	nodeMap,
		double &	distanceMatrixTime
	)

inlinestaticprivate

Builds the upper triangle of the distance matrix, as an array of length (numObjects * (numObjects - 1)) / 2, as required by fastcluster. Responsibility of caller to delete.

Definition at line 430 of file NodeIDAllocator.cpp.

{
    const double clkStart = PTAStat::getClk(true);
    size_t condensedSize = (numObjects * (numObjects - 1)) / 2;
    double *distMatrix = new double[condensedSize];
    for (size_t i = 0; i < condensedSize; ++i) distMatrix[i] = numObjects * numObjects;
 
    // TODO: maybe use machine epsilon?
    // For reducing distance due to extra occurrences.
    // Can differentiate ~9999 occurrences.
    double occurrenceEpsilon = 0.0001;
 
    for (const std::pair<const PointsTo *, unsigned> &ptsOcc : pointsToSets)
    {
        const PointsTo *pts = ptsOcc.first;
        assert(pts != nullptr);
        const unsigned occ = ptsOcc.second;
 
        // Distance between each element of pts.
        unsigned distance = requiredBits(*pts) / NATIVE_INT_SIZE;
 
        // Use a vector so we can index into pts.
        std::vector<NodeID> ptsVec;
        for (const NodeID o : *pts) ptsVec.push_back(o);
        for (size_t i = 0; i < ptsVec.size(); ++i)
        {
            const NodeID oi = ptsVec[i];
            const Map<NodeID, unsigned>::const_iterator moi = nodeMap.find(oi);
            assert(moi != nodeMap.end());
            for (size_t j = i + 1; j < ptsVec.size(); ++j)
            {
                const NodeID oj = ptsVec[j];
                const Map<NodeID, unsigned>::const_iterator moj = nodeMap.find(oj);
                assert(moj != nodeMap.end());
                double &existingDistance = distMatrix[condensedIndex(numObjects, moi->second, moj->second)];
 
                // Subtract extra occurrenceEpsilon to make upcoming logic simpler.
                // When existingDistance is never whole, it is always between two distances.
                if (distance < existingDistance) existingDistance = distance - occurrenceEpsilon;
 
                if (distance == std::ceil(existingDistance))
                {
                    // We have something like distance == x, existingDistance == x - e, for some e < 1
                    // (potentially even set during this iteration).
                    // So, the new distance is an occurrence the existingDistance being tracked, it just
                    // had some reductions because of multiple occurrences.
                    // If there is not room within this distance to reduce more (increase priority),
                    // just ignore it. TODO: maybe warn?
                    if (existingDistance - occ * occurrenceEpsilon > std::floor(existingDistance))
                    {
                        existingDistance -= occ * occurrenceEpsilon;
                    }
                    else
                    {
                        // Reached minimum.
                        existingDistance = std::floor(existingDistance) + occurrenceEpsilon;
                    }
                }
            }
        }
 
    }
 
    const double clkEnd = PTAStat::getClk(true);
    distanceMatrixTime += (clkEnd - clkStart) / TIMEINTERVAL;
 
    return distMatrix;
}

◆ getReverseNodeMapping()

std::vector< NodeID > SVF::NodeIDAllocator::Clusterer::getReverseNodeMapping ( const std::vector< NodeID > & nodeMapping )

static

Definition at line 397 of file NodeIDAllocator.cpp.

{
    // nodeMapping.size() may not be big enough because we leave some gaps, but it's a start.
    std::vector<NodeID> reverseNodeMapping(nodeMapping.size(), UINT_MAX);
    for (size_t i = 0; i < nodeMapping.size(); ++i)
    {
        const NodeID mapsTo = nodeMapping.at(i);
        if (mapsTo >= reverseNodeMapping.size()) reverseNodeMapping.resize(mapsTo + 1, UINT_MAX);
        reverseNodeMapping.at(mapsTo) = i;
    }
 
    return reverseNodeMapping;
}

◆ printStats()

void SVF::NodeIDAllocator::Clusterer::printStats	(	std::string	title,
		Map< std::string, std::string > &	stats
	)

static

Prints statistics to SVFUtil::outs(). TODO: make stats const.

Definition at line 690 of file NodeIDAllocator.cpp.

{
    // When not in order, it is too hard to compare original/new SBV/BV words, so this array forces an order.
    static const std::string statKeys[] =
    {
        NumObjects, TheoreticalNumWords, OriginalSbvNumWords, OriginalBvNumWords,
        NewSbvNumWords, NewBvNumWords, NumRegions, NumGtIntRegions,
        NumNonTrivialRegionObjects, LargestRegion, RegioningTime,
        DistanceMatrixTime, FastClusterTime, DendrogramTraversalTime,
        EvalTime, TotalTime, BestCandidate
    };
 
    const unsigned fieldWidth = 20;
    SVFUtil::outs().flags(std::ios::left);
    SVFUtil::outs() << "****Clusterer Statistics: " << subtitle << "****\n";
    for (const std::string& statKey : statKeys)
    {
        Map<std::string, std::string>::const_iterator stat = stats.find(statKey);
        if (stat != stats.end())
        {
            SVFUtil::outs() << std::setw(fieldWidth) << statKey << " " << stat->second << "\n";
        }
    }
 
    SVFUtil::outs().flush();
}

◆ regionObjects()

std::vector< NodeID > SVF::NodeIDAllocator::Clusterer::regionObjects	(	const Map< NodeID, Set< NodeID > > &	graph,
		size_t	numObjects,
		size_t &	numLabels
	)

inlinestaticprivate

Returns a vector mapping object IDs to a label such that if two objects appear in the same points-to set, they have the same label. The "appear in the same points-to set" is encoded by graph which is an adjacency list ensuring that x in pt(p) and y in pt(p) -> x is reachable from y.

Definition at line 532 of file NodeIDAllocator.cpp.

{
    unsigned label = UINT_MAX;
    std::vector<NodeID> labels(numObjects, UINT_MAX);
    Set<NodeID> labelled;
    for (const Map<NodeID, Set<NodeID>>::value_type &oos : graph)
    {
        const NodeID o = oos.first;
        if (labels[o] != UINT_MAX) continue;
        std::queue<NodeID> bfsQueue;
        bfsQueue.push(o);
        ++label;
        while (!bfsQueue.empty())
        {
            const NodeID o = bfsQueue.front();
            bfsQueue.pop();
            if (labels[o] != UINT_MAX)
            {
                assert(labels[o] == label);
                continue;
            }
 
            labels[o] = label;
            Map<NodeID, Set<NodeID>>::const_iterator neighboursIt = graph.find(o);
            assert(neighboursIt != graph.end());
            for (const NodeID neighbour : neighboursIt->second) bfsQueue.push(neighbour);
        }
    }
 
    // The remaining objects have no relation with others: they get their own label.
    for (size_t o = 0; o < numObjects; ++o)
    {
        if (labels[o] == UINT_MAX) labels[o] = ++label;
    }
 
    numLabels = label + 1;
 
    return labels;
}

◆ requiredBits() [1/2]

unsigned SVF::NodeIDAllocator::Clusterer::requiredBits ( const PointsTo & pts )

inlinestaticprivate

Returns the minimum number of bits required to represent pts in a perfect world.

Definition at line 417 of file NodeIDAllocator.cpp.

{
    return requiredBits(pts.count());
}

◆ requiredBits() [2/2]

unsigned SVF::NodeIDAllocator::Clusterer::requiredBits ( const size_t n )

inlinestaticprivate

Returns the minimum number of bits required to represent n items in a perfect world.

Definition at line 422 of file NodeIDAllocator.cpp.

{
    if (n == 0) return 0;
    // Ceiling of number of bits amongst each native integer gives needed native ints,
    // so we then multiply again by the number of bits in each native int.
    return ((n - 1) / NATIVE_INT_SIZE + 1) * NATIVE_INT_SIZE;
}

◆ traverseDendrogram()

void SVF::NodeIDAllocator::Clusterer::traverseDendrogram	(	std::vector< NodeID > &	nodeMap,
		const int *	dendrogram,
		const size_t	numObjects,
		unsigned &	allocCounter,
		Set< int > &	visited,
		const int	index,
		const std::vector< NodeID > &	regionNodeMap
	)

inlinestaticprivate

Traverses the dendrogram produced by fastcluster, making node o, where o is the nth leaf (per recursive DFS) map to n. index is the dendrogram node to work off. The traversal should start at the top, which is the "last" (consider that it is 2D) element of the dendrogram, numObjects - 1.

Definition at line 501 of file NodeIDAllocator.cpp.

{
    if (visited.find(index) != visited.end()) return;
    visited.insert(index);
 
    int left = dendrogram[index - 1];
    if (left < 0)
    {
        // Reached a leaf.
        // -1 because the items start from 1 per fastcluster (TODO).
        nodeMap[regionNodeMap[std::abs(left) - 1]] = allocCounter;
        ++allocCounter;
    }
    else
    {
        traverseDendrogram(nodeMap, dendrogram, numObjects, allocCounter, visited, left, regionNodeMap);
    }
 
    // Repeat for the right child.
    int right = dendrogram[(numObjects - 1) + index - 1];
    if (right < 0)
    {
        nodeMap[regionNodeMap[std::abs(right) - 1]] = allocCounter;
        ++allocCounter;
    }
    else
    {
        traverseDendrogram(nodeMap, dendrogram, numObjects, allocCounter, visited, right, regionNodeMap);
    }
}

Member Data Documentation

◆ BestCandidate

const std::string SVF::NodeIDAllocator::Clusterer::BestCandidate = "BestCandidate"

staticprivate

Definition at line 141 of file NodeIDAllocator.h.

◆ DendrogramTraversalTime

const std::string SVF::NodeIDAllocator::Clusterer::DendrogramTraversalTime = "DendrogramTravTime"

staticprivate

Definition at line 130 of file NodeIDAllocator.h.

◆ DistanceMatrixTime

const std::string SVF::NodeIDAllocator::Clusterer::DistanceMatrixTime = "DistanceMatrixTime"

staticprivate

Definition at line 128 of file NodeIDAllocator.h.

◆ EvalTime

const std::string SVF::NodeIDAllocator::Clusterer::EvalTime = "EvalTime"

staticprivate

Definition at line 131 of file NodeIDAllocator.h.

◆ FastClusterTime

const std::string SVF::NodeIDAllocator::Clusterer::FastClusterTime = "FastClusterTime"

staticprivate

Definition at line 129 of file NodeIDAllocator.h.

◆ LargestRegion

const std::string SVF::NodeIDAllocator::Clusterer::LargestRegion = "LargestRegion"

staticprivate

Definition at line 140 of file NodeIDAllocator.h.

◆ NewBvNumWords

const std::string SVF::NodeIDAllocator::Clusterer::NewBvNumWords = "NewBvWords"

staticprivate

Definition at line 136 of file NodeIDAllocator.h.

◆ NewSbvNumWords

const std::string SVF::NodeIDAllocator::Clusterer::NewSbvNumWords = "NewSbvWords"

staticprivate

Definition at line 137 of file NodeIDAllocator.h.

◆ NumGtIntRegions

const std::string SVF::NodeIDAllocator::Clusterer::NumGtIntRegions = "NumGtIntRegions"

staticprivate

Definition at line 139 of file NodeIDAllocator.h.

◆ NumNonTrivialRegionObjects

const std::string SVF::NodeIDAllocator::Clusterer::NumNonTrivialRegionObjects = "NumNonTrivObj"

staticprivate

Definition at line 142 of file NodeIDAllocator.h.

◆ NumObjects

const std::string SVF::NodeIDAllocator::Clusterer::NumObjects = "NumObjects"

staticprivate

Statistics strings.

Definition at line 126 of file NodeIDAllocator.h.

◆ NumRegions

const std::string SVF::NodeIDAllocator::Clusterer::NumRegions = "NumRegions"

staticprivate

Definition at line 138 of file NodeIDAllocator.h.

◆ OriginalBvNumWords

const std::string SVF::NodeIDAllocator::Clusterer::OriginalBvNumWords = "OriginalBvWords"

staticprivate

Definition at line 134 of file NodeIDAllocator.h.

◆ OriginalSbvNumWords

const std::string SVF::NodeIDAllocator::Clusterer::OriginalSbvNumWords = "OriginalSbvWords"

staticprivate

Definition at line 135 of file NodeIDAllocator.h.

◆ RegioningTime

const std::string SVF::NodeIDAllocator::Clusterer::RegioningTime = "RegioningTime"

staticprivate

Definition at line 127 of file NodeIDAllocator.h.

◆ TheoreticalNumWords

const std::string SVF::NodeIDAllocator::Clusterer::TheoreticalNumWords = "TheoreticalWords"

staticprivate

Definition at line 133 of file NodeIDAllocator.h.

◆ TotalTime

const std::string SVF::NodeIDAllocator::Clusterer::TotalTime = "TotalTime"

staticprivate

Definition at line 132 of file NodeIDAllocator.h.

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

/home/runner/work/SVF/SVF/svf/include/Util/NodeIDAllocator.h
/home/runner/work/SVF/SVF/svf/lib/Util/NodeIDAllocator.cpp

Static Public Member Functions

Private Types

Static Private Member Functions

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ DistOccMap

Member Function Documentation

◆ cluster()

◆ condensedIndex()

◆ determineBestMapping()

◆ evaluate()

◆ getDistanceMatrix()

◆ getReverseNodeMapping()

◆ printStats()

◆ regionObjects()

◆ requiredBits() [1/2]

◆ requiredBits() [2/2]

◆ traverseDendrogram()

Member Data Documentation

◆ BestCandidate

◆ DendrogramTraversalTime

◆ DistanceMatrixTime

◆ EvalTime

◆ FastClusterTime

◆ LargestRegion

◆ NewBvNumWords

◆ NewSbvNumWords

◆ NumGtIntRegions

◆ NumNonTrivialRegionObjects

◆ NumObjects

◆ NumRegions

◆ OriginalBvNumWords

◆ OriginalSbvNumWords

◆ RegioningTime

◆ TheoreticalNumWords

◆ TotalTime