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"
27 using namespace ARDOUR;
30 GraphEdges::add (GraphVertex from, GraphVertex to, bool via_sends_only)
32 insert (_from_to, from, to);
33 insert (_to_from, to, from);
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;
39 _from_to_with_sends.insert (
40 make_pair (from, make_pair (to, via_sends_only))
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().
48 GraphEdges::EdgeMapWithSends::iterator
49 GraphEdges::find_in_from_to_with_sends (GraphVertex from, GraphVertex to)
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) {
59 return _from_to_with_sends.end ();
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.
67 GraphEdges::has (GraphVertex from, GraphVertex to, bool* via_sends_only)
69 EdgeMapWithSends::iterator i = find_in_from_to_with_sends (from, to);
70 if (i == _from_to_with_sends.end ()) {
75 *via_sends_only = i->second.second;
81 /** @return the vertices that are fed from `r' */
83 GraphEdges::from (GraphVertex r) const
85 EdgeMap::const_iterator i = _from_to.find (r);
86 if (i == _from_to.end ()) {
87 return set<GraphVertex> ();
94 GraphEdges::remove (GraphVertex from, GraphVertex to)
96 EdgeMap::iterator i = _from_to.find (from);
97 assert (i != _from_to.end ());
99 if (i->second.empty ()) {
103 EdgeMap::iterator j = _to_from.find (to);
104 assert (j != _to_from.end ());
105 j->second.erase (from);
106 if (j->second.empty ()) {
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);
115 /** @param to `To' route.
116 * @return true if there are no edges going to `to'.
120 GraphEdges::has_none_to (GraphVertex to) const
122 return _to_from.find (to) == _to_from.end ();
126 GraphEdges::empty () const
128 assert (_from_to.empty () == _to_from.empty ());
129 return _from_to.empty ();
133 GraphEdges::dump () const
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() << " ";
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() << " ";
152 /** Insert an edge into one of the EdgeMaps */
154 GraphEdges::insert (EdgeMap& e, GraphVertex a, GraphVertex b)
156 EdgeMap::iterator i = e.find (a);
158 i->second.insert (b);
162 e.insert (make_pair (a, v));
166 struct RouteRecEnabledComparator
168 bool operator () (GraphVertex r1, GraphVertex r2) const
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 ();
175 /* r1 rec-enabled, r2 not rec-enabled, run r2 early */
179 if (r2->record_enabled()) {
180 /* r2 rec-enabled, r1 not rec-enabled, run r1 early */
183 /* neither rec-enabled, use signal order */
184 return r1->order_key () < r2->order_key ();
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).
193 boost::shared_ptr<RouteList>
194 ARDOUR::topological_sort (
195 boost::shared_ptr<RouteList> routes,
199 boost::shared_ptr<RouteList> sorted_routes (new RouteList);
201 /* queue of routes to process */
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);
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.
215 queue.sort (RouteRecEnabledComparator ());
217 /* Do the sort: algorithm is Kahn's from Wikipedia.
218 `Topological sorting of large networks', Communications of the ACM 5(11):558-562.
221 while (!queue.empty ()) {
222 GraphVertex r = queue.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);
234 if (!edges.empty ()) {
236 /* There are cycles in the graph, so we can't do a topological sort */
237 return boost::shared_ptr<RouteList> ();
240 return sorted_routes;