dijkstra.c File Reference

single-source distance filter More...

#include "config.h"
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <cgraph/cgraph.h>
#include <cgraph/ingraphs.h>
#include <getopt.h>
#include <util/agxbuf.h>
#include <util/alloc.h>
#include <util/exit.h>
#include <util/gv_math.h>
#include <util/unreachable.h>

Include dependency graph for dijkstra.c:

Go to the source code of this file.

Data Structures
struct	nodedata_t

Macros
#define	getprev(n)   (((nodedata_t*)((n)->base.data))->prev)
#define	setprev(n, p)   (((nodedata_t*)((n)->base.data))->prev = (p))
#define	isDone(n)   (((nodedata_t*)((n)->base.data))->done)
#define	setDone(n)   (((nodedata_t*)((n)->base.data))->done = true)

Functions
static double	getlength (Agedge_t *e)
static double	getdist (Agnode_t *n)
static void	setdist (Agnode_t *n, double dist)
static int	cmpf (void *key1, void *key2)
static Agnode_t *	extract_min (Dict_t *Q)
static void	update (Dict_t *Q, Agnode_t *dest, Agnode_t *src, double len)
static void	pre (Agraph_t *g)
static void	post (Agraph_t *g)
static void	dijkstra (Dict_t *Q, Agraph_t *G, Agnode_t *n)
static void	usage (int v)
static void	init (int argc, char *argv[])
int	main (int argc, char **argv)

Variables
static char *	CmdName
static char **	Files
static char **	Nodes
static bool	setall
static bool	doPath
static bool	doDirected
static Agsym_t *	len_sym
static Dtdisc_t	MyDisc
static char *	useString

Macro Definition Documentation

getprev

#define getprev

(

n

)

(((nodedata_t*)((n)->base.data))->prev)

Definition at line 79 of file dijkstra.c.

isDone

#define isDone

(

n

)

(((nodedata_t*)((n)->base.data))->done)

Definition at line 81 of file dijkstra.c.

setDone

#define setDone

(

n

)

(((nodedata_t*)((n)->base.data))->done = true)

Definition at line 82 of file dijkstra.c.

setprev

#define setprev	(		n,
			p
	)		(((nodedata_t*)((n)->base.data))->prev = (p))

Definition at line 80 of file dijkstra.c.

Function Documentation

cmpf()

static int cmpf ( void *  key1, void *  key2  )

static

Definition at line 84 of file dijkstra.c.

References dist2(), and getdist().

Referenced by dthash(), dttree(), and dtvsearch().

Here is the call graph for this function:

Here is the caller graph for this function:

dijkstra()

static void dijkstra ( Dict_t *  Q, Agraph_t *  G, Agnode_t *  n  )

static

Definition at line 194 of file dijkstra.c.

References agfstedge(), agfstout(), agnxtedge(), agnxtout(), doDirected, dtinsert, extract_min(), G, getlength(), isDone, Agedge_s::node, post, pre, setdist(), setDone, and update().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

extract_min()

static Agnode_t * extract_min ( Dict_t *  Q )

static

Definition at line 107 of file dijkstra.c.

References dtdelete, and dtfirst.

Referenced by dijkstra().

Here is the caller graph for this function:

getdist()

static double getdist ( Agnode_t *  n )

static

Definition at line 65 of file dijkstra.c.

References Agnode_s::base, Agobj_s::data, and nodedata_t::dist.

Referenced by cmpf(), post(), and update().

Here is the caller graph for this function:

getlength()

static double getlength ( Agedge_t *  e )

static

Definition at line 49 of file dijkstra.c.

References agxget(), len(), and len_sym.

Referenced by dijkstra().

Here is the call graph for this function:

Here is the caller graph for this function:

init()

static void init ( int  argc, char *  argv[]  )

static

Definition at line 234 of file dijkstra.c.

References CmdName, doDirected, doPath, Files, gv_calloc(), Nodes, NULL, setall, UNREACHABLE, and usage.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 281 of file dijkstra.c.

References agclose(), agnameof(), agnode(), agwrite(), CmdName, dijkstra(), dtclear, dtopen(), Dtoset, fileName(), Files, free(), graphviz_exit(), init(), MyDisc, newIngraph(), nextGraph(), and Nodes.

Here is the call graph for this function:

post()

static void post ( Agraph_t *  g )

static

Definition at line 138 of file dijkstra.c.

References agattr_text(), agattrsym(), agclean(), AGEDGE, agfstnode(), agnameof(), AGNODE, agnxtnode(), AGRAPH, agxbfree(), agxbprint(), agxbuse(), agxget(), agxset(), dist(), doPath, getdist(), getprev, is_exactly_zero(), NULL, prev, and setall.

Here is the call graph for this function:

pre()

static void pre ( Agraph_t *  g )

static

Definition at line 132 of file dijkstra.c.

References agattr_text(), AGEDGE, aginit(), AGNODE, len_sym, and NULL.

Here is the call graph for this function:

setdist()

static void setdist ( Agnode_t *  n, double  dist  )

static

Definition at line 72 of file dijkstra.c.

References Agnode_s::base, Agobj_s::data, nodedata_t::dist, and dist().

Referenced by dijkstra(), and update().

Here is the call graph for this function:

Here is the caller graph for this function:

update()

static void update ( Dict_t *  Q, Agnode_t *  dest, Agnode_t *  src, double  len  )

static

Definition at line 115 of file dijkstra.c.

References doPath, dtdelete, dtinsert, getdist(), is_exactly_zero(), len(), setdist(), and setprev.

Referenced by dijkstra().

Here is the call graph for this function:

Here is the caller graph for this function:

usage()

static void usage ( int  v )

static

Definition at line 228 of file dijkstra.c.

References graphviz_exit(), and useString.

Here is the call graph for this function:

Variable Documentation

CmdName

char* CmdName

static

Definition at line 32 of file dijkstra.c.

Referenced by init(), and main().

doDirected

bool doDirected

static

Definition at line 39 of file dijkstra.c.

Referenced by dijkstra(), and init().

doPath

bool doPath

static

Definition at line 38 of file dijkstra.c.

Referenced by init(), post(), and update().

Files

char** Files

static

Definition at line 33 of file dijkstra.c.

Referenced by init(), and main().

len_sym

Agsym_t* len_sym

static

Definition at line 40 of file dijkstra.c.

Referenced by getlength(), and pre().

MyDisc

Dtdisc_t MyDisc

static

Initial value:

= {
    0,                          
    0,                          
    -1,                         
    0,                          
    0,                          
    cmpf,                       
}

Definition at line 98 of file dijkstra.c.

Referenced by main().

Nodes

char** Nodes

static

Definition at line 34 of file dijkstra.c.

Referenced by init(), and main().

setall

bool setall

static

Definition at line 35 of file dijkstra.c.

Referenced by init(), and post().

useString

char* useString

static

Initial value:

=
    "Usage: dijkstra [-ap?] <node> [<file> <node> <file>]\n\
  -a - for nodes in a different component, set dist very large\n\
  -d - use forward directed edges\n\
  -p - attach shortest path info\n\
  -? - print usage\n\
If no files are specified, stdin is used\n"

Definition at line 220 of file dijkstra.c.

Referenced by usage().