Section 5 - The FHedge

10A.5.1 The FHedge Overview

I know what you're thinking. "He just spent a lot of advertizing dollars convincing us that we did not need a separate edge data structure in our graphs. So why is he starting up with FHedge?"

FHedge is not actually part of the graph data structure. As promised, the graph will only contain the vertices whose adjacency lists represent the edges without actually being edges. However, it is convenient to create a simple FHedge data structure that can be used by the graph and its algorithms in two ways:

1. FHedge will assist us in the process of building a graph from client-supplied edge data.
2. We will build FHedges and store them in temporary data structures during the implementation of the algorithms.

An edge, when viewed in isolation, does need both the source and destination vertices. It also needs the cost. It also needs a < operator (naturally, the cost of the edge will determine how "big" it is) so we can use it in priority_queues. We'll also add a > operator for convenience. That is exactly and only what our FHedge template class will contain.

10A.5.2 The FHedge Class Template

It is so short, I can just list it up front and talk about it after. Please skim this now:

template <class Object, typename CostType>
class FHedge
{
   // internal typedefs to simplify syntax
   typedef FHvertex<Object, CostType> Vertex;
   typedef FHvertex<Object, CostType>* VertPtr;

public:
   VertPtr source, dest;
   CostType cost;
 
   FHedge( 
      VertPtr src = NULL, 
      VertPtr dst = NULL,
      CostType cst = 1 )
      : source(src), dest(dst), cost(cst) 
      { }
   bool operator<( const FHedge & rhs) const
   {
      return (cost < rhs.cost);
   }
   // needed so we can use greater() rather than less() in STL::priority_queue
   bool operator>( const FHedge & rhs) const
   {
      return (cost > rhs.cost);
   }
};

The data are source, dest and cost. Again, we use VertPtrs to reference the FHvertex objects indirectly, rather than keeping bulky and troublesome internal copies in the edge structure.

The constructor sets the data, mindlessly.

There are two operators, < and >. It will be important in graph algorithms to find the smallest or largest edge in a set of edges. Smallest and largest will always refer to the edge costs. Normally, we only need to supply < since every data structure we have ever encountered can use that to make any and all decisions. However, we have a slight problem. The STL priority_queue always removes the largest element, not the smallest, and as we saw last week, to override that behavior, we have to supply a different compare function. This is most easily done by defining > and, when we instantiate ("specialize") the priority_queue, pass it the functor greater(). This is why I spent a little time showing you how that was done. Now you can at least understand the purpose of defining >, even if you don't quite see the exact use for it yet. You will be entertained, though, when this little maneuver is revealed.

That's FHedge. A simple yet powerful template that we will use in the ultimate class FHgraph. And now it is time to present the main course.