Line data    Source code

       1             : /******************************************************************************
       2             :  *
       3             :  * Project:  GDAL
       4             :  * Purpose:  Implementation of topologic sorting over a directed acyclic graph
       5             :  * Author:   Even Rouault
       6             :  *
       7             :  ******************************************************************************
       8             :  * Copyright (c) 2021, Even Rouault <even dot rouault at spatialys dot com>
       9             :  *
      10             :  * SPDX-License-Identifier: MIT
      11             :  ****************************************************************************/
      12             : 
      13             : #ifndef DIRECTEDACYCLICGRAPH_INCLUDED_H
      14             : #define DIRECTEDACYCLICGRAPH_INCLUDED_H
      15             : 
      16             : #include <algorithm>
      17             : #include <list>
      18             : #include <map>
      19             : #include <set>
      20             : #include <stack>
      21             : #include <string>
      22             : #include <vector>
      23             : 
      24             : #include <cassert>
      25             : 
      26             : namespace gdal
      27             : {
      28             : 
      29             : // See https://en.wikipedia.org/wiki/Directed_acyclic_graph
      30             : template <class T, class V = std::string> class DirectedAcyclicGraph
      31             : {
      32             :     std::set<T> nodes{};
      33             :     std::map<T, std::set<T>>
      34             :         incomingNodes{};  // incomingNodes[j][i] means an edge from i to j
      35             :     std::map<T, std::set<T>>
      36             :         outgoingNodes{};  // outgoingNodes[i][j] means an edge from i to j
      37             :     std::map<T, V> names{};
      38             : 
      39             :   public:
      40        1353 :     DirectedAcyclicGraph() = default;
      41             : 
      42             :     void clear()
      43             :     {
      44             :         nodes.clear();
      45             :         incomingNodes.clear();
      46             :         outgoingNodes.clear();
      47             :         names.clear();
      48             :     }
      49             : 
      50       20117 :     void addNode(const T &i, const V &s)
      51             :     {
      52       20117 :         nodes.insert(i);
      53       20117 :         names[i] = s;
      54       20117 :     }
      55             : 
      56             :     void removeNode(const T &i);
      57             :     const char *addEdge(const T &i, const T &j);
      58             :     const char *removeEdge(const T &i, const T &j);
      59             :     bool isTherePathFromTo(const T &i, const T &j) const;
      60             :     std::vector<T> findStartingNodes() const;
      61             :     std::vector<T> getTopologicalOrdering();
      62             : };
      63             : 
      64             : template <class T, class V>
      65           2 : void DirectedAcyclicGraph<T, V>::removeNode(const T &i)
      66             : {
      67           2 :     nodes.erase(i);
      68           2 :     names.erase(i);
      69             : 
      70             :     {
      71           2 :         auto incomingIter = incomingNodes.find(i);
      72           2 :         if (incomingIter != incomingNodes.end())
      73             :         {
      74           4 :             for (const T &j : incomingIter->second)
      75             :             {
      76           2 :                 auto outgoingIter = outgoingNodes.find(j);
      77           2 :                 assert(outgoingIter != outgoingNodes.end());
      78           2 :                 auto iterJI = outgoingIter->second.find(i);
      79           2 :                 assert(iterJI != outgoingIter->second.end());
      80           2 :                 outgoingIter->second.erase(iterJI);
      81           2 :                 if (outgoingIter->second.empty())
      82           2 :                     outgoingNodes.erase(outgoingIter);
      83             :             }
      84           2 :             incomingNodes.erase(incomingIter);
      85             :         }
      86             :     }
      87             : 
      88             :     {
      89           2 :         auto outgoingIter = outgoingNodes.find(i);
      90           2 :         if (outgoingIter != outgoingNodes.end())
      91             :         {
      92           0 :             for (const T &j : outgoingIter->second)
      93             :             {
      94           0 :                 auto incomingIter = incomingNodes.find(j);
      95           0 :                 assert(incomingIter != incomingNodes.end());
      96           0 :                 auto iterJI = incomingIter->second.find(i);
      97           0 :                 assert(iterJI != incomingIter->second.end());
      98           0 :                 incomingIter->second.erase(iterJI);
      99           0 :                 if (incomingIter->second.empty())
     100           0 :                     incomingNodes.erase(incomingIter);
     101             :             }
     102           0 :             outgoingNodes.erase(outgoingIter);
     103             :         }
     104             :     }
     105           2 : }
     106             : 
     107             : template <class T, class V>
     108       17643 : const char *DirectedAcyclicGraph<T, V>::addEdge(const T &i, const T &j)
     109             : {
     110       17643 :     if (i == j)
     111             :     {
     112           3 :         return "self cycle";
     113             :     }
     114       17640 :     const auto iterI = outgoingNodes.find(i);
     115       34582 :     if (iterI != outgoingNodes.end() &&
     116       34582 :         iterI->second.find(j) != iterI->second.end())
     117             :     {
     118       15342 :         return "already inserted edge";
     119             :     }
     120             : 
     121        2298 :     if (!cpl::contains(nodes, i))
     122             :     {
     123           0 :         return "node i unknown";
     124             :     }
     125        2298 :     if (!cpl::contains(nodes, j))
     126             :     {
     127           0 :         return "node j unknown";
     128             :     }
     129             : 
     130        2298 :     if (isTherePathFromTo(j, i))
     131             :     {
     132        1576 :         return "can't add edge: this would cause a cycle";
     133             :     }
     134             : 
     135         722 :     outgoingNodes[i].insert(j);
     136         722 :     incomingNodes[j].insert(i);
     137         722 :     return nullptr;
     138             : }
     139             : 
     140             : template <class T, class V>
     141         720 : const char *DirectedAcyclicGraph<T, V>::removeEdge(const T &i, const T &j)
     142             : {
     143         720 :     auto iterI = outgoingNodes.find(i);
     144         720 :     if (iterI == outgoingNodes.end())
     145           0 :         return "no outgoing nodes from i";
     146         720 :     auto iterIJ = iterI->second.find(j);
     147         720 :     if (iterIJ == iterI->second.end())
     148           0 :         return "no outgoing node from i to j";
     149         720 :     iterI->second.erase(iterIJ);
     150         720 :     if (iterI->second.empty())
     151         693 :         outgoingNodes.erase(iterI);
     152             : 
     153         720 :     auto iterJ = incomingNodes.find(j);
     154         720 :     assert(iterJ != incomingNodes.end());
     155         720 :     auto iterJI = iterJ->second.find(i);
     156         720 :     assert(iterJI != iterJ->second.end());
     157         720 :     iterJ->second.erase(iterJI);
     158         720 :     if (iterJ->second.empty())
     159         694 :         incomingNodes.erase(iterJ);
     160             : 
     161         720 :     return nullptr;
     162             : }
     163             : 
     164             : template <class T, class V>
     165        2298 : bool DirectedAcyclicGraph<T, V>::isTherePathFromTo(const T &i, const T &j) const
     166             : {
     167        4596 :     std::set<T> plannedForVisit;
     168        4596 :     std::stack<T> toVisit;
     169        2298 :     toVisit.push(i);
     170        2298 :     plannedForVisit.insert(i);
     171        6282 :     while (!toVisit.empty())
     172             :     {
     173        5560 :         const T n = toVisit.top();
     174        5560 :         toVisit.pop();
     175        5560 :         if (n == j)
     176        1576 :             return true;
     177        3984 :         const auto iter = outgoingNodes.find(n);
     178        3984 :         if (iter != outgoingNodes.end())
     179             :         {
     180        8100 :             for (const T &k : iter->second)
     181             :             {
     182        4839 :                 if (!cpl::contains(plannedForVisit, k))
     183             :                 {
     184        3263 :                     plannedForVisit.insert(k);
     185        3263 :                     toVisit.push(k);
     186             :                 }
     187             :             }
     188             :         }
     189             :     }
     190         722 :     return false;
     191             : }
     192             : 
     193             : template <class T, class V>
     194         631 : std::vector<T> DirectedAcyclicGraph<T, V>::findStartingNodes() const
     195             : {
     196         631 :     std::vector<T> ret;
     197        1696 :     for (const auto &i : nodes)
     198             :     {
     199        1065 :         if (!cpl::contains(incomingNodes, i))
     200         371 :             ret.emplace_back(i);
     201             :     }
     202         631 :     return ret;
     203             : }
     204             : 
     205             : // Kahn's algorithm:
     206             : // https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm
     207             : template <class T, class V>
     208         631 : std::vector<T> DirectedAcyclicGraph<T, V>::getTopologicalOrdering()
     209             : {
     210         631 :     std::vector<T> ret;
     211         631 :     ret.reserve(nodes.size());
     212             : 
     213         745 :     const auto cmp = [this](const T &a, const T &b)
     214          57 :     { return names.find(a)->second < names.find(b)->second; };
     215        1262 :     std::set<T, decltype(cmp)> S(cmp);
     216             : 
     217        1262 :     const auto sn = findStartingNodes();
     218        1002 :     for (const auto &i : sn)
     219         371 :         S.insert(i);
     220             : 
     221        1065 :     while (true)
     222             :     {
     223        1696 :         auto iterFirst = S.begin();
     224        1696 :         if (iterFirst == S.end())
     225         631 :             break;
     226        1065 :         const auto n = *iterFirst;
     227        1065 :         S.erase(iterFirst);
     228        1065 :         ret.emplace_back(n);
     229             : 
     230        1065 :         const auto iter = outgoingNodes.find(n);
     231        1065 :         if (iter != outgoingNodes.end())
     232             :         {
     233             :             // Need to take a copy as we remove edges during iteration
     234        1386 :             const std::set<T> myOutgoingNodes = iter->second;
     235        1413 :             for (const T &m : myOutgoingNodes)
     236             :             {
     237         720 :                 const char *retRemoveEdge = removeEdge(n, m);
     238             :                 (void)retRemoveEdge;
     239         720 :                 assert(retRemoveEdge == nullptr);
     240         720 :                 if (!cpl::contains(incomingNodes, m))
     241             :                 {
     242         694 :                     S.insert(m);
     243             :                 }
     244             :             }
     245             :         }
     246             :     }
     247             : 
     248             :     // Should not happen for a direct acyclic graph
     249         631 :     assert(incomingNodes.empty());
     250         631 :     assert(outgoingNodes.empty());
     251             : 
     252        1262 :     return ret;
     253             : }
     254             : 
     255             : }  // namespace gdal
     256             : 
     257             : #endif  // DIRECTEDACYCLICGRAPH_INCLUDED_H