COIN-OR::LEMON - Graph Library

Changeset 2498:290e43cddc1a in lemon-0.x


Ignore:
Timestamp:
10/19/07 17:21:07 (12 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3337
Message:

Bug fix in undirected graphs (adding loops)
Bug fix in undirected edgesets (alteration notifying)

Redesigned undirected edgesets (like the smart or ugraph)

Location:
lemon
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/edge_set_extender.h

    r2391 r2498  
    591591      UEdge uedge = Parent::addEdge(from, to);
    592592      notifier(UEdge()).add(uedge);
    593       notifier(Edge()).add(Parent::direct(uedge, true));
    594       notifier(Edge()).add(Parent::direct(uedge, false));
     593      std::vector<Edge> edges;
     594      edges.push_back(Parent::direct(uedge, true));
     595      edges.push_back(Parent::direct(uedge, false));
     596      notifier(Edge()).add(edges);
    595597      return uedge;
    596598    }
     
    603605
    604606    void erase(const UEdge& uedge) {
    605       notifier(Edge()).erase(Parent::direct(uedge, true));
    606       notifier(Edge()).erase(Parent::direct(uedge, false));
     607      std::vector<Edge> edges;
     608      edges.push_back(Parent::direct(uedge, true));
     609      edges.push_back(Parent::direct(uedge, false));
     610      notifier(Edge()).erase(edges);
    607611      notifier(UEdge()).erase(uedge);
    608612      Parent::erase(uedge);
  • lemon/edge_set.h

    r2391 r2498  
    242242  /// "Graph" concept.
    243243  ///
    244   /// In the edge extension and removing it conforms to the
    245   /// \ref concepts::Graph "Graph" concept.
    246244  template <typename _Graph>
    247245  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
     
    321319  };
    322320
     321  template <typename _Graph>
     322  class ListUEdgeSetBase {
     323  public:
     324
     325    typedef _Graph Graph;
     326    typedef typename Graph::Node Node;
     327    typedef typename Graph::NodeIt NodeIt;
     328
     329  protected:
     330
     331    struct NodeT {
     332      int first_out;
     333      NodeT() : first_out(-1) {}
     334    };
     335
     336    typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
     337
     338    NodesImplBase* nodes;
     339
     340    struct EdgeT {
     341      Node target;
     342      int prev_out, next_out;
     343      EdgeT() : prev_out(-1), next_out(-1) {}
     344    };
     345
     346    std::vector<EdgeT> edges;
     347
     348    int first_edge;
     349    int first_free_edge;
     350
     351    const Graph* graph;
     352
     353    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
     354      graph = &_graph;
     355      nodes = &_nodes;
     356    }
     357   
     358  public:
     359
     360    class UEdge {
     361      friend class ListUEdgeSetBase;
     362    protected:
     363
     364      int id;
     365      explicit UEdge(int _id) { id = _id;}
     366
     367    public:
     368      UEdge() {}
     369      UEdge (Invalid) { id = -1; }
     370      bool operator==(const UEdge& edge) const {return id == edge.id;}
     371      bool operator!=(const UEdge& edge) const {return id != edge.id;}
     372      bool operator<(const UEdge& edge) const {return id < edge.id;}
     373    };
     374
     375    class Edge {
     376      friend class ListUEdgeSetBase;
     377    protected:
     378      Edge(int _id) : id(_id) {}
     379      int id;
     380    public:
     381      operator UEdge() const { return uEdgeFromId(id / 2); }
     382
     383      Edge() {}
     384      Edge(Invalid) : id(-1) {}
     385      bool operator==(const Edge& edge) const { return id == edge.id; }
     386      bool operator!=(const Edge& edge) const { return id != edge.id; }
     387      bool operator<(const Edge& edge) const { return id < edge.id; }
     388    };
     389
     390    ListUEdgeSetBase() : first_edge(-1), first_free_edge(-1) {}
     391
     392    UEdge addEdge(const Node& u, const Node& v) {
     393      int n;
     394
     395      if (first_free_edge == -1) {
     396        n = edges.size();
     397        edges.push_back(EdgeT());
     398        edges.push_back(EdgeT());
     399      } else {
     400        n = first_free_edge;
     401        first_free_edge = edges[n].next_out;
     402      }
     403     
     404      edges[n].target = u;
     405      edges[n | 1].target = v;
     406
     407      edges[n].next_out = (*nodes)[v].first_out;
     408      if ((*nodes)[v].first_out != -1) {
     409        edges[(*nodes)[v].first_out].prev_out = n;
     410      }
     411      (*nodes)[v].first_out = n;
     412      edges[n].prev_out = -1;
     413     
     414      if ((*nodes)[u].first_out != -1) {
     415        edges[(*nodes)[u].first_out].prev_out = (n | 1);
     416      }
     417      edges[n | 1].next_out = (*nodes)[u].first_out;
     418      (*nodes)[u].first_out = (n | 1);
     419      edges[n | 1].prev_out = -1;
     420
     421      return UEdge(n / 2);
     422    }
     423
     424    void erase(const UEdge& edge) {
     425      int n = edge.id * 2;
     426     
     427      if (edges[n].next_out != -1) {
     428        edges[edges[n].next_out].prev_out = edges[n].prev_out;
     429      }
     430
     431      if (edges[n].prev_out != -1) {
     432        edges[edges[n].prev_out].next_out = edges[n].next_out;
     433      } else {
     434        (*nodes)[edges[n | 1].target].first_out = edges[n].next_out;
     435      }
     436
     437      if (edges[n | 1].next_out != -1) {
     438        edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out;
     439      }
     440
     441      if (edges[n | 1].prev_out != -1) {
     442        edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out;
     443      } else {
     444        (*nodes)[edges[n].target].first_out = edges[n | 1].next_out;
     445      }
     446     
     447      edges[n].next_out = first_free_edge;
     448      first_free_edge = n;     
     449           
     450    }
     451
     452    void clear() {
     453      Node node;
     454      for (first(node); node != INVALID; next(node)) {
     455        (*nodes)[node].first_out = -1;
     456      }
     457      edges.clear();
     458      first_edge = -1;
     459      first_free_edge = -1;
     460    }
     461
     462    void first(Node& node) const {
     463      graph->first(node);
     464    }
     465
     466    void next(Node& node) const {
     467      graph->next(node);
     468    }
     469
     470    void first(Edge& edge) const {
     471      Node node;
     472      first(node);
     473      while (node != INVALID && (*nodes)[node].first_out == -1) {
     474        next(node);
     475      }
     476      edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
     477    }
     478
     479    void next(Edge& edge) const {
     480      if (edges[edge.id].next_out != -1) {
     481        edge.id = edges[edge.id].next_out;
     482      } else {
     483        Node node = edges[edge.id ^ 1].target;
     484        next(node);
     485        while(node != INVALID && (*nodes)[node].first_out == -1) {
     486          next(node);
     487        }
     488        edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
     489      }     
     490    }
     491
     492    void first(UEdge& uedge) const {
     493      Node node;
     494      first(node);
     495      while (node != INVALID) {
     496        uedge.id = (*nodes)[node].first_out;
     497        while ((uedge.id & 1) != 1) {
     498          uedge.id = edges[uedge.id].next_out;
     499        }
     500        if (uedge.id != -1) {
     501          uedge.id /= 2;
     502          return;
     503        }
     504        next(node);
     505      }
     506      uedge.id = -1;
     507    }
     508
     509    void next(UEdge& uedge) const {
     510      Node node = edges[uedge.id * 2].target;
     511      uedge.id = edges[(uedge.id * 2) | 1].next_out;
     512      while ((uedge.id & 1) != 1) {
     513        uedge.id = edges[uedge.id].next_out;
     514      }
     515      if (uedge.id != -1) {
     516        uedge.id /= 2;
     517        return;
     518      }
     519      next(node);
     520      while (node != INVALID) {
     521        uedge.id = (*nodes)[node].first_out;
     522        while ((uedge.id & 1) != 1) {
     523          uedge.id = edges[uedge.id].next_out;
     524        }
     525        if (uedge.id != -1) {
     526          uedge.id /= 2;
     527          return;
     528        }
     529        next(node);
     530      }
     531      uedge.id = -1;
     532    }
     533
     534    void firstOut(Edge& edge, const Node& node) const {
     535      edge.id = (*nodes)[node].first_out;
     536    }
     537   
     538    void nextOut(Edge& edge) const {
     539      edge.id = edges[edge.id].next_out;       
     540    }
     541
     542    void firstIn(Edge& edge, const Node& node) const {
     543      edge.id = (((*nodes)[node].first_out) ^ 1);
     544      if (edge.id == -2) edge.id = -1;
     545    }
     546
     547    void nextIn(Edge& edge) const {
     548      edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
     549      if (edge.id == -2) edge.id = -1;
     550    }
     551
     552    void firstInc(UEdge &edge, bool& dir, const Node& node) const {
     553      int de = (*nodes)[node].first_out;
     554      if (de != -1 ) {
     555        edge.id = de / 2;
     556        dir = ((de & 1) == 1);
     557      } else {
     558        edge.id = -1;
     559        dir = true;
     560      }
     561    }
     562    void nextInc(UEdge &edge, bool& dir) const {
     563      int de = (edges[(edge.id * 2) | (dir ? 1 : 0)].next_out);
     564      if (de != -1 ) {
     565        edge.id = de / 2;
     566        dir = ((de & 1) == 1);
     567      } else {
     568        edge.id = -1;
     569        dir = true;
     570      }
     571    }
     572
     573    static bool direction(Edge edge) {
     574      return (edge.id & 1) == 1;
     575    }
     576
     577    static Edge direct(UEdge uedge, bool dir) {
     578      return Edge(uedge.id * 2 + (dir ? 1 : 0));
     579    }
     580
     581    int id(const Node& node) const { return graph->id(node); }
     582    static int id(Edge e) { return e.id; }
     583    static int id(UEdge e) { return e.id; }
     584
     585    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
     586    static Edge edgeFromId(int id) { return Edge(id);}
     587    static UEdge uEdgeFromId(int id) { return UEdge(id);}
     588
     589    int maxNodeId() const { return graph->maxNodeId(); };
     590    int maxUEdgeId() const { return edges.size() / 2 - 1; }
     591    int maxEdgeId() const { return edges.size()-1; }
     592
     593    Node source(Edge e) const { return edges[e.id ^ 1].target; }
     594    Node target(Edge e) const { return edges[e.id].target; }
     595
     596    Node source(UEdge e) const { return edges[2 * e.id].target; }
     597    Node target(UEdge e) const { return edges[2 * e.id + 1].target; }
     598
     599    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
     600
     601    NodeNotifier& notifier(Node) const {
     602      return graph->notifier(Node());
     603    }
     604
     605    template <typename _Value>
     606    class NodeMap : public Graph::template NodeMap<_Value> {
     607    public:
     608
     609      typedef typename _Graph::template NodeMap<_Value> Parent;
     610
     611      explicit NodeMap(const ListUEdgeSetBase<Graph>& edgeset)
     612        : Parent(*edgeset.graph) {}
     613
     614      NodeMap(const ListUEdgeSetBase<Graph>& edgeset, const _Value& value)
     615        : Parent(*edgeset.graph, value) {}
     616
     617      NodeMap& operator=(const NodeMap& cmap) {
     618        return operator=<NodeMap>(cmap);
     619      }
     620
     621      template <typename CMap>
     622      NodeMap& operator=(const CMap& cmap) {
     623        Parent::operator=(cmap);
     624        return *this;
     625      }
     626    };
     627
     628  };
     629
    323630  /// \ingroup semi_adaptors
    324631  ///
     
    337644  /// \ref concepts::UGraph "UGraph" concept.
    338645  template <typename _Graph>
    339   class ListUEdgeSet
    340     : public UEdgeSetExtender<UndirGraphExtender<ListEdgeSetBase<_Graph> > > {
    341 
    342   public:
    343 
    344     typedef UEdgeSetExtender<UndirGraphExtender<
    345       ListEdgeSetBase<_Graph> > > Parent;
     646  class ListUEdgeSet : public UEdgeSetExtender<ListUEdgeSetBase<_Graph> > {
     647
     648  public:
     649
     650    typedef UEdgeSetExtender<ListUEdgeSetBase<_Graph> > Parent;
    346651   
    347652    typedef typename Parent::Node Node;
     
    662967  };
    663968
     969
     970  template <typename _Graph>
     971  class SmartUEdgeSetBase {
     972  public:
     973
     974    typedef _Graph Graph;
     975    typedef typename Graph::Node Node;
     976    typedef typename Graph::NodeIt NodeIt;
     977
     978  protected:
     979
     980    struct NodeT {
     981      int first_out;
     982      NodeT() : first_out(-1) {}
     983    };
     984
     985    typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
     986
     987    NodesImplBase* nodes;
     988
     989    struct EdgeT {
     990      Node target;
     991      int next_out;
     992      EdgeT() {}
     993    };
     994
     995    std::vector<EdgeT> edges;
     996
     997    const Graph* graph;
     998
     999    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
     1000      graph = &_graph;
     1001      nodes = &_nodes;
     1002    }
     1003   
     1004  public:
     1005
     1006    class UEdge {
     1007      friend class SmartUEdgeSetBase;
     1008    protected:
     1009
     1010      int id;
     1011      explicit UEdge(int _id) { id = _id;}
     1012
     1013    public:
     1014      UEdge() {}
     1015      UEdge (Invalid) { id = -1; }
     1016      bool operator==(const UEdge& edge) const {return id == edge.id;}
     1017      bool operator!=(const UEdge& edge) const {return id != edge.id;}
     1018      bool operator<(const UEdge& edge) const {return id < edge.id;}
     1019    };
     1020
     1021    class Edge {
     1022      friend class SmartUEdgeSetBase;
     1023    protected:
     1024      Edge(int _id) : id(_id) {}
     1025      int id;
     1026    public:
     1027      operator UEdge() const { return uEdgeFromId(id / 2); }
     1028
     1029      Edge() {}
     1030      Edge(Invalid) : id(-1) {}
     1031      bool operator==(const Edge& edge) const { return id == edge.id; }
     1032      bool operator!=(const Edge& edge) const { return id != edge.id; }
     1033      bool operator<(const Edge& edge) const { return id < edge.id; }
     1034    };
     1035
     1036    SmartUEdgeSetBase() {}
     1037
     1038    UEdge addEdge(const Node& u, const Node& v) {
     1039      int n = edges.size();
     1040      edges.push_back(EdgeT());
     1041      edges.push_back(EdgeT());
     1042     
     1043      edges[n].target = u;
     1044      edges[n | 1].target = v;
     1045
     1046      edges[n].next_out = (*nodes)[v].first_out;
     1047      (*nodes)[v].first_out = n;
     1048
     1049      edges[n | 1].next_out = (*nodes)[u].first_out;   
     1050      (*nodes)[u].first_out = (n | 1);
     1051
     1052      return UEdge(n / 2);
     1053    }
     1054
     1055    void clear() {
     1056      Node node;
     1057      for (first(node); node != INVALID; next(node)) {
     1058        (*nodes)[node].first_out = -1;
     1059      }
     1060      edges.clear();
     1061    }
     1062
     1063    void first(Node& node) const {
     1064      graph->first(node);
     1065    }
     1066
     1067    void next(Node& node) const {
     1068      graph->next(node);
     1069    }
     1070
     1071    void first(Edge& edge) const {
     1072      edge.id = edges.size() - 1;
     1073    }
     1074
     1075    void next(Edge& edge) const {
     1076      --edge.id;
     1077    }
     1078
     1079    void first(UEdge& edge) const {
     1080      edge.id = edges.size() / 2 - 1;
     1081    }
     1082
     1083    void next(UEdge& edge) const {
     1084      --edge.id;
     1085    }
     1086
     1087    void firstOut(Edge& edge, const Node& node) const {
     1088      edge.id = (*nodes)[node].first_out;   
     1089    }
     1090   
     1091    void nextOut(Edge& edge) const {
     1092      edge.id = edges[edge.id].next_out;       
     1093    }
     1094
     1095    void firstIn(Edge& edge, const Node& node) const {
     1096      edge.id = (((*nodes)[node].first_out) ^ 1);
     1097      if (edge.id == -2) edge.id = -1;
     1098    }
     1099
     1100    void nextIn(Edge& edge) const {
     1101      edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
     1102      if (edge.id == -2) edge.id = -1;
     1103    }
     1104
     1105    void firstInc(UEdge &edge, bool& dir, const Node& node) const {
     1106      int de = (*nodes)[node].first_out;
     1107      if (de != -1 ) {
     1108        edge.id = de / 2;
     1109        dir = ((de & 1) == 1);
     1110      } else {
     1111        edge.id = -1;
     1112        dir = true;
     1113      }
     1114    }
     1115    void nextInc(UEdge &edge, bool& dir) const {
     1116      int de = (edges[(edge.id * 2) | (dir ? 1 : 0)].next_out);
     1117      if (de != -1 ) {
     1118        edge.id = de / 2;
     1119        dir = ((de & 1) == 1);
     1120      } else {
     1121        edge.id = -1;
     1122        dir = true;
     1123      }
     1124    }
     1125
     1126    static bool direction(Edge edge) {
     1127      return (edge.id & 1) == 1;
     1128    }
     1129
     1130    static Edge direct(UEdge uedge, bool dir) {
     1131      return Edge(uedge.id * 2 + (dir ? 1 : 0));
     1132    }
     1133
     1134    int id(Node node) const { return graph->id(node); }
     1135    static int id(Edge edge) { return edge.id; }
     1136    static int id(UEdge edge) { return edge.id; }
     1137
     1138    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
     1139    static Edge edgeFromId(int id) { return Edge(id); }
     1140    static UEdge uEdgeFromId(int id) { return UEdge(id);}
     1141
     1142    int maxNodeId() const { return graph->maxNodeId(); };
     1143    int maxEdgeId() const { return edges.size() - 1; }
     1144    int maxUEdgeId() const { return edges.size() / 2 - 1; }
     1145
     1146    Node source(Edge e) const { return edges[e.id ^ 1].target; }
     1147    Node target(Edge e) const { return edges[e.id].target; }
     1148
     1149    Node source(UEdge e) const { return edges[2 * e.id].target; }
     1150    Node target(UEdge e) const { return edges[2 * e.id + 1].target; }
     1151
     1152    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
     1153
     1154    NodeNotifier& notifier(Node) const {
     1155      return graph->notifier(Node());
     1156    }
     1157
     1158    template <typename _Value>
     1159    class NodeMap : public Graph::template NodeMap<_Value> {
     1160    public:
     1161
     1162      typedef typename _Graph::template NodeMap<_Value> Parent;
     1163
     1164      explicit NodeMap(const SmartUEdgeSetBase<Graph>& edgeset)
     1165        : Parent(*edgeset.graph) { }
     1166
     1167      NodeMap(const SmartUEdgeSetBase<Graph>& edgeset, const _Value& value)
     1168        : Parent(*edgeset.graph, value) { }
     1169
     1170      NodeMap& operator=(const NodeMap& cmap) {
     1171        return operator=<NodeMap>(cmap);
     1172      }
     1173
     1174      template <typename CMap>
     1175      NodeMap& operator=(const CMap& cmap) {
     1176        Parent::operator=(cmap);
     1177        return *this;
     1178      }
     1179    };
     1180
     1181  };
     1182
    6641183  /// \ingroup semi_adaptors
    6651184  ///
     
    6781197  /// \ref concepts::UGraph "UGraph" concept.
    6791198  template <typename _Graph>
    680   class SmartUEdgeSet
    681     : public UEdgeSetExtender<UndirGraphExtender<SmartEdgeSetBase<_Graph> > > {
    682 
    683   public:
    684 
    685     typedef UEdgeSetExtender<UndirGraphExtender<
    686       SmartEdgeSetBase<_Graph> > > Parent;
     1199  class SmartUEdgeSet : public UEdgeSetExtender<SmartUEdgeSetBase<_Graph> > {
     1200
     1201  public:
     1202
     1203    typedef UEdgeSetExtender<SmartUEdgeSetBase<_Graph> > Parent;
    6871204   
    6881205    typedef typename Parent::Node Node;
  • lemon/list_graph.h

    r2456 r2498  
    978978
    979979      edges[n].next_out = nodes[v.id].first_out;
    980       edges[n | 1].next_out = nodes[u.id].first_out;
    981980      if (nodes[v.id].first_out != -1) {
    982981        edges[nodes[v.id].first_out].prev_out = n;
    983       }
     982      }     
     983      edges[n].prev_out = -1;
     984      nodes[v.id].first_out = n;
     985     
     986      edges[n | 1].next_out = nodes[u.id].first_out;
    984987      if (nodes[u.id].first_out != -1) {
    985988        edges[nodes[u.id].first_out].prev_out = (n | 1);
    986989      }
    987      
    988       edges[n].prev_out = edges[n | 1].prev_out = -1;
    989        
    990       nodes[v.id].first_out = n;
     990      edges[n | 1].prev_out = -1;     
    991991      nodes[u.id].first_out = (n | 1);
    992992
  • lemon/smart_graph.h

    r2456 r2498  
    186186  typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
    187187
    188   /// \ingroup graphs
    189 
    190   ///A smart graph class.
    191 
     188  ///\ingroup graphs
     189  ///
     190  ///\brief A smart graph class.
     191  ///
    192192  ///This is a simple and fast graph implementation.
    193193  ///It is also quite memory efficient, but at the price
     
    572572
    573573      edges[n].next_out = nodes[v.id].first_out;
    574       edges[n | 1].next_out = nodes[u.id].first_out;
    575        
    576574      nodes[v.id].first_out = n;
     575
     576      edges[n | 1].next_out = nodes[u.id].first_out;   
    577577      nodes[u.id].first_out = (n | 1);
    578578
Note: See TracChangeset for help on using the changeset viewer.