COIN-OR::LEMON - Graph Library

Changeset 2338:359f0b71919b in lemon-0.x


Ignore:
Timestamp:
01/11/07 22:06:47 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3130
Message:

Changing implementation of undirected graphs
slightly faster, 10% speed-up

Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/list_graph.h

    r2302 r2338  
    9999
    100100   
    101     /// Maximum node ID.
    102    
    103     /// Maximum node ID.
    104     ///\sa id(Node)
    105101    int maxNodeId() const { return nodes.size()-1; }
    106 
    107     /// Maximum edge ID.
    108    
    109     /// Maximum edge ID.
    110     ///\sa id(Edge)
    111102    int maxEdgeId() const { return edges.size()-1; }
    112103
     
    165156    static Edge edgeFromId(int id) { return Edge(id);}
    166157
    167     /// Adds a new node to the graph.
    168 
    169     /// Adds a new node to the graph.
    170     ///
    171     /// \warning It adds the new node to the front of the list.
    172     /// (i.e. the lastly added node becomes the first.)
    173158    Node addNode() {     
    174159      int n;
     
    736721  ///@}
    737722
    738   /**************** Undirected List Graph ****************/
    739 
    740   typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
    741   ExtendedListUGraphBase;
     723  class ListUGraphBase {
     724
     725  protected:
     726
     727    struct NodeT {
     728      int first_out;
     729      int prev, next;
     730    };
     731 
     732    struct EdgeT {
     733      int target;
     734      int prev_out, next_out;
     735    };
     736
     737    std::vector<NodeT> nodes;
     738
     739    int first_node;
     740
     741    int first_free_node;
     742
     743    std::vector<EdgeT> edges;
     744
     745    int first_free_edge;
     746   
     747  public:
     748   
     749    typedef ListUGraphBase Graph;
     750   
     751    class Node {
     752      friend class ListUGraphBase;
     753    protected:
     754
     755      int id;
     756      explicit Node(int pid) { id = pid;}
     757
     758    public:
     759      Node() {}
     760      Node (Invalid) { id = -1; }
     761      bool operator==(const Node& node) const {return id == node.id;}
     762      bool operator!=(const Node& node) const {return id != node.id;}
     763      bool operator<(const Node& node) const {return id < node.id;}
     764    };
     765
     766    class UEdge {
     767      friend class ListUGraphBase;
     768    protected:
     769
     770      int id;
     771      explicit UEdge(int pid) { id = pid;}
     772
     773    public:
     774      UEdge() {}
     775      UEdge (Invalid) { id = -1; }
     776      bool operator==(const UEdge& edge) const {return id == edge.id;}
     777      bool operator!=(const UEdge& edge) const {return id != edge.id;}
     778      bool operator<(const UEdge& edge) const {return id < edge.id;}
     779    };
     780
     781    class Edge {
     782      friend class ListUGraphBase;
     783    protected:
     784
     785      int id;
     786      explicit Edge(int pid) { id = pid;}
     787
     788    public:
     789      operator UEdge() const { return UEdge(id / 2); }
     790
     791      Edge() {}
     792      Edge (Invalid) { id = -1; }
     793      bool operator==(const Edge& edge) const {return id == edge.id;}
     794      bool operator!=(const Edge& edge) const {return id != edge.id;}
     795      bool operator<(const Edge& edge) const {return id < edge.id;}
     796    };
     797
     798
     799
     800    ListUGraphBase()
     801      : nodes(), first_node(-1),
     802        first_free_node(-1), edges(), first_free_edge(-1) {}
     803
     804   
     805    int maxNodeId() const { return nodes.size()-1; }
     806    int maxUEdgeId() const { return edges.size() / 2 - 1; }
     807    int maxEdgeId() const { return edges.size()-1; }
     808
     809    Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
     810    Node target(Edge e) const { return Node(edges[e.id].target); }
     811
     812    Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
     813    Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
     814
     815    static bool direction(Edge e) {
     816      return (e.id & 1) == 1;
     817    }
     818
     819    static Edge direct(UEdge e, bool d) {
     820      return Edge(e.id * 2 + (d ? 1 : 0));
     821    }
     822
     823    void first(Node& node) const {
     824      node.id = first_node;
     825    }
     826
     827    void next(Node& node) const {
     828      node.id = nodes[node.id].next;
     829    }
     830
     831    void first(Edge& e) const {
     832      int n = first_node;
     833      while (n != -1 && nodes[n].first_out == -1) {
     834        n = nodes[n].next;
     835      }
     836      e.id = (n == -1) ? -1 : nodes[n].first_out;
     837    }
     838
     839    void next(Edge& e) const {
     840      if (edges[e.id].next_out != -1) {
     841        e.id = edges[e.id].next_out;
     842      } else {
     843        int n = nodes[edges[e.id ^ 1].target].next;
     844        while(n != -1 && nodes[n].first_out == -1) {
     845          n = nodes[n].next;
     846        }
     847        e.id = (n == -1) ? -1 : nodes[n].first_out;
     848      }     
     849    }
     850
     851    void first(UEdge& e) const {
     852      int n = first_node;
     853      while (n != -1) {
     854        e.id = nodes[n].first_out;
     855        while ((e.id & 1) != 1) {
     856          e.id = edges[e.id].next_out;
     857        }
     858        if (e.id != -1) {
     859          e.id /= 2;
     860          return;
     861        }
     862        n = nodes[n].next;
     863      }
     864      e.id = -1;
     865    }
     866
     867    void next(UEdge& e) const {
     868      int n = edges[e.id * 2].target;
     869      e.id = edges[(e.id * 2) | 1].next_out;
     870      while ((e.id & 1) != 1) {
     871        e.id = edges[e.id].next_out;
     872      }
     873      if (e.id != -1) {
     874        e.id /= 2;
     875        return;
     876      }
     877      n = nodes[n].next;
     878      while (n != -1) {
     879        e.id = nodes[n].first_out;
     880        while ((e.id & 1) != 1) {
     881          e.id = edges[e.id].next_out;
     882        }
     883        if (e.id != -1) {
     884          e.id /= 2;
     885          return;
     886        }
     887        n = nodes[n].next;
     888      }
     889      e.id = -1;
     890    }
     891
     892    void firstOut(Edge &e, const Node& v) const {
     893      e.id = nodes[v.id].first_out;
     894    }
     895    void nextOut(Edge &e) const {
     896      e.id = edges[e.id].next_out;
     897    }
     898
     899    void firstIn(Edge &e, const Node& v) const {
     900      e.id = ((nodes[v.id].first_out) ^ 1);
     901      if (e.id == -2) e.id = -1;
     902    }
     903    void nextIn(Edge &e) const {
     904      e.id = ((edges[e.id ^ 1].next_out) ^ 1);
     905      if (e.id == -2) e.id = -1;
     906    }
     907
     908    void firstInc(UEdge &e, bool& d, const Node& v) const {
     909      int de = nodes[v.id].first_out;
     910      e.id = de / 2;
     911      d = ((de & 1) == 1);
     912    }
     913    void nextInc(UEdge &e, bool& d) const {
     914      int de = (edges[(e.id * 2) | (d ? 1 : 0)].next_out);
     915      e.id = de / 2;
     916      d = ((de & 1) == 1);
     917    }
     918   
     919    static int id(Node v) { return v.id; }
     920    static int id(Edge e) { return e.id; }
     921    static int id(UEdge e) { return e.id; }
     922
     923    static Node nodeFromId(int id) { return Node(id);}
     924    static Edge edgeFromId(int id) { return Edge(id);}
     925    static UEdge uEdgeFromId(int id) { return UEdge(id);}
     926
     927    Node addNode() {     
     928      int n;
     929     
     930      if(first_free_node==-1) {
     931        n = nodes.size();
     932        nodes.push_back(NodeT());
     933      } else {
     934        n = first_free_node;
     935        first_free_node = nodes[n].next;
     936      }
     937     
     938      nodes[n].next = first_node;
     939      if (first_node != -1) nodes[first_node].prev = n;
     940      first_node = n;
     941      nodes[n].prev = -1;
     942     
     943      nodes[n].first_out = -1;
     944     
     945      return Node(n);
     946    }
     947   
     948    UEdge addEdge(Node u, Node v) {
     949      int n;     
     950
     951      if (first_free_edge == -1) {
     952        n = edges.size();
     953        edges.push_back(EdgeT());
     954        edges.push_back(EdgeT());
     955      } else {
     956        n = first_free_edge;
     957        first_free_edge = edges[n].next_out;
     958      }
     959     
     960      edges[n].target = u.id;
     961      edges[n | 1].target = v.id;
     962
     963      edges[n].next_out = nodes[v.id].first_out;
     964      edges[n | 1].next_out = nodes[u.id].first_out;
     965      if (nodes[v.id].first_out != -1) {
     966        edges[nodes[v.id].first_out].prev_out = n;
     967      }
     968      if (nodes[u.id].first_out != -1) {
     969        edges[nodes[u.id].first_out].prev_out = (n | 1);
     970      }
     971     
     972      edges[n].prev_out = edges[n | 1].prev_out = -1;
     973       
     974      nodes[v.id].first_out = n;
     975      nodes[u.id].first_out = (n | 1);
     976
     977      return UEdge(n / 2);
     978    }
     979   
     980    void erase(const Node& node) {
     981      int n = node.id;
     982     
     983      if(nodes[n].next != -1) {
     984        nodes[nodes[n].next].prev = nodes[n].prev;
     985      }
     986     
     987      if(nodes[n].prev != -1) {
     988        nodes[nodes[n].prev].next = nodes[n].next;
     989      } else {
     990        first_node = nodes[n].next;
     991      }
     992     
     993      nodes[n].next = first_free_node;
     994      first_free_node = n;
     995
     996    }
     997   
     998    void erase(const UEdge& edge) {
     999      int n = edge.id * 2;
     1000     
     1001      if (edges[n].next_out != -1) {
     1002        edges[edges[n].next_out].prev_out = edges[n].prev_out;
     1003      }
     1004
     1005      if (edges[n].prev_out != -1) {
     1006        edges[edges[n].prev_out].next_out = edges[n].next_out;
     1007      } else {
     1008        nodes[edges[n | 1].target].first_out = edges[n].next_out;
     1009      }
     1010
     1011      if (edges[n | 1].next_out != -1) {
     1012        edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out;
     1013      }
     1014
     1015      if (edges[n | 1].prev_out != -1) {
     1016        edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out;
     1017      } else {
     1018        nodes[edges[n].target].first_out = edges[n | 1].next_out;
     1019      }
     1020     
     1021      edges[n].next_out = first_free_edge;
     1022      first_free_edge = n;     
     1023
     1024    }
     1025
     1026    void clear() {
     1027      edges.clear();
     1028      nodes.clear();
     1029      first_node = first_free_node = first_free_edge = -1;
     1030    }
     1031
     1032  protected:
     1033
     1034    void changeTarget(UEdge e, Node n) {
     1035      if(edges[2 * e.id].next_out != -1) {
     1036        edges[edges[2 * e.id].next_out].prev_out = edges[2 * e.id].prev_out;
     1037      }
     1038      if(edges[2 * e.id].prev_out != -1) {
     1039        edges[edges[2 * e.id].prev_out].next_out =
     1040          edges[2 * e.id].next_out;
     1041      } else {
     1042        nodes[edges[(2 * e.id) | 1].target].first_out =
     1043          edges[2 * e.id].next_out;
     1044      }
     1045
     1046      if (nodes[n.id].first_out != -1) {
     1047        edges[nodes[n.id].first_out].prev_out = 2 * e.id;
     1048      }
     1049      edges[(2 * e.id) | 1].target = n.id;
     1050      edges[2 * e.id].prev_out = -1;
     1051      edges[2 * e.id].next_out = nodes[n.id].first_out;
     1052      nodes[n.id].first_out = 2 * e.id;
     1053    }
     1054
     1055    void changeSource(UEdge e, Node n) {
     1056      if(edges[(2 * e.id) | 1].next_out != -1) {
     1057        edges[edges[(2 * e.id) | 1].next_out].prev_out =
     1058          edges[(2 * e.id) | 1].prev_out;
     1059      }
     1060      if(edges[(2 * e.id) | 1].prev_out != -1) {
     1061        edges[edges[(2 * e.id) | 1].prev_out].next_out =
     1062          edges[(2 * e.id) | 1].next_out;
     1063      } else {
     1064        nodes[edges[2 * e.id].target].first_out =
     1065          edges[(2 * e.id) | 1].next_out;
     1066      }
     1067
     1068      if (nodes[n.id].first_out != -1) {
     1069        edges[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
     1070      }
     1071      edges[2 * e.id].target = n.id;
     1072      edges[(2 * e.id) | 1].prev_out = -1;
     1073      edges[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
     1074      nodes[n.id].first_out = ((2 * e.id) | 1);
     1075    }
     1076
     1077  };
     1078
     1079//   typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
     1080//   ExtendedListUGraphBase;
     1081
     1082  typedef UGraphExtender<ListUGraphBase> ExtendedListUGraphBase;
     1083
     1084
    7421085
    7431086  /// \addtogroup graphs
     
    7771120
    7781121    typedef ExtendedListUGraphBase Parent;
     1122
     1123    typedef Parent::OutEdgeIt IncEdgeIt;
     1124
    7791125    /// \brief Add a new node to the graph.
    7801126    ///
  • lemon/smart_graph.h

    r2261 r2338  
    367367
    368368
    369   /**************** Undirected List Graph ****************/
    370 
    371   typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
    372   ExtendedSmartUGraphBase;
     369  class SmartUGraphBase {
     370
     371  protected:
     372
     373    struct NodeT {
     374      int first_out;
     375    };
     376 
     377    struct EdgeT {
     378      int target;
     379      int next_out;
     380    };
     381
     382    std::vector<NodeT> nodes;
     383    std::vector<EdgeT> edges;
     384
     385    int first_free_edge;
     386   
     387  public:
     388   
     389    typedef SmartUGraphBase Graph;
     390   
     391    class Node {
     392      friend class SmartUGraphBase;
     393    protected:
     394
     395      int id;
     396      explicit Node(int pid) { id = pid;}
     397
     398    public:
     399      Node() {}
     400      Node (Invalid) { id = -1; }
     401      bool operator==(const Node& node) const {return id == node.id;}
     402      bool operator!=(const Node& node) const {return id != node.id;}
     403      bool operator<(const Node& node) const {return id < node.id;}
     404    };
     405
     406    class UEdge {
     407      friend class SmartUGraphBase;
     408    protected:
     409
     410      int id;
     411      explicit UEdge(int pid) { id = pid;}
     412
     413    public:
     414      UEdge() {}
     415      UEdge (Invalid) { id = -1; }
     416      bool operator==(const UEdge& edge) const {return id == edge.id;}
     417      bool operator!=(const UEdge& edge) const {return id != edge.id;}
     418      bool operator<(const UEdge& edge) const {return id < edge.id;}
     419    };
     420
     421    class Edge {
     422      friend class SmartUGraphBase;
     423    protected:
     424
     425      int id;
     426      explicit Edge(int pid) { id = pid;}
     427
     428    public:
     429      operator UEdge() const { return UEdge(id / 2); }
     430
     431      Edge() {}
     432      Edge (Invalid) { id = -1; }
     433      bool operator==(const Edge& edge) const {return id == edge.id;}
     434      bool operator!=(const Edge& edge) const {return id != edge.id;}
     435      bool operator<(const Edge& edge) const {return id < edge.id;}
     436    };
     437
     438
     439
     440    SmartUGraphBase()
     441      : nodes(), edges() {}
     442
     443   
     444    int maxNodeId() const { return nodes.size()-1; }
     445    int maxUEdgeId() const { return edges.size() / 2 - 1; }
     446    int maxEdgeId() const { return edges.size()-1; }
     447
     448    Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
     449    Node target(Edge e) const { return Node(edges[e.id].target); }
     450
     451    Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
     452    Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
     453
     454    static bool direction(Edge e) {
     455      return (e.id & 1) == 1;
     456    }
     457
     458    static Edge direct(UEdge e, bool d) {
     459      return Edge(e.id * 2 + (d ? 1 : 0));
     460    }
     461
     462    void first(Node& node) const {
     463      node.id = nodes.size() - 1;
     464    }
     465
     466    void next(Node& node) const {
     467      --node.id;
     468    }
     469
     470    void first(Edge& edge) const {
     471      edge.id = edges.size() - 1;
     472    }
     473
     474    void next(Edge& edge) const {
     475      --edge.id;
     476    }
     477
     478    void first(UEdge& edge) const {
     479      edge.id = edges.size() / 2 - 1;
     480    }
     481
     482    void next(UEdge& edge) const {
     483      --edge.id;
     484    }
     485
     486    void firstOut(Edge &edge, const Node& v) const {
     487      edge.id = nodes[v.id].first_out;
     488    }
     489    void nextOut(Edge &edge) const {
     490      edge.id = edges[edge.id].next_out;
     491    }
     492
     493    void firstIn(Edge &edge, const Node& v) const {
     494      edge.id = ((nodes[v.id].first_out) ^ 1);
     495      if (e.id == -2) e.id = -1;
     496    }
     497    void nextIn(Edge &edge) const {
     498      edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
     499      if (e.id == -2) e.id = -1;
     500    }
     501
     502    void firstInc(UEdge &edge, bool& d, const Node& v) const {
     503      int de = nodes[v.id].first_out;
     504      edge.id = de / 2;
     505      d = ((de & 1) == 1);
     506    }
     507    void nextInc(UEdge &edge, bool& d) const {
     508      int de = (edges[(edge.id * 2) | (d ? 1 : 0)].next_out);
     509      edge.id = de / 2;
     510      d = ((de & 1) == 1);
     511    }
     512   
     513    static int id(Node v) { return v.id; }
     514    static int id(Edge e) { return e.id; }
     515    static int id(UEdge e) { return e.id; }
     516
     517    static Node nodeFromId(int id) { return Node(id);}
     518    static Edge edgeFromId(int id) { return Edge(id);}
     519    static UEdge uEdgeFromId(int id) { return UEdge(id);}
     520
     521    Node addNode() {     
     522      int n = nodes.size();
     523      nodes.push_back(NodeT());
     524      nodes[n].first_out = -1;
     525     
     526      return Node(n);
     527    }
     528   
     529    UEdge addEdge(Node u, Node v) {
     530      int n = edges.size();
     531      edges.push_back(EdgeT());
     532      edges.push_back(EdgeT());
     533     
     534      edges[n].target = u.id;
     535      edges[n | 1].target = v.id;
     536
     537      edges[n].next_out = nodes[v.id].first_out;
     538      edges[n | 1].next_out = nodes[u.id].first_out;
     539       
     540      nodes[v.id].first_out = n;
     541      nodes[u.id].first_out = (n | 1);
     542
     543      return UEdge(n / 2);
     544    }
     545   
     546    void clear() {
     547      edges.clear();
     548      nodes.clear();
     549    }
     550
     551  };
     552
     553  typedef UGraphExtender<SmartUGraphBase> ExtendedSmartUGraphBase;
    373554
    374555  /// \ingroup graphs
     
    408589
    409590    typedef ExtendedSmartUGraphBase Parent;
     591    typedef Parent::OutEdgeIt IncEdgeIt;
    410592
    411593    /// Constructor
     
    444626  protected:
    445627
     628    void saveSnapshot(Snapshot &s)
     629    {
     630      s.g = this;
     631      s.node_num = nodes.size();
     632      s.edge_num = edges.size();
     633    }
    446634
    447635    void restoreSnapshot(const Snapshot &s)
    448636    {
    449637      while(s.edge_num<edges.size()) {
    450         UEdge edge = uEdgeFromId(edges.size()-1);
     638        int n=edges.size()-1;
     639        UEdge edge=uEdgeFromId(n/2);
    451640        Parent::getNotifier(UEdge()).erase(edge);
    452641        std::vector<Edge> dir;
    453         dir.push_back(Parent::direct(edge, true));
    454         dir.push_back(Parent::direct(edge, false));
     642        dir.push_back(edgeFromId(n));
     643        dir.push_back(edgeFromId(n-1));
    455644        Parent::getNotifier(Edge()).erase(dir);
    456         nodes[edges.back().source].first_out=edges.back().next_out;
    457         nodes[edges.back().target].first_in=edges.back().next_in;
     645        nodes[edges[n].target].first_out=edges[n].next_out;
     646        nodes[edges[n-1].target].first_out=edges[n-1].next_out;
    458647        edges.pop_back();
     648        edges.pop_back();
    459649      }
    460650      while(s.node_num<nodes.size()) {
    461         Node node = nodeFromId(nodes.size()-1);
     651        int n=nodes.size()-1;
     652        Node node = nodeFromId(n);
    462653        Parent::getNotifier(Node()).erase(node);
    463654        nodes.pop_back();
     
    500691      ///This constructor immediately makes a snapshot of the graph.
    501692      ///\param _g The graph we make a snapshot of.
    502       Snapshot(SmartUGraph &_g) :g(&_g) {
    503         node_num=g->nodes.size();
    504         edge_num=g->edges.size();
     693      Snapshot(SmartUGraph &g) {
     694        g.saveSnapshot(*this);
    505695      }
    506696
     
    512702      ///call, the previous snapshot gets lost.
    513703      ///\param _g The graph we make the snapshot of.
    514       void save(SmartUGraph &_g)
     704      void save(SmartUGraph &g)
    515705      {
    516         g=&_g;
    517         node_num=g->nodes.size();
    518         edge_num=g->edges.size();
     706        g.saveSnapshot(*this);
    519707      }
    520708
     
    528716      void restore()
    529717      {
    530         g->restoreSnapshot(*this);
     718        g->restoreSnapshot(*this);
    531719      }
    532720    };
Note: See TracChangeset for help on using the changeset viewer.