COIN-OR::LEMON - Graph Library

Changeset 691:014c2e4eb07b in lemon-0.x for src/work


Ignore:
Timestamp:
07/05/04 18:44:18 (20 years ago)
Author:
Hegyi Péter
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@941
Message:

t/bin/bash: line 1: q: command not found
-j-This line, and those below, will be ignored--

M peter/hierarchygraph.h

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/peter/hierarchygraph.h

    r690 r691  
    1010
    1111/// The namespace of HugoLib
    12 namespace hugo {
     12namespace hugo
     13{
    1314
    1415  // @defgroup empty_graph The HierarchyGraph class
     
    2223  /// layer.
    2324
    24   template <class Gact, class Gsub>
    25   class HierarchyGraph
     25  template < class Gact, class Gsub > class HierarchyGraph
    2626  {
    2727
     
    4040      struct actedgesubnodestruct
    4141      {
    42         typename Gact::Edge actedge;
    43         typename Gsub::Node subnode;
     42        typename Gact::Edge actedge;
     43        typename Gsub::Node subnode;
    4444      };
    4545
    4646      int edgenumber;
    4747      bool connectable;
    48       Gact * actuallayer;
     48      Gact *actuallayer;
    4949      typename Gact::Node * actuallayernode;
    50       Gsub * subnetwork;
    51       actedgesubnodestruct * assignments;
     50      Gsub *subnetwork;
     51      actedgesubnodestruct *assignments;
    5252
    5353    public:
    5454
    55       int addAssignment(typename Gact::Edge actedge, typename Gsub::Node subnode)
    56       {
    57         if(!(actuallayer->valid(actedge)))
    58         {
    59           cerr << "The given edge is not in the given network!" << endl;
    60           return -1;
    61         }
    62         else if(
    63            (actuallayer->id(actuallayer->tail(actedge))!=actuallayer->id(*actuallayernode))
    64            &&
    65            (actuallayer->id(actuallayer->head(actedge))!=actuallayer->id(*actuallayernode))
    66           )
    67         {
    68           cerr << "The given edge does not connect to the given node!" << endl;
    69           return -1;
    70         }
    71 
    72         if(!(subnetwork->valid(subnode)))
    73         {
    74           cerr << "The given node is not in the given network!" << endl;
    75           return -1;
    76         }
    77 
    78         int i=0;
     55      int addAssignment (typename Gact::Edge actedge,
     56                         typename Gsub::Node subnode)
     57      {
     58        if (!(actuallayer->valid (actedge)))
     59          {
     60            cerr << "The given edge is not in the given network!" << endl;
     61            return -1;
     62          }
     63        else if ((actuallayer->id (actuallayer->tail (actedge)) !=
     64                  actuallayer->id (*actuallayernode))
     65                 && (actuallayer->id (actuallayer->head (actedge)) !=
     66                     actuallayer->id (*actuallayernode)))
     67          {
     68            cerr << "The given edge does not connect to the given node!" <<
     69              endl;
     70            return -1;
     71          }
     72
     73        if (!(subnetwork->valid (subnode)))
     74          {
     75            cerr << "The given node is not in the given network!" << endl;
     76            return -1;
     77          }
     78
     79        int i = 0;
    7980        //while in the array there is valid note that is not equvivalent with the one that would be noted increase i
    80         while( (i<edgenumber) && (actuallayer->valid(assignments[i].actedge) ) && (assignments[i].actedge!=actedge) ) i++;
    81         if(assignments[i].actedge==actedge)
    82         {
    83           cout << "Warning: Redefinement of assigment!!!" << endl;
    84         }
    85         if(i==edgenumber)
    86         {
    87           cout << "This case can't be!!! (because there should be the guven edge in the array already and the cycle had to stop)" << endl;
    88         }
     81        while ((i < edgenumber)
     82               && (actuallayer->valid (assignments[i].actedge))
     83               && (assignments[i].actedge != actedge))
     84          i++;
     85        if (assignments[i].actedge == actedge)
     86          {
     87            cout << "Warning: Redefinement of assigment!!!" << endl;
     88          }
     89        if (i == edgenumber)
     90          {
     91            cout <<
     92              "This case can't be!!! (because there should be the guven edge in the array already and the cycle had to stop)"
     93              << endl;
     94          }
    8995        //if(!(actuallayer->valid(assignments[i].actedge)))   //this condition is necessary if we do not obey redefinition
    9096        {
    91           assignments[i].actedge=actedge;
    92           assignments[i].subnode=subnode;
     97          assignments[i].actedge = actedge;
     98          assignments[i].subnode = subnode;
    9399        }
    94100
     
    96102        /// We do not need to check for further attributes, because to notice an assignment we need
    97103        /// all of them to be correctly initialised before.
    98         if(i==edgenumber-1)connectable=1;
     104        if (i == edgenumber - 1)
     105          connectable = 1;
    99106
    100107        return 0;
    101108      }
    102109
    103       int setSubNetwork(Gsub * sn)
    104       {
    105         subnetwork=sn;
     110      int setSubNetwork (Gsub * sn)
     111      {
     112        subnetwork = sn;
    106113        return 0;
    107114      }
    108115
    109       int setActualLayer(Gact * al)
    110       {
    111         actuallayer=al;
     116      int setActualLayer (Gact * al)
     117      {
     118        actuallayer = al;
    112119        return 0;
    113120      }
    114121
    115       int setActualLayerNode(typename Gact::Node * aln)
     122      int setActualLayerNode (typename Gact::Node * aln)
    116123      {
    117124        typename Gact::InEdgeIt iei;
    118125        typename Gact::OutEdgeIt oei;
    119126
    120         actuallayernode=aln;
    121 
    122         edgenumber=0;
    123 
    124         if(actuallayer)
    125         {
    126           for(iei=actuallayer->first(iei,(*actuallayernode));((actuallayer->valid(iei))&&(actuallayer->head(iei)==(*actuallayernode)));actuallayer->next(iei))
    127           {
    128             cout << actuallayer->id(actuallayer->tail(iei)) << " " << actuallayer->id(actuallayer->head(iei)) << endl;
    129             edgenumber++;
    130           }
    131           //cout << "Number of in-edges: " << edgenumber << endl;
    132           for(oei=actuallayer->first(oei,(*actuallayernode));((actuallayer->valid(oei))&&(actuallayer->tail(oei)==(*actuallayernode)));actuallayer->next(oei))
    133           {
    134             cout << actuallayer->id(actuallayer->tail(oei)) << " " << actuallayer->id(actuallayer->head(oei)) << endl;
    135             edgenumber++;
    136           }
    137           //cout << "Number of in+out-edges: " << edgenumber << endl;
    138           assignments=new actedgesubnodestruct[edgenumber];
    139           for(int i=0;i<edgenumber;i++)
    140           {
    141             assignments[i].actedge=INVALID;
    142             assignments[i].subnode=INVALID;
    143           }
    144         }
     127        actuallayernode = aln;
     128
     129        edgenumber = 0;
     130
     131        if (actuallayer)
     132          {
     133            for (iei = actuallayer->first (iei, (*actuallayernode));
     134                 ((actuallayer->valid (iei))
     135                  && (actuallayer->head (iei) == (*actuallayernode)));
     136                 actuallayer->next (iei))
     137              {
     138                cout << actuallayer->id (actuallayer->
     139                                         tail (iei)) << " " << actuallayer->
     140                  id (actuallayer->head (iei)) << endl;
     141                edgenumber++;
     142              }
     143            //cout << "Number of in-edges: " << edgenumber << endl;
     144            for (oei = actuallayer->first (oei, (*actuallayernode));
     145                 ((actuallayer->valid (oei))
     146                  && (actuallayer->tail (oei) == (*actuallayernode)));
     147                 actuallayer->next (oei))
     148              {
     149                cout << actuallayer->id (actuallayer->
     150                                         tail (oei)) << " " << actuallayer->
     151                  id (actuallayer->head (oei)) << endl;
     152                edgenumber++;
     153              }
     154            //cout << "Number of in+out-edges: " << edgenumber << endl;
     155            assignments = new actedgesubnodestruct[edgenumber];
     156            for (int i = 0; i < edgenumber; i++)
     157              {
     158                assignments[i].actedge = INVALID;
     159                assignments[i].subnode = INVALID;
     160              }
     161          }
    145162        else
    146         {
    147           cerr << "There is no actual layer defined yet!" << endl;
    148           return -1;
    149         }
     163          {
     164            cerr << "There is no actual layer defined yet!" << endl;
     165            return -1;
     166          }
    150167
    151168        return 0;
    152169      }
    153170
    154       SubNetwork(): edgenumber(0), connectable(false), actuallayer(NULL), actuallayernode(NULL), subnetwork(NULL), assignments(NULL)
     171    SubNetwork ():edgenumber (0), connectable (false), actuallayer (NULL),
     172        actuallayernode (NULL), subnetwork (NULL),
     173        assignments (NULL)
    155174      {
    156175      }
     
    158177    };
    159178
    160     typename Gact::template NodeMap< SubNetwork > subnetworks;
     179    typename Gact::template NodeMap < SubNetwork > subnetworks;
    161180
    162181
     
    165184    /// variable has run its constructor, when we have created this class
    166185    /// So only the two maps has to be initialised here.
    167     HierarchyGraph() : subnetworks(actuallayer)
     186  HierarchyGraph ():subnetworks (actuallayer)
    168187    {
    169188    }
     
    171190
    172191    ///Copy consructor.
    173     HierarchyGraph(const HierarchyGraph<Gact, Gsub> & HG ) : actuallayer(HG.actuallayer), subnetworks(actuallayer)
     192  HierarchyGraph (const HierarchyGraph < Gact, Gsub > &HG):actuallayer (HG.actuallayer),
     193      subnetworks
     194      (actuallayer)
    174195    {
    175196    }
     
    198219    /// The base type of the edge iterators.
    199220    /// The Edge type of the HierarchyGraph is the Edge type of the actual layer.
    200     typedef typename  Gact::Edge Edge;
     221    typedef typename Gact::Edge Edge;
    201222
    202223
     
    248269    /// \retval i the first node.
    249270    /// \return the first node.
    250     typename Gact::NodeIt &first(typename Gact::NodeIt &i) const { return actuallayer.first(i);}
     271    typename Gact::NodeIt & first (typename Gact::NodeIt & i) const
     272    {
     273      return actuallayer.first (i);
     274    }
    251275
    252276
    253277    /// The first incoming edge.
    254     typename Gact::InEdgeIt &first(typename Gact::InEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);}
     278    typename Gact::InEdgeIt & first (typename Gact::InEdgeIt & i,
     279                                     typename Gact::Node) const
     280    {
     281      return actuallayer.first (i);
     282    }
    255283
    256284
    257285    /// The first outgoing edge.
    258     typename Gact::OutEdgeIt &first(typename Gact::OutEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);}
     286    typename Gact::OutEdgeIt & first (typename Gact::OutEdgeIt & i,
     287                                      typename Gact::Node) const
     288    {
     289      return actuallayer.first (i);
     290    }
    259291
    260292
    261293    //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
    262294    /// The first edge of the Graph.
    263     typename Gact::EdgeIt &first(typename Gact::EdgeIt &i) const { return actuallayer.first(i);}
     295    typename Gact::EdgeIt & first (typename Gact::EdgeIt & i) const
     296    {
     297      return actuallayer.first (i);
     298    }
    264299
    265300
     
    272307
    273308    /// Go to the next node.
    274     typename Gact::NodeIt &next(typename Gact::NodeIt &i) const { return actuallayer.next(i);}
     309    typename Gact::NodeIt & next (typename Gact::NodeIt & i) const
     310    {
     311      return actuallayer.next (i);
     312    }
    275313    /// Go to the next incoming edge.
    276     typename Gact::InEdgeIt &next(typename Gact::InEdgeIt &i) const { return actuallayer.next(i);}
     314    typename Gact::InEdgeIt & next (typename Gact::InEdgeIt & i) const
     315    {
     316      return actuallayer.next (i);
     317    }
    277318    /// Go to the next outgoing edge.
    278     typename Gact::OutEdgeIt &next(typename Gact::OutEdgeIt &i) const { return actuallayer.next(i);}
     319    typename Gact::OutEdgeIt & next (typename Gact::OutEdgeIt & i) const
     320    {
     321      return actuallayer.next (i);
     322    }
    279323    //SymEdgeIt &next(SymEdgeIt &) const {}
    280324    /// Go to the next edge.
    281     typename Gact::EdgeIt &next(typename Gact::EdgeIt &i) const { return actuallayer.next(i);}
     325    typename Gact::EdgeIt & next (typename Gact::EdgeIt & i) const
     326    {
     327      return actuallayer.next (i);
     328    }
    282329
    283330    ///Gives back the head node of an edge.
    284     typename Gact::Node head(typename Gact::Edge edge) const { return actuallayer.head(edge); }
     331    typename Gact::Node head (typename Gact::Edge edge) const
     332    {
     333      return actuallayer.head (edge);
     334    }
    285335    ///Gives back the tail node of an edge.
    286     typename Gact::Node tail(typename Gact::Edge edge) const { return actuallayer.tail(edge); }
     336    typename Gact::Node tail (typename Gact::Edge edge) const
     337    {
     338      return actuallayer.tail (edge);
     339    }
    287340
    288341    //   Node aNode(InEdgeIt) const {}
     
    298351    ///\todo Maybe, it would be better if iterator converted to
    299352    ///bool directly, as Jacint prefers.
    300     bool valid(const typename Gact::Node& node) const { return actuallayer.valid(node);}
     353    bool valid (const typename Gact::Node & node) const
     354    {
     355      return actuallayer.valid (node);
     356    }
    301357    /// Checks if an edge iterator is valid
    302358
    303359    ///\todo Maybe, it would be better if iterator converted to
    304360    ///bool directly, as Jacint prefers.
    305     bool valid(const typename Gact::Edge& edge) const { return actuallayer.valid(edge);}
     361    bool valid (const typename Gact::Edge & edge) const
     362    {
     363      return actuallayer.valid (edge);
     364    }
    306365
    307366    ///Gives back the \e id of a node.
     
    309368    ///\warning Not all graph structures provide this feature.
    310369    ///
    311     int id(const typename Gact::Node & node) const { return actuallayer.id(node);}
     370    int id (const typename Gact::Node & node) const
     371    {
     372      return actuallayer.id (node);
     373    }
    312374    ///Gives back the \e id of an edge.
    313375
    314376    ///\warning Not all graph structures provide this feature.
    315377    ///
    316     int id(const typename Gact::Edge & edge) const { return actuallayer.id(edge);}
     378    int id (const typename Gact::Edge & edge) const
     379    {
     380      return actuallayer.id (edge);
     381    }
    317382
    318383    //void setInvalid(Node &) const {};
     
    323388    /// \return the new node.
    324389    ///
    325     typename Gact::Node addNode() { return actuallayer.addNode();}
     390    typename Gact::Node addNode ()
     391    {
     392      return actuallayer.addNode ();
     393    }
    326394    ///Add a new edge to the graph.
    327395
     
    329397    ///and head node \c head.
    330398    ///\return the new edge.
    331     typename Gact::Edge addEdge(typename Gact::Node node1, typename Gact::Node node2) { return actuallayer.addEdge(node1, node2);}
     399    typename Gact::Edge addEdge (typename Gact::Node node1,
     400                                 typename Gact::Node node2)
     401    {
     402      return actuallayer.addEdge (node1, node2);
     403    }
    332404
    333405    /// Resets the graph.
     
    335407    /// This function deletes all edges and nodes of the graph.
    336408    /// It also frees the memory allocated to store them.
    337     void clear() {actuallayer.clear();}
    338 
    339     int nodeNum() const { return actuallayer.nodeNum();}
    340     int edgeNum() const { return actuallayer.edgeNum();}
     409    void clear ()
     410    {
     411      actuallayer.clear ();
     412    }
     413
     414    int nodeNum () const
     415    {
     416      return actuallayer.nodeNum ();
     417    }
     418    int edgeNum () const
     419    {
     420      return actuallayer.edgeNum ();
     421    }
    341422
    342423    ///Read/write/reference map of the nodes to type \c T.
     
    350431    /// needs extra attention!
    351432
    352     template<class T> class NodeMap
     433    template < class T > class NodeMap
    353434    {
    354435    public:
     
    356437      typedef Node KeyType;
    357438
    358       NodeMap(const HierarchyGraph &) {}
    359       NodeMap(const HierarchyGraph &, T) {}
    360 
    361       template<typename TT> NodeMap(const NodeMap<TT> &) {}
     439      NodeMap (const HierarchyGraph &)
     440      {
     441      }
     442      NodeMap (const HierarchyGraph &, T)
     443      {
     444      }
     445
     446      template < typename TT > NodeMap (const NodeMap < TT > &)
     447      {
     448      }
    362449
    363450      /// Sets the value of a node.
     
    365452      /// Sets the value associated with node \c i to the value \c t.
    366453      ///
    367       void set(Node, T) {}
     454      void set (Node, T)
     455      {
     456      }
    368457      // Gets the value of a node.
    369458      //T get(Node i) const {return *(T*)0;}  //FIXME: Is it necessary?
    370       T &operator[](Node) {return *(T*)0;}
    371       const T &operator[](Node) const {return *(T*)0;}
     459      T & operator[](Node)
     460      {
     461        return *(T *) 0;
     462      }
     463      const T & operator[] (Node) const
     464      {
     465        return *(T *) 0;
     466      }
    372467
    373468      /// Updates the map if the graph has been changed
     
    375470      /// \todo Do we need this?
    376471      ///
    377       void update() {}
    378       void update(T a) {}   //FIXME: Is it necessary
     472      void update ()
     473      {
     474      }
     475      void update (T a)
     476      {
     477      }                         //FIXME: Is it necessary
    379478    };
    380479
     
    388487    /// \todo We may need conversion from other edgetype
    389488    /// \todo We may need operator=
    390     template<class T> class EdgeMap
     489    template < class T > class EdgeMap
    391490    {
    392491    public:
     
    394493      typedef Edge KeyType;
    395494
    396       EdgeMap(const HierarchyGraph &) {}
    397       EdgeMap(const HierarchyGraph &, T ) {}
     495      EdgeMap (const HierarchyGraph &)
     496      {
     497      }
     498      EdgeMap (const HierarchyGraph &, T)
     499      {
     500      }
    398501
    399502      ///\todo It can copy between different types.
    400503      ///
    401       template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
    402 
    403       void set(Edge, T) {}
     504      template < typename TT > EdgeMap (const EdgeMap < TT > &)
     505      {
     506      }
     507
     508      void set (Edge, T)
     509      {
     510      }
    404511      //T get(Edge) const {return *(T*)0;}
    405       T &operator[](Edge) {return *(T*)0;}
    406       const T &operator[](Edge) const {return *(T*)0;}
    407 
    408       void update() {}
    409       void update(T a) {}   //FIXME: Is it necessary
     512      T & operator[](Edge)
     513      {
     514        return *(T *) 0;
     515      }
     516      const T & operator[] (Edge) const
     517      {
     518        return *(T *) 0;
     519      }
     520
     521      void update ()
     522      {
     523      }
     524      void update (T a)
     525      {
     526      }                         //FIXME: Is it necessary
    410527    };
    411528  };
     
    430547  /// like @ref ListGraph or
    431548  /// @ref SmartGraph will just refer to this structure.
    432   template <typename Gact, typename Gsub>
    433   class EraseableHierarchyGraph : public HierarchyGraph<Gact, Gsub>
     549template < typename Gact, typename Gsub > class EraseableHierarchyGraph:public HierarchyGraph < Gact,
     550    Gsub
     551    >
    434552  {
    435553  public:
    436554    /// Deletes a node.
    437     void erase(typename Gact::Node n) {actuallayer.erase(n);}
     555    void erase (typename Gact::Node n)
     556    {
     557      actuallayer.erase (n);
     558    }
    438559    /// Deletes an edge.
    439     void erase(typename Gact::Edge e) {actuallayer.erase(e);}
     560    void erase (typename Gact::Edge e)
     561    {
     562      actuallayer.erase (e);
     563    }
    440564
    441565    /// Defalult constructor.
    442     EraseableHierarchyGraph() {}
     566    EraseableHierarchyGraph ()
     567    {
     568    }
    443569    ///Copy consructor.
    444     EraseableHierarchyGraph(const HierarchyGraph<Gact, Gsub> &EPG) {}
     570    EraseableHierarchyGraph (const HierarchyGraph < Gact, Gsub > &EPG)
     571    {
     572    }
    445573  };
    446574
     
    448576  // @}
    449577
    450 } //namespace hugo
     578}                               //namespace hugo
    451579
    452580
Note: See TracChangeset for help on using the changeset viewer.