Graphviz: lib/graph/edge.c Source File

00001 /* $Id: edge.c,v 1.3 2008/02/26 03:35:43 glenlow Exp $ $Revision: 1.3 $ */
00002 /* vim:set shiftwidth=4 ts=8: */
00003 
00004 /**********************************************************
00005 *      This software is part of the graphviz package      *
00006 *                http://www.graphviz.org/                 *
00007 *                                                         *
00008 *            Copyright (c) 1994-2004 AT&T Corp.           *
00009 *                and is licensed under the                *
00010 *            Common Public License, Version 1.0           *
00011 *                      by AT&T Corp.                      *
00012 *                                                         *
00013 *        Information and Software Systems Research        *
00014 *              AT&T Research, Florham Park NJ             *
00015 **********************************************************/
00016 
00017 #include <limits.h>
00018 
00019 #include "libgraph.h"
00020 
00021 #ifdef DMALLOC
00022 #include "dmalloc.h"
00023 #endif
00024 
00025 static void graphs_of_e(Agedge_t * e, Dict_t * g_e, Agraph_t * g)
00026 {
00027     Agedge_t *sub;
00028 
00029     if (dtsearch(g->inedges, e) == NULL)
00030         return;
00031     if (dtsearch(g_e, g->meta_node))
00032         return;
00033     dtinsert(g_e, g->meta_node);
00034     for (sub = agfstin(g->meta_node->graph, g->meta_node); sub;
00035          sub = agnxtin(g->meta_node->graph, sub))
00036         graphs_of_e(e, g_e, agusergraph(sub->head));
00037 }
00038 
00039 static Agedge_t *esearch(Agraph_t * g, Agnode_t * tail, Agnode_t * head,
00040                          char *usrkey)
00041 {
00042     Agedge_t key, *e;
00043     char *attr[KEYX + 1];
00044 
00045     attr[KEYX] = usrkey;
00046     key.tail = tail;
00047     key.head = head;
00048     key.attr = (usrkey ? attr : 0);
00049     if (usrkey)
00050         e = (Agedge_t *) dtsearch(g->inedges, &key);
00051     else {
00052         e = (Agedge_t *) dtnext(g->inedges, &key);
00053         if (e && ((e->tail != tail) || (e->head != head)))
00054             e = NULL;
00055     }
00056     return e;
00057 }
00058 
00059 Agedge_t *agfindedge(Agraph_t * g, Agnode_t * tail, Agnode_t * head)
00060 {
00061     Agedge_t *e;
00062 
00063     e = esearch(g, tail, head, NULL);
00064     if ((e == NULL) && !(AG_IS_DIRECTED(g)))
00065         e = esearch(g, head, tail, NULL);
00066     return e;
00067 }
00068 
00069 static void install_edge(Agraph_t * g, Agedge_t * e)
00070 {
00071     Agraph_t *meta;
00072     Agedge_t *f;
00073 
00074     if (dtsearch(g->inedges, e))
00075         return;
00076     agINSnode(g, e->tail);
00077     agINSnode(g, e->head);
00078     dtinsert(g->outedges, e);
00079     dtinsert(g->inedges, e);
00080     f = (Agedge_t *) dtprev(g->outedges, e);
00081     if (f && (f->tail == e->tail) && (f->head == e->head)
00082         && (e->printkey == NOPRINT))
00083         e->printkey = MULTIPLE;
00084     if (AG_IS_METAGRAPH(g) == FALSE) {
00085         meta = g->meta_node->graph;
00086         for (f = agfstin(meta, g->meta_node); f; f = agnxtin(meta, f)) {
00087             install_edge(agusergraph(f->tail), e);
00088         }
00089     }
00090 }
00091 
00092 void agINSedge(Agraph_t * g, Agedge_t * e)
00093 {
00094     if (e->printkey == MULTIPLE)
00095         e->printkey = MUSTPRINT;
00096     install_edge(g, e);
00097 }
00098 
00099 
00100 static int printedge(Dict_t * d, void *p, void *ignored)
00101 {
00102     Agedge_t *e = (Agedge_t *) p;
00103     agerr(AGPREV, "\t%p %s,%s\n", e, e->tail->name, e->head->name);
00104     return 0;
00105 }
00106 
00107 Agedge_t *agfstedge(Agraph_t * g, Agnode_t * n)
00108 {
00109     Agedge_t *e;
00110 
00111     e = NULL;
00112     if ((g != NULL) && (n != NULL)) {
00113         e = agfstout(g, n);
00114         if (e == NULL)
00115             e = agfstin(g, n);
00116     }
00117     return e;
00118 }
00119 
00120 Agedge_t *agnxtedge(Agraph_t * g, Agedge_t * e, Agnode_t * n)
00121 {
00122     Agedge_t *f;
00123 
00124     f = NULL;
00125     if ((g != NULL) && (e != NULL) && (n != NULL)) {
00126         if (e->tail == n) {
00127             f = (Agedge_t *) dtnext(g->outedges, e);
00128             if ((f != NULL) && (f->tail == n))
00129                 return f;
00130             f = agfstin(g, n);
00131             while (f && (f->head == f->tail) && (f->head == n))
00132                 f = (Agedge_t *) dtnext(g->inedges, f);
00133         } else {
00134             if (e->head != n)
00135                 return NULL;
00136             else
00137                 f = (Agedge_t *) dtnext(g->inedges, e);
00138         }
00139         while (f && (f->head == f->tail) && (f->head == n))
00140             f = (Agedge_t *) dtnext(g->inedges, f);
00141         if (f && (f->head != n))
00142             f = NULL;
00143     }
00144     return f;
00145 }
00146 
00147 Agedge_t *agfstout(Agraph_t * g, Agnode_t * n)
00148 {
00149     Agedge_t *f, key;
00150 
00151     f = NULL;
00152     if ((g != NULL) && (n != NULL)) {
00153         key.tail = n;
00154         key.head = NULL;
00155         key.attr = NULL;
00156         f = (Agedge_t *) dtnext(g->outedges, &key);
00157         if (f && (f->tail != n))
00158             f = NULL;
00159     }
00160     return f;
00161 }
00162 
00163 Agedge_t *agnxtout(Agraph_t * g, Agedge_t * e)
00164 {
00165     Agedge_t *f;
00166     f = (Agedge_t *) dtnext(g->outedges, e);
00167     if (f && (f->tail != e->tail))
00168         f = NULL;
00169     return f;
00170 }
00171 
00172 Agedge_t *agfstin(Agraph_t * g, Agnode_t * n)
00173 {
00174     Agedge_t *f, key;
00175 
00176     f = NULL;
00177     if ((g != NULL) && (n != NULL)) {
00178         key.head = n;
00179         key.tail = NULL;
00180         key.attr = NULL;
00181         f = (Agedge_t *) dtnext(g->inedges, &key);
00182         if (f && (f->head != n))
00183             f = NULL;
00184     }
00185     return f;
00186 }
00187 
00188 Agedge_t *agnxtin(Agraph_t * g, Agedge_t * e)
00189 {
00190     Agedge_t *f;
00191 
00192     f = (Agedge_t *) dtnext(g->inedges, e);
00193     if (f && (f->head != e->head))
00194         f = NULL;
00195     return f;
00196 }
00197 
00198 Agedge_t *agNEWedge(Agraph_t * subg, Agnode_t * tail, Agnode_t * head,
00199                     Agedge_t * proto)
00200 {
00201     int i, nobj;
00202     Agedge_t *e;
00203 
00204     e = (Agedge_t *) calloc(1, AG.edge_nbytes);
00205     e->tag = TAG_EDGE;
00206     e->tail = tail;
00207     e->head = head;
00208     e->id = subg->univ->max_edge_id++;
00209 
00210     nobj = dtsize(subg->univ->edgeattr->dict);
00211     if (nobj) {
00212                 e->attr = N_NEW(nobj, char *);
00213                 e->didset = N_NEW((nobj + CHAR_BIT - 1) / CHAR_BIT, char);
00214         }
00215     else {
00216                 e->attr = NULL;
00217                 e->didset = NULL;
00218         }
00219     for (i = 0; i < nobj; i++)
00220                 e->attr[i] =
00221                         agstrdup(proto ? proto->attr[i] : subg->univ->edgeattr->
00222                                  list[i]->value);
00223     return e;
00224 }
00225 
00226 Agedge_t *agedge(Agraph_t * g, Agnode_t * tail, Agnode_t * head)
00227 {
00228     Agedge_t *e;
00229     char *keystr, key[SMALLBUF], printkey = NOPRINT;
00230     static int ctr;
00231 
00232     keystr = g->proto->e->attr[KEYX];   /* temporarily set aside */
00233     e = NULL;
00234     g->proto->e->head = head;
00235     g->proto->e->tail = tail;
00236     if (AG_IS_STRICT(g)) {
00237         e = esearch(g, tail, head, NULL);
00238         if (!e && !AG_IS_DIRECTED(g))
00239             e = esearch(g, head, tail, NULL);
00240         if (e)
00241             install_edge(g, e);
00242     } else {
00243         if (keystr[0]) {
00244             e = esearch(g, tail, head, keystr);
00245             if (!e && !AG_IS_DIRECTED(g))
00246                 e = esearch(g, head, tail, keystr);
00247             if (e)
00248                 agINSedge(g, e);
00249             else
00250                 printkey = MUSTPRINT;
00251         } else {
00252             sprintf(key, "%d", ctr++);
00253             g->proto->e->attr[KEYX] = key;
00254         }
00255     }
00256     if (e == NULL) {
00257         e = agNEWedge(g, tail, head, g->proto->e);
00258         install_edge(g, e);
00259         g->proto->e->head = g->proto->e->tail = g->proto->n;
00260         e->printkey = printkey;
00261     }
00262     g->proto->e->attr[KEYX] = keystr;
00263     return e;
00264 }
00265 
00266 void agFREEedge(Agedge_t * e)
00267 {
00268     int i, nobj;
00269     Agdict_t *dict = agdictof(e);
00270 
00271     dict = dict;
00272     TAG_OF(e) = -1;
00273     nobj = dtsize(e->tail->graph->univ->edgeattr->dict);
00274     for (i = 0; i < nobj; i++)
00275         agstrfree(e->attr[i]);
00276     free(e->attr);
00277         free(e->didset);
00278     free(e);
00279 }
00280 
00281 void agDELedge(Agraph_t * g, Agedge_t * e)
00282 {
00283     Agraph_t *meta;
00284     Agraph_t *g0;
00285     Agedge_t *f;
00286 
00287     if (dtsearch(g->inedges, e) == NULL) {
00288         agerr(AGERR, "Edge %p was not found\n", e);
00289         dtwalk(g->inedges, printedge, NIL(void *));
00290         return;
00291     }
00292     if (AG_IS_METAGRAPH(g) == FALSE) {
00293         meta = g->meta_node->graph;
00294         for (f = agfstout(meta, g->meta_node); f; f = agnxtout(meta, f)) {
00295             g0 = agusergraph(f->head);
00296             if (dtsearch(g0->inedges, e))
00297                 agDELedge(g0, e);
00298         }
00299     }
00300     dtdelete(g->inedges, e);
00301     dtdelete(g->outedges, e);
00302     if (g == g->root)
00303         agFREEedge(e);
00304 }