< Summary

Class:Itinero.Profiles.EdgeTypesMap.ProfileEdgeTypeSetMinimizer
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Profiles/EdgeTypesMap/ProfilesEdgeTypeSetMinimizer.cs
Covered lines:0
Uncovered lines:96
Coverable lines:96
Total lines:169
Line coverage:0% (0 of 96)
Covered branches:0
Total branches:26
Branch coverage:0% (0 of 26)
Tag:224_14471318300

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)0%20%
MinimizeAttributes(...)0%140%
AddImportance(...)0%40%
AddNotImportant(...)0%20%
ImportanceOf(...)0%20%
GetEdgeFactorHash(...)0%20%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Profiles/EdgeTypesMap/ProfilesEdgeTypeSetMinimizer.cs

#LineLine coverage
 1using System.Collections.Generic;
 2using System.Linq;
 3using Itinero.Network.Attributes;
 4
 5namespace Itinero.Profiles.EdgeTypesMap;
 6
 7internal class ProfileEdgeTypeSetMinimizer
 8{
 09    private readonly LruCache<long, (IEnumerable<(string key, string value)> attributes, long edgeFactorHash)>
 010        _cache = new(100000);
 011    private readonly Dictionary<string, int> _probablyImportant = new();
 12    private readonly IReadOnlyCollection<Profile> _profiles;
 13
 014    public ProfileEdgeTypeSetMinimizer(IReadOnlyCollection<Profile> profiles,
 015        params string[] defaultKeys)
 016    {
 017        _profiles = profiles;
 018        for (var i = 0; i < defaultKeys.Length; i++)
 019        {
 020            var key = defaultKeys[i];
 021            _probablyImportant[key] = 1 + defaultKeys.Length - i;
 022        }
 023    }
 24
 25    /// <summary>
 26    ///     Calculates the smallest attribute set which gives equivalent routing properties for the given profile.
 27    ///     It'll try to remove as much attributes as possible, while keeping the same speeds and factors.
 28    ///     Thus:
 29    ///     <code>
 30    /// var attributes = ...
 31    /// var edgeFactors = profiles.Select(profile => profile.Factor(attributes));
 32    /// var pruned =  new AttributeSetMinimizer(profiles).MinimizeAttributes(attributes);
 33    /// var edgeFactorsPruned = profiles.Select(profile => profile.Factor(pruned));
 34    /// Assert.Equals(edgeFactors, edgeFactorsPruned);
 35    /// </code>
 36    /// </summary>
 37    /// <param name="attributes">The attributes to pruned</param>
 38    /// <returns>A pruned set of attributes</returns>
 39    public IEnumerable<(string key, string value)> MinimizeAttributes(
 40        IEnumerable<(string key, string value)> attributes)
 041    {
 042        if (attributes.Count() <= 1)
 043        {
 44            // Nothing to cull here
 045            return attributes;
 46        }
 47
 048        var attributesHash = attributes.GetHash();
 049        if (_cache.TryGet(attributesHash, out var prunedSet))
 050        {
 51            // The current attributes are already known!
 52            // We simply return the cached set
 053            return prunedSet.attributes;
 54        }
 55
 56        // The hash of the factors for the profiles over the full attributes
 57        // The hash of the factors for the _pruned_ attributes must be the same in the end!
 058        var targetHash = this.GetEdgeFactorHash(attributes);
 59
 60        // We make a ranking of what keys are probably important
 061        var importantKeys =
 062            attributes.Select(attr => (attr.key, this.ImportanceOf(attr.key)))
 063                .OrderByDescending(attr => attr.Item2);
 64
 65        // The pruned attributes
 066        HashSet<(string key, string value)> pruned = new();
 067        long prunedAttributesHash = 0;
 068        long lastFactorHash = 0;
 69
 70        // We add the important keys one by one, until we have the same hash
 071        foreach (var (importantKey, _) in importantKeys)
 072        {
 073            attributes.TryGetValue(importantKey, out var value);
 74
 075            pruned.Add((importantKey, value));
 076            prunedAttributesHash = (importantKey, value).GetDiffHash(prunedAttributesHash);
 77
 078            if (_cache.TryGet(prunedAttributesHash, out var fromCache))
 079            {
 080                lastFactorHash = fromCache.edgeFactorHash;
 81                // We've already seen this hash! Lets inspect the previously calculated values...
 082                if (fromCache.edgeFactorHash == targetHash)
 083                {
 84                    // Hooray! We have found the correct value without doing a thing
 085                    this.AddImportance(fromCache.attributes);
 086                    return fromCache.attributes;
 87                }
 088            }
 89            else
 090            {
 091                long currentFactorHash = this.GetEdgeFactorHash(pruned);
 092                _cache.Add(prunedAttributesHash,
 093                    (new HashSet<(string key, string value)>(pruned), currentFactorHash));
 094                if (currentFactorHash == targetHash)
 095                {
 96                    // We have found our smaller configuration!
 097                    this.AddImportance(pruned);
 098                    return pruned;
 99                }
 100
 0101                if (lastFactorHash == currentFactorHash)
 0102                {
 103                    // Hmm, this last key didn't change anything... We negatively affect this value in order to prevent 
 0104                    this.AddNotImportant(importantKey);
 0105                }
 106
 0107                lastFactorHash = currentFactorHash;
 0108            }
 0109        }
 110
 111        // Normally, we don't reach this point
 0112        return pruned;
 0113    }
 114
 115    private void AddImportance(IEnumerable<(string key, string value)> attributes)
 0116    {
 0117        var usedKeys = new HashSet<string>();
 0118        foreach (var (key, _) in attributes)
 0119        {
 0120            usedKeys.Add(key);
 0121            if (!_probablyImportant.ContainsKey(key))
 0122            {
 0123                _probablyImportant[key] = 1;
 0124            }
 125            else
 0126            {
 0127                _probablyImportant[key]++;
 0128            }
 0129        }
 0130    }
 131
 132    private void AddNotImportant(string key)
 0133    {
 0134        if (!_probablyImportant.ContainsKey(key))
 0135        {
 0136            _probablyImportant[key] = -1;
 0137        }
 138        else
 0139        {
 0140            _probablyImportant[key]--;
 0141        }
 0142    }
 143
 144    private int ImportanceOf(string key)
 0145    {
 0146        if (_probablyImportant.TryGetValue(key, out var v))
 0147        {
 0148            return v;
 149        }
 150
 0151        return 0;
 0152    }
 153
 154    /// <summary>
 155    ///     Calculates, for every profile, the respective factor and hashes them together
 156    /// </summary>
 157    private int GetEdgeFactorHash(IEnumerable<(string key, string value)> attributes)
 0158    {
 0159        var hash = 13.GetHashCode();
 160
 0161        foreach (var profile in _profiles)
 0162        {
 0163            var factor = profile.Factor(attributes);
 0164            hash ^= factor.GetHashCode();
 0165        }
 166
 0167        return hash;
 0168    }
 169}
Generated by: ReportGenerator 4.8.2.0
04/15/2025 - 13:59:49
GitHub | www.palmmedia.de

Methods/Properties

.ctor(...)
MinimizeAttributes(...)
AddImportance(...)
AddNotImportant(...)
ImportanceOf(...)
GetEdgeFactorHash(...)