wolffd@0: To create a new layout plugin called xxx, you first need
wolffd@0: to provide two functions: xxx_layout and xxx_cleanup. The
wolffd@0: semantics of these are described below.
wolffd@0: 
wolffd@0: ========================
wolffd@0: 
wolffd@0:   void xxx_layout(Agraph_t * g)
wolffd@0: 
wolffd@0:     Initialize the graph.
wolffd@0:        - If the algorithm will use the common edge routing code, it should
wolffd@0:     call setEdgeType (g, ...);
wolffd@0: 
wolffd@0:        - For each node, call common_init_node and gv_nodesize.
wolffd@0: 
wolffd@0:          If the algorithm will use spline_edges() to route the edges, the
wolffd@0:     node coordinates need to be stored in ND_pos, so this should be
wolffd@0:     allocated here. This, and the two calls mentioned above, are all
wolffd@0:     handled by a call to neato_init_node().
wolffd@0: 
wolffd@0:        - For each edge, call common_init_edge
wolffd@0: 
wolffd@0:        - The algorithm should allocate whatever other data structures it
wolffd@0:     needs. This can involve fields in the A*info_t fields. In addition,
wolffd@0:     each of these fields contains a void* alg; subfield that the algorithm
wolffd@0:     can use the store additional data. 
wolffd@0:          Once we move to cgraph, this will all be replace with 
wolffd@0:     algorithm specific records.
wolffd@0: 
wolffd@0:     Layout the graph. When finished, each node should have its coordinates
wolffd@0:   stored in points in ND_coord_i(n), each edge should have its layout
wolffd@0:   described in ED_spl(e). 
wolffd@0:   (N.B. As of version 2.21, ND_coord_i has been replaced by ND_coord,
wolffd@0:   which are now floating point coordinates.)
wolffd@0: 
wolffd@0:     To add edges, there are 3 functions available:
wolffd@0: 
wolffd@0:       - spline_edges1 (Agraph_t*, int edgeType)
wolffd@0:           Assumes the node coordinates are stored in ND_coord_i, and that
wolffd@0:         GD_bb is set. For each edge, this function constructs the appropriate 
wolffd@0:         data and stores it in ED_spl.
wolffd@0:       - spline_edges0 (Agraph_t*)
wolffd@0:           Assumes the node coordinates are stored in ND_pos, and that
wolffd@0:         GD_bb is set. This function uses the ratio attribute if set, 
wolffd@0:         copies the values in ND_pos to ND_coord_i (converting from 
wolffd@0:         inches to points); and calls spline_edges1 using the edge type
wolffd@0:         specified by setEdgeType().
wolffd@0:       - spline_edges (Agraph_t*)
wolffd@0:           Assumes the node coordinates are stored in ND_pos. This
wolffd@0:         function calculates the bounding box of g and stores it in GD_bb,
wolffd@0:         then calls spline_edges0().
wolffd@0: 
wolffd@0:     If the algorithm only works with connected components, the code can
wolffd@0:   use the pack library to get components, lay them out individually, and
wolffd@0:   pack them together based on user specifications. A typical schema is
wolffd@0:   given below. One can look at the code for twopi, circo, neato or fdp
wolffd@0:   for more detailed examples.
wolffd@0: 
wolffd@0:         Agraph_t **ccs;
wolffd@0:         Agraph_t *sg;
wolffd@0:         Agnode_t *c = NULL;
wolffd@0:         int ncc;
wolffd@0:         int i;
wolffd@0: 
wolffd@0:         ccs = ccomps(g, &ncc, 0);
wolffd@0:         if (ncc == 1) {
wolffd@0:             /* layout nodes of g */
wolffd@0:             adjustNodes(g);  /* if you need to remove overlaps */
wolffd@0:             spline_edges(g); /* generic edge routing code */
wolffd@0: 
wolffd@0:         } else {
wolffd@0:             pack_info pinfo;
wolffd@0:             pack_mode pmode = getPackMode(g, l_node);
wolffd@0: 
wolffd@0:             for (i = 0; i < ncc; i++) {
wolffd@0:                 sg = ccs[i];
wolffd@0:                 /* layout sg */
wolffd@0:                 adjustNodes(sg);  /* if you need to remove overlaps */
wolffd@0:             }
wolffd@0:             spline_edges(g);  /* generic edge routing */
wolffd@0: 
wolffd@0:             /* initialize packing info, e.g. */
wolffd@0:             pinfo.margin = getPack(g, CL_OFFSET, CL_OFFSET);
wolffd@0:             pinfo.doSplines = 1;
wolffd@0:             pinfo.mode = pmode;
wolffd@0:             pinfo.fixed = 0;
wolffd@0:             packSubgraphs(ncc, ccs, g, &pinfo);
wolffd@0:         }
wolffd@0:         for (i = 0; i < ncc; i++) {
wolffd@0:             agdelete(g, ccs[i]);
wolffd@0:         }
wolffd@0: 
wolffd@0:         free(ccs);
wolffd@0: 
wolffd@0:     Be careful in laying of subgraphs if you rely on attributes that have
wolffd@0:   only been set in the root graph. With connected components, edges can
wolffd@0:   be added with each component, before packing (as above) or after the
wolffd@0:   components have been packed (see circo).
wolffd@0: 
wolffd@0:     It good to check for trivial cases where the graph has 0 or 1 nodes,
wolffd@0:   or no edges.
wolffd@0: 
wolffd@0:     At the end of xxx_layout, call
wolffd@0: 
wolffd@0:        dotneato_postprocess(g);
wolffd@0: 
wolffd@0:   The following template will work in most cases, ignoring the problems of
wolffd@0:   handling disconnected graphs and removing node overlaps:
wolffd@0: 
wolffd@0:   static void
wolffd@0:   xxx_init_node(node_t * n)
wolffd@0:   {
wolffd@0:     neato_init_node(n);
wolffd@0:     /* add algorithm-specific data, if desired */
wolffd@0:   }
wolffd@0: 
wolffd@0:   static void
wolffd@0:   xxx_init_edge(edge_t * e)
wolffd@0:   {
wolffd@0:     common_init_edge(e);
wolffd@0:     /* add algorithm-specific data, if desired */
wolffd@0:   }
wolffd@0: 
wolffd@0:   static void
wolffd@0:   xxx_init_node_edge(graph_t * g)
wolffd@0:   {
wolffd@0:     node_t *n;
wolffd@0:     edge_t *e;
wolffd@0: 
wolffd@0:     for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
wolffd@0:         xxx_init_node(n);
wolffd@0:     }
wolffd@0:     for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
wolffd@0:         for (e = agfstout(g, n); e; e = agnxtout(g, e)){          
wolffd@0:             xxx_init_edge(e);
wolffd@0:         }
wolffd@0:     }
wolffd@0:   }
wolffd@0: 
wolffd@0:   void
wolffd@0:   xxx_layout (Agraph_t* g)
wolffd@0:   {
wolffd@0:     xxx_init_node_edge(g);
wolffd@0:     /* Set ND_pos(n) for each node n */
wolffd@0:     spline_edges(g);
wolffd@0:     dotneato_postprocess(g);
wolffd@0:   }  
wolffd@0: 
wolffd@0: ======================
wolffd@0: 
wolffd@0:   void xxx_cleanup(Agraph_t * g)
wolffd@0: 
wolffd@0:     Free up any resources allocated in the layout.
wolffd@0: 
wolffd@0:     Finish with calls to gv_cleanup_node and gv_cleanup_edge for
wolffd@0:   each node and edge. This cleans up splines labels, ND_pos, shapes
wolffd@0:   and 0's out the A*info_t, so these have to occur last, but could be
wolffd@0:   part of explicit xxx_cleanup_node and xxx_cleanup_edge, if desired.
wolffd@0:     At the end, you should do
wolffd@0: 
wolffd@0:   if (g != g->root) memset(&(g->u), 0, sizeof(Agraphinfo_t));
wolffd@0: 
wolffd@0:   This is necessary for the graph to be laid out again, as the layout
wolffd@0:   code assumes this structure is clean.
wolffd@0: 
wolffd@0:   libgvc does a final cleanup to the root graph, freeing any drawing,
wolffd@0:   freeing its label, and zeroing out Agraphinfo_t of the root graph.
wolffd@0: 
wolffd@0:   The following template will work in most cases:
wolffd@0: 
wolffd@0:   static void xxx_cleanup_graph(Agraph_t * g)
wolffd@0:   {
wolffd@0:     /* Free any algorithm-specific data attached to the graph */
wolffd@0:     if (g != g->root) memset(&(g->u), 0, sizeof(Agraphinfo_t));
wolffd@0:   }
wolffd@0: 
wolffd@0:   static void xxx_cleanup_edge (Agedge_t* e)
wolffd@0:   {
wolffd@0:     /* Free any algorithm-specific data attached to the edge */
wolffd@0:     gv_cleanup_edge(e);
wolffd@0:   }
wolffd@0: 
wolffd@0:   static void xxx_cleanup_node (Agnode_t* n)
wolffd@0:   {
wolffd@0:     /* Free any algorithm-specific data attached to the node */
wolffd@0:     gv_cleanup_node(e);
wolffd@0:   }
wolffd@0: 
wolffd@0:   void xxx_cleanup(Agraph_t * g)
wolffd@0:   {
wolffd@0:     Agnode_t *n;
wolffd@0:     Agedge_t *e;
wolffd@0: 
wolffd@0:     for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
wolffd@0:         for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
wolffd@0:             xxx_cleanup_edge(e);
wolffd@0:         }
wolffd@0:         xxx_cleanup_node(n);
wolffd@0:     }
wolffd@0:     xxx_cleanup_graph(g);
wolffd@0:   }   
wolffd@0: 
wolffd@0: ==================
wolffd@0: 
wolffd@0: Most layouts use auxiliary routines similar to neato, so
wolffd@0: the entry points can be added in plugin/neato_layout
wolffd@0: 
wolffd@0: Add to gvlayout_neato_layout.c:
wolffd@0: 
wolffd@0: gvlayout_engine_t xxxgen_engine = {
wolffd@0:     xxx_layout,
wolffd@0:     xxx_cleanup,
wolffd@0: };
wolffd@0: 
wolffd@0: and the line
wolffd@0: 
wolffd@0:     {LAYOUT_XXX, "xxx", 0, &xxxgen_engine, &neatogen_features},
wolffd@0: 
wolffd@0: to gvlayout_neato_types and a new emum
wolffd@0: 
wolffd@0:     LAYOUT_XXX
wolffd@0: 
wolffd@0: to layout_type in that file.
wolffd@0: 
wolffd@0: The above allows the new layout to piggyback on top of the neato
wolffd@0: plugin, but requires rebuilding the plugin. In general, a user
wolffd@0: can (and probably should) build a layout plugin totally separately. 
wolffd@0: 
wolffd@0: To do this, after writing xxx_layout and xxx_cleanup, it is necessary to:
wolffd@0: 
wolffd@0:   - add the types and data structures
wolffd@0: 
wolffd@0: typedef enum { LAYOUT_XXX } layout_type;
wolffd@0: 
wolffd@0: static gvlayout_features_t xxxgen_features = {
wolffd@0:     0
wolffd@0: };
wolffd@0: gvlayout_engine_t xxxgen_engine = {
wolffd@0:     xxx_layout,
wolffd@0:     xxx_cleanup,
wolffd@0: };
wolffd@0: static gvplugin_installed_t gvlayout_xxx_types[] = {
wolffd@0:     {LAYOUT_XXX, "xxx", 0, &xxxgen_engine, &xxxgen_features},
wolffd@0:     {0, NULL, 0, NULL, NULL}
wolffd@0: };
wolffd@0: static gvplugin_api_t apis[] = {
wolffd@0:     {API_layout, &gvlayout_xxx_types},
wolffd@0:     {(api_t)0, 0},
wolffd@0: };
wolffd@0: gvplugin_library_t gvplugin_xxx_layout_LTX_library = { "xxx_layout", apis };
wolffd@0: 
wolffd@0:   - combine all of this into a dynamic library whose name contains the 
wolffd@0:   string "gvplugin_" and install the library in the same directory as the 
wolffd@0:   other Graphviz plugins. For example, on Linux systems, the dot layout 
wolffd@0:   plugin is in the library libgvplugin_dot_layout.so.
wolffd@0: 
wolffd@0:   - run
wolffd@0:       dot -c
wolffd@0:   to regenerate the config file.
wolffd@0: 
wolffd@0: NOTES:
wolffd@0:   - Additional layouts can be added as extra lines in gvlayout_xxx_types.
wolffd@0:   - Obviously, most of the names and strings can be arbitrary. One
wolffd@0:   constraint is that external identifier for the gvplugin_library_t
wolffd@0:   type must end in "_LTX_library". In addition, the string "xxx" in
wolffd@0:   each entry of gvlayout_xxx_types is the name used to identify the
wolffd@0:   layout algorithm, so needs to be distinct from any other layout name.
wolffd@0:   - The features of a layout algorithm are currently limited to a 
wolffd@0:   flag of bits, and the only flag supported is LAYOUT_USES_RANKDIR,
wolffd@0:   which enables the layout to the rankdir attribute.
wolffd@0: 
wolffd@0: Changes need to be made to any applications, such as gvedit, that
wolffd@0: statically know about layout algorithms.
wolffd@0: 
wolffd@0: ==================
wolffd@0: 
wolffd@0: Software configuration - automake
wolffd@0: 
wolffd@0: If you want to integrate your code into the Graphviz software
wolffd@0: and use its build system, follow the instructions below. 
wolffd@0: You can certainly build and install your plugin using your own
wolffd@0: build software.
wolffd@0: 
wolffd@0: 0. Put your software in lib/xxxgen, and added the hooks describe above
wolffd@0: into gvlayout_neato_layout.c
wolffd@0: 1. In lib/xxxgen, provide a Makefile.am (based on a simple example
wolffd@0: like lib/fdpgen/Makefile.am)
wolffd@0: 3. In lib/Makefile.am, add xxxgen to SUBDIRS
wolffd@0: 2. In configure.ac, add lib/xxxgen/Makefile to AC_CONFIG_FILES.
wolffd@0: 4. In lib/plugin/neato_layout/Makefile.am, insert
wolffd@0: 	$(top_builddir)/lib/xxxgen/libxxxgen_C.la 
wolffd@0: 	in libgvplugin_neato_layout_C_la_LIBADD
wolffd@0: 5. Remember to run autogen.sh because on its own configure can guess wrong.
wolffd@0: 
wolffd@0: This also assumes you have a good version of the various automake tools
wolffd@0: on your system.
wolffd@0: 
wolffd@0: