COIN-OR::LEMON - Graph Library

Changeset 2115:4cd528a30ec1 in lemon-0.x for lemon/list_graph.h


Ignore:
Timestamp:
06/30/06 14:14:36 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2821
Message:

Splitted graph files

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/list_graph.h

    r2114 r2115  
    2222///\ingroup graphs
    2323///\file
    24 ///\brief ListGraph, ListUGraph classes.
    25 
    26 #include <lemon/bits/base_extender.h>
     24///\brief ListGraph class.
     25
    2726#include <lemon/bits/graph_extender.h>
    28 
    29 #include <lemon/error.h>
    3027
    3128#include <vector>
     
    310307  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
    311308
    312   /// \addtogroup graphs
    313   /// @{
     309  /// \ingroup graphs
    314310
    315311  ///A list graph class.
     
    706702  };
    707703
    708   ///@}
    709 
    710   /**************** Undirected List Graph ****************/
    711 
    712   typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
    713   ExtendedListUGraphBase;
    714 
    715   /// \addtogroup graphs
    716   /// @{
    717 
    718   ///An undirected list graph class.
    719 
    720   ///This is a simple and fast erasable undirected graph implementation.
    721   ///
    722   ///It conforms to the
    723   ///\ref concept::UGraph "UGraph" concept.
    724   ///
    725   ///\sa concept::UGraph.
    726   ///
    727   ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
    728   ///haven't been implemented yet.
    729   ///
    730   class ListUGraph : public ExtendedListUGraphBase {
    731   public:
    732     typedef ExtendedListUGraphBase Parent;
    733     /// \brief Add a new node to the graph.
    734     ///
    735     /// \return the new node.
    736     ///
    737     Node addNode() { return Parent::addNode(); }
    738 
    739     /// \brief Add a new edge to the graph.
    740     ///
    741     /// Add a new edge to the graph with source node \c s
    742     /// and target node \c t.
    743     /// \return the new undirected edge.
    744     UEdge addEdge(const Node& s, const Node& t) {
    745       return Parent::addEdge(s, t);
    746     }
    747     /// \brief Changes the target of \c e to \c n
    748     ///
    749     /// Changes the target of \c e to \c n
    750     ///
    751     /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
    752     /// referencing the changed edge remain
    753     /// valid. However <tt>InEdge</tt>'s are invalidated.
    754     void changeTarget(UEdge e, Node n) {
    755       Parent::changeTarget(e,n);
    756     }
    757     /// Changes the source of \c e to \c n
    758     ///
    759     /// Changes the source of \c e to \c n
    760     ///
    761     ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
    762     ///referencing the changed edge remain
    763     ///valid. However <tt>OutEdge</tt>'s are invalidated.
    764     void changeSource(UEdge e, Node n) {
    765       Parent::changeSource(e,n);
    766     }
    767     /// \brief Contract two nodes.
    768     ///
    769     /// This function contracts two nodes.
    770     ///
    771     /// Node \p b will be removed but instead of deleting
    772     /// its neighboring edges, they will be joined to \p a.
    773     /// The last parameter \p r controls whether to remove loops. \c true
    774     /// means that loops will be removed.
    775     ///
    776     /// \note The <tt>Edge</tt>s
    777     /// referencing a moved edge remain
    778     /// valid.
    779     void contract(Node a, Node b, bool r = true) {
    780       for(IncEdgeIt e(*this, b); e!=INVALID;) {
    781         IncEdgeIt f = e; ++f;
    782         if (r && runningNode(e) == a) {
    783           erase(e);
    784         } else if (source(e) == b) {
    785           changeSource(e, a);
    786         } else {
    787           changeTarget(e, a);
    788         }
    789         e = f;
    790       }
    791       erase(b);
    792     }
    793   };
    794 
    795 
    796   class ListBpUGraphBase {
    797   public:
    798 
    799     class NodeSetError : public LogicError {
    800       virtual const char* exceptionName() const {
    801         return "lemon::ListBpUGraph::NodeSetError";
    802       }
    803     };
    804 
    805   protected:
    806 
    807     struct NodeT {
    808       int first_edge, prev, next;
    809     };
    810 
    811     struct UEdgeT {
    812       int aNode, prev_out, next_out;
    813       int bNode, prev_in, next_in;
    814     };
    815 
    816     std::vector<NodeT> aNodes;
    817     std::vector<NodeT> bNodes;
    818 
    819     std::vector<UEdgeT> edges;
    820 
    821     int first_anode;
    822     int first_free_anode;
    823 
    824     int first_bnode;
    825     int first_free_bnode;
    826 
    827     int first_free_edge;
    828 
    829   public:
    830  
    831     class Node {
    832       friend class ListBpUGraphBase;
    833     protected:
    834       int id;
    835 
    836       explicit Node(int _id) : id(_id) {}
    837     public:
    838       Node() {}
    839       Node(Invalid) { id = -1; }
    840       bool operator==(const Node i) const {return id==i.id;}
    841       bool operator!=(const Node i) const {return id!=i.id;}
    842       bool operator<(const Node i) const {return id<i.id;}
    843     };
    844 
    845     class UEdge {
    846       friend class ListBpUGraphBase;
    847     protected:
    848       int id;
    849 
    850       explicit UEdge(int _id) { id = _id;}
    851     public:
    852       UEdge() {}
    853       UEdge (Invalid) { id = -1; }
    854       bool operator==(const UEdge i) const {return id==i.id;}
    855       bool operator!=(const UEdge i) const {return id!=i.id;}
    856       bool operator<(const UEdge i) const {return id<i.id;}
    857     };
    858 
    859     ListBpUGraphBase()
    860       : first_anode(-1), first_free_anode(-1),
    861         first_bnode(-1), first_free_bnode(-1),
    862         first_free_edge(-1) {}
    863 
    864     void firstANode(Node& node) const {
    865       node.id = first_anode != -1 ? (first_anode << 1) : -1;
    866     }
    867     void nextANode(Node& node) const {
    868       node.id = aNodes[node.id >> 1].next;
    869     }
    870 
    871     void firstBNode(Node& node) const {
    872       node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
    873     }
    874     void nextBNode(Node& node) const {
    875       node.id = bNodes[node.id >> 1].next;
    876     }
    877 
    878     void first(Node& node) const {
    879       if (first_anode != -1) {
    880         node.id = (first_anode << 1);
    881       } else if (first_bnode != -1) {
    882         node.id = (first_bnode << 1) + 1;
    883       } else {
    884         node.id = -1;
    885       }
    886     }
    887     void next(Node& node) const {
    888       if (aNode(node)) {
    889         node.id = aNodes[node.id >> 1].next;
    890         if (node.id == -1) {
    891           if (first_bnode != -1) {
    892             node.id = (first_bnode << 1) + 1;
    893           }
    894         }
    895       } else {
    896         node.id = bNodes[node.id >> 1].next;
    897       }
    898     }
    899  
    900     void first(UEdge& edge) const {
    901       int aNodeId = first_anode;
    902       while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
    903         aNodeId = aNodes[aNodeId].next != -1 ?
    904           aNodes[aNodeId].next >> 1 : -1;
    905       }
    906       if (aNodeId != -1) {
    907         edge.id = aNodes[aNodeId].first_edge;
    908       } else {
    909         edge.id = -1;
    910       }
    911     }
    912     void next(UEdge& edge) const {
    913       int aNodeId = edges[edge.id].aNode >> 1;
    914       edge.id = edges[edge.id].next_out;
    915       if (edge.id == -1) {
    916         aNodeId = aNodes[aNodeId].next != -1 ?
    917           aNodes[aNodeId].next >> 1 : -1;
    918         while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
    919           aNodeId = aNodes[aNodeId].next != -1 ?
    920           aNodes[aNodeId].next >> 1 : -1;
    921         }
    922         if (aNodeId != -1) {
    923           edge.id = aNodes[aNodeId].first_edge;
    924         } else {
    925           edge.id = -1;
    926         }
    927       }
    928     }
    929 
    930     void firstFromANode(UEdge& edge, const Node& node) const {
    931       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
    932       edge.id = aNodes[node.id >> 1].first_edge;
    933     }
    934     void nextFromANode(UEdge& edge) const {
    935       edge.id = edges[edge.id].next_out;
    936     }
    937 
    938     void firstFromBNode(UEdge& edge, const Node& node) const {
    939       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
    940       edge.id = bNodes[node.id >> 1].first_edge;
    941     }
    942     void nextFromBNode(UEdge& edge) const {
    943       edge.id = edges[edge.id].next_in;
    944     }
    945 
    946     static int id(const Node& node) {
    947       return node.id;
    948     }
    949     static Node nodeFromId(int id) {
    950       return Node(id);
    951     }
    952     int maxNodeId() const {
    953       return aNodes.size() > bNodes.size() ?
    954         aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
    955     }
    956  
    957     static int id(const UEdge& edge) {
    958       return edge.id;
    959     }
    960     static UEdge uEdgeFromId(int id) {
    961       return UEdge(id);
    962     }
    963     int maxUEdgeId() const {
    964       return edges.size();
    965     }
    966  
    967     static int aNodeId(const Node& node) {
    968       return node.id >> 1;
    969     }
    970     static Node fromANodeId(int id) {
    971       return Node(id << 1);
    972     }
    973     int maxANodeId() const {
    974       return aNodes.size();
    975     }
    976 
    977     static int bNodeId(const Node& node) {
    978       return node.id >> 1;
    979     }
    980     static Node fromBNodeId(int id) {
    981       return Node((id << 1) + 1);
    982     }
    983     int maxBNodeId() const {
    984       return bNodes.size();
    985     }
    986 
    987     Node aNode(const UEdge& edge) const {
    988       return Node(edges[edge.id].aNode);
    989     }
    990     Node bNode(const UEdge& edge) const {
    991       return Node(edges[edge.id].bNode);
    992     }
    993 
    994     static bool aNode(const Node& node) {
    995       return (node.id & 1) == 0;
    996     }
    997 
    998     static bool bNode(const Node& node) {
    999       return (node.id & 1) == 1;
    1000     }
    1001 
    1002     Node addANode() {
    1003       int aNodeId;
    1004       if (first_free_anode == -1) {
    1005         aNodeId = aNodes.size();
    1006         aNodes.push_back(NodeT());
    1007       } else {
    1008         aNodeId = first_free_anode;
    1009         first_free_anode = aNodes[first_free_anode].next;
    1010       }
    1011       if (first_anode != -1) {
    1012         aNodes[aNodeId].next = first_anode << 1;
    1013         aNodes[first_anode].prev = aNodeId << 1;
    1014       } else {
    1015         aNodes[aNodeId].next = -1;
    1016       }
    1017       aNodes[aNodeId].prev = -1;
    1018       first_anode = aNodeId;
    1019       aNodes[aNodeId].first_edge = -1;
    1020       return Node(aNodeId << 1);
    1021     }
    1022 
    1023     Node addBNode() {
    1024       int bNodeId;
    1025       if (first_free_bnode == -1) {
    1026         bNodeId = bNodes.size();
    1027         bNodes.push_back(NodeT());
    1028       } else {
    1029         bNodeId = first_free_bnode;
    1030         first_free_bnode = bNodes[first_free_bnode].next;
    1031       }
    1032       if (first_bnode != -1) {
    1033         bNodes[bNodeId].next = (first_bnode << 1) + 1;
    1034         bNodes[first_bnode].prev = (bNodeId << 1) + 1;
    1035       } else {
    1036         bNodes[bNodeId].next = -1;
    1037       }
    1038       first_bnode = bNodeId;
    1039       bNodes[bNodeId].first_edge = -1;
    1040       return Node((bNodeId << 1) + 1);
    1041     }
    1042 
    1043     UEdge addEdge(const Node& source, const Node& target) {
    1044       LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
    1045       int edgeId;
    1046       if (first_free_edge != -1) {
    1047         edgeId = first_free_edge;
    1048         first_free_edge = edges[edgeId].next_out;
    1049       } else {
    1050         edgeId = edges.size();
    1051         edges.push_back(UEdgeT());
    1052       }
    1053       if ((source.id & 1) == 0) {
    1054         edges[edgeId].aNode = source.id;
    1055         edges[edgeId].bNode = target.id;
    1056       } else {
    1057         edges[edgeId].aNode = target.id;
    1058         edges[edgeId].bNode = source.id;
    1059       }
    1060       edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
    1061       edges[edgeId].prev_out = -1;
    1062       if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
    1063         edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
    1064       }
    1065       aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
    1066       edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
    1067       edges[edgeId].prev_in = -1;
    1068       if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
    1069         edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
    1070       }
    1071       bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
    1072       return UEdge(edgeId);
    1073     }
    1074 
    1075     void erase(const Node& node) {
    1076       if (aNode(node)) {
    1077         int aNodeId = node.id >> 1;
    1078         if (aNodes[aNodeId].prev != -1) {
    1079           aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
    1080         } else {
    1081           first_anode = aNodes[aNodeId].next >> 1;
    1082         }
    1083         if (aNodes[aNodeId].next != -1) {
    1084           aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
    1085         }
    1086         aNodes[aNodeId].next = first_free_anode;
    1087         first_free_anode = aNodeId;
    1088       } else {
    1089         int bNodeId = node.id >> 1;
    1090         if (bNodes[bNodeId].prev != -1) {
    1091           bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
    1092         } else {
    1093           first_bnode = bNodes[bNodeId].next >> 1;
    1094         }
    1095         if (bNodes[bNodeId].next != -1) {
    1096           bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
    1097         }
    1098         bNodes[bNodeId].next = first_free_bnode;
    1099         first_free_bnode = bNodeId;
    1100       }
    1101     }
    1102 
    1103     void erase(const UEdge& edge) {
    1104 
    1105       if (edges[edge.id].prev_out != -1) {
    1106         edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
    1107       } else {
    1108         aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
    1109       }
    1110       if (edges[edge.id].next_out != -1) {
    1111         edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
    1112       }
    1113 
    1114       if (edges[edge.id].prev_in != -1) {
    1115         edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
    1116       } else {
    1117         bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
    1118       }
    1119       if (edges[edge.id].next_in != -1) {
    1120         edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
    1121       }
    1122 
    1123       edges[edge.id].next_out = first_free_edge;
    1124       first_free_edge = edge.id;
    1125     }
    1126 
    1127     void clear() {
    1128       aNodes.clear();
    1129       bNodes.clear();
    1130       edges.clear();
    1131       first_anode = -1;
    1132       first_free_anode = -1;
    1133       first_bnode = -1;
    1134       first_free_bnode = -1;
    1135       first_free_edge = -1;
    1136     }
    1137 
    1138   };
    1139 
    1140 
    1141   typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
    1142 
    1143   /// \ingroup graphs
    1144   ///
    1145   /// \brief A smart bipartite undirected graph class.
    1146   ///
    1147   /// This is a bipartite undirected graph implementation.
    1148   /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph"
    1149   /// concept.
    1150   /// \sa concept::BpUGraph.
    1151   ///
    1152   class ListBpUGraph : public ExtendedListBpUGraphBase {};
    1153 
    1154  
    1155   /// @} 
    1156704} //namespace lemon
    1157705 
Note: See TracChangeset for help on using the changeset viewer.