RhodeCode

The authors of the 1.x series are

 * Balazs Dezso <deba@inf.elte.hu>

 * Alpar Juttner <alpar@cs.elte.hu>

 * Peter Kovacs <kpeter@inf.elte.hu>

 * Akos Ladanyi <ladanyi@tmit.bme.hu>

For more details on the actual contribution, please visit the history

of the main LEMON source repository: http://lemon.cs.elte.hu/hg/lemon

Moreover, this version is heavily based on the 0.x series of

LEMON. Here is the list of people who contributed to those versions.

 * Mihaly Barasz <klao@cs.elte.hu>

 * Johanna Becker <beckerjc@cs.elte.hu>

 * Attila Bernath <athos@cs.elte.hu>

 * Balazs Dezso <deba@inf.elte.hu>

 * Peter Hegyi <hegyi@tmit.bme.hu>

 * Alpar Juttner <alpar@cs.elte.hu>

 * Peter Kovacs <kpeter@inf.elte.hu>

 * Akos Ladanyi <ladanyi@tmit.bme.hu>

 * Marton Makai <marci@cs.elte.hu>

 * Jacint Szabo <jacint@cs.elte.hu>

Again, please visit the history of the old LEMON repository for more

a header line. The header lines starts with an \c '@' character followed by the

type of section. The standard section types are \c \@nodes, \c

\@arcs and \c \@edges

and \@attributes. Each header line may also have an optional

\e name, which can be use to distinguish the sections of the same

type.

The standard sections are column oriented, each line consists of

<em>token</em>s separated by whitespaces. A token can be \e plain or

\e quoted. A plain token is just a sequence of non-whitespace characters,

while a quoted token is a

character sequence surrounded by double quotes, and it can also

contain whitespaces and escape sequences.

The \c \@nodes section describes a set of nodes and associated

maps. The first is a header line, its columns are the names of the

maps appearing in the following lines.

One of the maps must be called \c

"label", which plays special role in the file.

The following

non-empty lines until the next section describes nodes of the

graph. Each line contains the values of the node maps

associated to the current node.

\code

 @nodes

 label  coordinates  size    title

 1      (10,20)      10      "First node"

 2      (80,80)      8       "Second node"

 3      (40,10)      10      "Third node"

\endcode

values. The source and target tokens must be node labels.

\code

 @arcs

         capacity

 1   2   16

 1   3   12

 2   3   18

\endcode

The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can

also store the edge set of an undirected graph. In such case there is

a conventional method for store arc maps in the file, if two columns

can be regarded as the values of an arc map.

The \c \@attributes section contains key-value pairs, each line

consists of two tokens, an attribute name, and then an attribute

value. The value of the attribute could be also a label value of a

node or an edge, or even an edge label prefixed with \c '+' or \c '-',

which regards to the forward or backward directed arc of the

corresponding edge.

\code

 @attributes

 source 1

 target 3

 caption "LEMON test digraph"

\endcode

The \e LGF can contain extra sections, but there is no restriction on

the format of such sections.

*/

}

//  LocalWords:  whitespace whitespaces

EXTRA_DIST += \

	lemon/lemon.pc.in \

	lemon/CMakeLists.txt \

	lemon/config.h.cmake

pkgconfig_DATA += lemon/lemon.pc

lib_LTLIBRARIES += lemon/libemon.la

lemon_libemon_la_SOURCES = \

	lemon/arg_parser.cc \

	lemon/base.cc \

	lemon/color.cc \

	lemon/lp_base.cc \

	lemon/lp_skeleton.cc \

	lemon/random.cc \

	lemon/bits/windows.cc

nodist_lemon_HEADERS = lemon/config.h	

lemon_libemon_la_CXXFLAGS = \

	$(AM_CXXFLAGS) \

	$(GLPK_CFLAGS) \

	$(CPLEX_CFLAGS) \

	$(SOPLEX_CXXFLAGS) \

	$(CLP_CXXFLAGS) \

	$(CBC_CXXFLAGS)

lemon_libemon_la_LDFLAGS = \

	$(GLPK_LIBS) \

	$(CPLEX_LIBS) \

	$(SOPLEX_LIBS) \

	$(CLP_LIBS) \

	$(CBC_LIBS)

#define LEMON_BITS_PATH_DUMP_H

#include <lemon/core.h>

#include <lemon/concept_check.h>

namespace lemon {

  template <typename _Digraph, typename _PredMap>

  class PredMapPath {

  public:

    typedef True RevPathTag;

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    typedef _PredMap PredMap;

    PredMapPath(const Digraph& _digraph, const PredMap& _predMap,

                typename Digraph::Node _target)

      : digraph(_digraph), predMap(_predMap), target(_target) {}

    int length() const {

      int len = 0;

      typename Digraph::Node node = target;

      typename Digraph::Arc arc;

      while ((arc = predMap[node]) != INVALID) {

        node = digraph.source(arc);

        ++len;

      }

      return len;

    }

    bool empty() const {

    }

    class RevArcIt {

    public:

      RevArcIt() {}

      RevArcIt(Invalid) : path(0), current(INVALID) {}

      RevArcIt(const PredMapPath& _path)

        : path(&_path), current(_path.target) {

        if (path->predMap[current] == INVALID) current = INVALID;

      }

      operator const typename Digraph::Arc() const {

        return path->predMap[current];

      }

      RevArcIt& operator++() {

        current = path->digraph.source(path->predMap[current]);

        if (path->predMap[current] == INVALID) current = INVALID;

        return *this;

      }

      bool operator==(const RevArcIt& e) const {

        return current == e.current;

      }

      bool operator!=(const RevArcIt& e) const {

        return current != e.current;

      }

      bool operator<(const RevArcIt& e) const {

        return current < e.current;

      }

    typename Digraph::Node target;

  };

  template <typename _Digraph, typename _PredMatrixMap>

  class PredMatrixMapPath {

  public:

    typedef True RevPathTag;

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    typedef _PredMatrixMap PredMatrixMap;

    PredMatrixMapPath(const Digraph& _digraph,

                      const PredMatrixMap& _predMatrixMap,

                      typename Digraph::Node _source,

                      typename Digraph::Node _target)

      : digraph(_digraph), predMatrixMap(_predMatrixMap),

        source(_source), target(_target) {}

    int length() const {

      int len = 0;

      typename Digraph::Node node = target;

      typename Digraph::Arc arc;

      while ((arc = predMatrixMap(source, node)) != INVALID) {

        node = digraph.source(arc);

        ++len;

      }

      return len;

    }

    bool empty() const {

    }

    class RevArcIt {

    public:

      RevArcIt() {}

      RevArcIt(Invalid) : path(0), current(INVALID) {}

      RevArcIt(const PredMatrixMapPath& _path)

        : path(&_path), current(_path.target) {

        if (path->predMatrixMap(path->source, current) == INVALID)

          current = INVALID;

      }

      operator const typename Digraph::Arc() const {

        return path->predMatrixMap(path->source, current);

      }

      RevArcIt& operator++() {

        current =

          path->digraph.source(path->predMatrixMap(path->source, current));

        if (path->predMatrixMap(path->source, current) == INVALID)

          current = INVALID;

        return *this;

      }

      bool operator==(const RevArcIt& e) const {

        return current == e.current;

      }

      bool operator!=(const RevArcIt& e) const {

        return current != e.current;

      }

        for (ItemIt it(digraph); it != INVALID; ++it) {

          _map.set(it, refMap[it]);

        }

      }

    private:

      Ref& _map;

    };

    template <typename Digraph, typename Item, typename RefMap,

              typename CrossRef>

    class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {

    public:

      CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}

      virtual void copy(const Digraph& digraph, const RefMap& refMap) {

        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;

        for (ItemIt it(digraph); it != INVALID; ++it) {

          _cmap.set(refMap[it], it);

        }

      }

    private:

      CrossRef& _cmap;

    };

    template <typename Digraph, typename Enable = void>

    struct DigraphCopySelector {

      template <typename From, typename NodeRefMap, typename ArcRefMap>

      static void copy(const From& from, Digraph &to,

                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {

        for (typename From::NodeIt it(from); it != INVALID; ++it) {

          nodeRefMap[it] = to.addNode();

        }

        for (typename From::ArcIt it(from); it != INVALID; ++it) {

          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],

                                    nodeRefMap[from.target(it)]);

        }

      }

    };

    template <typename Digraph>

    struct DigraphCopySelector<

      Digraph,

      typename enable_if<typename Digraph::BuildTag, void>::type>

    {

      template <typename From, typename NodeRefMap, typename ArcRefMap>

      static void copy(const From& from, Digraph &to,

                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {

        to.build(from, nodeRefMap, arcRefMap);

      }

    };

    template <typename Graph, typename Enable = void>

    struct GraphCopySelector {

      template <typename From, typename NodeRefMap, typename EdgeRefMap>

      static void copy(const From& from, Graph &to,

                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {

        for (typename From::NodeIt it(from); it != INVALID; ++it) {

          nodeRefMap[it] = to.addNode();

        }

        for (typename From::EdgeIt it(from); it != INVALID; ++it) {

          edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],

                                      nodeRefMap[from.v(it)]);

        }

      }

    };

    template <typename Graph>

    struct GraphCopySelector<

      Graph,

      typename enable_if<typename Graph::BuildTag, void>::type>

    {

      template <typename From, typename NodeRefMap, typename EdgeRefMap>

      static void copy(const From& from, Graph &to,

                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {

        to.build(from, nodeRefMap, edgeRefMap);

      }

    };

  }

  /// \brief Class to copy a digraph.

  ///

  /// Class to copy a digraph to another digraph (duplicate a digraph). The

  /// simplest way of using it is through the \c digraphCopy() function.

  ///

  /// This class not only make a copy of a digraph, but it can create

  /// references and cross references between the nodes and arcs of

  /// the two digraphs, and it can copy maps to use with the newly created

    ///- the %DFS tree,

    ///- the distance of each node from the root in the %DFS tree.

    ///

    ///\pre init() must be called and a root node should be

    ///added with addSource() before using this function.

    ///

    ///\note <tt>d.start()</tt> is just a shortcut of the following code.

    ///\code

    ///  while ( !d.emptyQueue() ) {

    ///    d.processNextArc();

    ///  }

    ///\endcode

    void start()

    {

      while ( !emptyQueue() ) processNextArc();

    }

    ///Executes the algorithm until the given target node is reached.

    ///Executes the algorithm until the given target node is reached.

    ///

    ///This method runs the %DFS algorithm from the root node

    ///in order to compute the DFS path to \c t.

    ///

    ///The algorithm computes

    ///- the %DFS path to \c t,

    ///- the distance of \c t from the root in the %DFS tree.

    ///

    ///\pre init() must be called and a root node should be

    ///added with addSource() before using this function.

    void start(Node t)

    {

        processNextArc();

    }

    ///Executes the algorithm until a condition is met.

    ///Executes the algorithm until a condition is met.

    ///

    ///This method runs the %DFS algorithm from the root node

    ///until an arc \c a with <tt>am[a]</tt> true is found.

    ///

    ///\param am A \c bool (or convertible) arc map. The algorithm

    ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true.

    ///

    ///\return The reached arc \c a with <tt>am[a]</tt> true or

    ///\c INVALID if no such arc was found.

    ///

    ///\pre init() must be called and a root node should be

    ///added with addSource() before using this function.

    ///

    ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,

    ///not a node map.

    template<class ArcBoolMap>

    Arc start(const ArcBoolMap &am)

    {

      while ( !emptyQueue() && !am[_stack[_stack_head]] )

        processNextArc();

      return emptyQueue() ? INVALID : _stack[_stack_head];

    }

    ///Runs the algorithm from the given source node.

    ///This method runs the %DFS algorithm from node \c s

    ///

    /// The algorithm computes

    /// - the %DFS tree,

    /// - the distance of each node from the root in the %DFS tree.

    ///

    /// \pre init() must be called and a root node should be

    /// added with addSource() before using this function.

    ///

    /// \note <tt>d.start()</tt> is just a shortcut of the following code.

    /// \code

    ///   while ( !d.emptyQueue() ) {

    ///     d.processNextArc();

    ///   }

    /// \endcode

    void start() {

      while ( !emptyQueue() ) processNextArc();

    }

    /// \brief Executes the algorithm until the given target node is reached.

    ///

    /// Executes the algorithm until the given target node is reached.

    ///

    /// This method runs the %DFS algorithm from the root node

    /// in order to compute the DFS path to \c t.

    ///

    /// The algorithm computes

    /// - the %DFS path to \c t,

    /// - the distance of \c t from the root in the %DFS tree.

    ///

    /// \pre init() must be called and a root node should be added

    /// with addSource() before using this function.

    void start(Node t) {

        processNextArc();

    }

    /// \brief Executes the algorithm until a condition is met.

    ///

    /// Executes the algorithm until a condition is met.

    ///

    /// This method runs the %DFS algorithm from the root node

    /// until an arc \c a with <tt>am[a]</tt> true is found.

    ///

    /// \param am A \c bool (or convertible) arc map. The algorithm

    /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true.

    ///

    /// \return The reached arc \c a with <tt>am[a]</tt> true or

    /// \c INVALID if no such arc was found.

    ///

    /// \pre init() must be called and a root node should be added

    /// with addSource() before using this function.

    ///

    /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,

    /// not a node map.

    template <typename AM>

    Arc start(const AM &am) {

      while ( !emptyQueue() && !am[_stack[_stack_head]] )

        processNextArc();

      return emptyQueue() ? INVALID : _stack[_stack_head];

    }

    /// \brief Runs the algorithm from the given source node.

    ///

    /// This method runs the %DFS algorithm from node \c s.

    /// in order to compute the DFS path to each node.

public:

  ~GraphToEps() { }

  ///Draws the graph.

  ///Like other functions using

  ///\ref named-templ-func-param "named template parameters",

  ///this function calls the algorithm itself, i.e. in this case

  ///it draws the graph.

  void run() {

    const double EPSILON=1e-9;

    if(dontPrint) return;

    _graph_to_eps_bits::_NegY<typename T::CoordsMapType>

      mycoords(_coords,_negY);

    os << "%!PS-Adobe-2.0 EPSF-2.0\n";

    if(_title.size()>0) os << "%%Title: " << _title << '\n';

     if(_copyright.size()>0) os << "%%Copyright: " << _copyright << '\n';

    os << "%%Creator: LEMON, graphToEps()\n";

    {

      os << "%%CreationDate: ";

#ifndef WIN32

      timeval tv;

      gettimeofday(&tv, 0);

      char cbuf[26];

      ctime_r(&tv.tv_sec,cbuf);

      os << cbuf;

#else

      os << bits::getWinFormattedDate();

#endif

    }

    if (_autoArcWidthScale) {

      double max_w=0;

      for(ArcIt e(g);e!=INVALID;++e)

        max_w=std::max(double(_arcWidths[e]),max_w);

      if(max_w>EPSILON) {

        _arcWidthScale/=max_w;

      }

    }

    if (_autoNodeScale) {

      double max_s=0;

      for(NodeIt n(g);n!=INVALID;++n)

        max_s=std::max(double(_nodeSizes[n]),max_s);

      if(max_s>EPSILON) {

        _nodeScale/=max_s;

      }

    }

    double diag_len = 1;

    if(!(_absoluteNodeSizes&&_absoluteArcWidths)) {

      dim2::Box<double> bb;

      for(NodeIt n(g);n!=INVALID;++n) bb.add(mycoords[n]);

      if (bb.empty()) {

        bb = dim2::Box<double>(dim2::Point<double>(0,0));

      }

      diag_len = std::sqrt((bb.bottomLeft()-bb.topRight()).normSquare());

      if(diag_len<EPSILON) diag_len = 1;

      if(!_absoluteNodeSizes) _nodeScale*=diag_len;

      if(!_absoluteArcWidths) _arcWidthScale*=diag_len;

    }

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

///\ingroup lemon_io

///\file

///\brief \ref lgf-format "LEMON Graph Format" reader.

#ifndef LEMON_LGF_READER_H

#define LEMON_LGF_READER_H

#include <iostream>

#include <fstream>

#include <sstream>

#include <set>

#include <map>

#include <lemon/core.h>

#include <lemon/lgf_writer.h>

        }

        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {

          _node_maps[i].second->set(n, tokens[map_index[i]]);

        }

      }

      if (readSuccess()) {

        line.putback(c);

      }

    }

    void readArcs() {

      std::vector<int> map_index(_arc_maps.size());

      int map_num, label_index;

      char c;

      if (!readLine() || !(line >> c) || c == '@') {

        if (readSuccess() && line) line.putback(c);

        if (!_arc_maps.empty())

          throw FormatError("Cannot find map names");

        return;

      }

      line.putback(c);

      {

        std::map<std::string, int> maps;

        std::string map;

        int index = 0;

        while (_reader_bits::readToken(line, map)) {

          if (maps.find(map) != maps.end()) {

            std::ostringstream msg;

            msg << "Multiple occurence of arc map: " << map;

            throw FormatError(msg.str());

          }

          maps.insert(std::make_pair(map, index));

          ++index;

        }

        for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {

          std::map<std::string, int>::iterator jt =

            maps.find(_arc_maps[i].first);

          if (jt == maps.end()) {

            std::ostringstream msg;

            msg << "Map not found: " << _arc_maps[i].first;

            throw FormatError(msg.str());

          }

          map_index[i] = jt->second;

        }

        {

          std::map<std::string, int>::iterator jt = maps.find("label");

          if (jt != maps.end()) {

            label_index = jt->second;

          } else {

            label_index = -1;

          }

        }

        map_num = maps.size();

      }

      while (readLine() && line >> c && c != '@') {

        }

        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {

          _node_maps[i].second->set(n, tokens[map_index[i]]);

        }

      }

      if (readSuccess()) {

        line.putback(c);

      }

    }

    void readEdges() {

      std::vector<int> map_index(_edge_maps.size());

      int map_num, label_index;

      char c;

      if (!readLine() || !(line >> c) || c == '@') {

        if (readSuccess() && line) line.putback(c);

        if (!_edge_maps.empty())

          throw FormatError("Cannot find map names");

        return;

      }

      line.putback(c);

      {

        std::map<std::string, int> maps;

        std::string map;

        int index = 0;

        while (_reader_bits::readToken(line, map)) {

          if (maps.find(map) != maps.end()) {

            std::ostringstream msg;

            msg << "Multiple occurence of edge map: " << map;

            throw FormatError(msg.str());

          }

          maps.insert(std::make_pair(map, index));

          ++index;

        }

        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {

          std::map<std::string, int>::iterator jt =

            maps.find(_edge_maps[i].first);

          if (jt == maps.end()) {

            std::ostringstream msg;

            msg << "Map not found: " << _edge_maps[i].first;

            throw FormatError(msg.str());

          }

          map_index[i] = jt->second;

        }

        {

          std::map<std::string, int>::iterator jt = maps.find("label");

          if (jt != maps.end()) {

            label_index = jt->second;

          } else {

            label_index = -1;

          }

        }

        map_num = maps.size();

      }

      while (readLine() && line >> c && c != '@') {

  ${PROJECT_SOURCE_DIR}

  ${PROJECT_BINARY_DIR}

)

LINK_DIRECTORIES(

  ${PROJECT_BINARY_DIR}/lemon

)

SET(TEST_WITH_VALGRIND "NO" CACHE STRING

  "Run the test with valgrind (YES/NO).")

SET(VALGRIND_FLAGS "" CACHE STRING "Valgrind flags used by the tests.")

SET(TESTS

  adaptors_test

  bfs_test

  circulation_test

  connectivity_test

  counter_test

  dfs_test

  digraph_test

  dijkstra_test

  dim_test

  edge_set_test

  error_test

  euler_test

  gomory_hu_test

  graph_copy_test

  graph_test

  graph_utils_test

  hao_orlin_test

  heap_test

  kruskal_test

  maps_test

  matching_test

  min_cost_arborescence_test

  min_cost_flow_test

  path_test

  preflow_test

  radix_sort_test

  random_test

  suurballe_test

  time_measure_test

  unionfind_test

)

IF(LEMON_HAVE_LP)

  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")

    ADD_EXECUTABLE(lp_test lp_test.cc)

  ELSE()

    ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc)

  ENDIF()

  SET(LP_TEST_LIBS lemon)

  IF(LEMON_HAVE_GLPK)

    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${GLPK_LIBRARIES})

  ENDIF()

  IF(LEMON_HAVE_CPLEX)

    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES})

  ENDIF()

  IF(LEMON_HAVE_CLP)

    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${COIN_CLP_LIBRARIES})

  ENDIF()

EXTRA_DIST += \

	test/CMakeLists.txt

noinst_HEADERS += \

	test/graph_test.h \

	test/test_tools.h

check_PROGRAMS += \

	test/adaptors_test \

	test/bfs_test \

	test/circulation_test \

	test/connectivity_test \

	test/counter_test \

	test/dfs_test \

	test/digraph_test \

	test/dijkstra_test \

	test/dim_test \

	test/edge_set_test \

	test/error_test \

	test/euler_test \

	test/gomory_hu_test \

	test/graph_copy_test \

	test/graph_test \

	test/graph_utils_test \

	test/hao_orlin_test \

	test/heap_test \

	test/kruskal_test \

	test/maps_test \

	test/matching_test \

	test/min_cost_arborescence_test \

	test/min_cost_flow_test \

	test/path_test \

	test/preflow_test \

	test/radix_sort_test \

	test/random_test \

	test/suurballe_test \

	test/test_tools_fail \

	test/test_tools_pass \

	test/time_measure_test \

	test/unionfind_test

test_test_tools_pass_DEPENDENCIES = demo

if HAVE_LP

check_PROGRAMS += test/lp_test

endif HAVE_LP

if HAVE_MIP

check_PROGRAMS += test/mip_test

endif HAVE_MIP

TESTS += $(check_PROGRAMS)

XFAIL_TESTS += test/test_tools_fail$(EXEEXT)

test_adaptors_test_SOURCES = test/adaptors_test.cc

test_bfs_test_SOURCES = test/bfs_test.cc

test_circulation_test_SOURCES = test/circulation_test.cc

test_counter_test_SOURCES = test/counter_test.cc

test_connectivity_test_SOURCES = test/connectivity_test.cc

test_dfs_test_SOURCES = test/dfs_test.cc

test_digraph_test_SOURCES = test/digraph_test.cc

test_dijkstra_test_SOURCES = test/dijkstra_test.cc

test_dim_test_SOURCES = test/dim_test.cc

test_edge_set_test_SOURCES = test/edge_set_test.cc