You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@madlib.apache.org by orhankislal <gi...@git.apache.org> on 2017/06/10 00:50:28 UTC
[GitHub] incubator-madlib pull request #140: APSP: Remove multiple updates for GPDB c...
GitHub user orhankislal opened a pull request:
https://github.com/apache/incubator-madlib/pull/140
APSP: Remove multiple updates for GPDB compatibility
Also adds the design document section for APSP.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/orhankislal/incubator-madlib graph/apsp_gr_take4
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/incubator-madlib/pull/140.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #140
----
commit 18d7416f8cce265b6e92371524d957b16c14810f
Author: Orhan Kislal <ok...@pivotal.io>
Date: 2017-06-10T00:48:39Z
APSP: Remove multiple updates for GPDB compatibility
Also adds the design document section for APSP.
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-madlib pull request #140: APSP: Remove multiple updates for GPDB c...
Posted by njayaram2 <gi...@git.apache.org>.
Github user njayaram2 commented on a diff in the pull request:
https://github.com/apache/incubator-madlib/pull/140#discussion_r121803411
--- Diff: doc/design/modules/graph.tex ---
@@ -273,6 +274,91 @@ \subsection{Implementation Details}
Please note that, for ideal performance, \emph{vertex} and \emph{edge} tables
should be distributed on \emph{vertex id} and \emph{source id} respectively.
+\section{All Pairs Shortest Paths} \label{sec:graph:apsp}
+
+Given a graph and a source vertex, all pairs shortest paths (APSP) algorithm
+finds a path for every vertex pair such that the sum of the weights of its
+constituent edges is minimized. Please refer to the
+Section~\ref{sec:graph:sssp} on single source shortest path for the
+mathematical definition of shortest path.
+
+Our implementation is based on the matrix multiplication inspired APSP
+algorithm \cite{apsp}. The idea is similar to the one from SSSP
+implementation. We start with a naive approximation for the cost of every
--- End diff --
This is actually a dynamic programming approach, you might want to mention that along with what you have here.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-madlib pull request #140: APSP: Remove multiple updates for GPDB c...
Posted by orhankislal <gi...@git.apache.org>.
Github user orhankislal closed the pull request at:
https://github.com/apache/incubator-madlib/pull/140
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---