COIN-OR::LEMON - Graph Library

Changeset 1472:c3bda060cfa3 in lemon-0.x


Ignore:
Timestamp:
06/10/05 14:22:22 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1952
Message:

New EdgeSet? Adaptor

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_adaptor.h

    r1435 r1472  
    2828#include <lemon/invalid.h>
    2929#include <lemon/maps.h>
     30#include <lemon/bits/erasable_graph_extender.h>
     31#include <lemon/bits/clearable_graph_extender.h>
     32#include <lemon/bits/extendable_graph_extender.h>
    3033#include <lemon/bits/iterable_graph_extender.h>
     34#include <lemon/bits/alteration_notifier.h>
     35#include <lemon/bits/default_map.h>
    3136#include <lemon/bits/undir_graph_extender.h>
    3237#include <iostream>
     
    12111216  };
    12121217
     1218  /// \e
     1219  template <typename _Graph>
     1220  class NewEdgeSetAdaptorBase {
     1221  public:
     1222
     1223    typedef _Graph Graph;
     1224    typedef typename Graph::Node Node;
     1225    typedef typename Graph::NodeIt NodeIt;
     1226
     1227  protected:
     1228
     1229    struct NodeT {
     1230      int first_out, first_in;
     1231      NodeT() : first_out(-1), first_in(-1) {}
     1232    };
     1233   
     1234    class NodesImpl : protected Graph::template NodeMap<NodeT> {
     1235
     1236      typedef typename Graph::template NodeMap<NodeT> Parent;
     1237      typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
     1238
     1239      Adaptor& adaptor;
     1240
     1241    public:
     1242
     1243      NodesImpl(Adaptor& _adaptor, const Graph& _graph)
     1244        : Parent(_graph), adaptor(_adaptor) {}
     1245
     1246      virtual ~NodesImpl() {}
     1247
     1248      virtual void build() {
     1249        Parent::build();
     1250      }
     1251
     1252      virtual void clear() {
     1253        adaptor._clear();
     1254        Parent::clear();
     1255      }
     1256     
     1257      virtual void add(const Node& node) {
     1258        Parent::add(node);
     1259        adaptor._add(node);
     1260      }
     1261     
     1262      virtual void erase(const Node& node) {
     1263        adaptor._erase(node);
     1264        Parent::erase(node);
     1265      }
     1266
     1267      NodeT& operator[](const Node& node) {
     1268        return Parent::operator[](node);
     1269      }
     1270
     1271      const NodeT& operator[](const Node& node) const {
     1272        return Parent::operator[](node);
     1273      }
     1274     
     1275    };
     1276
     1277    NodesImpl* nodes;
     1278
     1279    struct EdgeT {
     1280      Node source, target;
     1281      int next_out, next_in;
     1282      int prev_out, prev_in;
     1283      EdgeT() : prev_out(-1), prev_in(-1) {}
     1284    };
     1285
     1286    std::vector<EdgeT> edges;
     1287
     1288    int first_edge;
     1289    int first_free_edge;
     1290
     1291    virtual void _clear() = 0;
     1292    virtual void _add(const Node& node) = 0;
     1293    virtual void _erase(const Node& node) = 0;
     1294   
     1295    const Graph* graph;
     1296
     1297    void initalize(const Graph& _graph, NodesImpl& _nodes) {
     1298      graph = &_graph;
     1299      nodes = &_nodes;
     1300    }
     1301   
     1302  public:
     1303
     1304    class Edge {
     1305      friend class NewEdgeSetAdaptorBase<Graph>;
     1306    protected:
     1307      Edge(int _id) : id(_id) {}
     1308      int id;
     1309    public:
     1310      Edge() {}
     1311      Edge(Invalid) : id(-1) {}
     1312      bool operator==(const Edge& edge) const { return id == edge.id; }
     1313      bool operator!=(const Edge& edge) const { return id != edge.id; }
     1314      bool operator<(const Edge& edge) const { return id < edge.id; }
     1315    };
     1316
     1317    NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {}
     1318    virtual ~NewEdgeSetAdaptorBase() {}
     1319
     1320    Edge addEdge(const Node& source, const Node& target) {
     1321      int n;
     1322      if (first_free_edge == -1) {
     1323        n = edges.size();
     1324        edges.push_back(EdgeT());
     1325      } else {
     1326        n = first_free_edge;
     1327        first_free_edge = edges[first_free_edge].next_in;
     1328      }
     1329      edges[n].next_in = (*nodes)[target].first_in;
     1330      (*nodes)[target].first_in = n;
     1331      edges[n].next_out = (*nodes)[source].first_out;
     1332      (*nodes)[source].first_out = n;
     1333      edges[n].source = source;
     1334      edges[n].target = target;
     1335      return Edge(n);
     1336    }
     1337
     1338    void erase(const Edge& edge) {
     1339      int n = edge.id;
     1340      if (edges[n].prev_in != -1) {
     1341        edges[edges[n].prev_in].next_in = edges[n].next_in;
     1342      } else {
     1343        (*nodes)[edges[n].target].first_in = edges[n].next_in;
     1344      }
     1345      if (edges[n].next_in != -1) {
     1346        edges[edges[n].next_in].prev_in = edges[n].prev_in;
     1347      }
     1348
     1349      if (edges[n].prev_out != -1) {
     1350        edges[edges[n].prev_out].next_out = edges[n].next_out;
     1351      } else {
     1352        (*nodes)[edges[n].source].first_out = edges[n].next_out;
     1353      }
     1354      if (edges[n].next_out != -1) {
     1355        edges[edges[n].next_out].prev_out = edges[n].prev_out;
     1356      }
     1357           
     1358    }
     1359
     1360    void first(Node& node) const {
     1361      graph->first(node);
     1362    }
     1363
     1364    void next(Node& node) const {
     1365      graph->next(node);
     1366    }
     1367
     1368    void first(Edge& edge) const {
     1369      Node node;
     1370      for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
     1371           next(node));
     1372      edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
     1373    }
     1374
     1375    void next(Edge& edge) const {
     1376      if (edges[edge.id].next_in != -1) {
     1377        edge.id = edges[edge.id].next_in;
     1378      } else {
     1379        Node node = edges[edge.id].target;
     1380        for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
     1381             next(node));
     1382        edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
     1383      }     
     1384    }
     1385
     1386    void firstOut(Edge& edge, const Node& node) const {
     1387      edge.id = (*nodes)[node].first_out;   
     1388    }
     1389   
     1390    void nextOut(Edge& edge) const {
     1391      edge.id = edges[edge.id].next_out;       
     1392    }
     1393
     1394    void firstIn(Edge& edge, const Node& node) const {
     1395      edge.id = (*nodes)[node].first_in;         
     1396    }
     1397
     1398    void nextIn(Edge& edge) const {
     1399      edge.id = edges[edge.id].next_in;   
     1400    }
     1401
     1402    int id(const Node& node) const { return graph->id(node); }
     1403    int id(const Edge& edge) const { return edge.id; }
     1404
     1405    Node fromId(int id, Node) const { return graph->fromId(id, Node()); }
     1406    Edge fromId(int id, Edge) const { return Edge(id); }
     1407
     1408    int maxId(Node) const { return graph->maxId(Node()); };
     1409    int maxId(Edge) const { return edges.size() - 1; }
     1410
     1411    Node source(const Edge& edge) const { return edges[edge.id].source;}
     1412    Node target(const Edge& edge) const { return edges[edge.id].target;}
     1413
     1414  };
     1415
     1416  template <typename _Graph>
     1417  class NewEdgeSetAdaptor :
     1418    public ErasableGraphExtender<
     1419    ClearableGraphExtender<
     1420    ExtendableGraphExtender<
     1421    DefaultMappableGraphExtender<
     1422    IterableGraphExtender<
     1423    AlterableGraphExtender<
     1424    NewEdgeSetAdaptorBase<_Graph> > > > > > > {
     1425
     1426  public:
     1427
     1428    typedef ErasableGraphExtender<
     1429      ClearableGraphExtender<
     1430      ExtendableGraphExtender<
     1431      DefaultMappableGraphExtender<
     1432      IterableGraphExtender<
     1433      AlterableGraphExtender<
     1434      NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;
     1435   
     1436
     1437    typedef typename Parent::Node Node;
     1438    typedef typename Parent::Edge Edge;
     1439
     1440  private:
     1441
     1442    virtual void _clear() {
     1443      Parent::edges.clear();
     1444      Parent::first_edge = -1;
     1445      Parent::first_free_edge = -1;
     1446      Parent::getNotifier(Edge()).clear();
     1447      Parent::getNotifier(Node()).clear();
     1448    }
     1449
     1450    virtual void _add(const Node& node) {
     1451      Parent::getNotifier(Node()).add(node);
     1452    }
     1453
     1454    virtual void _erase(const Node& node) {
     1455      Edge edge;
     1456      Parent::firstOut(edge, node);
     1457      while (edge != INVALID) {
     1458        Parent::erase(edge);
     1459        Parent::firstOut(edge, node);
     1460      }
     1461
     1462      Parent::firstIn(edge, node);
     1463      while (edge != INVALID) {
     1464        Parent::erase(edge);
     1465        Parent::firstIn(edge, node);
     1466      }
     1467     
     1468      Parent::getNotifier(Node()).erase(node);
     1469    }
     1470
     1471
     1472    typedef typename Parent::NodesImpl NodesImpl;
     1473
     1474    NodesImpl nodes;
     1475   
     1476  public:
     1477
     1478    NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
     1479      Parent::initalize(_graph, nodes);
     1480    }
     1481
     1482    void clear() {
     1483      Parent::edges.clear();
     1484      Parent::first_edge = -1;
     1485      Parent::first_free_edge = -1;
     1486
     1487      Parent::getNotifier(Edge()).clear();     
     1488    }
     1489   
     1490  };
     1491
    12131492  ///@}
    12141493
Note: See TracChangeset for help on using the changeset viewer.