COIN-OR::LEMON - Graph Library

Changeset 690:a0f95e1b17fc in lemon-0.x


Ignore:
Timestamp:
07/05/04 17:52:35 (15 years ago)
Author:
Hegyi Péter
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@940
Message:
 
Location:
src/work/peter
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/peter/Makefile

    r677 r690  
     1hier: hierarchygraph.h hierarchygraph_test.cc
     2        g++ -Wall -W -I../.. -I../klao -I../../hugo hierarchygraph_test.cc -o test
     3
    14edge: edgepathgraph_test.cc edgepathgraph.h
    2         g++ -I../.. -I../klao -I../../hugo edgepathgraph_test.cc -o test
     5        g++ -Wall -W -I../.. -I../klao -I../../hugo edgepathgraph_test.cc -o test
    36
    4 hier: hierarchygraph.h hierarchygraph_test.cc
    5         g++ -I../.. -I../klao -I../../hugo hierarchygraph_test.cc -o test
  • src/work/peter/hierarchygraph.h

    r677 r690  
    1616
    1717  /// A graph class in that a simple edge can represent a path.
    18  
     18
    1919  /// This class provides common features of a graph structure
    2020  /// that represents a network. You can handle with it layers. This
     
    3232
    3333
    34     /// Map of subnetworks that are represented by the nodes of this layer
    35     typename Gact::template NodeMap<Gsub> subnetwork;
    36 
     34    /// Map of the subnetworks in the sublayer
     35    /// The appropriate edge nodes are also stored here
     36
     37    class SubNetwork
     38    {
     39
     40      struct actedgesubnodestruct
     41      {
     42        typename Gact::Edge actedge;
     43        typename Gsub::Node subnode;
     44      };
     45
     46      int edgenumber;
     47      bool connectable;
     48      Gact * actuallayer;
     49      typename Gact::Node * actuallayernode;
     50      Gsub * subnetwork;
     51      actedgesubnodestruct * assignments;
     52
     53    public:
     54
     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;
     79        //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        }
     89        //if(!(actuallayer->valid(assignments[i].actedge)))   //this condition is necessary if we do not obey redefinition
     90        {
     91          assignments[i].actedge=actedge;
     92          assignments[i].subnode=subnode;
     93        }
     94
     95        /// If to all of the edges a subnode is assigned then the subnetwork is connectable (attachable?)
     96        /// We do not need to check for further attributes, because to notice an assignment we need
     97        /// all of them to be correctly initialised before.
     98        if(i==edgenumber-1)connectable=1;
     99
     100        return 0;
     101      }
     102
     103      int setSubNetwork(Gsub * sn)
     104      {
     105        subnetwork=sn;
     106        return 0;
     107      }
     108
     109      int setActualLayer(Gact * al)
     110      {
     111        actuallayer=al;
     112        return 0;
     113      }
     114
     115      int setActualLayerNode(typename Gact::Node * aln)
     116      {
     117        typename Gact::InEdgeIt iei;
     118        typename Gact::OutEdgeIt oei;
     119
     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        }
     145        else
     146        {
     147          cerr << "There is no actual layer defined yet!" << endl;
     148          return -1;
     149        }
     150
     151        return 0;
     152      }
     153
     154      SubNetwork(): edgenumber(0), connectable(false), actuallayer(NULL), actuallayernode(NULL), subnetwork(NULL), assignments(NULL)
     155      {
     156      }
     157
     158    };
     159
     160    typename Gact::template NodeMap< SubNetwork > subnetworks;
    37161
    38162
     
    41165    /// variable has run its constructor, when we have created this class
    42166    /// So only the two maps has to be initialised here.
    43     HierarchyGraph() : subnetwork(actuallayer)
     167    HierarchyGraph() : subnetworks(actuallayer)
    44168    {
    45169    }
     
    47171
    48172    ///Copy consructor.
    49     HierarchyGraph(const HierarchyGraph<Gact, Gsub> & HG ) : actuallayer(HG.actuallayer), subnetwork(actuallayer)
     173    HierarchyGraph(const HierarchyGraph<Gact, Gsub> & HG ) : actuallayer(HG.actuallayer), subnetworks(actuallayer)
    50174    {
    51175    }
    52176
    53  
     177
    54178    /// The base type of the node iterators.
    55179
     
    59183    typedef typename Gact::Node Node;
    60184
    61    
     185
    62186    /// This iterator goes through each node.
    63187
     
    70194    /// The NodeIt type of the HierarchyGraph is the NodeIt type of the actual layer.
    71195    typedef typename Gact::NodeIt NodeIt;
    72    
    73    
     196
     197
    74198    /// The base type of the edge iterators.
    75199    /// The Edge type of the HierarchyGraph is the Edge type of the actual layer.
    76200    typedef typename  Gact::Edge Edge;
    77201
    78    
     202
    79203    /// This iterator goes trough the outgoing edges of a node.
    80204
     
    161285    ///Gives back the tail node of an edge.
    162286    typename Gact::Node tail(typename Gact::Edge edge) const { return actuallayer.tail(edge); }
    163  
     287
    164288    //   Node aNode(InEdgeIt) const {}
    165289    //   Node aNode(OutEdgeIt) const {}
     
    194318    //void setInvalid(Node &) const {};
    195319    //void setInvalid(Edge &) const {};
    196  
     320
    197321    ///Add a new node to the graph.
    198322
     
    206330    ///\return the new edge.
    207331    typename Gact::Edge addEdge(typename Gact::Node node1, typename Gact::Node node2) { return actuallayer.addEdge(node1, node2);}
    208    
     332
    209333    /// Resets the graph.
    210334
     
    272396      EdgeMap(const HierarchyGraph &) {}
    273397      EdgeMap(const HierarchyGraph &, T ) {}
    274    
     398
    275399      ///\todo It can copy between different types.
    276400      ///
     
    281405      T &operator[](Edge) {return *(T*)0;}
    282406      const T &operator[](Edge) const {return *(T*)0;}
    283    
     407
    284408      void update() {}
    285409      void update(T a) {}   //FIXME: Is it necessary
     
    288412
    289413  /// An empty eraseable graph class.
    290  
     414
    291415  /// This class provides all the common features of an \e eraseable graph
    292416  /// structure,
     
    301425  /// It can be used for checking the interface compatibility,
    302426  /// or it can serve as a skeleton of a new graph structure.
    303   /// 
     427  ///
    304428  /// Also, you will find here the full documentation of a certain graph
    305429  /// feature, the documentation of a real graph imlementation
     
    321445  };
    322446
    323  
     447
    324448  // @}
    325449
  • src/work/peter/hierarchygraph_test.cc

    r677 r690  
    2323{
    2424  HierarchyGraph<SmartGraph, ListGraph> HGr;
     25  ListGraph subnetwork, othernetwork;
     26  typedef HierarchyGraph<SmartGraph, ListGraph>::Node Node;
     27  typedef HierarchyGraph<SmartGraph, ListGraph>::Edge Edge;
     28  typedef HierarchyGraph<SmartGraph, ListGraph>::SubNetwork Sntype;
     29
     30  Node n0, n1, n2;
     31  Edge e0, e1, e2, e3, e4, e5;
     32
     33  ListGraph::Node sn0, sn1, on0;
     34  ListGraph::Edge se0;
     35
     36  n0=HGr.addNode();
     37
     38  cout << "Az n0 id-je: " << HGr.actuallayer.id(n0) << endl;
     39
     40  n1=HGr.addNode();
     41  n2=HGr.addNode();
     42 
     43  e0=HGr.addEdge(n0,n1);
     44  e1=HGr.addEdge(n1,n0);
     45  e2=HGr.addEdge(n0,n2);
     46  e3=HGr.addEdge(n2,n0);
     47  e4=HGr.addEdge(n1,n2);
     48  e5=HGr.addEdge(n2,n1);
     49
     50  sn0=subnetwork.addNode();
     51  sn1=subnetwork.addNode();
     52  se0=subnetwork.addEdge(sn0,sn1);
     53
     54  Sntype sn;
     55  sn.setActualLayer(&(HGr.actuallayer));
     56  sn.setActualLayerNode(&(n0));
     57  sn.addAssignment(e0, sn0);
     58  sn.addAssignment(e1, sn1);
     59  sn.addAssignment(e2, sn1);
     60  sn.addAssignment(e3, sn0);
     61  sn.addAssignment(e1, sn0);
     62  sn.addAssignment(e5, sn0);
     63 
     64
     65
     66  on0=othernetwork.addNode();
     67
     68  cout << "ID of a node from a different graph: " << subnetwork.id(on0) << endl;
     69  cout << "ID of a node in its graph: " << othernetwork.id(on0) << endl;
     70  cout << "ID of a node from a  graph: " << subnetwork.id(sn0) << endl;
     71
     72  ListGraph::NodeIt snni;
     73  //ListGraph::Node snn;
     74
     75  for(subnetwork.first(snni);subnetwork.valid(snni);subnetwork.next(snni))
     76  {
     77    if(snni==on0)
     78    {
     79      cout << "Nem jo, megtalalta az idegen node-ot sajat haloban, pedig azt nem szabad!!!"
     80           << subnetwork.id(snni) << subnetwork.id(on0) << othernetwork.id(snni) << othernetwork.id(on0) << endl;
     81    }
     82    else cout << "ID:" << subnetwork.id(snni) << endl;
     83     
     84  }
     85 
     86
     87  HGr.subnetworks[n0]=sn;
     88 
    2589}
Note: See TracChangeset for help on using the changeset viewer.