dijkstra.c File Reference

single-source distance filter More...

#include "config.h"
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <cgraph/cgraph.h>
#include <cgraph/ingraphs.h>
#include <getopt.h>
#include <util/alloc.h>
#include <util/exit.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 76 of file dijkstra.c.

isDone

#define isDone

(

n

)

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

Definition at line 78 of file dijkstra.c.

setDone

#define setDone

(

n

)

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

Definition at line 79 of file dijkstra.c.

setprev

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

Definition at line 77 of file dijkstra.c.

Function Documentation

cmpf()

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

static

Definition at line 81 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 188 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 compute_apsp_dijkstra(), embed_graph(), main(), and sparse_stress_subspace_majorization_kD().

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 104 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 62 of file dijkstra.c.

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

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 46 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 228 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 275 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 135 of file dijkstra.c.

References agattr(), agattrsym(), agclean(), AGEDGE, agfstnode(), agnameof(), AGNODE, agnxtnode(), AGRAPH, agxget(), agxset(), dist(), doPath, getdist(), getprev, NULL, prev, and setall.

Here is the call graph for this function:

pre()

static void pre ( Agraph_t *  g )

static

Definition at line 129 of file dijkstra.c.

References agattr(), 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 69 of file dijkstra.c.

References Agnode_s::base, Agobj_s::data, 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 112 of file dijkstra.c.

References doPath, dtdelete, dtinsert, getdist(), 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 222 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 29 of file dijkstra.c.

Referenced by init(), and main().

doDirected

bool doDirected

static

Definition at line 36 of file dijkstra.c.

Referenced by dijkstra(), and init().

doPath

bool doPath

static

Definition at line 35 of file dijkstra.c.

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

Files

char** Files

static

Definition at line 30 of file dijkstra.c.

Referenced by init(), and main().

len_sym

Agsym_t* len_sym

static

Definition at line 37 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 95 of file dijkstra.c.

Referenced by main().

Nodes

char** Nodes

static

Definition at line 31 of file dijkstra.c.

Referenced by init(), and main().

setall

bool setall

static

Definition at line 32 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 214 of file dijkstra.c.

Referenced by usage().