eg_edgraph.ex.c

Go to the documentation of this file.
00001 /* EGlib "Efficient General Library" provides some basic structures and
00002  * algorithms commons in many optimization algorithms.
00003  *
00004  * Copyright (C) 2005 Daniel Espinoza and Marcos Goycoolea.
00005  * 
00006  * This library is free software; you can redistribute it and/or modify it
00007  * under the terms of the GNU Lesser General Public License as published by the
00008  * Free Software Foundation; either version 2.1 of the License, or (at your
00009  * option) any later version.
00010  *
00011  * This library is distributed in the hope that it will be useful, but 
00012  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
00013  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
00014  * License for more details.
00015  *
00016  * You should have received a copy of the GNU Lesser General Public License
00017  * along with this library; if not, write to the Free Software Foundation,
00018  * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
00019  * */
00020 /** @file
00021  * @ingroup EGeDgraph
00022  * */
00023 /** @addtogroup EGeDgraph */
00024 /** @{ */
00025 #include "EGlib.h"
00026 /* ========================================================================= */
00027 /** @brief example of a graph structure using the embeded substructures. */
00028 typedef struct my_dgraph_t
00029 {
00030   int id;
00031   EGeDgraph_t G;
00032 }
00033 my_dgraph_t;
00034 
00035 /* ========================================================================= */
00036 /** @brief example of a node structure using the embeded substructures. */
00037 typedef struct my_dnode_t
00038 {
00039   int id;
00040   EGeDgraphNode_t v;
00041 }
00042 my_dnode_t;
00043 
00044 /* ========================================================================= */
00045 /** @brief example of an edge structure using the embeded substructures. */
00046 typedef struct my_dedge_t
00047 {
00048   int id;
00049   EGeDgraphEdge_t e;
00050 }
00051 my_dedge_t;
00052 
00053 /* ========================================================================= */
00054 /** @brief Display the contents of our graph structure */
00055 static inline void display_DG (my_dgraph_t * myG)
00056 {
00057   EGeDgraph_t *G = &(myG->G);
00058   my_dnode_t *cn;
00059   my_dedge_t *ce;
00060   EGeList_t *node_it,
00061    *edge_it;
00062   fprintf (stderr, "Graph %d (%d nodes, %d edges):\n", myG->id, G->n_nodes,
00063            G->n_edges);
00064   /* we display the nodes and it's contents only if it is not empty */
00065   if (!EGeListIsEmpty (&(G->nodes)))
00066   {
00067     fprintf (stderr, "Nodes:\n");
00068     for (node_it = G->nodes.next; node_it != &(G->nodes);
00069          node_it = node_it->next)
00070     {
00071       cn = EGcontainerOf (node_it, my_dnode_t, v.node_cn);
00072       fprintf (stderr, "\t%d: ", cn->id);
00073       if (!EGeListIsEmpty (&(cn->v.in_edge)))
00074       {
00075         fprintf (stderr, "(in edges) ");
00076         for (edge_it = cn->v.in_edge.next; edge_it != &(cn->v.in_edge);
00077              edge_it = edge_it->next)
00078         {
00079           ce = EGcontainerOf (edge_it, my_dedge_t, e.head_cn);
00080           fprintf (stderr, "%d ", ce->id);
00081         }
00082       }
00083       if (!EGeListIsEmpty (&(cn->v.out_edge)))
00084       {
00085         fprintf (stderr, "(out edges) ");
00086         for (edge_it = cn->v.out_edge.next; edge_it != &(cn->v.out_edge);
00087              edge_it = edge_it->next)
00088         {
00089           ce = EGcontainerOf (edge_it, my_dedge_t, e.tail_cn);
00090           fprintf (stderr, "%d ", ce->id);
00091         }
00092       }
00093       fprintf (stderr, "\n");
00094     }
00095   }
00096 
00097 }
00098 
00099 /* ========================================================================= */
00100 /** @brief A simple example of a directed graph using (EGdEgraph) structures.
00101  * @return zero on success, non-zero- otherwise.
00102  * @par Description:
00103  * Show how to use a directed graph, modify it and display it's contents */
00104 int main (void)
00105 {
00106   int rval = 0;
00107   my_dgraph_t myG;
00108   my_dnode_t nodes[5];
00109   my_dedge_t edges[5];
00110   int i;
00111 
00112   /* initialize all structures */
00113   EGlib_info();
00114   EGlib_version();
00115   EGeDgraphInit (&(myG.G));
00116   myG.id = 0;
00117   /* set signal and limits */
00118   EGsigSet(rval,CLEANUP);
00119   EGsetLimits(3600.0,4294967295UL);
00120   display_DG (&myG);
00121   /* note that this is a backward loop that should be more eficient than the
00122    * regular forward loop (you save the last update condition ) */
00123   for (i = 5; i--;)
00124   {
00125     EGeDgraphNodeInit (&(nodes[i].v));
00126     EGeDgraphEdgeInit (&(edges[i].e));
00127     nodes[i].id = i;
00128     edges[i].id = i;
00129   }
00130   /* now we can use all edges and nodes and add them to the graph, we will
00131    * create a circular graph on 5 edges */
00132   for (i = 5; i--;)
00133     EGeDgraphAddNode (&(myG.G), &(nodes[i].v));
00134   display_DG (&myG);
00135   for (i = 5; i--;)
00136     EGeDgraphAddEdge (&(myG.G), &(nodes[i].v), &(nodes[(i + 1) % 5].v),
00137                       &(edges[i].e));
00138   display_DG (&myG);
00139   /* now we will push all incomming edges to a previous node, and all outgoing
00140    * edges to the next edge */
00141   for (i = 5; i--;)
00142   {
00143     EGeDgraphChangeHead (&(myG.G), &(edges[i].e), &(nodes[(i + 4) % 5].v));
00144     EGeDgraphChangeTail (&(myG.G), &(edges[i].e), &(nodes[(i + 2) % 5].v));
00145   }
00146   display_DG (&myG);
00147   /* now we delete one edge at a time */
00148   for (i = 5; i--;)
00149   {
00150     EGeDgraphDelEdge (&(myG.G), &(edges[i].e));
00151     display_DG (&myG);
00152   }
00153   /* and delete nodes one by one */
00154   for (i = 5; i--;)
00155   {
00156     EGeDgraphDelNode (&(myG.G), &(nodes[i].v));
00157     display_DG (&myG);
00158   }
00159   /* ending */
00160   CLEANUP:
00161   EGeDgraphClear (&myG);
00162   for (i = 5; i--;)
00163   {
00164     EGeDgraphNodeClear (&(nodes[i].v));
00165     EGeDgraphEdgeClear (&(edges[i].e));
00166   }
00167   return rval;
00168 }
00169 
00170 /* ========================================================================= */
00171 /** @} */