GSoC'18: Detailed Signature for Bellman-Ford algorithm

[codeSG]

Please give your feedback on below signature's description for Bellman-Ford algorithm.

Name of function:

_pgr_bellmanford → Returns the shortest path(s) using Bellman-ford algorithm for negative weighted graph, It will use the bellman-ford implemented by Boost Graph Library[1].

Main Characteristics of function:

• Process is valid for edges with both positive and negative edge weights.

• Returned values would be ordered ascending with respect to start_vids and end_vids. They will follow certain rules:

1. When the start vertex and the end vertex are the same, there is no path. The agg_cost would be 0.
2. When the start vertex and the end vertex are different, and there exists a path between them without having a ‘negative cycle’. The agg_cost would be some finite value denoting the shortest distance between them.
3. When the start vertex and the end vertex are different, and there exists a path between them, but it contains a ‘negative cycle’. In such case, agg_cost for those vertices keep on decreasing furthermore, Hence agg_cost can’t be defined for them. (Please suggest how to represent them in function’s output)
4. When the start vertex and the end vertex are different, and there is no path. The agg_cost is ∞. For optimization purposes, any duplicated value in the start_vids or end_vids is ignored.

• Running Time: O(|start_vids| (VE)) Where, V, E represents no of vertices and edges in the graph respectively.

All Varients of Signature:

• pgr_bellman_ford(edges_sql, start_vid, end_vid, directed=TRUE)

• pgr_bellman_ford(edges_sql, start_vid, end_vids, directed=TRUE)

• pgr_bellman_ford(edges_sql, start_vids, end_vid, directed=TRUE)

• pgr_bellman_ford(edges_sql, start_vids, end_vids, directed=TRUE)

RETURNS SET OF (seq, path_seq [ start_vid] [ end_vid], node, edge, cost, agg_cost) OR EMPTY SET

Characteristics of Parameters :

1. Directed or Undirected: _For the pgr_bellmanford function, we may consider both Directed and Undirected graph . Generally, Bellman-Ford algorithm is meant for directed graphs with no negative cycle; For those graphs, it correctly determines the distances from start vertex to all other vertices in time O(V*E)[2][3][4]. Since, In Boost graph library, it is accepting both directed or undirected graph[1](see parameters). For an undirected edge (u,v), it is replaced by two directed edges (u,v)(direction u to v) and (v,u)(direction v to u) and weight of both of these edges are same as the weight of undirected edge (u,v). But it means any edge with a negative weight will count as a loop(due to parallel edges in opposite directions)[5]. Hence, for undirected graph, it mustn't contain any edges with negative weight, and there doesn’t exist use of the Bellman-ford algorithm.

2. Source and Target Vertex Set: They may contain single vertex or an array of vertices, represented by start_vid/end_vid and start_vids/end_vids respectively.

Description of the parameters of the signatures:

Column	Type	Description
edges_sql	TEXT	SQL query as described below.
start_vid or start_vids	BIGINT orARRAY [BIGINT]	Identifier of the starting vertices of the path.
End_vid or end_vids	BIGINT orARRAY [BIGINT]	Identifier of the ending vertices of the path.

Description of the edges_sql query:

edges_sql: an SQL query, which should return a set of rows with the following columns:

SELECT id, source, target, cost FROM edge_table

Column	Type	Description
id	ANY-INTEGER	Identifier of the edge
source	ANY-INTEGER	Identifier of the first endpoint vertex of the edge.
target	ANY-INTEGER	Identifier of the second endpoint vertex of the edge.
cost	ANY-NUMERICAL	Weight of the edge (source, target), When negative: edge (source, target) does not exist, therefore it’s not part of the graph.
reverse cost	ANY-NUMERICAL	Weight of the edge (target, source), When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

References:

[1]. Bellman_ford_shortest_paths algorithm Boost Graph Library, https://www.boost.org/doc/libs/1_48_0/libs/graph/doc/bellman_ford_shortest.html [2]. Bang-Jensen, Jørgen; Gutin, Gregory (2000). "Section 2.3.4: The Bellman-Ford-Moore algorithm". Digraphs: Theory, Algorithms, and Applications (First ed.). ISBN 978-1-84800-997-4. [3].T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. McGraw-Hill, 1990. [4]. Introduction to ALgorithms, Lecture17 Bellman-Ford, by Srini Devadas MIT Fall 2011 https://www.youtube.com/watch?v=ozsuci5pIso [5].https://stackoverflow.com/questions/14785413/can-we-apply-the-bellman-ford-algorithm-to-an-undirected-graph.

[cvvergara]

Q. does bellman ford works on directed graph only or on undirected graph only?

[cvvergara]

SELECT id, source, target, cost FROM edge_table

cost is ANY-NUMERICAL is Weight of the edge (source, target)

so for the edge (target, source) an extra row is needed on the table?

So for example instead of this

id	source	target	cost	reverse_cost
1	1	2	1500	200

have this

id	source	target	cost
1	1	2	1500
2	2	1	200

 

[codeSG]

If we take an undirected graph, then we have to transform each undirected edge as two directed edges in both directions, and their weights would have to be same as of undirected one. For any negative weighted edge and it will form a negative loop between the two nodes, and that result in the undefined shortest distance for those vertices. Hence, for undirected graph, we are constraint to choose positive weighted edges only.

[cvvergara]

Back again on the functions parameters you mention:

Characteristics of Parameters : Directed or Undirected:

But in none of the signatures there is a parameter to indicate if the graph is directed or undirected

[codeSG]

Yes

[cvvergara]

Yes to what? https://github.com/pgRouting/pgrouting/issues/1030#issuecomment-390422389

[cvvergara]

About https://github.com/pgRouting/pgrouting/issues/1030#issuecomment-390422341 maybe you should read the documentation about what a negative weight is considered https://docs.pgrouting.org/2.6/en/pgRouting-concepts.html#id46

[cvvergara]

I will rephrase this Q https://github.com/pgRouting/pgrouting/issues/1030#issuecomment-390421986 bellman ford works for: A) directed graph B) undirected graph C) both directed or undirected please choose only A, B or C and put a link to this comment when you are answering. (you get the link by clicking on the time that the comment was posted)

[codeSG]

about https://github.com/pgRouting/pgrouting/issues/1030#issuecomment-390422513 I read that documentation.

[codeSG]

https://github.com/pgRouting/pgrouting/issues/1030#issuecomment-390422668 option A

[cvvergara]

Why does it not work for undirected graph? you mention:

In Boost graph library, it is accepting both directed or undirected graph[1](see parameters).

[codeSG]

Explained here https://github.com/pgRouting/pgrouting/issues/1030#issuecomment-390422341

For undirected graph, we can take only positive weights for edges. Hence, there is no utility for Bellman-Ford algorithm.

[codeSG]

Please update me, if I am wrong somewhere.

[cvvergara]

But if boost graph accepts both directed and undirected why do you want to only use directed?

[codeSG]

https://github.com/pgRouting/pgrouting/issues/1030#issuecomment-390423208 We can also accept both graphs, for generalization, but if there exists a negative edge, it will output undefined distance for many (or all) vertices.

[cvvergara]

about:

if there exists a negative edge

the way the data is read, the negative cost mean that the edge does not exist please read: https://docs.pgrouting.org/2.6/en/pgRouting-concepts.html#id46

cost	ANY-NUMERICAL		Weight of the edge (source, target) When negative: edge (source, target) does not exist, therefore it’s not part of the graph.
reverse_cost	ANY-NUMERICAL	-1	Weight of the edge (target, source), When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

[codeSG]

That is for Dijkstra like functions, which doesn't accept negative weights.

[cvvergara]

Does Belman ford accept negative costs?

[codeSG]

https://github.com/pgRouting/pgrouting/issues/1030#issuecomment-390425829 Yes

[codeSG]

Modifications[1]:(included directed parameter with default value)

All Varients of Signature:

pgr_bellman_ford(edges_sql, start_vid, end_vid, directed=TRUE)

pgr_bellman_ford(edges_sql, start_vid, end_vids, directed=TRUE)

pgr_bellman_ford(edges_sql, start_vids, end_vid, directed=TRUE)

pgr_bellman_ford(edges_sql, start_vids, end_vids, directed=TRUE)

RETURNS SET OF (seq, path_seq [ start_vid] [ end_vid], node, edge, cost, agg_cost) OR EMPTY SET

[codeSG]

Modifications[2]: (included reverse cost)

Description of the edges_sql query:

edges_sql: an SQL query, which should return a set of rows with the following columns:

SELECT id, source, target, cost FROM edge_table

Column	Type	Description
id	ANY-INTEGER	Identifier of the edge
source	ANY-INTEGER	Identifier of the first endpoint vertex of the edge.
target	ANY-INTEGER	Identifier of the second endpoint vertex of the edge.
cost	ANY-NUMERICAL	Weight of the edge (source, target), When negative: edge (source, target) does not exist, therefore it’s not part of the graph.
reverse cost	ANY-NUMERICAL	Weight of the edge (target, source), When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

[codeSG]

@cvvergara I have modified the above things, here https://github.com/pgRouting/pgrouting/issues/1030#issuecomment-391365980 and https://github.com/pgRouting/pgrouting/issues/1030#issuecomment-391364637. Doesn't We need to make any changes in input and output parameters for the function?

[cvvergara]

I think they are fine, if at the end, for example, directed flag is not needed (some functions do work only on a certain kind of graph) then its easier to delete than to add