Gamesmithing: Tarjan's Bridges
In this article, I'm taking a look at Tarjan's bridge-finding algorithm for graphs. I'll look at why it was needed and how it works. At the end of the article, I'll post my code with an MIT license. This article will assume some knowledge of basic graph algorithms, like depth-first search. Note: I refer to vertices as nodes in my code, so I'll do the same in my descriptions.
Conversation in video games can be unrealistic - there’s more to it than approaching someone and pressing “A”. Collision Bend, the game I've been working on, handles conversation a little differently. Instead of representing a conversation with a branching tree, the player instead navigates a graph. The player moves along an edge from one node to another, but they can't move along the same edge twice. Pictures help.
Here, the player started on node C, then moved to D and E (currently covered by the big orange player avatar). The player can no longer reach nodes A and B because the edge between D and E has been traversed already.
Many of the conversation graphs in the game are generated randomly. The algorithm guarantees that each node has at least two edges. Useful, as it prevents any node from being a dead end the player cannot escape from. However, the end result still suffered from two problems, one obvious and one non-obvious. The following graph shows both.
The obvious problem is that nodes J, K, and L are not connected to the rest of the graph. If the player starts on A and the Goal node is on L, there's no way to beat the level. This is easy enough to solve with a Depth-First Search (DFS), as I will show later.
The non-obvious problem is that the graph has bridges. A bridge is an edge that breaks the graph into separate parts if the bridge is removed. For example, if we removed the edge from B to D in the graph above, you could still find a path from B to D. However, if we removed edge DE, then you can't get from D to E anymore. If the player starts on A and the Goal node is on C, then the player is unable to visit nodes E through I and still finish the level. Once they move from D to E, there's no path back to C as they aren't allowed to cross edge DE again. If there's some treasure or bonus points on node F, the player sees it but can't reach it. That's frustrating for the player.
How do we fix this on an arbitrary graph? First, we have to identify the bridges, and that's where Robert Tarjan comes into play. Besides having a last name particularly well-suited for a death metal band, Tarjan also came up with an algorithm to do just this in 1974.
First, we're going to create a spanning tree of the graph. A spanning tree is going to (eventually) touch every node. I say eventually, because we'll also use this step to figure out which nodes are not connected to the main graph and then connect them. We'll make a few classes, SpanningTree, SpanningTreeNode, and Node. Node will represent the nodes in the conversation graph. SpanningTreeNode represents that node within our spanning tree. SpanningTree has a root SpanningTreeNode we can access. Here's what they look like at the beginning:
public class Node : MonoBehaviour
{
public List<Node> ConnectedNodes;
}
public class SpanningTreeNode
{
public Node Node;
public List<SpanningTreeNode> Children;
public SpanningTreeNode(Node node)
{
Node = node;
Children = new List<SpanningTreeNode>();
}
}
public class SpanningTree
{
private SpanningTreeNode _root;
}Just as a style aside, we're using the class SpanningTree to solve our bridge problem and our unconnected node problem, but neither of those functions are obvious from the class's name. I'm going to insert a small static function that clarifies what I'm trying to do.
class SpanningTree
{
private SpanningTreeNode _root;
// For now, we don't use the spanning tree for anything else but fixing bridges and connecting things. To keep code clean,
// build it in a static function for clarity.
public static void ConnectAndFixBridges(List<Node> nodes)
{
var spanningTree = new SpanningTree(nodes);
}
}That's better - now when some poor soul (read: me, six months from now, looking back over the code) is wondering why the hell I'm building a spanning tree, the answer will be more obvious.
As the function above implies, we'll be passing in our List of Nodes to create our SpanningTree. We'll randomly assign the first node in the list as our root node of the spanning tree. Any node can be the root node. We'll build the spanning tree from this root node.
Before we build the spanning tree, we're going to add a public List<string> UnusedConnections to SpanningTreeNode. A spanning tree contains all nodes in a graph and a minimum set of edges that connects them all. If there is a cycle in the graph (such as the ABCD cycle in the graph above), it will ignore one of the edges so that the cycle is not present in the tree. These connections will be useful later, though, so we’re making note of them inside UnusedConnections.
Here's the Build function that creates the initial spanning tree:
public class SpanningTreeNode
{
public Node Node;
public List<SpanningTreeNode> Children;
public List<string> UnusedConnections; // this doesn't count connections to the parent or any children.
public SpanningTreeNode(Node node)
{
Node = node;
Children = new List<SpanningTreeNode>();
UnusedConnections = new List<string>();
}
}
public class SpanningTree
{
private SpanningTreeNode _root;
public SpanningTree(List<Node> nodes)
{
_root = new SpanningTreeNode(originalNodes[0]);
Build(_root, null);
}
// Check if each connected Node is already in the tree. For any that aren't, they are this treeNode's children. Recurse on.
// If they are already in the tree and the node in question isn't a parent, then add it to UnusedConnections.
private void Build(SpanningTreeNode treeNode, SpanningTreeNode parentTreeNode)
{
foreach (var connection in treeNode.Node.ConnectedNodes)
{
if (Contains(connection.name))
{
// Connection in question is stored elsewhere in our tree. If it's not the parent, note this.
if (parentTreeNode != null && parentTreeNode.Node != connection)
}
else
{
var child = new SpanningTreeNode(connection);
treeNode.Children.Add(child);
Build(child, treeNode);
}
}
}
// Using 'name' instead of node or treeNode here lets us go back and forth between the two mostly seamlessly
private bool Contains(string name)
{
return Contains(name, _root);
}
private bool Contains(string name, SpanningTreeNode treeNode)
{
if (treeNode.Node.name == name) return true;
bool childContains = false;
foreach (var child in treeNode.Children)
{
if (Contains(name, child))
{
childContains = true;
}
}
return childContains;
}
}We have two recursive functions: Build() and Contains(). As the comment says, Contains uses a string parameter so that we don't have to worry if we're looking for a SpanningTreeNode or just a Node. We can work with either. For this reason, the UnusedConnections field in SpanningTreeNode is also a List of strings instead of Nodes or SpanningTreeNodes. Contains() is a straightforward function otherwise.
In Build(), we're looking through each Node in the SpanningTreeNode's Node.ConnectedNodes. If it's already contained in the SpanningTree and it's not the parent, then we'll store it in the SpanningTreeNode's UnusedConnections. This means that our graph has a connection here but it isn't part of the SpanningTree. Otherwise, we haven't come across this node before and we can make it a child of this current SpanningTreeNode.
We have a SpanningTree that covers our main graph, but we aren't guaranteed that all nodes are covered by this tree. What we can do is to keep a List<Node> of all nodes that aren't part of the SpanningTree, and remove nodes from that list when they are added to the SpanningTree. After the first Build(), we can take whatever remains in the unconnected nodes list and simply connect them with any node from our spanning tree.
public class SpanningTree
{
private SpanningTreeNode _root;
private List<Node> _unconnectedNodes;
// Creates a spanning tree from graph of nodes. Will add in edges if needed.
public SpanningTree(List<Node> nodes)
{
_unconnectedNodes = new List<Node>(); // track nodes not connected to the tree, so that we can add unconnected components later
foreach (var node in nodes)
_root = new SpanningTreeNode(originalNodes[0]);
_unconnectedNodes.Remove(originalNodes[0]);
Build(_root, null);
// We might have two (or more) unconnected components in this graph. If that's the case, then build a bridge.
// Another edge will be added to fix this new bridge later.
// Right now, there's no order to the unconnected nodes. Later on we could measure distance and order on that to ensure the smallest edges are added.
while (_unconnectedNodes.Count > 0)
{
var node = _unconnectedNodes[0];
var closeTreeNode = ClosestTo(node, _root);
closeTreeNode.Node.ConnectedNodes.Add(node);
_log.Write("Adding edge between and to connect components", closeTreeNode.Node.name, node.name);
Build(closeTreeNode, null);
}
_log.Write("Spanning tree");
Print(_root);
}
private void Build(SpanningTreeNode treeNode, SpanningTreeNode parentTreeNode)
{
foreach (var connection in treeNode.Node.ConnectedNodes)
{
if (treeNode.UnusedConnections.Contains(connection.name))
{
// already noted on a previous Build call
}
else if (Contains(connection.name))
{
// Connection in question is stored elsewhere in our tree. If it's not the parent, note this.
if (parentTreeNode != null && parentTreeNode.Node != connection)
}
else
{
var child = new SpanningTreeNode(connection);
_unconnectedNodes.Remove(connection);
treeNode.Children.Add(child);
Build(child, treeNode);
}
}
}
private SpanningTreeNode ClosestTo(Node node, SpanningTreeNode treeNode)
{
SpanningTreeNode closest = treeNode;
float distance = Vector3.Distance(treeNode.Node.transform.position, node.transform.position);
foreach (var child in treeNode.Children)
{
var closestChild = ClosestTo(node, child);
float childDistance = Vector3.Distance(closestChild.Node.transform.position, node.transform.position);
if (childDistance < distance)
{
closest = closestChild;
distance = childDistance;
}
}
return closest;
}
private void Print(SpanningTreeNode treeNode)
{
_log.Write("Node w/ children , unused connections to ",
treeNode.Node.name,
treeNode.Children.Count > 0 ? treeNode.Children.Select(c => c.Node.name).Aggregate((x, y) => x + ", " + y) : "NONE",
treeNode.UnusedConnections.Count > 0 ? treeNode.UnusedConnections.Aggregate((x, y) => x + ", " + y) : "NONE");
foreach (var child in treeNode.Children)
}
}That's a big snippet of code right there. The main work is done inside the constructor, where we haphazardly add edges between unconnected nodes and the closest node within our spanning tree. Note that these edges are guaranteed to be bridges. We change Build() so that it still works if we call Build() multiple times on a node, like we do just after we connect a node in the spanning tree with a previously unconnected node. We add some helper functions for finding the closest SpanningTreeNode to a given Node, and a Print() function.
Here’s what our graph looks like after adding in the edge:
And here’s a spanning tree that represents the graph, randomly picking F as our root:
Spanning tree edges are dark gray, while non-tree edges (UnusedConnections) are shown in light grey.
So! We have a spanning tree that covers every node, but the thing is (probably) filthy with bridges. To solve that problem, we'll do the following.
1) Give each node a postorder number, call it P.
2) Count the number of descendants of each node (counting the node itself), call it ND.
3) Take a look at the lowest Jump number, which is the lowest postorder number of the node, its children, and a single "jump" along a connection present in the graph but absent from the SpanningTree. (This is why we stored these connections in UnusedConnections earlier.) Call this L.
4) Likewise, take a look at the highest Jump number, call it H.
If the node's high Jump is less than or equal to the node's postorder number AND the node's low Jump is greater than the node's postorder minus the node's number of descendants, or more tersely, (H <= P && L > P - ND), than we've found a bridge! Thanks, Tarjan!
public class SpanningTreeNode
{
public Node Node;
public int Postorder;
public List<SpanningTreeNode> Children;
public List<string> UnusedConnections; // this doesn't count connections to the parent or any children.
public int NumDescendants; // includes self
public int LowestWithJump;
public int HighestWithJump;
public SpanningTreeNode(Node node)
{
Node = node;
Children = new List<SpanningTreeNode>();
UnusedConnections = new List<string>();
}
}
public class SpanningTree
{
private int _counter;
private void MarkPostorder(SpanningTreeNode treeNode)
{
foreach (var child in treeNode.Children)
treeNode.Postorder = _counter;
_counter++;
}
private int CountDescendants(SpanningTreeNode treeNode)
{
int sum = 0;
foreach (var child in treeNode.Children)
{
sum += CountDescendants(child);
}
treeNode.NumDescendants = sum + 1; // Includes self
return treeNode.NumDescendants;
}
private void PrintNodeDetail(SpanningTreeNode treeNode)
{
_log.Write("Node Postorder numDesc low high ",
treeNode.Node.name, treeNode.Postorder, treeNode.NumDescendants, treeNode.LowestWithJump, treeNode.HighestWithJump);
foreach (var child in treeNode.Children)
}
}Here's the final version of SpanningTreeNode, with everything we need. Following that is a quick and easy postorder transversal of the tree, and a descendent-counting function. Another Print function gives us a different view of the SpanningTreeNode.
// Calculates the lowest NumDescendants value of the node, any children, and any connected nodes not connected in the spanning tree.
// HasJumped prevents cyclical checks by tracking the one non-tree edge jump.
private int CountLowJump(SpanningTreeNode treeNode, bool hasJumped)
{
int lowestMark = _root.NumDescendants + 1; // 1 more than max value here
if (!hasJumped)
{
foreach (var child in treeNode.Children)
{
int childLow = CountLowJump(child, hasJumped);
if (childLow < lowestMark)
{
lowestMark = childLow;
}
}
foreach (var connection in treeNode.Node.ConnectedNodes)
{
if (treeNode.UnusedConnections.Contains(connection.name))
{
var jumpNode = Find(connection.name);
int jumpLow = CountLowJump(jumpNode, true);
if (jumpLow < lowestMark)
{
lowestMark = jumpLow;
}
}
}
}
if (treeNode.Postorder < lowestMark)
{
lowestMark = treeNode.Postorder;
}
if (lowestMark < treeNode.LowestWithJump)
{
treeNode.LowestWithJump = lowestMark;
}
return lowestMark;
}Here, we're calculating the low Jump number. As long as we're staying within the SpanningTreeNode's children, we do our basic recursion. However, if this particular node has an unused connection (unused within the SpanningTree, but present on the original graph), we'll also jump to that node and possibly use its own low postorder number. We only jump once, and once we've jumped or compared all the original node's descendants, we take the lowest postorder number we've found. It gets returned and propagated to all parent nodes that don't have a better option.
private int CountHighJump(SpanningTreeNode treeNode, bool hasJumped)
{
int highestMark = 0;
if (!hasJumped)
{
foreach (var child in treeNode.Children)
{
int childHigh = CountHighJump(child, hasJumped);
if (childHigh > highestMark)
{
highestMark = childHigh;
}
}
foreach (var connection in treeNode.Node.ConnectedNodes)
{
if (treeNode.UnusedConnections.Contains(connection.name))
{
var jumpNode = Find(connection.name);
int jumpHigh = CountHighJump(jumpNode, true);
if (jumpHigh > highestMark)
{
highestMark = jumpHigh;
}
}
}
}
if (treeNode.Postorder > highestMark)
{
highestMark = treeNode.Postorder;
}
if (highestMark > treeNode.HighestWithJump)
{
treeNode.HighestWithJump = highestMark;
}
return highestMark;
}Getting the highest Jump number is analogous.
private void FixBridges(SpanningTreeNode treeNode, SpanningTreeNode parent)
{
foreach (var child in treeNode.Children)
{
if (child.HighestWithJump <= child.Postorder && child.LowestWithJump > child.Postorder - child.NumDescendants)
{
// Bring out the bridge brigade, yo
if (parent != null)
{
parent.Node.ConnectedNodes.Add(child.Node);
child.Node.ConnectedNodes.Add(parent.Node);
_log.Write("Fixed bridge between and by connecting nodes and ", treeNode.Node.name, child.Node.name, parent.Node.name, child.Node.name);
}
else if (child.Children.Count > 0)
{
treeNode.Node.ConnectedNodes.Add(child.Children[0].Node);
child.Children[0].Node.ConnectedNodes.Add(treeNode.Node);
_log.Write("Fixed bridge between and by connecting nodes and ", treeNode.Node.name, child.Node.name, treeNode.Node.name, child.Children[0].Node.name);
}
else // panic and grab a random node
{
var panicNode = _originalNodes.Where(n => n != child.Node && n != treeNode.Node).First();
panicNode.ConnectedNodes.Add(child.Node);
child.Node.ConnectedNodes.Add(panicNode);
_log.Write("Fixed bridge between and by connecting nodes and ", treeNode.Node.name, child.Node.name, panicNode.name, child.Node.name);
}
}
FixBridges(child, treeNode);
}
}Now, we'll go back and find all nodes where (H <= P && L > P - ND) applies. If it does, we'll create a new connection between one end of the bridge and some other node.
Woot. Our graph has no more bridges. But why? Why does (H <= P && L > P - ND) suffice to prove a bridge? Well, we know that any bridges must be within our spanning tree because our tree covers every node. If there's an edge not included in the tree, then there is an alternate path from the nodes the edge connects, and therefore that edge is not a bridge. Remember, a bridge must disconnect a graph if it is removed, so there can't be alternate paths.
Next, let's consider the Jump numbers. Without the single jump across a non-tree edge, we would simply have the lowest and the highest postorder numbers of each Node and its descendants. H would simply be the node's own postorder label, and L would be the postorder label of one of its descendants. With the jump, H > P implies that one descendant of a node W is connected to a non-descendant of W. Since P is a postordering, that specifically means a descendant is connected to a non-descendant that was postorder labeled "later on". On the other side, consider the condition L > P - ND. Now, any descendant of a node W must have a postorder label between W(P) - W(ND) and W(P). The first descendant of W to get a postorder label will have the label W(P) - W(ND), while W itself will have the label W(P). If we had a node W with L <= P - ND, then we know that a descendant must be connected (via a jump across a non-tree edge) to a node that was postorder labeled "earlier" than W or its descendants.
Taken together, we can show that if (H <= P && L > P - ND) is false for node W, then there is some descendant X of node W that is connected to a node Y that is not a descendant of W. That means there are at least two paths between X and W - one as a descendant in our spanning tree, and another through this non-tree connection. (The non-descendant node Y in question trivially shares a connection with W by going back up to the root of the tree.) If there are two paths, then we don't have a bridge. If (H <= P && L > P - ND) is true, then there are not two paths between W and X, so the edge between W and its parent must be a bridge.
Phew. Let's take a look at this in action. Here’s the graph and spanning tree shown earlier.
Calculating out all the numbers gives us the following:
Let's apply the equation from I through G.
For node I, H = 3, L = 1, ND = 1, and P = 1. So, H is greater than P, and we have no bridge.
For node H, H = 3, L = 1, ND = 2, and P = 2. H is still greater than P, so no bridge.
For node G, H = 3, L = 1, ND = 3, and P = 3. H <= P && L > P - ND, so this is a bridge between this and G's parent, F.
Going through this process for the whole graph, we end up with nodes G, J, D, and E being on the end of bridges. Here's the tree bridges marked in red.
Or, back to the original graph format.
Here's what the graph looks like after ConnectAndFixBridges() has been called. Added edges are marked in blue.
And that's that. Players can now be guaranteed access to all nodes on the conversational graph. It’s not the minimum set of edges needed to remove the bridges (edges like DF make DE and EF non-bridges so FH and EC aren’t strictly necessary), but extra edges don’t hurt gameplay at all. The algorithm runs in O(N + E) time, where N is the number of nodes and E is the number of edges. The algorithm works just as well with breadth-first search as it does with depth-first.
Game development can be a strange beast. You get stuck on some level design problem, and then you find out that someone solved this exact problem forty-five years earlier.
Here's the code. As stated before, it's under the MIT license. You can also find the code on Github.
using Assets.Scripts.Logging;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
namespace Assets.Scripts.Screens.Conversation.Graph
{
public class SpanningTreeNode
{
public Node Node;
public int Postorder;
public List<SpanningTreeNode> Children;
public List<string> UnusedConnections; // this doesn't count connections to the parent or any children.
public int NumDescendants; // includes self
public int LowestWithJump;
public int HighestWithJump;
public SpanningTreeNode(Node node)
{
Node = node;
Children = new List<SpanningTreeNode>();
UnusedConnections = new List<string>();
}
}
/// <summary>
/// A class for creating a spanning tree out of graph nodes. Good for connecting separate components and running Tarjan's Bridge Finding algorithm
/// </summary>
public class SpanningTree
{
static readonly ILog _log = Log.GetLogger(typeof(SpanningTree));
private SpanningTreeNode _root;
private List<Node> _originalNodes;
private List<Node> _unconnectedNodes;
private int _counter;
// For now, we don't use the spanning tree for anything else but fixing bridges and connecting things. To keep code clean,
// build it in a static function for clarity.
public static void ConnectAndFixBridges(List<Node> nodes)
{
var spanningTree = new SpanningTree(nodes);
}
// Creates a spanning tree from graph of nodes. Will add in edges if needed.
public SpanningTree(List<Node> nodes)
{
_originalNodes = nodes;
_unconnectedNodes = new List<Node>(); // track nodes not connected to the tree, so that we can add unconnected components later
foreach (var node in nodes)
_root = new SpanningTreeNode(_originalNodes[0]);
_unconnectedNodes.Remove(_originalNodes[0]);
Build(_root, null);
_log.Write("");
// We might have two (or more) unconnected components in this graph. If that's the case, then build a bridge.
// Another edge will be added to fix this new bridge later.
// Right now, there's no order to the unconnected nodes. Later on we could order by distance that to ensure the smallest edges are added.
while (_unconnectedNodes.Count > 0)
{
var node = _unconnectedNodes[0];
var closeTreeNode = ClosestTo(node, _root);
closeTreeNode.Node.ConnectedNodes.Add(node); // Possible improvement: avoid bad overlapping angles. See seed 208382959 on WorkTutorial
_log.Write("Adding edge between and to connect components", closeTreeNode.Node.name, node.name);
Build(closeTreeNode, null);
}
_log.Write("Spanning tree");
Print(_root);
// Tarjan magic
_counter = 1;
MarkPostorder(_root);
CountDescendants(_root);
MarkMaxLowJump();
CountLowJump(_root, false);
CountHighJump(_root, false);
_log.Write("Tree node details");
PrintNodeDetail(_root);
FixBridges(_root, null);
_log.Write("Graph connections, w/ new connections and no bridges");
PrintConnections(_root);
_log.Write("");
}
// Depth first search
// Check if each connected Node is already in the tree. For any that aren't, they are this treeNode's children. Recurse on.
// If they are already in the tree and the node in question isn't a parent, then add it to UnusedConnections.
// Can call twice to update with new connections to previously-unconnected components
private void Build(SpanningTreeNode treeNode, SpanningTreeNode parentTreeNode)
{
foreach (var connection in treeNode.Node.ConnectedNodes)
{
if (treeNode.UnusedConnections.Contains(connection.name))
{
// already noted on a previous Build call
}
else if (Contains(connection.name))
{
// Connection in question is stored elsewhere in our tree. If it's not the parent, note this.
if (parentTreeNode != null && parentTreeNode.Node != connection)
}
else
{
var child = new SpanningTreeNode(connection);
_unconnectedNodes.Remove(connection);
treeNode.Children.Add(child);
Build(child, treeNode);
}
}
}
// The raison d'etre of this class (mostly). Add edges if an edge to a child is identified as a bridge, preferring using grandchildren to this node's parent
private void FixBridges(SpanningTreeNode treeNode, SpanningTreeNode parent)
{
foreach (var child in treeNode.Children)
{
if (child.HighestWithJump <= child.Postorder && child.LowestWithJump > child.Postorder - child.NumDescendants)
{
// Bring out the bridge brigade, yo
if (parent != null)
{
parent.Node.ConnectedNodes.Add(child.Node);
child.Node.ConnectedNodes.Add(parent.Node);
_log.Write("Fixed bridge between and by connecting nodes and ", treeNode.Node.name, child.Node.name, parent.Node.name, child.Node.name);
}
else if (child.Children.Count > 0)
{
treeNode.Node.ConnectedNodes.Add(child.Children[0].Node);
child.Children[0].Node.ConnectedNodes.Add(treeNode.Node);
_log.Write("Fixed bridge between and by connecting nodes and ", treeNode.Node.name, child.Node.name, treeNode.Node.name, child.Children[0].Node.name);
}
else // panic and grab a random node
{
var panicNode = _originalNodes.Where(n => n != child.Node && n != treeNode.Node).First();
panicNode.ConnectedNodes.Add(child.Node);
child.Node.ConnectedNodes.Add(panicNode);
_log.Write("Fixed bridge between and by connecting nodes and ", treeNode.Node.name, child.Node.name, panicNode.name, child.Node.name);
}
}
FixBridges(child, treeNode);
}
}
private void MarkMaxLowJump()
{
MarkMaxLowJump(_root, _root.Postorder + 1);
}
private void MarkMaxLowJump(SpanningTreeNode treeNode, int max)
{
treeNode.LowestWithJump = max;
foreach (var child in treeNode.Children)
{
MarkMaxLowJump(child, max);
}
}
// Calculates the lowest NumDescendants value of the node, any children, and any connected nodes not connected in the spanning tree.
// HasJumped prevents cyclical checks by tracking the one non-tree edge jump.
private int CountLowJump(SpanningTreeNode treeNode, bool hasJumped)
{
int lowestMark = _root.NumDescendants + 1; // 1 more than max value here
if (!hasJumped)
{
foreach (var child in treeNode.Children)
{
int childLow = CountLowJump(child, hasJumped);
if (childLow < lowestMark)
{
lowestMark = childLow;
}
}
foreach (var connection in treeNode.Node.ConnectedNodes)
{
if (treeNode.UnusedConnections.Contains(connection.name))
{
var jumpNode = Find(connection.name);
int jumpLow = CountLowJump(jumpNode, true);
if (jumpLow < lowestMark)
{
lowestMark = jumpLow;
}
}
}
}
if (treeNode.Postorder < lowestMark)
{
lowestMark = treeNode.Postorder;
}
if (lowestMark < treeNode.LowestWithJump)
{
treeNode.LowestWithJump = lowestMark;
}
return lowestMark;
}
// analog to CountLowJump
private int CountHighJump(SpanningTreeNode treeNode, bool hasJumped)
{
int highestMark = 0;
if (!hasJumped)
{
foreach (var child in treeNode.Children)
{
int childHigh = CountHighJump(child, hasJumped);
if (childHigh > highestMark)
{
highestMark = childHigh;
}
}
foreach (var connection in treeNode.Node.ConnectedNodes)
{
if (treeNode.UnusedConnections.Contains(connection.name))
{
var jumpNode = Find(connection.name);
int jumpHigh = CountHighJump(jumpNode, true);
if (jumpHigh > highestMark)
{
highestMark = jumpHigh;
}
}
}
}
if (treeNode.Postorder > highestMark)
{
highestMark = treeNode.Postorder;
}
if (highestMark > treeNode.HighestWithJump)
{
treeNode.HighestWithJump = highestMark;
}
return highestMark;
}
private int CountDescendants(SpanningTreeNode treeNode)
{
int sum = 0;
foreach (var child in treeNode.Children)
{
sum += CountDescendants(child);
}
treeNode.NumDescendants = sum + 1; // Includes self
return treeNode.NumDescendants;
}
private void MarkPostorder(SpanningTreeNode treeNode)
{
foreach (var child in treeNode.Children)
treeNode.Postorder = _counter;
_counter++;
}
private void Print(SpanningTreeNode treeNode)
{
_log.Write("Node w/ children , unused connections to ",
treeNode.Node.name,
treeNode.Children.Count > 0 ? treeNode.Children.Select(c => c.Node.name).Aggregate((x, y) => x + ", " + y) : "NONE",
treeNode.UnusedConnections.Count > 0 ? treeNode.UnusedConnections.Aggregate((x, y) => x + ", " + y) : "NONE");
foreach (var child in treeNode.Children)
}
private void PrintNodeDetail(SpanningTreeNode treeNode)
{
_log.Write("Node Postorder numDesc low high ",
treeNode.Node.name, treeNode.Postorder, treeNode.NumDescendants, treeNode.LowestWithJump, treeNode.HighestWithJump);
foreach (var child in treeNode.Children)
}
private void PrintConnections(SpanningTreeNode treeNode)
{
_log.Write("Node w/ graph connections ",
treeNode.Node.name,
treeNode.Node.ConnectedNodes.Count > 0 ? treeNode.Node.ConnectedNodes.Select(c => c.name).Aggregate((x, y) => x + ", " + y) : "NONE");
foreach (var child in treeNode.Children)
}
private SpanningTreeNode ClosestTo(Node node, SpanningTreeNode treeNode)
{
SpanningTreeNode closest = treeNode;
float distance = Vector3.Distance(treeNode.Node.transform.position, node.transform.position);
foreach (var child in treeNode.Children)
{
var closestChild = ClosestTo(node, child);
float childDistance = Vector3.Distance(closestChild.Node.transform.position, node.transform.position);
if (childDistance < distance)
{
closest = closestChild;
distance = childDistance;
}
}
return closest;
}
private SpanningTreeNode Find(string name)
{
var treeNode = Find(name, _root);
if (treeNode == null)
{
_log.Write("Could not find node with name ", name);
}
return treeNode;
}
private SpanningTreeNode Find(string name, SpanningTreeNode treeNode)
{
if (treeNode.Node.name == name) return treeNode;
foreach (var child in treeNode.Children)
{
var childResult = Find(name, child);
if (childResult != null)
{
return childResult;
}
}
return null;
}
// Using 'name' instead of node or treeNode here lets us go back and forth between the two mostly seamlessly
private bool Contains(string name)
{
return Contains(name, _root);
}
private bool Contains(string name, SpanningTreeNode treeNode)
{
if (treeNode.Node.name == name) return true;
bool childContains = false;
foreach (var child in treeNode.Children)
{
if (Contains(name, child))
{
childContains = true;
}
}
return childContains;
}
}
}