libs/ardour/route_graph.cc

   1 /*
   2     Copyright (C) 2011 Paul Davis
   3     Author: Carl Hetherington <cth@carlh.net>
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with this program; if not, write to the Free Software
  17     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18
  19 */
  20
  21 #include "ardour/route.h"
  22 #include "ardour/route_graph.h"
  23
  24 #include "i18n.h"
  25
  26 using namespace std;
  27 using namespace ARDOUR;
  28
  29 void
  30 GraphEdges::add (GraphVertex from, GraphVertex to, bool via_sends_only)
  31 {
  32         insert (_from_to, from, to);
  33         insert (_to_from, to, from);
  34
  35         EdgeMapWithSends::iterator i = find_in_from_to_with_sends (from, to);
  36         if (i != _from_to_with_sends.end ()) {
  37                 i->second.second = via_sends_only;
  38         } else {
  39                 _from_to_with_sends.insert (
  40                         make_pair (from, make_pair (to, via_sends_only))
  41                         );
  42         }
  43 }
  44
  45 /** Find a from/to pair in the _from_to_with_sends map.
  46  *  @return iterator to the edge, or _from_to_with_sends.end().
  47  */
  48 GraphEdges::EdgeMapWithSends::iterator
  49 GraphEdges::find_in_from_to_with_sends (GraphVertex from, GraphVertex to)
  50 {
  51         typedef EdgeMapWithSends::iterator Iter;
  52         pair<Iter, Iter> r = _from_to_with_sends.equal_range (from);
  53         for (Iter i = r.first; i != r.second; ++i) {
  54                 if (i->second.first == to) {
  55                         return i;
  56                 }
  57         }
  58
  59         return _from_to_with_sends.end ();
  60 }
  61
  62 GraphEdges::EdgeMapWithSends::iterator
  63 GraphEdges::find_recursively_in_from_to_with_sends (GraphVertex from, GraphVertex to)
  64 {
  65         typedef EdgeMapWithSends::iterator Iter;
  66         pair<Iter, Iter> r = _from_to_with_sends.equal_range (from);
  67         for (Iter i = r.first; i != r.second; ++i) {
  68                 if (i->second.first == to) {
  69                         return i;
  70                 }
  71                 GraphEdges::EdgeMapWithSends::iterator t = find_recursively_in_from_to_with_sends (i->second.first, to);
  72                 if (t != _from_to_with_sends.end ()) {
  73                         return t;
  74                 }
  75         }
  76
  77         return _from_to_with_sends.end ();
  78 }
  79
  80 /** @param via_sends_only if non-0, filled in with true if the edge is a
  81  *  path via a send only.
  82  *  @return true if the given edge is present.
  83  */
  84 bool
  85 GraphEdges::has (GraphVertex from, GraphVertex to, bool* via_sends_only)
  86 {
  87         EdgeMapWithSends::iterator i = find_in_from_to_with_sends (from, to);
  88         if (i == _from_to_with_sends.end ()) {
  89                 return false;
  90         }
  91
  92         if (via_sends_only) {
  93                 *via_sends_only = i->second.second;
  94         }
  95
  96         return true;
  97 }
  98
  99 bool
 100 GraphEdges::feeds (GraphVertex from, GraphVertex to)
 101 {
 102         EdgeMapWithSends::iterator i = find_recursively_in_from_to_with_sends (from, to);
 103         if (i == _from_to_with_sends.end ()) {
 104                 return false;
 105         }
 106         return true;
 107 }
 108
 109 /** @return the vertices that are fed from `r' */
 110 set<GraphVertex>
 111 GraphEdges::from (GraphVertex r) const
 112 {
 113         EdgeMap::const_iterator i = _from_to.find (r);
 114         if (i == _from_to.end ()) {
 115                 return set<GraphVertex> ();
 116         }
 117
 118         return i->second;
 119 }
 120
 121 void
 122 GraphEdges::remove (GraphVertex from, GraphVertex to)
 123 {
 124         EdgeMap::iterator i = _from_to.find (from);
 125         assert (i != _from_to.end ());
 126         i->second.erase (to);
 127         if (i->second.empty ()) {
 128                 _from_to.erase (i);
 129         }
 130
 131         EdgeMap::iterator j = _to_from.find (to);
 132         assert (j != _to_from.end ());
 133         j->second.erase (from);
 134         if (j->second.empty ()) {
 135                 _to_from.erase (j);
 136         }
 137
 138         EdgeMapWithSends::iterator k = find_in_from_to_with_sends (from, to);
 139         assert (k != _from_to_with_sends.end ());
 140         _from_to_with_sends.erase (k);
 141 }
 142
 143 /** @param to `To' route.
 144  *  @return true if there are no edges going to `to'.
 145  */
 146
 147 bool
 148 GraphEdges::has_none_to (GraphVertex to) const
 149 {
 150         return _to_from.find (to) == _to_from.end ();
 151 }
 152
 153 bool
 154 GraphEdges::empty () const
 155 {
 156         assert (_from_to.empty () == _to_from.empty ());
 157         return _from_to.empty ();
 158 }
 159
 160 void
 161 GraphEdges::dump () const
 162 {
 163         for (EdgeMap::const_iterator i = _from_to.begin(); i != _from_to.end(); ++i) {
 164                 cout << "FROM: " << i->first->name() << " ";
 165                 for (set<GraphVertex>::const_iterator j = i->second.begin(); j != i->second.end(); ++j) {
 166                         cout << (*j)->name() << " ";
 167                 }
 168                 cout << "\n";
 169         }
 170
 171         for (EdgeMap::const_iterator i = _to_from.begin(); i != _to_from.end(); ++i) {
 172                 cout << "TO: " << i->first->name() << " ";
 173                 for (set<GraphVertex>::const_iterator j = i->second.begin(); j != i->second.end(); ++j) {
 174                         cout << (*j)->name() << " ";
 175                 }
 176                 cout << "\n";
 177         }
 178 }
 179
 180 /** Insert an edge into one of the EdgeMaps */
 181 void
 182 GraphEdges::insert (EdgeMap& e, GraphVertex a, GraphVertex b)
 183 {
 184         EdgeMap::iterator i = e.find (a);
 185         if (i != e.end ()) {
 186                 i->second.insert (b);
 187         } else {
 188                 set<GraphVertex> v;
 189                 v.insert (b);
 190                 e.insert (make_pair (a, v));
 191         }
 192 }
 193
 194 struct RouteRecEnabledComparator
 195 {
 196         bool operator () (GraphVertex r1, GraphVertex r2) const
 197         {
 198                 if (r1->record_enabled()) {
 199                         if (r2->record_enabled()) {
 200                                 /* both rec-enabled, just use signal order */
 201                                 return r1->order_key () < r2->order_key ();
 202                         } else {
 203                                 /* r1 rec-enabled, r2 not rec-enabled, run r2 early */
 204                                 return false;
 205                         }
 206                 } else {
 207                         if (r2->record_enabled()) {
 208                                 /* r2 rec-enabled, r1 not rec-enabled, run r1 early */
 209                                 return true;
 210                         } else {
 211                                 /* neither rec-enabled, use signal order */
 212                                 return r1->order_key () < r2->order_key ();
 213                         }
 214                 }
 215         }
 216 };
 217
 218 /** Perform a topological sort of a list of routes using a directed graph representing connections.
 219  *  @return Sorted list of routes, or 0 if the graph contains cycles (feedback loops).
 220  */
 221 boost::shared_ptr<RouteList>
 222 ARDOUR::topological_sort (
 223         boost::shared_ptr<RouteList> routes,
 224         GraphEdges edges
 225         )
 226 {
 227         boost::shared_ptr<RouteList> sorted_routes (new RouteList);
 228
 229         /* queue of routes to process */
 230         RouteList queue;
 231
 232         /* initial queue has routes that are not fed by anything */
 233         for (RouteList::iterator i = routes->begin(); i != routes->end(); ++i) {
 234                 if (edges.has_none_to (*i)) {
 235                         queue.push_back (*i);
 236                 }
 237         }
 238
 239         /* Sort the initial queue so that non-rec-enabled routes are run first.
 240            This is so that routes can record things coming from other routes
 241            via external connections.
 242         */
 243         queue.sort (RouteRecEnabledComparator ());
 244
 245         /* Do the sort: algorithm is Kahn's from Wikipedia.
 246            `Topological sorting of large networks', Communications of the ACM 5(11):558-562.
 247         */
 248
 249         while (!queue.empty ()) {
 250                 GraphVertex r = queue.front ();
 251                 queue.pop_front ();
 252                 sorted_routes->push_back (r);
 253                 set<GraphVertex> e = edges.from (r);
 254                 for (set<GraphVertex>::iterator i = e.begin(); i != e.end(); ++i) {
 255                         edges.remove (r, *i);
 256                         if (edges.has_none_to (*i)) {
 257                                 queue.push_back (*i);
 258                         }
 259                 }
 260         }
 261
 262         if (!edges.empty ()) {
 263                 edges.dump ();
 264                 /* There are cycles in the graph, so we can't do a topological sort */
 265                 return boost::shared_ptr<RouteList> ();
 266         }
 267
 268         return sorted_routes;
 269 }