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 #include "ardour/track.h"
  24
  25 #include "i18n.h"
  26
  27 using namespace std;
  28 using namespace ARDOUR;
  29
  30 void
  31 GraphEdges::add (GraphVertex from, GraphVertex to, bool via_sends_only)
  32 {
  33         insert (_from_to, from, to);
  34         insert (_to_from, to, from);
  35
  36         EdgeMapWithSends::iterator i = find_in_from_to_with_sends (from, to);
  37         if (i != _from_to_with_sends.end ()) {
  38                 i->second.second = via_sends_only;
  39         } else {
  40                 _from_to_with_sends.insert (
  41                         make_pair (from, make_pair (to, via_sends_only))
  42                         );
  43         }
  44 }
  45
  46 /** Find a from/to pair in the _from_to_with_sends map.
  47  *  @return iterator to the edge, or _from_to_with_sends.end().
  48  */
  49 GraphEdges::EdgeMapWithSends::iterator
  50 GraphEdges::find_in_from_to_with_sends (GraphVertex from, GraphVertex to)
  51 {
  52         typedef EdgeMapWithSends::iterator Iter;
  53         pair<Iter, Iter> r = _from_to_with_sends.equal_range (from);
  54         for (Iter i = r.first; i != r.second; ++i) {
  55                 if (i->second.first == to) {
  56                         return i;
  57                 }
  58         }
  59
  60         return _from_to_with_sends.end ();
  61 }
  62
  63 GraphEdges::EdgeMapWithSends::iterator
  64 GraphEdges::find_recursively_in_from_to_with_sends (GraphVertex from, GraphVertex to)
  65 {
  66         typedef EdgeMapWithSends::iterator Iter;
  67         pair<Iter, Iter> r = _from_to_with_sends.equal_range (from);
  68         for (Iter i = r.first; i != r.second; ++i) {
  69                 if (i->second.first == to) {
  70                         return i;
  71                 }
  72                 GraphEdges::EdgeMapWithSends::iterator t = find_recursively_in_from_to_with_sends (i->second.first, to);
  73                 if (t != _from_to_with_sends.end ()) {
  74                         return t;
  75                 }
  76         }
  77
  78         return _from_to_with_sends.end ();
  79 }
  80
  81 /** @param via_sends_only if non-0, filled in with true if the edge is a
  82  *  path via a send only.
  83  *  @return true if the given edge is present.
  84  */
  85 bool
  86 GraphEdges::has (GraphVertex from, GraphVertex to, bool* via_sends_only)
  87 {
  88         EdgeMapWithSends::iterator i = find_in_from_to_with_sends (from, to);
  89         if (i == _from_to_with_sends.end ()) {
  90                 return false;
  91         }
  92
  93         if (via_sends_only) {
  94                 *via_sends_only = i->second.second;
  95         }
  96
  97         return true;
  98 }
  99
 100 bool
 101 GraphEdges::feeds (GraphVertex from, GraphVertex to)
 102 {
 103         EdgeMapWithSends::iterator i = find_recursively_in_from_to_with_sends (from, to);
 104         if (i == _from_to_with_sends.end ()) {
 105                 return false;
 106         }
 107         return true;
 108 }
 109
 110 /** @return the vertices that are fed from `r' */
 111 set<GraphVertex>
 112 GraphEdges::from (GraphVertex r) const
 113 {
 114         EdgeMap::const_iterator i = _from_to.find (r);
 115         if (i == _from_to.end ()) {
 116                 return set<GraphVertex> ();
 117         }
 118
 119         return i->second;
 120 }
 121
 122 void
 123 GraphEdges::remove (GraphVertex from, GraphVertex to)
 124 {
 125         EdgeMap::iterator i = _from_to.find (from);
 126         assert (i != _from_to.end ());
 127         i->second.erase (to);
 128         if (i->second.empty ()) {
 129                 _from_to.erase (i);
 130         }
 131
 132         EdgeMap::iterator j = _to_from.find (to);
 133         assert (j != _to_from.end ());
 134         j->second.erase (from);
 135         if (j->second.empty ()) {
 136                 _to_from.erase (j);
 137         }
 138
 139         EdgeMapWithSends::iterator k = find_in_from_to_with_sends (from, to);
 140         assert (k != _from_to_with_sends.end ());
 141         _from_to_with_sends.erase (k);
 142 }
 143
 144 /** @param to `To' route.
 145  *  @return true if there are no edges going to `to'.
 146  */
 147
 148 bool
 149 GraphEdges::has_none_to (GraphVertex to) const
 150 {
 151         return _to_from.find (to) == _to_from.end ();
 152 }
 153
 154 bool
 155 GraphEdges::empty () const
 156 {
 157         assert (_from_to.empty () == _to_from.empty ());
 158         return _from_to.empty ();
 159 }
 160
 161 void
 162 GraphEdges::dump () const
 163 {
 164         for (EdgeMap::const_iterator i = _from_to.begin(); i != _from_to.end(); ++i) {
 165                 cout << "FROM: " << i->first->name() << " ";
 166                 for (set<GraphVertex>::const_iterator j = i->second.begin(); j != i->second.end(); ++j) {
 167                         cout << (*j)->name() << " ";
 168                 }
 169                 cout << "\n";
 170         }
 171
 172         for (EdgeMap::const_iterator i = _to_from.begin(); i != _to_from.end(); ++i) {
 173                 cout << "TO: " << i->first->name() << " ";
 174                 for (set<GraphVertex>::const_iterator j = i->second.begin(); j != i->second.end(); ++j) {
 175                         cout << (*j)->name() << " ";
 176                 }
 177                 cout << "\n";
 178         }
 179 }
 180
 181 /** Insert an edge into one of the EdgeMaps */
 182 void
 183 GraphEdges::insert (EdgeMap& e, GraphVertex a, GraphVertex b)
 184 {
 185         EdgeMap::iterator i = e.find (a);
 186         if (i != e.end ()) {
 187                 i->second.insert (b);
 188         } else {
 189                 set<GraphVertex> v;
 190                 v.insert (b);
 191                 e.insert (make_pair (a, v));
 192         }
 193 }
 194
 195 struct RouteRecEnabledComparator
 196 {
 197         bool operator () (GraphVertex r1, GraphVertex r2) const
 198         {
 199                 boost::shared_ptr<Track> t1 (boost::dynamic_pointer_cast<Track>(r1));
 200                 boost::shared_ptr<Track> t2 (boost::dynamic_pointer_cast<Track>(r2));
 201
 202                 if (!t1) {
 203                         if (!t2) {
 204                                 /* makes no difference which is first, use signal order */
 205                                 return r1->order_key () < r2->order_key ();
 206                         } else {
 207                                 /* r1 is not a track, r2 is, run it early */
 208                                 return false;
 209                         }
 210                 }
 211
 212                 if (!t2) {
 213                         /* we already tested !t1, so just use signal order */
 214                         return r1->order_key () < r2->order_key ();
 215                 }
 216
 217                 if (t1->rec_enable_control()->get_value()) {
 218                         if (t2->rec_enable_control()->get_value()) {
 219                                 /* both rec-enabled, just use signal order */
 220                                 return t1->order_key () < t2->order_key ();
 221                         } else {
 222                                 /* t1 rec-enabled, t2 not rec-enabled, run t2 early */
 223                                 return false;
 224                         }
 225                 } else {
 226                         if (t2->rec_enable_control()->get_value()) {
 227                                 /* t2 rec-enabled, t1 not rec-enabled, run t1 early */
 228                                 return true;
 229                         } else {
 230                                 /* neither rec-enabled, use signal order */
 231                                 return t1->order_key () < t2->order_key ();
 232                         }
 233                 }
 234         }
 235 };
 236
 237 /** Perform a topological sort of a list of routes using a directed graph representing connections.
 238  *  @return Sorted list of routes, or 0 if the graph contains cycles (feedback loops).
 239  */
 240 boost::shared_ptr<RouteList>
 241 ARDOUR::topological_sort (
 242         boost::shared_ptr<RouteList> routes,
 243         GraphEdges edges
 244         )
 245 {
 246         boost::shared_ptr<RouteList> sorted_routes (new RouteList);
 247
 248         /* queue of routes to process */
 249         RouteList queue;
 250
 251         /* initial queue has routes that are not fed by anything */
 252         for (RouteList::iterator i = routes->begin(); i != routes->end(); ++i) {
 253                 if (edges.has_none_to (*i)) {
 254                         queue.push_back (*i);
 255                 }
 256         }
 257
 258         /* Sort the initial queue so that non-rec-enabled routes are run first.
 259            This is so that routes can record things coming from other routes
 260            via external connections.
 261         */
 262         queue.sort (RouteRecEnabledComparator ());
 263
 264         /* Do the sort: algorithm is Kahn's from Wikipedia.
 265            `Topological sorting of large networks', Communications of the ACM 5(11):558-562.
 266         */
 267
 268         while (!queue.empty ()) {
 269                 GraphVertex r = queue.front ();
 270                 queue.pop_front ();
 271                 sorted_routes->push_back (r);
 272                 set<GraphVertex> e = edges.from (r);
 273                 for (set<GraphVertex>::iterator i = e.begin(); i != e.end(); ++i) {
 274                         edges.remove (r, *i);
 275                         if (edges.has_none_to (*i)) {
 276                                 queue.push_back (*i);
 277                         }
 278                 }
 279         }
 280
 281         if (!edges.empty ()) {
 282                 edges.dump ();
 283                 /* There are cycles in the graph, so we can't do a topological sort */
 284                 return boost::shared_ptr<RouteList> ();
 285         }
 286
 287         return sorted_routes;
 288 }