2 Copyright (C) 2011 Paul Davis
3 Author: Carl Hetherington <cth@carlh.net>
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.
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.
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.
21 #include "ardour/route.h"
22 #include "ardour/route_graph.h"
23 #include "ardour/track.h"
28 using namespace ARDOUR;
31 GraphEdges::add (GraphVertex from, GraphVertex to, bool via_sends_only)
33 insert (_from_to, from, to);
34 insert (_to_from, to, from);
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;
40 _from_to_with_sends.insert (
41 make_pair (from, make_pair (to, via_sends_only))
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().
49 GraphEdges::EdgeMapWithSends::iterator
50 GraphEdges::find_in_from_to_with_sends (GraphVertex from, GraphVertex to)
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) {
60 return _from_to_with_sends.end ();
63 GraphEdges::EdgeMapWithSends::iterator
64 GraphEdges::find_recursively_in_from_to_with_sends (GraphVertex from, GraphVertex to)
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) {
72 GraphEdges::EdgeMapWithSends::iterator t = find_recursively_in_from_to_with_sends (i->second.first, to);
73 if (t != _from_to_with_sends.end ()) {
78 return _from_to_with_sends.end ();
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.
86 GraphEdges::has (GraphVertex from, GraphVertex to, bool* via_sends_only)
88 EdgeMapWithSends::iterator i = find_in_from_to_with_sends (from, to);
89 if (i == _from_to_with_sends.end ()) {
94 *via_sends_only = i->second.second;
101 GraphEdges::feeds (GraphVertex from, GraphVertex to)
103 EdgeMapWithSends::iterator i = find_recursively_in_from_to_with_sends (from, to);
104 if (i == _from_to_with_sends.end ()) {
110 /** @return the vertices that are fed from `r' */
112 GraphEdges::from (GraphVertex r) const
114 EdgeMap::const_iterator i = _from_to.find (r);
115 if (i == _from_to.end ()) {
116 return set<GraphVertex> ();
123 GraphEdges::remove (GraphVertex from, GraphVertex to)
125 EdgeMap::iterator i = _from_to.find (from);
126 assert (i != _from_to.end ());
127 i->second.erase (to);
128 if (i->second.empty ()) {
132 EdgeMap::iterator j = _to_from.find (to);
133 assert (j != _to_from.end ());
134 j->second.erase (from);
135 if (j->second.empty ()) {
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);
144 /** @param to `To' route.
145 * @return true if there are no edges going to `to'.
149 GraphEdges::has_none_to (GraphVertex to) const
151 return _to_from.find (to) == _to_from.end ();
155 GraphEdges::empty () const
157 assert (_from_to.empty () == _to_from.empty ());
158 return _from_to.empty ();
162 GraphEdges::dump () const
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() << " ";
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() << " ";
181 /** Insert an edge into one of the EdgeMaps */
183 GraphEdges::insert (EdgeMap& e, GraphVertex a, GraphVertex b)
185 EdgeMap::iterator i = e.find (a);
187 i->second.insert (b);
191 e.insert (make_pair (a, v));
195 struct RouteRecEnabledComparator
197 bool operator () (GraphVertex r1, GraphVertex r2) const
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 PresentationInfo::order_t r1o = r1->presentation_info().order();
202 PresentationInfo::order_t r2o = r2->presentation_info().order();
206 /* makes no difference which is first, use presentation order */
209 /* r1 is not a track, r2 is, run it early */
215 /* we already tested !t1, so just use presentation order */
219 if (t1->rec_enable_control()->get_value()) {
220 if (t2->rec_enable_control()->get_value()) {
221 /* both rec-enabled, just use signal order */
224 /* t1 rec-enabled, t2 not rec-enabled, run t2 early */
228 if (t2->rec_enable_control()->get_value()) {
229 /* t2 rec-enabled, t1 not rec-enabled, run t1 early */
232 /* neither rec-enabled, use presentation order */
239 /** Perform a topological sort of a list of routes using a directed graph representing connections.
240 * @return Sorted list of routes, or 0 if the graph contains cycles (feedback loops).
242 boost::shared_ptr<RouteList>
243 ARDOUR::topological_sort (
244 boost::shared_ptr<RouteList> routes,
248 boost::shared_ptr<RouteList> sorted_routes (new RouteList);
250 /* queue of routes to process */
253 /* initial queue has routes that are not fed by anything */
254 for (RouteList::iterator i = routes->begin(); i != routes->end(); ++i) {
255 if (edges.has_none_to (*i)) {
256 queue.push_back (*i);
260 /* Sort the initial queue so that non-rec-enabled routes are run first.
261 This is so that routes can record things coming from other routes
262 via external connections.
264 queue.sort (RouteRecEnabledComparator ());
266 /* Do the sort: algorithm is Kahn's from Wikipedia.
267 `Topological sorting of large networks', Communications of the ACM 5(11):558-562.
270 while (!queue.empty ()) {
271 GraphVertex r = queue.front ();
273 sorted_routes->push_back (r);
274 set<GraphVertex> e = edges.from (r);
275 for (set<GraphVertex>::iterator i = e.begin(); i != e.end(); ++i) {
276 edges.remove (r, *i);
277 if (edges.has_none_to (*i)) {
278 queue.push_back (*i);
283 if (!edges.empty ()) {
285 /* There are cycles in the graph, so we can't do a topological sort */
286 return boost::shared_ptr<RouteList> ();
289 return sorted_routes;