24#define ORIGE(e) (ED_to_orig(e))
75static int cmpDegree(
const void *x,
const void *y) {
108 int has_pair_count = 0;
109 int no_pair_count = 0;
141 neighbors_with[has_pair_count] = n1;
144 neighbors_without[no_pair_count] = n1;
155 if (diff < no_pair_count) {
157 if ((
mark + 1) >= no_pair_count)
159 tp = neighbors_without[
mark];
160 hp = neighbors_without[
mark + 1];
169 tp = neighbors_without[0];
170 hp = neighbors_without[
mark];
179 else if (diff == no_pair_count) {
180 tp = neighbors_with[0];
182 hp = neighbors_without[
mark];
190 free(neighbors_without);
191 free(neighbors_with);
209 while (counter < nodeCount - 3) {
215 if (currnode == adjNode)
224 if (currnode == adjNode)
289 nodelist_t beginPath = {0};
314 nodelist_t beginPath = {0};
422 for (eitem =
dtfirst(openEdgeList); eitem;
423 eitem =
dtnext(openEdgeList, eitem)) {
457 int crossings, j, newCrossings;
469 for (j = 0; j < 2; j++) {
474 if (newCrossings < crossings) {
475 crossings = newCrossings;
477 if (crossings == 0) {
493 int i, crossings, origCrossings;
500 origCrossings = crossings;
501 list =
reduce(list, subg, &crossings);
503 if (origCrossings == crossings || crossings == 0)
529 nodelist_t neighbors = {0};
542 for (
size_t one = 0; one <
LIST_SIZE(list); ++one) {
543 const size_t two = (one + 1) %
LIST_SIZE(list);
555 for (
size_t one = 0; one <
LIST_SIZE(list); ++one) {
567 for (
size_t one = 0; one <
LIST_SIZE(&neighbors); ++one)
588 double theta, radius, largest_node;
610 radius = (double)
N * (min_dist + largest_node) / (2 *
M_PI);
626 theta = k * (2.0 *
M_PI / (double)
N);
628 ND_pos(n)[0] = radius * cos(theta);
629 ND_pos(n)[1] = radius * sin(theta);
635 sn->
radius = largest_node / 2;
654 fprintf(stderr,
"%s ",
agnameof(n));
static void agxbfree(agxbuf *xb)
free any malloced resources
static int agxbprint(agxbuf *xb, const char *fmt,...)
Printf-style output to an agxbuf.
static WUR char * agxbuse(agxbuf *xb)
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
static int count_all_crossings(nodelist_t *list, Agraph_t *subg)
static void place_node(Agraph_t *g, Agnode_t *n, nodelist_t *list)
Add n to list. By construction, n is not in list at start.
static nodelist_t find_longest_path(Agraph_t *tree)
Find and return longest path in tree.
static void block_graph(Agraph_t *g, block_t *sn)
Add induced edges.
static nodelist_t reduce(nodelist_t list, Agraph_t *subg, int *cnt)
static void place_residual_nodes(Agraph_t *g, nodelist_t *list)
Add nodes not in list to list.
static void dfs(Agraph_t *g, Agnode_t *n, Agraph_t *tree)
Simple depth first search, adding traversed edges to tree.
static double largest_nodesize(nodelist_t *list)
Return max dimension of nodes on list.
static Agraph_t * spanning_tree(Agraph_t *g, circ_state *state)
static void find_pair_edges(Agraph_t *g, Agnode_t *n, Agraph_t *outg)
static void measure_distance(Agnode_t *n, Agnode_t *ancestor, int dist, Agnode_t *change)
static Agraph_t * clone_graph(Agraph_t *ing, Agraph_t **xg, circ_state *state)
static Agraph_t * remove_pair_edges(Agraph_t *ing, circ_state *state)
static deglist_t getList(Agraph_t *g)
Add nodes to deg_list, storing them by descending degree.
nodelist_t layout_block(Agraph_t *g, block_t *sn, double min_dist, circ_state *state)
static nodelist_t reduce_edge_crossings(nodelist_t list, Agraph_t *subg)
#define UNSET_NEIGHBOR(n)
static Extype_t length(Exid_t *rhs, Exdisc_t *disc)
void add_edge(edgelist *list, Agedge_t *e)
edgelist * init_edgelist(void)
void free_edgelist(edgelist *list)
void remove_edge(edgelist *list, Agedge_t *e)
static void endPath(bezier_path_t *polypath)
static double dist(int dim, double *x, double *y)
static int cnt(Dict_t *d, Dtlink_t **set)
int agnnodes(Agraph_t *g)
Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Agedge_t * agsubedge(Agraph_t *g, Agedge_t *e, int createflag)
Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
#define agfindedge(g, t, h)
Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Agedge_t * agfstin(Agraph_t *g, Agnode_t *n)
int agclose(Agraph_t *g)
deletes a graph, freeing its associated storage
Agraph_t * agopen(char *name, Agdesc_t desc, Agdisc_t *disc)
creates a new graph with the given name and kind
Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Agnode_t * agfstnode(Agraph_t *g)
Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
char * agnameof(void *)
returns a string descriptor for the object.
int agdelete(Agraph_t *g, void *obj)
deletes object. Equivalent to agclose, agdelnode, and agdeledge for obj being a graph,...
void * agbindrec(void *obj, const char *name, unsigned int recsize, int move_to_front)
attaches a new record of the given size to the object
Agraph_t * agsubg(Agraph_t *g, char *name, int cflag)
static void mark(const stk_t *stk, Agnode_t *n)
set a mark on n
type-generic dynamically expanding list
#define LIST_APPEND(list, item)
#define LIST_POP_BACK(list)
#define LIST_SORT(list, cmp)
#define LIST_IS_EMPTY(list)
#define LIST_COPY(dst, src)
#define LIST_REMOVE(list, item)
#define LIST_GET(list, index)
#define neighbor(t, i, edim, elist)
void realignNodelist(nodelist_t *list, size_t np)
Make np new front of list, with current last hooked to current first.
void insertNodelist(nodelist_t *list, Agnode_t *cn, Agnode_t *neighbor, int pos)
void reverseAppend(nodelist_t *l1, nodelist_t *l2)
Create l1 @ (rev l2) Destroys and frees l2.
void appendNodelist(nodelist_t *list, size_t one, Agnode_t *n)
Add node after one.
int graphCopyCount
how many cloned graphs have we created?
int spanningTreeCount
how many spanning trees have we created?