I have attached a minimal working program to test the sort function on a list of edges.
Compile with : g++ -O3 prog.cpp -o prog

The problem is line "myList.sort(SortByName< graph_t <edge_t> >);" near the bottom of the page.
See comments.

//=======================================================================
// Sort Testing Program - prog.cpp
//=======================================================================

#include <iostream>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>

using namespace boost;
using namespace std;

  struct vertex_properties
  {
       
  };

  struct edge_properties
  {
        string eName;
  };


  typedef adjacency_list < vecS, vecS, bidirectionalS >::edge_descriptor edge_t;
  typedef adjacency_list < vecS, vecS, bidirectionalS >::vertex_descriptor vertex_t;
  typedef adjacency_list < vecS, vecS, bidirectionalS, vertex_properties, edge_properties > graph_t;


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

  template < typename Graph >
    void add_edges(Graph & g)
  { // Add some edges with names.

    typename graph_traits<Graph>::edge_iterator edge_iter, edges_end;

    std::pair< typename graph_traits<Graph>::edge_descriptor, bool > a = add_edge(1,2,g); g[a.first].eName = "A";
    std::pair< typename graph_traits<Graph>::edge_descriptor, bool > b = add_edge(1,3,g); g[b.first].eName = "B";
    std::pair< typename graph_traits<Graph>::edge_descriptor, bool > c = add_edge(2,1,g); g[c.first].eName = "C";
    std::pair< typename graph_traits<Graph>::edge_descriptor, bool > d = add_edge(2,3,g); g[d.first].eName = "D";

    cout << endl << " list of edges " << endl;
    for (tie(edge_iter, edges_end) = edges(g); edge_iter != edges_end; ++edge_iter)
          cout <<  " " << g[*edge_iter].eName << endl;

}


  template < typename Graph >
    struct SortByName
 { // The Predicate

      template < typename edge_t >
        bool operator()(const edge_t& a, const edge_t& b) const
      {
        return g[a].eName < g[b].eName;
      }

   
    Graph g;

 };


  template < typename Graph >
    void Sort_Test(Graph & g)
  { // Test the sort function.

    typedef std::list<graph_traits<graph_t>::edge_descriptor> edge_list;
    typename graph_traits<Graph>::edge_iterator edge_iter, edges_end;

    edge_list myList;

    // Load myList with the edges of g
    for (tie(edge_iter, edges_end) = edges(g); edge_iter != edges_end; ++edge_iter)
        myList.push_back(*edge_iter);
       
    // Write out myList
    cout << endl << " myList " << endl;
    for (edge_list::iterator i = myList.begin(); i != myList.end(); ++i)
          cout <<  " " << g[*i].eName << endl;

    // Sort myList
    // If the following line is commented out the program compiles and runs OK.
    myList.sort(SortByName< graph_t <edge_t> >);
    //With the above line uncommented the compiler says:
    // "prog.cpp:88: error: ‘graph_t’ is not a template" -- I'm stumped.

 }


  int main()
  {

      graph_t g;

    add_edges(g);

    Sort_Test(g);
           
  }