libs/ardour/route_graph.cc

   1 /*
   2  * Copyright (C) 2012-2016 Paul Davis <paul@linuxaudiosystems.com>
   3  * Copyright (C) 2015-2016 Robin Gareus <robin@gareus.org>
   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 along
  16  * with this program; if not, write to the Free Software Foundation, Inc.,
  17  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18  */
  19
  20 #include "ardour/route.h"
  21 #include "ardour/route_graph.h"
  22 #include "ardour/track.h"
  23
  24 #include "pbd/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                 boost::shared_ptr<Track> t1 (boost::dynamic_pointer_cast<Track>(r1));
 199                 boost::shared_ptr<Track> t2 (boost::dynamic_pointer_cast<Track>(r2));
 200                 PresentationInfo::order_t r1o = r1->presentation_info().order();
 201                 PresentationInfo::order_t r2o = r2->presentation_info().order();
 202
 203                 if (!t1) {
 204                         if (!t2) {
 205                                 /* makes no difference which is first, use presentation order */
 206                                 return r1o < r2o;
 207                         } else {
 208                                 /* r1 is not a track, r2 is, run it early */
 209                                 return false;
 210                         }
 211                 }
 212
 213                 if (!t2) {
 214                         /* we already tested !t1, so just use presentation order */
 215                         return r1o < r2o;
 216                 }
 217
 218                 if (t1->rec_enable_control()->get_value()) {
 219                         if (t2->rec_enable_control()->get_value()) {
 220                                 /* both rec-enabled, just use signal order */
 221                                 return r1o < r2o;
 222                         } else {
 223                                 /* t1 rec-enabled, t2 not rec-enabled, run t2 early */
 224                                 return false;
 225                         }
 226                 } else {
 227                         if (t2->rec_enable_control()->get_value()) {
 228                                 /* t2 rec-enabled, t1 not rec-enabled, run t1 early */
 229                                 return true;
 230                         } else {
 231                                 /* neither rec-enabled, use presentation order */
 232                                 return r1o < r2o;
 233                         }
 234                 }
 235         }
 236 };
 237
 238 /** Perform a topological sort of a list of routes using a directed graph representing connections.
 239  *  @return Sorted list of routes, or 0 if the graph contains cycles (feedback loops).
 240  */
 241 boost::shared_ptr<RouteList>
 242 ARDOUR::topological_sort (
 243         boost::shared_ptr<RouteList> routes,
 244         GraphEdges edges
 245         )
 246 {
 247         boost::shared_ptr<RouteList> sorted_routes (new RouteList);
 248
 249         /* queue of routes to process */
 250         RouteList queue;
 251
 252         /* initial queue has routes that are not fed by anything */
 253         for (RouteList::iterator i = routes->begin(); i != routes->end(); ++i) {
 254                 if (edges.has_none_to (*i)) {
 255                         queue.push_back (*i);
 256                 }
 257         }
 258
 259         /* Sort the initial queue so that non-rec-enabled routes are run first.
 260            This is so that routes can record things coming from other routes
 261            via external connections.
 262         */
 263         queue.sort (RouteRecEnabledComparator ());
 264
 265         /* Do the sort: algorithm is Kahn's from Wikipedia.
 266            `Topological sorting of large networks', Communications of the ACM 5(11):558-562.
 267         */
 268
 269         while (!queue.empty ()) {
 270                 GraphVertex r = queue.front ();
 271                 queue.pop_front ();
 272                 sorted_routes->push_back (r);
 273                 set<GraphVertex> e = edges.from (r);
 274                 for (set<GraphVertex>::iterator i = e.begin(); i != e.end(); ++i) {
 275                         edges.remove (r, *i);
 276                         if (edges.has_none_to (*i)) {
 277                                 queue.push_back (*i);
 278                         }
 279                 }
 280         }
 281
 282         if (!edges.empty ()) {
 283                 edges.dump ();
 284                 /* There are cycles in the graph, so we can't do a topological sort */
 285                 return boost::shared_ptr<RouteList> ();
 286         }
 287
 288         return sorted_routes;
 289 }