flow.c File Reference

Network Analysis library - flow in graph. More...

#include <stdio.h>
#include <stdlib.h>
#include <grass/gis.h>
#include <grass/Vect.h>
#include <grass/glocale.h>
#include <grass/dgl/graph.h>
#include <grass/neta.h>

Include dependency graph for flow.c:

Go to the source code of this file.

Functions
dglInt32_t	sign (dglInt32_t x)
int	NetA_flow (dglGraph_s *graph, struct ilist *source_list, struct ilist *sink_list, int *flow)
	Get max flow from source to sink. More...
int	NetA_min_cut (dglGraph_s *graph, struct ilist *source_list, struct ilist *sink_list, int *flow, struct ilist *cut)
	Calculates minimum cut between source(s) and sink(s). More...
int	NetA_split_vertices (dglGraph_s *in, dglGraph_s *out, int *node_costs)
	Splits each vertex of in graph into two vertices. More...

Detailed Description

Network Analysis library - flow in graph.

Computes the length of the shortest path between all pairs of nodes in the network.

(C) 2009-2010 by Daniel Bundala, and the GRASS Development Team

This program is free software under the GNU General Public License (>=v2). Read the file COPYING that comes with GRASS for details.

Author

Daniel Bundala (Google Summer of Code 2009)

Definition in file flow.c.

Function Documentation

int NetA_flow	(	dglGraph_s *	graph,
		struct ilist *	source_list,
		struct ilist *	sink_list,
		int *	flow
	)

Get max flow from source to sink.

Array flow stores flow for each edge. Negative flow corresponds to a flow in opposite direction The function assumes that the edge costs correspond to edge capacities.

Parameters

	graph	input graph
	source_list	list of sources
	sink_list	list of sinks
[out]	flow	max flows

Returns

number of flows

-1 on failure

Definition at line 47 of file flow.c.

References dglEdgeGet_Cost(), dglEdgeGet_Head(), dglEdgeGet_Id(), dglEdgeGet_Tail(), dglEdgeset_T_First(), dglEdgeset_T_Initialize(), dglEdgeset_T_Next(), dglEdgeset_T_Release(), dglGet_EdgeCount(), dglGet_NodeCount(), dglGetNode(), dglNodeGet_Id(), dglNodeGet_OutEdgeset(), for(), G_fatal_error(), G_free(), NULL, and sign().

int NetA_min_cut	(	dglGraph_s *	graph,
		struct ilist *	source_list,
		struct ilist *	sink_list,
		int *	flow,
		struct ilist *	cut
	)

Calculates minimum cut between source(s) and sink(s).

Flow is the array produced by NetA_flow() method when called with source_list and sink_list as the input. The output of this and NetA_flow() method should be the same.

Parameters

	graph	input graph
	source_list	list of sources
	sink_list	list of sinks
[out]	cut	list of edges (cut)

Returns

number of edges

-1 on failure

Definition at line 165 of file flow.c.

References dglEdgeGet_Cost(), dglEdgeGet_Id(), dglEdgeGet_Tail(), dglEdgeset_T_First(), dglEdgeset_T_Initialize(), dglEdgeset_T_Next(), dglEdgeset_T_Release(), dglGet_NodeCount(), dglGetNode(), dglNodeGet_Id(), dglNodeGet_OutEdgeset(), G_fatal_error(), G_free(), sign(), Vect_list_append(), and Vect_reset_list().

int NetA_split_vertices	(	dglGraph_s *	in,
		dglGraph_s *	out,
		int *	node_costs
	)

Splits each vertex of in graph into two vertices.

The method splits each vertex of in graph into two vertices: in vertex and out vertex. Also, it adds an edge from an in vertex to the corresponding out vertex (capacity=2) and it adds an edge from out vertex to in vertex for each edge present in the in graph (forward capacity=1, backward capacity=0). If the id of a vertex is v then id of in vertex is 2*v-1 and of out vertex 2*v.

Parameters

in	from graph
out	to graph
node_cost	list of node costs

Returns

number of undirected edges in the graph

-1 on failure

Definition at line 258 of file flow.c.

References dglAddEdge(), dglEdgeGet_Tail(), dglEdgeset_T_First(), dglEdgeset_T_Initialize(), dglEdgeset_T_Next(), dglEdgeset_T_Release(), dglFlatten(), dglGet_NodeCount(), dglInitialize(), dglNode_T_First(), dglNode_T_Initialize(), dglNode_T_Next(), dglNode_T_Release(), dglNodeGet_Id(), dglNodeGet_OutEdgeset(), and G_fatal_error().

dglInt32_t sign

(

dglInt32_t

x

)

Definition at line 25 of file flow.c.

Referenced by G_fpcompress_dissectXdrDouble(), NetA_flow(), and NetA_min_cut().