COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 100:4f754b4cf82b in lemon


Ignore:
Timestamp:
02/07/08 22:37:07 (17 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Bfs/Dfs/Dijkstra? and their deps ported from svn trung -r 3441.

Files:
11 added
4 edited

Legend:

Unmodified
Added
Removed

  • lemon/Makefile.am

    r99 r100  
    1616
    1717lemon_HEADERS += \
    18         lemon/concept_check.h \
     18        lemon/bfs.h \
     19        lemon/bin_heap.h \
     20        lemon/dfs.h \
     21        lemon/dijkstra.h \
    1922        lemon/dim2.h \
    2023        lemon/error.h \
     24        lemon/graph_utils.h \
    2125        lemon/list_graph.h \
    2226        lemon/maps.h \
    … …  
    3337        lemon/bits/invalid.h \
    3438        lemon/bits/map_extender.h \
     39        lemon/bits/path_dump.h \
    3540        lemon/bits/traits.h \
    3641        lemon/bits/utility.h \
    … …  
    4146        lemon/concepts/digraph.h \
    4247        lemon/concepts/graph.h \
     48        lemon/concepts/heap.h \
    4349        lemon/concepts/maps.h \
    4450        lemon/concepts/path.h \

  • lemon/path.h

    r98 r100  
    3030#include <lemon/error.h>
    3131#include <lemon/bits/invalid.h>
     32#include <lemon/concepts/path.h>
    3233
    3334namespace lemon {

  • test/Makefile.am

    r99 r100  
    44noinst_HEADERS += \
    55        test/digraph_test.h \
     6        test/heap_test.h \
    67        test/map_test.h \
    78        test/test_tools.h
    89
    910check_PROGRAMS += \
     11        test/bfs_test \
     12        test/dfs_test \
    1013        test/digraph_test \
    1114        test/dim_test \
    … …  
    2023XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    2124
     25test_bfs_test_SOURCES = test/bfs_test.cc
     26test_dfs_test_SOURCES = test/dfs_test.cc
    2227test_digraph_test_SOURCES = test/digraph_test.cc
    2328test_dim_test_SOURCES = test/dim_test.cc
    2429#test_error_test_SOURCES = test/error_test.cc
    2530test_graph_test_SOURCES = test/graph_test.cc
     31# test_heap_test_SOURCES = test/heap_test.cc
    2632test_maps_test_SOURCES = test/maps_test.cc
    2733test_path_test_SOURCES = test/path_test.cc

  • test/test_tools.h

    r39 r100  
    2121
    2222#include <iostream>
     23#include <vector>
     24
     25#include <cstdlib>
     26#include <ctime>
     27
     28#include <lemon/concept_check.h>
     29#include <lemon/concepts/digraph.h>
     30
     31#include <lemon/random.h>
     32
     33using namespace lemon;
    2334
    2435//! \ingroup misc
    … …  
    3748///\code check(0==1,"This is obviously false.");\endcode will
    3849///print this (and then exits).
    39 ///\verbatim graph_test.cc:123: error: This is obviously false. \endverbatim
     50///\verbatim digraph_test.cc:123: error: This is obviously false. \endverbatim
    4051///
    4152///\todo It should be in \c error.h
    … …  
    4657  } else { } \
    4758
     59///Structure returned by \ref addPetersen().
     60
     61///Structure returned by \ref addPetersen().
     62///
     63template<class Digraph> struct PetStruct
     64{
     65  ///Vector containing the outer nodes.
     66  std::vector<typename Digraph::Node> outer;
     67  ///Vector containing the inner nodes.
     68  std::vector<typename Digraph::Node> inner;
     69  ///Vector containing the arcs of the inner circle.
     70  std::vector<typename Digraph::Arc> incir;
     71  ///Vector containing the arcs of the outer circle.
     72  std::vector<typename Digraph::Arc> outcir;
     73  ///Vector containing the chord arcs.
     74  std::vector<typename Digraph::Arc> chords;
     75};
     76
     77
     78
     79///Adds a Petersen digraph to \c G.
     80
     81///Adds a Petersen digraph to \c G.
     82///\return The nodes and arcs of the generated digraph.
     83
     84template<typename Digraph>
     85PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
     86{
     87  PetStruct<Digraph> n;
     88
     89  for(int i=0;i<num;i++) {
     90    n.outer.push_back(G.addNode());
     91    n.inner.push_back(G.addNode());
     92  }
     93
     94 for(int i=0;i<num;i++) {
     95   n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
     96   n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
     97   n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
     98  }
     99 return n;
     100}
     101
     102/// \brief Adds to the digraph the reverse pair of all arcs.
     103///
     104/// Adds to the digraph the reverse pair of all arcs.
     105///
     106template<class Digraph> void bidirDigraph(Digraph &G)
     107{
     108  typedef typename Digraph::Arc Arc;
     109  typedef typename Digraph::ArcIt ArcIt;
     110 
     111  std::vector<Arc> ee;
     112 
     113  for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
     114
     115  for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++)
     116    G.addArc(G.target(*p),G.source(*p));
     117}
     118
     119
     120/// \brief Checks the bidirectioned Petersen digraph.
     121///
     122///  Checks the bidirectioned Petersen digraph.
     123///
     124template<class Digraph> void checkBidirPetersen(Digraph &G, int num = 5)
     125{
     126  typedef typename Digraph::Node Node;
     127
     128  typedef typename Digraph::ArcIt ArcIt;
     129  typedef typename Digraph::NodeIt NodeIt;
     130
     131  checkDigraphNodeList(G, 2 * num);
     132  checkDigraphArcList(G, 6 * num);
     133
     134  for(NodeIt n(G);n!=INVALID;++n) {
     135    checkDigraphInArcList(G, n, 3);
     136    checkDigraphOutArcList(G, n, 3);
     137  } 
     138}
     139
     140///Structure returned by \ref addUPetersen().
     141
     142///Structure returned by \ref addUPetersen().
     143///
     144template<class Digraph> struct UPetStruct
     145{
     146  ///Vector containing the outer nodes.
     147  std::vector<typename Digraph::Node> outer;
     148  ///Vector containing the inner nodes.
     149  std::vector<typename Digraph::Node> inner;
     150  ///Vector containing the arcs of the inner circle.
     151  std::vector<typename Digraph::Edge> incir;
     152  ///Vector containing the arcs of the outer circle.
     153  std::vector<typename Digraph::Edge> outcir;
     154  ///Vector containing the chord arcs.
     155  std::vector<typename Digraph::Edge> chords;
     156};
     157
     158///Adds a Petersen digraph to the undirected \c G.
     159
     160///Adds a Petersen digraph to the undirected \c G.
     161///\return The nodes and arcs of the generated digraph.
     162
     163template<typename Digraph>
     164UPetStruct<Digraph> addUPetersen(Digraph &G,int num=5)
     165{
     166  UPetStruct<Digraph> n;
     167
     168  for(int i=0;i<num;i++) {
     169    n.outer.push_back(G.addNode());
     170    n.inner.push_back(G.addNode());
     171  }
     172
     173 for(int i=0;i<num;i++) {
     174   n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
     175   n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1)%5]));
     176   n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2)%5]));
     177 }
     178 return n;
     179}
     180
    48181#endif
Note: See TracChangeset for help on using the changeset viewer.