Graphviz: lib/circogen/blockpath.c File Reference

Searching...

No Matches

#include <circogen/blockpath.h>
#include <circogen/circular.h>
#include <circogen/edgelist.h>
#include <stddef.h>
#include <stdbool.h>
#include <util/agxbuf.h>
#include <util/alloc.h>
#include <util/list.h>

Include dependency graph for blockpath.c:

Go to the source code of this file.

Macros
#define	ORIGE(e) (ED_to_orig(e))

#define	CROSS_ITER 10

Functions
static Agraph_t *	clone_graph (Agraph_t ing, Agraph_t xg, circ_state state)

typedef	LIST (Agnode_t *)

static deglist_t	getList (Agraph_t *g)
	Add nodes to deg_list, storing them by descending degree.

static void	find_pair_edges (Agraph_t g, Agnode_t n, Agraph_t *outg)

static Agraph_t *	remove_pair_edges (Agraph_t ing, circ_state state)

static void	measure_distance (Agnode_t n, Agnode_t ancestor, int dist, Agnode_t *change)

static nodelist_t	find_longest_path (Agraph_t *tree)
	Find and return longest path in tree.

static void	dfs (Agraph_t g, Agnode_t n, Agraph_t *tree)
	Simple depth first search, adding traversed edges to tree.

static Agraph_t *	spanning_tree (Agraph_t g, circ_state state)

static void	block_graph (Agraph_t g, block_t sn)
	Add induced edges.

static int	count_all_crossings (nodelist_t list, Agraph_t subg)

static nodelist_t	reduce (nodelist_t list, Agraph_t subg, int cnt)

static nodelist_t	reduce_edge_crossings (nodelist_t list, Agraph_t *subg)

static double	largest_nodesize (nodelist_t *list)
	Return max dimension of nodes on list.

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 void	place_residual_nodes (Agraph_t g, nodelist_t list)
	Add nodes not in list to list.

nodelist_t	layout_block (Agraph_t g, block_t sn, double min_dist, circ_state *state)

Macro Definition Documentation

◆ CROSS_ITER

#define CROSS_ITER 10

Definition at line 447 of file blockpath.c.

◆ ORIGE

#define ORIGE ( e ) (ED_to_orig(e))

Definition at line 24 of file blockpath.c.

Function Documentation

◆ block_graph()

static void block_graph	(	Agraph_t *	g,
		block_t *	sn
	)

static

Definition at line 386 of file blockpath.c.

References agfstnode(), agfstout(), aghead, agnxtnode(), agnxtout(), agsubedge(), BLOCK, and block::sub_graph.

Referenced by layout_block().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clone_graph()

static Agraph_t * clone_graph	(	Agraph_t *	ing,
		Agraph_t **	xg,
		circ_state *	state
	)

static

Definition at line 33 of file blockpath.c.

References agbindrec(), agedge(), agfstnode(), agfstout(), aghead, agnameof(), agnode(), agnxtnode(), agnxtout(), agopen(), agsubedge(), agsubg(), agsubnode(), agxbfree(), agxbprint(), agxbuse(), CLONE, DEGREE, Agraph_s::desc, gname, circ_state::graphCopyCount, NULL, and ORIGE.

Referenced by remove_pair_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ count_all_crossings()

static int count_all_crossings	(	nodelist_t *	list,
		Agraph_t *	subg
	)

static

Definition at line 400 of file blockpath.c.

References add_edge(), agfstedge(), agfstnode(), agfstout(), aghead, agnxtedge(), agnxtnode(), agnxtout(), agtail, dtfirst, dtnext, edgelistitem::edge, EDGEORDER, free_edgelist(), init_edgelist(), LIST_GET, LIST_SIZE, and remove_edge().

Referenced by reduce(), and reduce_edge_crossings().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dfs()

static void dfs	(	Agraph_t *	g,
		Agnode_t *	n,
		Agraph_t *	tree
	)

static

Definition at line 335 of file blockpath.c.

References agfstedge(), aghead, agnxtedge(), agsubedge(), agtail, dfs(), neighbor, SET_VISITED, TPARENT, tree, and VISITED.

Referenced by dfs(), and spanning_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ find_longest_path()

static nodelist_t find_longest_path ( Agraph_t * tree )

static

Definition at line 281 of file blockpath.c.

References agfstedge(), agfstnode(), agnnodes(), agnxtedge(), agnxtnode(), DISTONE, DISTTWO, endPath(), LEAFONE, LEAFTWO, length(), LIST_APPEND, measure_distance(), NULL, reverseAppend(), SET_ONPATH, TPARENT, and tree.

Referenced by layout_block().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ find_pair_edges()

static void find_pair_edges	(	Agraph_t *	g,
		Agnode_t *	n,
		Agraph_t *	outg
	)

static

Definition at line 99 of file blockpath.c.

References agbindrec(), agdelete(), agedge(), agfindedge, agfstedge(), aghead, agnxtedge(), agtail, DEGREE, free(), gv_calloc(), mark(), node_degree, NULL, and ORIGE.

Referenced by remove_pair_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ getList()

static deglist_t getList ( Agraph_t * g )

static

Definition at line 88 of file blockpath.c.

References agfstnode(), agnxtnode(), LIST_APPEND, and LIST_SORT.

Referenced by remove_pair_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ largest_nodesize()

static double largest_nodesize ( nodelist_t * list )

static

Definition at line 510 of file blockpath.c.

References LIST_GET, LIST_SIZE, ND_height, ND_width, and ORIGN.

Referenced by layout_block().

Here is the caller graph for this function:

◆ layout_block()

nodelist_t layout_block	(	Agraph_t *	g,
		block_t *	sn,
		double	min_dist,
		circ_state *	state
	)

Parameters

state Context containing a counter to use for graph copy naming

Definition at line 584 of file blockpath.c.

References agclose(), block_graph(), find_longest_path(), ISPARENT, largest_nodesize(), LIST_GET, LIST_SIZE, M_PI, N, ND_pos, block::parent_pos, place_residual_nodes(), POSITION, PSI, block::rad0, block::radius, realignNodelist(), reduce_edge_crossings(), remove_pair_edges(), spanning_tree(), block::sub_graph, and tree.

Referenced by doBlock().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ LIST()

typedef LIST ( Agnode_t * )

Definition at line 72 of file blockpath.c.

References DEGREE.

◆ measure_distance()

static void measure_distance	(	Agnode_t *	n,
		Agnode_t *	ancestor,
		int	dist,
		Agnode_t *	change
	)

static

Definition at line 243 of file blockpath.c.

References dist(), DISTONE, DISTTWO, LEAFONE, LEAFTWO, measure_distance(), NULL, parent, and TPARENT.

Referenced by find_longest_path(), and measure_distance().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ place_node()

static void place_node	(	Agraph_t *	g,
		Agnode_t *	n,
		nodelist_t *	list
	)

static

Definition at line 525 of file blockpath.c.

References agfstin(), agfstout(), aghead, agnxtin(), agnxtout(), agtail, appendNodelist(), LIST_APPEND, LIST_FREE, LIST_GET, LIST_IS_EMPTY, LIST_SIZE, NEIGHBOR, SET_NEIGHBOR, and UNSET_NEIGHBOR.

Referenced by place_residual_nodes().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ place_residual_nodes()

static void place_residual_nodes	(	Agraph_t *	g,
		nodelist_t *	list
	)

static

Definition at line 573 of file blockpath.c.

References agfstnode(), agnxtnode(), ONPATH, and place_node().

Referenced by layout_block().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ reduce()

static nodelist_t reduce	(	nodelist_t	list,
		Agraph_t *	subg,
		int *	cnt
	)

static

Definition at line 453 of file blockpath.c.

References agfstedge(), agfstnode(), aghead, agnxtedge(), agnxtnode(), agtail, cnt(), count_all_crossings(), insertNodelist(), LIST_COPY, LIST_FREE, and neighbor.

Referenced by reduce_edge_crossings().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ reduce_edge_crossings()

static nodelist_t reduce_edge_crossings	(	nodelist_t	list,
		Agraph_t *	subg
	)

static

Definition at line 492 of file blockpath.c.

References count_all_crossings(), CROSS_ITER, and reduce().

Referenced by layout_block().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ remove_pair_edges()

static Agraph_t * remove_pair_edges	(	Agraph_t *	ing,
		circ_state *	state
	)

static

Create layout skeleton of ing. Why is returned graph connected?

Parameters

state Context containing a counter to use for graph copy naming

Definition at line 197 of file blockpath.c.

References agclose(), agdelete(), agfstedge(), aghead, agnnodes(), agnxtedge(), agtail, clone_graph(), DEGREE, find_pair_edges(), getList(), LIST_APPEND, LIST_FREE, LIST_IS_EMPTY, LIST_POP_BACK, LIST_REMOVE, LIST_SORT, and NULL.

Referenced by layout_block().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ spanning_tree()

static Agraph_t * spanning_tree	(	Agraph_t *	g,
		circ_state *	state
	)

static

Construct spanning forest of g as subgraph

Parameters

state Context containing a counter to use for spanning tree naming

Definition at line 358 of file blockpath.c.

References agbindrec(), agfstnode(), agnxtnode(), agsubg(), agsubnode(), agxbfree(), agxbprint(), agxbuse(), dfs(), DISTONE, DISTTWO, gname, NULL, circ_state::spanningTreeCount, TPARENT, tree, UNSET_VISITED, and VISITED.

Referenced by layout_block().

Here is the call graph for this function:

Here is the caller graph for this function:

Macros

Functions

Macro Definition Documentation

◆ CROSS_ITER

◆ ORIGE

Function Documentation

◆ block_graph()

◆ clone_graph()

◆ count_all_crossings()

◆ dfs()

◆ find_longest_path()

◆ find_pair_edges()

◆ getList()

◆ largest_nodesize()

◆ layout_block()

◆ LIST()

◆ measure_distance()

◆ place_node()

◆ place_residual_nodes()

◆ reduce()

◆ reduce_edge_crossings()

◆ remove_pair_edges()

◆ spanning_tree()