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 /** @param via_sends_only if non-0, filled in with true if the edge is a
  63  *  path via a send only.
  64  *  @return true if the given edge is present.
  65  */
  66 bool
  67 GraphEdges::has (GraphVertex from, GraphVertex to, bool* via_sends_only)
  68 {
  69         EdgeMapWithSends::iterator i = find_in_from_to_with_sends (from, to);
  70         if (i == _from_to_with_sends.end ()) {
  71                 return false;
  72         }
  73
  74         if (via_sends_only) {
  75                 *via_sends_only = i->second.second;
  76         }
  77
  78         return true;
  79 }
  80
  81 /** @return the vertices that are fed from `r' */
  82 set<GraphVertex>
  83 GraphEdges::from (GraphVertex r) const
  84 {
  85         EdgeMap::const_iterator i = _from_to.find (r);
  86         if (i == _from_to.end ()) {
  87                 return set<GraphVertex> ();
  88         }
  89
  90         return i->second;
  91 }
  92
  93 void
  94 GraphEdges::remove (GraphVertex from, GraphVertex to)
  95 {
  96         EdgeMap::iterator i = _from_to.find (from);
  97         assert (i != _from_to.end ());
  98         i->second.erase (to);
  99         if (i->second.empty ()) {
 100                 _from_to.erase (i);
 101         }
 102
 103         EdgeMap::iterator j = _to_from.find (to);
 104         assert (j != _to_from.end ());
 105         j->second.erase (from);
 106         if (j->second.empty ()) {
 107                 _to_from.erase (j);
 108         }
 109
 110         EdgeMapWithSends::iterator k = find_in_from_to_with_sends (from, to);
 111         assert (k != _from_to_with_sends.end ());
 112         _from_to_with_sends.erase (k);
 113 }
 114
 115 /** @param to `To' route.
 116  *  @return true if there are no edges going to `to'.
 117  */
 118
 119 bool
 120 GraphEdges::has_none_to (GraphVertex to) const
 121 {
 122         return _to_from.find (to) == _to_from.end ();
 123 }
 124
 125 bool
 126 GraphEdges::empty () const
 127 {
 128         assert (_from_to.empty () == _to_from.empty ());
 129         return _from_to.empty ();
 130 }
 131
 132 void
 133 GraphEdges::dump () const
 134 {
 135         for (EdgeMap::const_iterator i = _from_to.begin(); i != _from_to.end(); ++i) {
 136                 cout << "FROM: " << i->first->name() << " ";
 137                 for (set<GraphVertex>::const_iterator j = i->second.begin(); j != i->second.end(); ++j) {
 138                         cout << (*j)->name() << " ";
 139                 }
 140                 cout << "\n";
 141         }
 142
 143         for (EdgeMap::const_iterator i = _to_from.begin(); i != _to_from.end(); ++i) {
 144                 cout << "TO: " << i->first->name() << " ";
 145                 for (set<GraphVertex>::const_iterator j = i->second.begin(); j != i->second.end(); ++j) {
 146                         cout << (*j)->name() << " ";
 147                 }
 148                 cout << "\n";
 149         }
 150 }
 151
 152 /** Insert an edge into one of the EdgeMaps */
 153 void
 154 GraphEdges::insert (EdgeMap& e, GraphVertex a, GraphVertex b)
 155 {
 156         EdgeMap::iterator i = e.find (a);
 157         if (i != e.end ()) {
 158                 i->second.insert (b);
 159         } else {
 160                 set<GraphVertex> v;
 161                 v.insert (b);
 162                 e.insert (make_pair (a, v));
 163         }
 164 }
 165
 166 struct RouteRecEnabledComparator
 167 {
 168         bool operator () (GraphVertex r1, GraphVertex r2) const
 169         {
 170                 if (r1->record_enabled()) {
 171                         if (r2->record_enabled()) {
 172                                 /* both rec-enabled, just use signal order */
 173                                 return r1->order_key () < r2->order_key ();
 174                         } else {
 175                                 /* r1 rec-enabled, r2 not rec-enabled, run r2 early */
 176                                 return false;
 177                         }
 178                 } else {
 179                         if (r2->record_enabled()) {
 180                                 /* r2 rec-enabled, r1 not rec-enabled, run r1 early */
 181                                 return true;
 182                         } else {
 183                                 /* neither rec-enabled, use signal order */
 184                                 return r1->order_key () < r2->order_key ();
 185                         }
 186                 }
 187         }
 188 };
 189
 190 /** Perform a topological sort of a list of routes using a directed graph representing connections.
 191  *  @return Sorted list of routes, or 0 if the graph contains cycles (feedback loops).
 192  */
 193 boost::shared_ptr<RouteList>
 194 ARDOUR::topological_sort (
 195         boost::shared_ptr<RouteList> routes,
 196         GraphEdges edges
 197         )
 198 {
 199         boost::shared_ptr<RouteList> sorted_routes (new RouteList);
 200
 201         /* queue of routes to process */
 202         RouteList queue;
 203
 204         /* initial queue has routes that are not fed by anything */
 205         for (RouteList::iterator i = routes->begin(); i != routes->end(); ++i) {
 206                 if (edges.has_none_to (*i)) {
 207                         queue.push_back (*i);
 208                 }
 209         }
 210
 211         /* Sort the initial queue so that non-rec-enabled routes are run first.
 212            This is so that routes can record things coming from other routes
 213            via external connections.
 214         */
 215         queue.sort (RouteRecEnabledComparator ());
 216
 217         /* Do the sort: algorithm is Kahn's from Wikipedia.
 218            `Topological sorting of large networks', Communications of the ACM 5(11):558-562.
 219         */
 220
 221         while (!queue.empty ()) {
 222                 GraphVertex r = queue.front ();
 223                 queue.pop_front ();
 224                 sorted_routes->push_back (r);
 225                 set<GraphVertex> e = edges.from (r);
 226                 for (set<GraphVertex>::iterator i = e.begin(); i != e.end(); ++i) {
 227                         edges.remove (r, *i);
 228                         if (edges.has_none_to (*i)) {
 229                                 queue.push_back (*i);
 230                         }
 231                 }
 232         }
 233
 234         if (!edges.empty ()) {
 235                 edges.dump ();
 236                 /* There are cycles in the graph, so we can't do a topological sort */
 237                 return boost::shared_ptr<RouteList> ();
 238         }
 239
 240         return sorted_routes;
 241 }