Network Know-How: Exploring Network Algorithms

etworks can be very interesting objects to study. They can represent obvious physical systems such as street, telephone, and electric networks. They can also represent less obvious arrangements of data that let you schedule complex tasks, assign jobs to employees, and find critical tasks that can delay a large project.

The first article in this series explained how to build networks and find the shortest paths between two points in the network.

This article describes four other network algorithms: traversal, minimal spanning trees, maximal flow, and minimal flow cut.

Traversal
The goal of a traversal algorithm is to move through the network visiting each node that is reachable from a particular start node. When you visit a node, you might perform some task, such as listing the node, examining it for a particular piece of data, and so forth.

Figure 1 shows the NetAlgs example program, available with the downloadable code for this article in Visual Basic and C# versions. This program demonstrates all the algorithms described in this article. In Figure 1, the output shows the result of traversing a network starting from node B. Each time the program visited a node, it changed the node's caption to lower case and changed the node's background color to pink. (The numbers on the links between the nodes indicate their costs. Those aren't needed for traversal.)

Figure 1. Terrific Traversal: When it visits a node, program NetAlgs changes the node's caption to lower case and gives it a pink background.

The network shown in Figure 1 is directed (you can only cross a link in the direction of the arrows) so you cannot reach every node if you start at node B. In this example, there are no paths through the network from node B to nodes A, C, H, I, or J so they were not visited.

There are many reasons why you might want to traverse a network. For example, you might simply want to know if you can reach a node from the start node. Consider a complex campus phone network: You want to ensure that it can connect every building to every other building. Assuming all the links are non-directional (calls can travel both ways across the link), you can check by traversing the network, starting from any node and ensuring that you can reach every other node.

As another example, suppose you have two computer networks: a secure internal network and an external network that connects to the Internet. You want to be sure that the two networks are separate, so the internal network is safe from attack by cyber-banditos. In this scenario, by traversing the network starting from any internal node, you should not be able to reach any external node.

As a final example, you can also use a traversal to determine whether the maze of one-way streets in downtown Boston will let you get to your destination—or whether the old New England saying, "Ya can't get theah from heah" is true.

Basic network traversal is relatively easy. The procedure is:

1. Start at a selected root node.
2. Visit the node.
3. Follow each of the node's links to recursively visit the node's neighboring nodes.

The only trick to the algorithm is that you need to be careful not to follow the links in a closed loop; otherwise, you'll enter an infinite loop that follows the same series of links repeatedly

To avoid infinite loops, you can simply mark each node that you visit. For example, you can give the node class an IsMarked property and set it to True when you visit a node. Now when you examine a node's links in step 3, you don't visit any neighboring node that is already marked.

Here's the revised algorithm:

1. Start at a selected root node.
2. Visit the node and mark it.
3. Follow each of the node's links to recursively visit the node's unmarked neighboring nodes.

When the algorithm completes, all the visited nodes are marked. To reset the network, the program should unmark those nodes. It can either repeat the algorithm again, this time visiting only those nodes for which IsMarked is True, setting it to False as it goes, or it can simply loop through a list of every node in the network unmarking them.

The NetAlgs example program uses the following code to traverse its network:

   ' Traverse executes this kind of routine on each node.
   Public Delegate Sub TraversalSub(ByVal node As PathNode)
   
   ' Traverse the network starting at this node.
   Public Sub Traverse(ByVal clicked_node As PathNode, _
      ByVal traversal_sub As TraversalSub)
   
       ' Traverse the network.
       If clicked_node Is Nothing Then Exit Sub
       clicked_node.Traverse(traversal_sub)
   
       ' Unmark all nodes.
       For Each node As PathNode In AllNodes
           node.IsMarked = False
       Next node
   End Sub

The code first declares the TraversalSub delegate type, which defines the type of method that you must pass to the Traverse method. Each time it visits a node, the program calls the TraversalSub method for that node. That lets the main program do whatever it wants with the nodes without the Network class having to know anything about the details.

The Traverse subroutine performs the traversal. It takes as parameters the node where the traversal should start (node B in Figure 1), and the TraversalSub delegate it should call for each node visited.

The code does most of its work by calling the start node's Traverse method. It finishes by looping through all the nodes in the AllNodes list and resetting their IsMarked flags. Here's the PathNode class's Traverse method:

   ' Traverse the network from this node.
   Public Sub Traverse(ByVal traversal_sub As Network.TraversalSub)
       ' Mark the node as visited.
       IsMarked = True
   
       ' Execute the traversal routine on this node.
       traversal_sub(Me)
   
       ' Visit neighbors.
       For Each link As PathLink In Links
           Dim nbr As PathNode = link.ToNode
           If Not nbr.IsMarked Then
               nbr.Traverse(traversal_sub)
           End If
       Next link
   End Sub

The method starts by marking the current node as visited. It then calls the traversal subroutine, passing the current node as a parameter. This is where the main program does whatever it wants to the node (NetAlgs changes the node's caption and background color).

The Traverse method then loops through the node's links and examines its neighboring nodes. If a neighbor node is not marked, the routine calls that node's Traverse method.

The following code shows the ChangedNodeCaption subroutine defined by the NetAlgs main program. This routine takes a PathNode object as a parameter. It simply changes the node's background color to pink and its label to lower case.

   ' This is the method performed on each node during traversal.
   Public Sub ChangeNodeCaption(ByVal node As PathNode)
       node.EllipseBrush = Brushes.Pink
       node.Label = node.Label.ToLower()
   End Sub

Finally, the following code shows how the program calls the Network object's Traverse method. It passes the node that the user clicked and the address of the ChangeNodeCaption subroutine.

   m_Network.Traverse(clicked_node, AddressOf ChangeNodeCaption)