Searching edge by their unique name in Agstrictdirected graph

t is possible to search a subgraph and node by their unique names;


n = agnode(g, "myUniqueNodeName", FALSE);
h = agsubg(g, "myUniqueSubgrahName", FALSE);

Likewise, is there a way to search edges in a strict directed graph by their unique names?


e = agedge (g, u, v, "e28", FALSE);

Documentation indicates that:


The 'name' of an edge (more correctly, identifier) is treated as a unique indentifier for edges between a particular node pair. That is, there can only be at most one edge with name e28 between any given u and v, but there can be many other edges between other nodes.

It seems that there must be a list of edges that can be searched by name. Otherwise, a separate (ID -> edge) map will need to be maintained separately. The section on ID discipline may be involved but is beyond me at this point. An example, would be greatly appreciated.

Thanks,

TR

In a directed graph, an edge

In a directed graph, an edge is identified by its head node, its tail node and its name. So your usage

  e = agedge (g, u, v, "e28", FALSE);

will return the unique edge from u to v whose name is e28, or NULL if it doesn't exist.

However, you specify a strict directed graph, so there can be at most one edge from u to v. 

Finally, if you just want a map from a key (integer, string) to an edge, you would need to set this up yourself, but that is fairly simple to do using the cdt library that comes with Graphviz.

Thanks for the clarification.

Thanks for the clarification. I had two follow-up questions: 1. If the edge name is unique, can this work?: e = agedge (, NULL, NULL, "e28", FALSE); 2. Is there any documentation/tutorial on using CDT, besides the man pages? Thanks again, TR

As Stephen North noted, there

As Stephen North noted, there is no builtin matching for edge names. Edges are keyed by the tuple head,tail,name.

I'm afraid our colleage who wrote cdt never provided a tutorial. It is a very good package and should be better known.

I've put together an edge map package, and a little test program. Here are the files:

 

/* edgemap.h */
#ifndef EDGEMAP_H
#define EDGEMAP_H

#include <cgraph.h>

typedef Dt_t edgemap_t;

#define sizeEdgemap(em)  dtsize(em)

extern Agedge_t* findEdge (edgemap_t*, char*);

extern edgemap_t* newEdgemap();
extern void addEdge (edgemap_t*, char*, Agedge_t*);
extern Agedge_t* findEdge (edgemap_t*, char*);
extern void closeEdgemap(edgemap_t*);

#endif

/* edgemap.c */
#include <stdlib.h>
#include <edgemap.h>

#define NOTUSED(var)    (void) var
#define NEW(t)           (t*)calloc(1,sizeof(t))

typedef struct {
    Dtlink_t link;
    char* id;
    Agedge_t* e;
} edgeitem;

static void *
newitem(Dt_t * d, edgeitem * obj, Dtdisc_t * disc)
{
    edgeitem *newp;

    NOTUSED(disc);
    newp = NEW(edgeitem);
    newp->id = obj->id;
    newp->e = obj->e;

    return newp;
}

static void
freeitem(Dt_t* d, edgeitem* obj, Dtdisc_t* disc)
{
    free(obj);
}

Dtdisc_t emDisc = {
    offsetof(edgeitem, id),    /* where to find the key */
    -1,                        /* strcmp on id */
    offsetof(edgeitem, link),  /* where to find the link */
    (Dtmake_f) newitem,
    (Dtfree_f) freeitem,
    0,
    0,
    0,
    0
};

edgemap_t*
newEdgemap()
{
  edgemap_t* map = dtopen(&emDisc, Dtoset);
  return map;
}

void
addEdge (edgemap_t* em, char* name, Agedge_t* e)
{
  edgeitem dummy;
  dummy.id = name;
  dummy.e = e;
  dtinsert (em, &dummy);
}

Agedge_t*
findEdge (edgemap_t* em, char* name)
{
  edgeitem* ep = dtmatch (em, name);
  if (ep) {
    return ep->e;
  }
  else return NULL;
}


void
closeEdgemap(edgemap_t* map)
{
  dtclose(map);
}

/* test.c */
 * assumes edges in input graph have id attributes
 * for example, a -- b [id = george]
 */
#include <stdio.h>
#include <assert.h>
#include <edgemap.h>

int
main()
{
  Agraph_t* g = agread (stdin, 0);
  edgemap_t* em = newEdgemap();
  Agnode_t* n;
  Agedge_t* e;
  Agedge_t* e0;
  char* name;

  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
    for (e = agfstout(g,n); e; e = agnxtout(g, e)) {
      name = agget(e, "id");
      addEdge (em, name, e);
    }
  }

  printf ("%d edges in edgemap\n", sizeEdgemap(em));

  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
    for (e = agfstout(g,n); e; e = agnxtout(g, e)) {
      name = agget(e, "id");
      e0 = findEdge (em, name);
      assert(e0 == e);
    }
  }

  closeEdgemap(em);
  return 0;
}

 

Wow.

Thank you. This is above ane beyond the call of duty.

While solving the immediate problem, the complete solution suggests ways of solving other problems.

TR.

 

 

If the edge name is unique, can this work? No, unfortunately

Sorry, there is no global index of edges by edge "name".

I think the best approach would be to copy some of the
code in graphviz/src/lib/cgraph/refstr.c that maintains
an index of shared strings.  (I see it has suffered some
wear-and-tear with the introduction of HTML strings...)

 

 

 

 

 

Recent comments