lemon-0.x: src/work/peter/hierarchygraph.h@3bb4ed285c39

     1 // -*- c++ -*-

     2 #ifndef LEMON_NET_GRAPH_H

     3 #define LEMON_NET_GRAPH_H

     5 ///\file

     6 ///\brief Declaration of HierarchyGraph.

     8 #include <lemon/invalid.h>

     9 #include <lemon/maps.h>

    11 /// The namespace of LEMON

    12 namespace lemon

    13 {

    15   // @defgroup empty_graph The HierarchyGraph class

    16   // @{

    18   /// A graph class in that a simple edge can represent a path.

    20   /// This class provides common features of a graph structure

    21   /// that represents a network. You can handle with it layers. This

    22   /// means that a node in one layer can be a complete network in a nother

    23   /// layer.

    25   template < class Gact, class Gsub > class HierarchyGraph

    26   {

    28   public:

    30     /// The actual layer

    31     Gact actuallayer;

    34     /// Map of the subnetworks in the sublayer

    35     /// The appropriate edge nodes are also stored here

    37     class SubNetwork

    38     {

    40       struct actedgesubnodestruct

    41       {

    42 	typename Gact::Edge actedge;

    43 	typename Gsub::Node subnode;

    44       };

    46       int edgenumber;

    47       bool connectable;

    48       Gact *actuallayer;

    49       typename Gact::Node * actuallayernode;

    50       Gsub *subnetwork;

    51       actedgesubnodestruct *assignments;

    53     public:

    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->source (actedge)) !=

    64 		  actuallayer->id (*actuallayernode))

    65 		 && (actuallayer->id (actuallayer->target (actedge)) !=

    66 		     actuallayer->id (*actuallayernode)))

    67 	  {

    68 	    cerr << "The given edge does not connect to the given node!" <<

    69 	      endl;

    70 	    return -1;

    71 	  }

    73 	if (!(subnetwork->valid (subnode)))

    74 	  {

    75 	    cerr << "The given node is not in the given network!" << endl;

    76 	    return -1;

    77 	  }

    79 	int i = 0;

    80 	//while in the array there is valid note that is not equvivalent with the one that would be noted increase i

    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 	  }

    95 	//if(!(actuallayer->valid(assignments[i].actedge)))   //this condition is necessary if we do not obey redefinition

    96 	{

    97 	  assignments[i].actedge = actedge;

    98 	  assignments[i].subnode = subnode;

    99 	}

   101 	/// If to all of the edges a subnode is assigned then the subnetwork is connectable (attachable?)

   102 	/// We do not need to check for further attributes, because to notice an assignment we need

   103 	/// all of them to be correctly initialised before.

   104 	if (i == edgenumber - 1)

   105 	  connectable = 1;

   107 	return 0;

   108       }

   110       int setSubNetwork (Gsub * sn)

   111       {

   112 	subnetwork = sn;

   113 	return 0;

   114       }

   116       int setActualLayer (Gact * al)

   117       {

   118 	actuallayer = al;

   119 	return 0;

   120       }

   122       int setActualLayerNode (typename Gact::Node * aln)

   123       {

   124 	typename Gact::InEdgeIt iei;

   125 	typename Gact::OutEdgeIt oei;

   127 	actuallayernode = aln;

   129 	edgenumber = 0;

   131 	if (actuallayer)

   132 	  {

   133 	    for (iei = actuallayer->first (iei, (*actuallayernode));

   134 		 ((actuallayer->valid (iei))

   135 		  && (actuallayer->target (iei) == (*actuallayernode)));

   136 		 actuallayer->next (iei))

   137 	      {

   138 		cout << actuallayer->id (actuallayer->

   139 					 source (iei)) << " " << actuallayer->

   140 		  id (actuallayer->target (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->source (oei) == (*actuallayernode)));

   147 		 actuallayer->next (oei))

   148 	      {

   149 		cout << actuallayer->id (actuallayer->

   150 					 source (oei)) << " " << actuallayer->

   151 		  id (actuallayer->target (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 	  }

   162 	else

   163 	  {

   164 	    cerr << "There is no actual layer defined yet!" << endl;

   165 	    return -1;

   166 	  }

   168 	return 0;

   169       }

   171     SubNetwork ():edgenumber (0), connectable (false), actuallayer (NULL),

   172 	actuallayernode (NULL), subnetwork (NULL),

   173 	assignments (NULL)

   174       {

   175       }

   177     };

   179     typename Gact::template NodeMap < SubNetwork > subnetworks;

   182     /// Defalult constructor.

   183     /// We don't need any extra lines, because the actuallayer

   184     /// variable has run its constructor, when we have created this class

   185     /// So only the two maps has to be initialised here.

   186   HierarchyGraph ():subnetworks (actuallayer)

   187     {

   188     }

   191     ///Copy consructor.

   192   HierarchyGraph (const HierarchyGraph < Gact, Gsub > &HG):actuallayer (HG.actuallayer),

   193       subnetworks

   194       (actuallayer)

   195     {

   196     }

   199     /// The base type of the node iterators.

   201     /// This is the base type of each node iterators,

   202     /// thus each kind of node iterator will convert to this.

   203     /// The Node type of the HierarchyGraph is the Node type of the actual layer.

   204     typedef typename Gact::Node Node;

   207     /// This iterator goes through each node.

   209     /// Its usage is quite simple, for example you can count the number

   210     /// of nodes in graph \c G of type \c Graph like this:

   211     /// \code

   212     ///int count=0;

   213     ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;

   214     /// \endcode

   215     /// The NodeIt type of the HierarchyGraph is the NodeIt type of the actual layer.

   216     typedef typename Gact::NodeIt NodeIt;

   219     /// The base type of the edge iterators.

   220     /// The Edge type of the HierarchyGraph is the Edge type of the actual layer.

   221     typedef typename Gact::Edge Edge;

   224     /// This iterator goes trough the outgoing edges of a node.

   226     /// This iterator goes trough the \e outgoing edges of a certain node

   227     /// of a graph.

   228     /// Its usage is quite simple, for example you can count the number

   229     /// of outgoing edges of a node \c n

   230     /// in graph \c G of type \c Graph as follows.

   231     /// \code

   232     ///int count=0;

   233     ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;

   234     /// \endcode

   235     /// The OutEdgeIt type of the HierarchyGraph is the OutEdgeIt type of the actual layer.

   236     typedef typename Gact::OutEdgeIt OutEdgeIt;

   239     /// This iterator goes trough the incoming edges of a node.

   241     /// This iterator goes trough the \e incoming edges of a certain node

   242     /// of a graph.

   243     /// Its usage is quite simple, for example you can count the number

   244     /// of outgoing edges of a node \c n

   245     /// in graph \c G of type \c Graph as follows.

   246     /// \code

   247     ///int count=0;

   248     ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;

   249     /// \endcode

   250     /// The InEdgeIt type of the HierarchyGraph is the InEdgeIt type of the actual layer.

   251     typedef typename Gact::InEdgeIt InEdgeIt;

   254     /// This iterator goes through each edge.

   256     /// This iterator goes through each edge of a graph.

   257     /// Its usage is quite simple, for example you can count the number

   258     /// of edges in a graph \c G of type \c Graph as follows:

   259     /// \code

   260     ///int count=0;

   261     ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;

   262     /// \endcode

   263     /// The EdgeIt type of the HierarchyGraph is the EdgeIt type of the actual layer.

   264     typedef typename Gact::EdgeIt EdgeIt;

   267     /// First node of the graph.

   269     /// \retval i the first node.

   270     /// \return the first node.

   271     typename Gact::NodeIt & first (typename Gact::NodeIt & i) const

   272     {

   273       return actuallayer.first (i);

   274     }

   277     /// The first incoming edge.

   278     typename Gact::InEdgeIt & first (typename Gact::InEdgeIt & i,

   279 				     typename Gact::Node) const

   280     {

   281       return actuallayer.first (i);

   282     }

   285     /// The first outgoing edge.

   286     typename Gact::OutEdgeIt & first (typename Gact::OutEdgeIt & i,

   287 				      typename Gact::Node) const

   288     {

   289       return actuallayer.first (i);

   290     }

   293     //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}

   294     /// The first edge of the Graph.

   295     typename Gact::EdgeIt & first (typename Gact::EdgeIt & i) const

   296     {

   297       return actuallayer.first (i);

   298     }

   301 //     Node getNext(Node) const {}

   302 //     InEdgeIt getNext(InEdgeIt) const {}

   303 //     OutEdgeIt getNext(OutEdgeIt) const {}

   304 //     //SymEdgeIt getNext(SymEdgeIt) const {}

   305 //     EdgeIt getNext(EdgeIt) const {}

   308     /// Go to the next node.

   309     typename Gact::NodeIt & next (typename Gact::NodeIt & i) const

   310     {

   311       return actuallayer.next (i);

   312     }

   313     /// Go to the next incoming edge.

   314     typename Gact::InEdgeIt & next (typename Gact::InEdgeIt & i) const

   315     {

   316       return actuallayer.next (i);

   317     }

   318     /// Go to the next outgoing edge.

   319     typename Gact::OutEdgeIt & next (typename Gact::OutEdgeIt & i) const

   320     {

   321       return actuallayer.next (i);

   322     }

   323     //SymEdgeIt &next(SymEdgeIt &) const {}

   324     /// Go to the next edge.

   325     typename Gact::EdgeIt & next (typename Gact::EdgeIt & i) const

   326     {

   327       return actuallayer.next (i);

   328     }

   330     ///Gives back the target node of an edge.

   331     typename Gact::Node target (typename Gact::Edge edge) const

   332     {

   333       return actuallayer.target (edge);

   334     }

   335     ///Gives back the source node of an edge.

   336     typename Gact::Node source (typename Gact::Edge edge) const

   337     {

   338       return actuallayer.source (edge);

   339     }

   341     //   Node aNode(InEdgeIt) const {}

   342     //   Node aNode(OutEdgeIt) const {}

   343     //   Node aNode(SymEdgeIt) const {}

   345     //   Node bNode(InEdgeIt) const {}

   346     //   Node bNode(OutEdgeIt) const {}

   347     //   Node bNode(SymEdgeIt) const {}

   349     /// Checks if a node iterator is valid

   351     ///\todo Maybe, it would be better if iterator converted to

   352     ///bool directly, as Jacint prefers.

   353     bool valid (const typename Gact::Node & node) const

   354     {

   355       return actuallayer.valid (node);

   356     }

   357     /// Checks if an edge iterator is valid

   359     ///\todo Maybe, it would be better if iterator converted to

   360     ///bool directly, as Jacint prefers.

   361     bool valid (const typename Gact::Edge & edge) const

   362     {

   363       return actuallayer.valid (edge);

   364     }

   366     ///Gives back the \e id of a node.

   368     ///\warning Not all graph structures provide this feature.

   369     ///

   370     int id (const typename Gact::Node & node) const

   371     {

   372       return actuallayer.id (node);

   373     }

   374     ///Gives back the \e id of an edge.

   376     ///\warning Not all graph structures provide this feature.

   377     ///

   378     int id (const typename Gact::Edge & edge) const

   379     {

   380       return actuallayer.id (edge);

   381     }

   383     //void setInvalid(Node &) const {};

   384     //void setInvalid(Edge &) const {};

   386     ///Add a new node to the graph.

   388     /// \return the new node.

   389     ///

   390     typename Gact::Node addNode ()

   391     {

   392       return actuallayer.addNode ();

   393     }

   394     ///Add a new edge to the graph.

   396     ///Add a new edge to the graph with source node \c source

   397     ///and target node \c target.

   398     ///\return the new edge.

   399     typename Gact::Edge addEdge (typename Gact::Node node1,

   400 				 typename Gact::Node node2)

   401     {

   402       return actuallayer.addEdge (node1, node2);

   403     }

   405     /// Resets the graph.

   407     /// This function deletes all edges and nodes of the graph.

   408     /// It also frees the memory allocated to store them.

   409     void clear ()

   410     {

   411       actuallayer.clear ();

   412     }

   414     int nodeNum () const

   415     {

   416       return actuallayer.nodeNum ();

   417     }

   418     int edgeNum () const

   419     {

   420       return actuallayer.edgeNum ();

   421     }

   423     ///Read/write/reference map of the nodes to type \c T.

   425     ///Read/write/reference map of the nodes to type \c T.

   426     /// \sa MemoryMap

   427     /// \todo We may need copy constructor

   428     /// \todo We may need conversion from other nodetype

   429     /// \todo We may need operator=

   430     /// \warning Making maps that can handle bool type (NodeMap<bool>)

   431     /// needs extra attention!

   433     template < class T > class NodeMap

   434     {

   435     public:

   436       typedef T Value;

   437       typedef Node Key;

   439       NodeMap (const HierarchyGraph &)

   440       {

   441       }

   442       NodeMap (const HierarchyGraph &, T)

   443       {

   444       }

   446       template < typename TT > NodeMap (const NodeMap < TT > &)

   447       {

   448       }

   450       /// Sets the value of a node.

   452       /// Sets the value associated with node \c i to the value \c t.

   453       ///

   454       void set (Node, T)

   455       {

   456       }

   457       // Gets the value of a node.

   458       //T get(Node i) const {return *(T*)0;}  //FIXME: Is it necessary?

   459       T & operator[](Node)

   460       {

   461 	return *(T *) 0;

   462       }

   463       const T & operator[] (Node) const

   464       {

   465 	return *(T *) 0;

   466       }

   468       /// Updates the map if the graph has been changed

   470       /// \todo Do we need this?

   471       ///

   472       void update ()

   473       {

   474       }

   475       void update (T a)

   476       {

   477       }				//FIXME: Is it necessary

   478     };

   480     ///Read/write/reference map of the edges to type \c T.

   482     ///Read/write/reference map of the edges to type \c T.

   483     ///It behaves exactly in the same way as \ref NodeMap.

   484     /// \sa NodeMap

   485     /// \sa MemoryMap

   486     /// \todo We may need copy constructor

   487     /// \todo We may need conversion from other edgetype

   488     /// \todo We may need operator=

   489     template < class T > class EdgeMap

   490     {

   491     public:

   492       typedef T Value;

   493       typedef Edge Key;

   495       EdgeMap (const HierarchyGraph &)

   496       {

   497       }

   498       EdgeMap (const HierarchyGraph &, T)

   499       {

   500       }

   502       ///\todo It can copy between different types.

   503       ///

   504       template < typename TT > EdgeMap (const EdgeMap < TT > &)

   505       {

   506       }

   508       void set (Edge, T)

   509       {

   510       }

   511       //T get(Edge) const {return *(T*)0;}

   512       T & operator[](Edge)

   513       {

   514 	return *(T *) 0;

   515       }

   516       const T & operator[] (Edge) const

   517       {

   518 	return *(T *) 0;

   519       }

   521       void update ()

   522       {

   523       }

   524       void update (T a)

   525       {

   526       }				//FIXME: Is it necessary

   527     };

   528   };

   530   /// An empty erasable graph class.

   532   /// This class provides all the common features of an \e erasable graph

   533   /// structure,

   534   /// however completely without implementations and real data structures

   535   /// behind the interface.

   536   /// All graph algorithms should compile with this class, but it will not

   537   /// run properly, of course.

   538   ///

   539   /// \todo This blabla could be replaced by a sepatate description about

   540   /// s.

   541   ///

   542   /// It can be used for checking the interface compatibility,

   543   /// or it can serve as a skeleton of a new graph structure.

   544   ///

   545   /// Also, you will find here the full documentation of a certain graph

   546   /// feature, the documentation of a real graph imlementation

   547   /// like @ref ListGraph or

   548   /// @ref SmartGraph will just refer to this structure.

   549 template < typename Gact, typename Gsub > class ErasableHierarchyGraph:public HierarchyGraph < Gact,

   550     Gsub

   551     >

   552   {

   553   public:

   554     /// Deletes a node.

   555     void erase (typename Gact::Node n)

   556     {

   557       actuallayer.erase (n);

   558     }

   559     /// Deletes an edge.

   560     void erase (typename Gact::Edge e)

   561     {

   562       actuallayer.erase (e);

   563     }

   565     /// Defalult constructor.

   566     ErasableHierarchyGraph ()

   567     {

   568     }

   569     ///Copy consructor.

   570     ErasableHierarchyGraph (const HierarchyGraph < Gact, Gsub > &EPG)

   571     {

   572     }

   573   };

   576   // @}

   578 }				//namespace lemon

   581 #endif // LEMON_SKELETON_GRAPH_H

author	alpar
	Fri, 25 Mar 2005 08:18:27 +0000
changeset 1256	3bb4ed285c39
parent 986	e997802b855c
permissions	-rw-r--r--