Alert the user if a connection is made which causes

feedback, and preserve the route graph in the state
that it was in before the feedback was introduced. The
intent being to simplify the code, reduce the number of
areas of code which must consider feedback, and fix a
few bugs.


git-svn-id: svn://localhost/ardour2/branches/3.0@10510 d708f5d6-7413-0410-9779-e7cbd77b26cf

11 files changed, 287 insertions, 196 deletions

diff --git a/libs/ardour/ardour/graph.h b/libs/ardour/ardour/graph.h
index 14ef353853..f1ebba698a 100644
--- a/libs/ardour/ardour/graph.h
+++ b/libs/ardour/ardour/graph.h
@@ -46,6 +46,7 @@ class Graph;
 
 class Route;
 class Session;
+class GraphEdges;	
 
 typedef boost::shared_ptr<GraphNode> node_ptr_t;
 
@@ -61,7 +62,7 @@ public:
 
 	void prep();
 	void trigger (GraphNode * n);
-	void rechain (boost::shared_ptr<RouteList> r);
+	void rechain (boost::shared_ptr<RouteList>, GraphEdges const &);
 
 	void dump (int chain);
 	void process();
diff --git a/libs/ardour/ardour/route.h b/libs/ardour/ardour/route.h
index bc84fd9470..6df6934517 100644
--- a/libs/ardour/ardour/route.h
+++ b/libs/ardour/ardour/route.h
@@ -310,9 +310,17 @@ class Route : public SessionObject, public Automatable, public RouteGroupMember,
 
 	/**
 	 * return true if this route feeds the first argument directly, via
-	 * either its main outs or a send.
+	 * either its main outs or a send.  This is checked by the actual
+	 * connections, rather than by what the graph is currently doing.
 	 */
-	bool direct_feeds (boost::shared_ptr<Route>, bool* via_send_only = 0);
+	bool direct_feeds_according_to_reality (boost::shared_ptr<Route>, bool* via_send_only = 0);
+
+	/**
+	 * return true if this route feeds the first argument directly, via
+	 * either its main outs or a send, according to the graph that
+	 * is currently being processed.
+	 */
+	bool direct_feeds_according_to_graph (boost::shared_ptr<Route>, bool* via_send_only = 0);
 
 	struct FeedRecord {
 		boost::weak_ptr<Route> r;
@@ -334,7 +342,6 @@ class Route : public SessionObject, public Automatable, public RouteGroupMember,
 	const FedBy& fed_by() const { return _fed_by; }
 	void clear_fed_by ();
 	bool add_fed_by (boost::shared_ptr<Route>, bool sends_only);
-	bool not_fed() const { return _fed_by.empty(); }
 
 	/* Controls (not all directly owned by the Route */
 
diff --git a/libs/ardour/ardour/route_dag.h b/libs/ardour/ardour/route_dag.h
deleted file mode 100644
index c9ce08ba71..0000000000
--- a/libs/ardour/ardour/route_dag.h
+++ /dev/null
@@ -1,58 +0,0 @@
-/*
-    Copyright (C) 2011 Paul Davis
-    Author: Carl Hetherington <cth@carlh.net>
-
-    This program is free software; you can redistribute it and/or modify
-    it under the terms of the GNU General Public License as published by
-    the Free Software Foundation; either version 2 of the License, or
-    (at your option) any later version.
-
-    This program is distributed in the hope that it will be useful,
-    but WITHOUT ANY WARRANTY; without even the implied warranty of
-    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-    GNU General Public License for more details.
-
-    You should have received a copy of the GNU General Public License
-    along with this program; if not, write to the Free Software
-    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
-
-*/
-
-#include <map>
-#include <set>
-
-namespace ARDOUR {
-
-typedef boost::shared_ptr<Route> DAGVertex;
-
-/** A list of edges for a directed acyclic graph for routes */	
-class DAGEdges
-{
-public:
-	typedef std::map<DAGVertex, std::set<DAGVertex> > EdgeMap;
-	
-	void add (DAGVertex from, DAGVertex to);
-	std::set<DAGVertex> from (DAGVertex r) const;
-	void remove (DAGVertex from, DAGVertex to);
-	bool has_none_to (DAGVertex to) const;
-	bool empty () const;
-	void dump () const;
-	
-private:
-	void insert (EdgeMap& e, DAGVertex a, DAGVertex b);
-
-	/* Keep a map in both directions to speed lookups */
-
-	/** map of edges with from as `first' and to as `second' */
-	EdgeMap _from_to;
-	/** map of the same edges with to as `first' and from as `second' */
-	EdgeMap _to_from;
-};
-
-boost::shared_ptr<RouteList> topological_sort (
-	boost::shared_ptr<RouteList>,
-	DAGEdges
-	);
-
-}
-
diff --git a/libs/ardour/ardour/route_graph.h b/libs/ardour/ardour/route_graph.h
new file mode 100644
index 0000000000..0b0af6c7dd
--- /dev/null
+++ b/libs/ardour/ardour/route_graph.h
@@ -0,0 +1,78 @@
+/*
+    Copyright (C) 2011 Paul Davis
+    Author: Carl Hetherington <cth@carlh.net>
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License
+    along with this program; if not, write to the Free Software
+    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+
+*/
+
+#ifndef __ardour_route_graph_h__
+#define __ardour_route_graph_h__
+
+#include <map>
+#include <set>
+
+namespace ARDOUR {
+
+typedef boost::shared_ptr<Route> GraphVertex;
+
+/** A list of edges for a directed graph for routes.
+ *
+ *  It keeps the same data in a few different ways, with add() adding edges
+ *  to all different representations, remove() removing similarly, and the
+ *  lookup method using whichever representation is most efficient for
+ *  that particular lookup.
+ *
+ *  This may be a premature optimisation...
+ */
+class GraphEdges
+{
+public:
+	typedef std::map<GraphVertex, std::set<GraphVertex> > EdgeMap;
+	
+	void add (GraphVertex from, GraphVertex to, bool via_sends_only);
+	bool has (GraphVertex from, GraphVertex to, bool* via_sends_only);
+	std::set<GraphVertex> from (GraphVertex r) const;
+	void remove (GraphVertex from, GraphVertex to);
+	bool has_none_to (GraphVertex to) const;
+	bool empty () const;
+	void dump () const;
+	
+private:
+	void insert (EdgeMap& e, GraphVertex a, GraphVertex b);
+	
+	typedef std::multimap<GraphVertex, std::pair<GraphVertex, bool> > EdgeMapWithSends;
+	
+	EdgeMapWithSends::iterator find_in_from_to_with_sends (GraphVertex, GraphVertex);
+
+	/** map of edges with from as `first' and to as `second' */
+	EdgeMap _from_to;
+	/** map of the same edges with to as `first' and from as `second' */
+	EdgeMap _to_from;
+	/** map of edges with via-sends information; first part of the map is
+	    the `from' vertex, second is the `to' vertex and a flag which is
+	    true if the edge is via a send only.
+	*/
+	EdgeMapWithSends _from_to_with_sends;
+};
+
+boost::shared_ptr<RouteList> topological_sort (
+	boost::shared_ptr<RouteList>,
+	GraphEdges
+	);
+
+}
+
+#endif
diff --git a/libs/ardour/ardour/session.h b/libs/ardour/ardour/session.h
index ad42ee768b..c0e9e304fc 100644
--- a/libs/ardour/ardour/session.h
+++ b/libs/ardour/ardour/session.h
@@ -56,6 +56,7 @@
 #include "ardour/session_event.h"
 #include "ardour/location.h"
 #include "ardour/interpolation.h"
+#include "ardour/route_graph.h"
 
 #ifdef HAVE_JACK_SESSION
 #include <jack/session.h>
@@ -826,6 +827,12 @@ class Session : public PBD::StatefulDestructible, public PBD::ScopedConnectionLi
 
 	std::list<std::string> unknown_processors () const;
 
+	/** Emitted when a feedback cycle has been detected within Ardour's signal
+	    processing path.  Until it is fixed (by the user) some (unspecified)
+	    routes will not be run.
+	*/
+	static PBD::Signal0<void> FeedbackDetected;
+
 	/* handlers can return an integer value:
 	   0: config.set_audio_search_path() or config.set_midi_search_path() was used
 	   to modify the search path and we should try to find it again.
@@ -1206,7 +1213,7 @@ class Session : public PBD::StatefulDestructible, public PBD::ScopedConnectionLi
 
 	/* routes stuff */
 
-	boost::shared_ptr<Graph> route_graph;
+	boost::shared_ptr<Graph> _process_graph;
 
 	SerializedRCUManager<RouteList>  routes;
 
@@ -1500,6 +1507,11 @@ class Session : public PBD::StatefulDestructible, public PBD::ScopedConnectionLi
 
 	boost::shared_ptr<Speakers> _speakers;
 	void load_nested_sources (const XMLNode& node);
+
+	/** The directed graph of routes that is currently being used for audio processing
+	    and solo/mute computations.
+	*/
+	GraphEdges _current_route_graph;
 };
 
 } // namespace ARDOUR
diff --git a/libs/ardour/graph.cc b/libs/ardour/graph.cc
index 8658d30828..7d75738e0b 100644
--- a/libs/ardour/graph.cc
+++ b/libs/ardour/graph.cc
@@ -276,45 +276,18 @@ Graph::restart_cycle()
         // starting with waking up the others.
 }
 
-static bool
-is_feedback (boost::shared_ptr<RouteList> routelist, Route* from, boost::shared_ptr<Route> to)
-{
-        for (RouteList::iterator ri=routelist->begin(); ri!=routelist->end(); ri++) {
-                if ((*ri).get() == from) {
-                        return false;
-		}
-                if ((*ri) == to) {
-                        return true;
-		}
-        }
-
-        return false;
-}
-
-static bool
-is_feedback (boost::shared_ptr<RouteList> routelist, boost::shared_ptr<Route> from, Route* to)
-{
-        for (RouteList::iterator ri=routelist->begin(); ri!=routelist->end(); ri++) {
-                if ((*ri).get() == to) {
-                        return true;
-		}
-                if ((*ri) == from) {
-                        return false;
-		}
-        }
-
-        return false;
-}
+/** Rechain our stuff using a list of routes (which can be in any order) and
+ *  a directed graph of their interconnections, which is guaranteed to be
+ *  acyclic.
+ */
 
 void
-Graph::rechain (boost::shared_ptr<RouteList> routelist)
+Graph::rechain (boost::shared_ptr<RouteList> routelist, GraphEdges const & edges)
 {
-        node_list_t::iterator ni;
         Glib::Mutex::Lock ls (_swap_mutex);
 
         int chain = _setup_chain;
         DEBUG_TRACE (DEBUG::Graph, string_compose ("============== setup %1\n", chain));
-        // set all refcounts to 0;
 
 	/* This will become the number of nodes that do not feed any other node;
 	   once we have processed this number of those nodes, we have finished.
@@ -337,53 +310,38 @@ Graph::rechain (boost::shared_ptr<RouteList> routelist)
 
         // now add refs for the connections.
 
-        for (ni=_nodes_rt[chain].begin(); ni!=_nodes_rt[chain].end(); ni++) {
-
-		/* We will set this to true if the node *ni is directly or
-		   indirectly fed by anything (without feedback)
-		*/
-                bool has_input  = false;
-
-		/* We will set this to true if the node *ni directly feeds
-		   anything (without feedback)
-		*/
-                bool has_output = false;
+        for (node_list_t::iterator ni = _nodes_rt[chain].begin(); ni != _nodes_rt[chain].end(); ni++) {
 
-		/* We will also set up *ni's _activation_set to contain any nodes
-		   that it directly feeds.
-		*/
+                boost::shared_ptr<Route> r = boost::dynamic_pointer_cast<Route> (*ni);
 
-                boost::shared_ptr<Route> rp = boost::dynamic_pointer_cast<Route>( *ni);
+		/* The routes that are directly fed by r */
+		set<GraphVertex> fed_from_r = edges.from (r);
 
-                for (RouteList::iterator ri=routelist->begin(); ri!=routelist->end(); ri++) {
-                        if (rp->direct_feeds (*ri)) {
-                                if (is_feedback (routelist, rp.get(), *ri)) {
-                                        continue;
-                                }
+		/* Hence whether r has an output */
+		bool const has_output = !fed_from_r.empty ();
 
-                                has_output = true;
-                                (*ni)->_activation_set[chain].insert (*ri);
-                        }
-                }
+		/* Set up r's activation set */
+		for (set<GraphVertex>::iterator i = fed_from_r.begin(); i != fed_from_r.end(); ++i) {
+			r->_activation_set[chain].insert (*i);
+		}
 
-                for (Route::FedBy::iterator fi=rp->fed_by().begin(); fi!=rp->fed_by().end(); fi++) {
-                        if (boost::shared_ptr<Route> r = fi->r.lock()) {
-                                if (!is_feedback (routelist, r, rp.get())) {
-                                        has_input = true;
-                                }
-                        }
-                }
+		/* r has an input if there are some incoming edges to r in the graph */
+		bool const has_input = !edges.has_none_to (r);
 
 		/* Increment the refcount of any route that we directly feed */
-                for (node_set_t::iterator ai=(*ni)->_activation_set[chain].begin(); ai!=(*ni)->_activation_set[chain].end(); ai++) {
+                for (node_set_t::iterator ai = r->_activation_set[chain].begin(); ai != r->_activation_set[chain].end(); ai++) {
                         (*ai)->_init_refcount[chain] += 1;
                 }
 
                 if (!has_input) {
+			/* no input, so this node needs to be triggered initially to get things going */
                         _init_trigger_list[chain].push_back (*ni);
 		}
 
                 if (!has_output) {
+			/* no output, so this is one of the nodes that we can count off to decide
+			   if we've finished
+			*/
                         _init_finished_refcount[chain] += 1;
 		}
         }
diff --git a/libs/ardour/route.cc b/libs/ardour/route.cc
index 0b5ccdc53d..d07faf506c 100644
--- a/libs/ardour/route.cc
+++ b/libs/ardour/route.cc
@@ -81,7 +81,7 @@ PBD::Signal0<void> Route::RemoteControlIDChange;
 Route::Route (Session& sess, string name, Flag flg, DataType default_type)
 	: SessionObject (sess, name)
 	, Automatable (sess)
-	, GraphNode (sess.route_graph)
+	, GraphNode (sess._process_graph)
 	, _active (true)
 	, _signal_latency (0)
 	, _initial_delay (0)
@@ -744,7 +744,7 @@ Route::set_solo_isolated (bool yn, void *src)
 		}
 
 		bool sends_only;
-		bool does_feed = direct_feeds (*i, &sends_only); // we will recurse anyway, so don't use ::feeds()
+		bool does_feed = direct_feeds_according_to_graph (*i, &sends_only); // we will recurse anyway, so don't use ::feeds()
 
 		if (does_feed && !sends_only) {
 			(*i)->set_solo_isolated (yn, (*i)->route_group());
@@ -2644,14 +2644,14 @@ Route::feeds (boost::shared_ptr<Route> other, bool* via_sends_only)
 }
 
 bool
-Route::direct_feeds (boost::shared_ptr<Route> other, bool* only_send)
+Route::direct_feeds_according_to_reality (boost::shared_ptr<Route> other, bool* via_send_only)
 {
 	DEBUG_TRACE (DEBUG::Graph, string_compose ("Feeds? %1\n", _name));
 
 	if (_output->connected_to (other->input())) {
 		DEBUG_TRACE (DEBUG::Graph, string_compose ("\tdirect FEEDS %2\n", other->name()));
-		if (only_send) {
-			*only_send = false;
+		if (via_send_only) {
+			*via_send_only = false;
 		}
 
 		return true;
@@ -2665,8 +2665,8 @@ Route::direct_feeds (boost::shared_ptr<Route> other, bool* only_send)
 		if ((iop = boost::dynamic_pointer_cast<IOProcessor>(*r)) != 0) {
 			if (iop->feeds (other)) {
 				DEBUG_TRACE (DEBUG::Graph,  string_compose ("\tIOP %1 does feed %2\n", iop->name(), other->name()));
-				if (only_send) {
-					*only_send = true;
+				if (via_send_only) {
+					*via_send_only = true;
 				}
 				return true;
 			} else {
@@ -2682,6 +2682,12 @@ Route::direct_feeds (boost::shared_ptr<Route> other, bool* only_send)
 	return false;
 }
 
+bool
+Route::direct_feeds_according_to_graph (boost::shared_ptr<Route> other, bool* via_send_only)
+{
+	return _session._current_route_graph.has (shared_from_this (), other, via_send_only);
+}
+
 /** Called from the (non-realtime) butler thread when the transport is stopped */
 void
 Route::nonrealtime_handle_transport_stopped (bool /*abort_ignored*/, bool did_locate, bool can_flush_processors)
diff --git a/libs/ardour/route_dag.cc b/libs/ardour/route_graph.cc
index 3b13cf9415..fbf406fd92 100644
--- a/libs/ardour/route_dag.cc
+++ b/libs/ardour/route_graph.cc
@@ -19,7 +19,7 @@
 */
 
 #include "ardour/route.h"
-#include "ardour/route_dag.h"
+#include "ardour/route_graph.h"
 
 #include "i18n.h"
 
@@ -27,35 +27,71 @@ using namespace std;
 using namespace ARDOUR;
 
 void
-DAGEdges::add (DAGVertex from, DAGVertex to)
+GraphEdges::add (GraphVertex from, GraphVertex to, bool via_sends_only)
 {
 	insert (_from_to, from, to);
 	insert (_to_from, to, from);
-	
-	EdgeMap::iterator i = _from_to.find (from);
-	if (i != _from_to.end ()) {
-		i->second.insert (to);
+
+	EdgeMapWithSends::iterator i = find_in_from_to_with_sends (from, to);
+	if (i != _from_to_with_sends.end ()) {
+		i->second.second = via_sends_only;
 	} else {
-		set<DAGVertex> v;
-		v.insert (to);
-		_from_to.insert (make_pair (from, v));
+		_from_to_with_sends.insert (
+			make_pair (from, make_pair (to, via_sends_only))
+			);
+	}
+}
+
+/** Find a from/to pair in the _from_to_with_sends map.
+ *  @return iterator to the edge, or _from_to_with_sends.end().
+ */
+GraphEdges::EdgeMapWithSends::iterator
+GraphEdges::find_in_from_to_with_sends (GraphVertex from, GraphVertex to)
+{
+	typedef EdgeMapWithSends::iterator Iter;
+	pair<Iter, Iter> r = _from_to_with_sends.equal_range (from);
+	for (Iter i = r.first; i != r.second; ++i) {
+		if (i->second.first == to) {
+			return i;
+		}
+	}
+
+	return _from_to_with_sends.end ();
+}
+
+/** @param via_sends_only if non-0, filled in with true if the edge is a
+ *  path via a send only.
+ *  @return true if the given edge is present.
+ */
+bool
+GraphEdges::has (GraphVertex from, GraphVertex to, bool* via_sends_only)
+{
+	EdgeMapWithSends::iterator i = find_in_from_to_with_sends (from, to);
+	if (i == _from_to_with_sends.end ()) {
+		return false;
 	}
 	
+	if (via_sends_only) {
+		*via_sends_only = i->second.second;
+	}
+
+	return true;
 }
 
-set<DAGVertex>
-DAGEdges::from (DAGVertex r) const
+/** @return the vertices that are fed from `r' */
+set<GraphVertex>
+GraphEdges::from (GraphVertex r) const
 {
 	EdgeMap::const_iterator i = _from_to.find (r);
 	if (i == _from_to.end ()) {
-		return set<DAGVertex> ();
+		return set<GraphVertex> ();
 	}
 	
 	return i->second;
 }
 
 void
-DAGEdges::remove (DAGVertex from, DAGVertex to)
+GraphEdges::remove (GraphVertex from, GraphVertex to)
 {
 	EdgeMap::iterator i = _from_to.find (from);
 	assert (i != _from_to.end ());
@@ -70,6 +106,10 @@ DAGEdges::remove (DAGVertex from, DAGVertex to)
 	if (j->second.empty ()) {
 		_to_from.erase (j);
 	}
+
+	EdgeMapWithSends::iterator k = find_in_from_to_with_sends (from, to);
+	assert (k != _from_to_with_sends.end ());
+	_from_to_with_sends.erase (k);
 }
 
 /** @param to `To' route.
@@ -77,24 +117,24 @@ DAGEdges::remove (DAGVertex from, DAGVertex to)
  */
 
 bool
-DAGEdges::has_none_to (DAGVertex to) const
+GraphEdges::has_none_to (GraphVertex to) const
 {
 	return _to_from.find (to) == _to_from.end ();
 }
 
 bool
-DAGEdges::empty () const
+GraphEdges::empty () const
 {
 	assert (_from_to.empty () == _to_from.empty ());
 	return _from_to.empty ();
 }
 
 void
-DAGEdges::dump () const
+GraphEdges::dump () const
 {
 	for (EdgeMap::const_iterator i = _from_to.begin(); i != _from_to.end(); ++i) {
 		cout << "FROM: " << i->first->name() << " ";
-		for (set<DAGVertex>::const_iterator j = i->second.begin(); j != i->second.end(); ++j) {
+		for (set<GraphVertex>::const_iterator j = i->second.begin(); j != i->second.end(); ++j) {
 			cout << (*j)->name() << " ";
 		}
 		cout << "\n";
@@ -102,21 +142,22 @@ DAGEdges::dump () const
 	
 	for (EdgeMap::const_iterator i = _to_from.begin(); i != _to_from.end(); ++i) {
 		cout << "TO: " << i->first->name() << " ";
-		for (set<DAGVertex>::const_iterator j = i->second.begin(); j != i->second.end(); ++j) {
+		for (set<GraphVertex>::const_iterator j = i->second.begin(); j != i->second.end(); ++j) {
 			cout << (*j)->name() << " ";
 		}
 		cout << "\n";
 	}
 }
-	
+
+/** Insert an edge into one of the EdgeMaps */
 void
-DAGEdges::insert (EdgeMap& e, DAGVertex a, DAGVertex b)
+GraphEdges::insert (EdgeMap& e, GraphVertex a, GraphVertex b)
 {
 	EdgeMap::iterator i = e.find (a);
 	if (i != e.end ()) {
 		i->second.insert (b);
 	} else {
-		set<DAGVertex> v;
+		set<GraphVertex> v;
 		v.insert (b);
 		e.insert (make_pair (a, v));
 	}
@@ -124,7 +165,7 @@ DAGEdges::insert (EdgeMap& e, DAGVertex a, DAGVertex b)
 
 struct RouteRecEnabledComparator
 {
-	bool operator () (DAGVertex r1, DAGVertex r2) const
+	bool operator () (GraphVertex r1, GraphVertex r2) const
 	{
 		if (r1->record_enabled()) {
 			if (r2->record_enabled()) {
@@ -152,7 +193,7 @@ struct RouteRecEnabledComparator
 boost::shared_ptr<RouteList>
 ARDOUR::topological_sort (
 	boost::shared_ptr<RouteList> routes,
-	DAGEdges edges
+	GraphEdges edges
 	)
 {
 	boost::shared_ptr<RouteList> sorted_routes (new RouteList);
@@ -162,7 +203,7 @@ ARDOUR::topological_sort (
 
 	/* initial queue has routes that are not fed by anything */
 	for (RouteList::iterator i = routes->begin(); i != routes->end(); ++i) {
-		if ((*i)->not_fed ()) {
+		if (edges.has_none_to (*i)) {
 			queue.push_back (*i);
 		}
 	}
@@ -178,11 +219,11 @@ ARDOUR::topological_sort (
 	*/
 	
 	while (!queue.empty ()) {
-		DAGVertex r = queue.front ();
+		GraphVertex r = queue.front ();
 		queue.pop_front ();
 		sorted_routes->push_back (r);
-		set<DAGVertex> e = edges.from (r);
-		for (set<DAGVertex>::iterator i = e.begin(); i != e.end(); ++i) {
+		set<GraphVertex> e = edges.from (r);
+		for (set<GraphVertex>::iterator i = e.begin(); i != e.end(); ++i) {
 			edges.remove (r, *i);
 			if (edges.has_none_to (*i)) {
 				queue.push_back (*i);
@@ -191,6 +232,7 @@ ARDOUR::topological_sort (
 	}
 
 	if (!edges.empty ()) {
+		edges.dump ();
 		/* There are cycles in the graph, so we can't do a topological sort */
 		return boost::shared_ptr<RouteList> ();
 	}
diff --git a/libs/ardour/session.cc b/libs/ardour/session.cc
index 9aed414b1c..e940009e94 100644
--- a/libs/ardour/session.cc
+++ b/libs/ardour/session.cc
@@ -86,7 +86,7 @@
 #include "ardour/recent_sessions.h"
 #include "ardour/region_factory.h"
 #include "ardour/return.h"
-#include "ardour/route_dag.h"
+#include "ardour/route_graph.h"
 #include "ardour/route_group.h"
 #include "ardour/send.h"
 #include "ardour/session.h"
@@ -129,6 +129,7 @@ PBD::Signal0<void> Session::AutoBindingOff;
 PBD::Signal2<void,std::string, std::string> Session::Exported;
 PBD::Signal1<int,boost::shared_ptr<Playlist> > Session::AskAboutPlaylistDeletion;
 PBD::Signal0<void> Session::Quit;
+PBD::Signal0<void> Session::FeedbackDetected;
 
 static void clean_up_session_event (SessionEvent* ev) { delete ev; }
 const SessionEvent::RTeventCallback Session::rt_cleanup (clean_up_session_event);
@@ -149,7 +150,7 @@ Session::Session (AudioEngine &eng,
 	, _post_transport_work (0)
 	, _send_timecode_update (false)
 	, _all_route_group (new RouteGroup (*this, "all"))
-	, route_graph (new Graph(*this))
+	, _process_graph (new Graph (*this))
 	, routes (new RouteList)
 	, _total_free_4k_blocks (0)
 	, _bundles (new BundleList)
@@ -1293,7 +1294,7 @@ Session::resort_routes ()
 		/* writer goes out of scope and forces update */
 	}
 
-	//route_graph->dump(1);
+	//_process_graph->dump(1);
 
 #ifndef NDEBUG
 	boost::shared_ptr<RouteList> rl = routes.reader ();
@@ -1313,51 +1314,95 @@ Session::resort_routes ()
 
 }
 
+/** This is called whenever we need to rebuild the graph of how we will process
+ *  routes.
+ *  @param r List of routes, in any order.
+ */
+
 void
 Session::resort_routes_using (boost::shared_ptr<RouteList> r)
 {
-	DAGEdges edges;
-
+	/* We are going to build a directed graph of our routes;
+	   this is where the edges of that graph are put.
+	*/
+	
+	GraphEdges edges;
+
+	/* Go through all routes doing two things:
+	 *
+	 * 1. Collect the edges of the route graph.  Each of these edges
+	 *    is a pair of routes, one of which directly feeds the other
+	 *    either by a JACK connection or by an internal send.
+	 *
+	 * 2. Begin the process of making routes aware of which other
+	 *    routes directly or indirectly feed them.  This information
+	 *    is used by the solo code.
+	 */
+	   
 	for (RouteList::iterator i = r->begin(); i != r->end(); ++i) {
 
+		/* Clear out the route's list of direct or indirect feeds */
 		(*i)->clear_fed_by ();
 
 		for (RouteList::iterator j = r->begin(); j != r->end(); ++j) {
 
-			/* although routes can feed themselves, it will
-			   cause an endless recursive descent if we
-			   detect it. so don't bother checking for
-			   self-feeding.
-			*/
-
-			if (*j == *i) {
-				continue;
-			}
-
 			bool via_sends_only;
 
-			if ((*j)->direct_feeds (*i, &via_sends_only)) {
-				edges.add (*j, *i);
+			/* See if this *j feeds *i according to the current state of the JACK
+			   connections and internal sends.
+			*/
+			if ((*j)->direct_feeds_according_to_reality (*i, &via_sends_only)) {
+				/* add the edge to the graph (part #1) */
+				edges.add (*j, *i, via_sends_only);
+				/* tell the route (for part #2) */
 				(*i)->add_fed_by (*j, via_sends_only);
 			}
 		}
 	}
 
-	for (RouteList::iterator i = r->begin(); i != r->end(); ++i) {
-		trace_terminal (*i, *i);
-	}
-
+	/* Attempt a topological sort of the route graph */
 	boost::shared_ptr<RouteList> sorted_routes = topological_sort (r, edges);
-	route_graph->rechain (sorted_routes);
+	
+	if (sorted_routes) {
+		/* We got a satisfactory topological sort, so there is no feedback;
+		   use this new graph.
+
+		   Note: the process graph rechain does not require a
+		   topologically-sorted list, but hey ho.
+		*/
+		_process_graph->rechain (sorted_routes, edges);
+		_current_route_graph = edges;
+
+		/* Complete the building of the routes' lists of what directly
+		   or indirectly feeds them.
+		*/
+		for (RouteList::iterator i = r->begin(); i != r->end(); ++i) {
+			trace_terminal (*i, *i);
+		}
+
+		r = sorted_routes;
 
 #ifndef NDEBUG
-	DEBUG_TRACE (DEBUG::Graph, "Routes resorted, order follows:\n");
-	for (RouteList::iterator i = sorted_routes->begin(); i != sorted_routes->end(); ++i) {
-		DEBUG_TRACE (DEBUG::Graph, string_compose ("\t%1 signal order %2\n",
-		                                           (*i)->name(), (*i)->order_key ("signal")));
-	}
+		DEBUG_TRACE (DEBUG::Graph, "Routes resorted, order follows:\n");
+		for (RouteList::iterator i = r->begin(); i != r->end(); ++i) {
+			DEBUG_TRACE (DEBUG::Graph, string_compose ("\t%1 signal order %2\n",
+								   (*i)->name(), (*i)->order_key ("signal")));
+		}
 #endif
 
+	} else {
+		/* The topological sort failed, so we have a problem.  Tell everyone
+		   and stick to the old graph; this will continue to be processed, so
+		   until the feedback is fixed, what is played back will not quite
+		   reflect what is actually connected.  Note also that we do not
+		   do trace_terminal here, as it would fail due to an endless recursion,
+		   so the solo code will think that everything is still connected
+		   as it was before.
+		*/
+		
+		FeedbackDetected (); /* EMIT SIGNAL */
+	}
+
 }
 
 /** Find a route name starting with \a base, maybe followed by the
@@ -2174,7 +2219,7 @@ Session::remove_route (boost::shared_ptr<Route> route)
 	 */
 
 	resort_routes ();
-	route_graph->clear_other_chain ();
+	_process_graph->clear_other_chain ();
 
 	/* get rid of it from the dead wood collection in the route list manager */
 
diff --git a/libs/ardour/session_process.cc b/libs/ardour/session_process.cc
index 2384dd5fb3..33c4e5621c 100644
--- a/libs/ardour/session_process.cc
+++ b/libs/ardour/session_process.cc
@@ -107,9 +107,9 @@ Session::no_roll (pframes_t nframes)
 		_click_io->silence (nframes);
 	}
 
-	if (route_graph->threads_in_use() > 0) {
+	if (_process_graph->threads_in_use() > 0) {
 		DEBUG_TRACE(DEBUG::ProcessThreads,"calling graph/no-roll\n");
-		route_graph->routes_no_roll( nframes, _transport_frame, end_frame, non_realtime_work_pending(), declick);
+		_process_graph->routes_no_roll( nframes, _transport_frame, end_frame, non_realtime_work_pending(), declick);
 	} else {
 		for (RouteList::iterator i = r->begin(); i != r->end(); ++i) {
 
@@ -148,9 +148,9 @@ Session::process_routes (pframes_t nframes, bool& need_butler)
 	   using 1 thread. its needed because otherwise when we remove
 	   tracks, the graph never gets updated.
 	*/
-	if (1 || route_graph->threads_in_use() > 0) {
+	if (1 || _process_graph->threads_in_use() > 0) {
 		DEBUG_TRACE(DEBUG::ProcessThreads,"calling graph/process-routes\n");
-		route_graph->process_routes (nframes, start_frame, end_frame, declick, need_butler);
+		_process_graph->process_routes (nframes, start_frame, end_frame, declick, need_butler);
 	} else {
 
 		for (RouteList::iterator i = r->begin(); i != r->end(); ++i) {
@@ -185,8 +185,8 @@ Session::silent_process_routes (pframes_t nframes, bool& need_butler)
 	   using 1 thread. its needed because otherwise when we remove
 	   tracks, the graph never gets updated.
 	*/
-	if (1 || route_graph->threads_in_use() > 0) {
-		route_graph->silent_process_routes (nframes, start_frame, end_frame, need_butler);
+	if (1 || _process_graph->threads_in_use() > 0) {
+		_process_graph->silent_process_routes (nframes, start_frame, end_frame, need_butler);
 	} else {
 		for (RouteList::iterator i = r->begin(); i != r->end(); ++i) {
 
diff --git a/libs/ardour/wscript b/libs/ardour/wscript
index 9bde8abab2..5836af03ee 100644
--- a/libs/ardour/wscript
+++ b/libs/ardour/wscript
@@ -170,7 +170,7 @@ libardour_sources = [
         'return.cc',
         'reverse.cc',
         'route.cc',
-        'route_dag.cc',
+        'route_graph.cc',
         'route_group.cc',
         'route_group_member.cc',
         'rb_effect.cc',