COIN-OR::LEMON - Graph Library

Changeset 2338:359f0b71919b in lemon-0.x for lemon/list_graph.h


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

File:
1 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    ///
Note: See TracChangeset for help on using the changeset viewer.