Return-Path: 
 <user-return-1080-apmail-giraph-user-archive=giraph.apache.org@giraph.apache.org>
X-Original-To: apmail-giraph-user-archive@www.apache.org
Delivered-To: apmail-giraph-user-archive@www.apache.org
Received: from mail.apache.org (hermes.apache.org [140.211.11.3])
	by minotaur.apache.org (Postfix) with SMTP id 8FBB7FBD8
	for <apmail-giraph-user-archive@www.apache.org>;
 Thu, 18 Apr 2013 14:07:33 +0000 (UTC)
Received: (qmail 43744 invoked by uid 500); 18 Apr 2013 14:07:33 -0000
Delivered-To: apmail-giraph-user-archive@giraph.apache.org
Received: (qmail 42606 invoked by uid 500); 18 Apr 2013 14:07:28 -0000
Mailing-List: contact user-help@giraph.apache.org; run by ezmlm
Precedence: bulk
List-Help: <mailto:user-help@giraph.apache.org>
List-Unsubscribe: <mailto:user-unsubscribe@giraph.apache.org>
List-Post: <mailto:user@giraph.apache.org>
List-Id: <user.giraph.apache.org>
Reply-To: user@giraph.apache.org
Delivered-To: mailing list user@giraph.apache.org
Received: (qmail 42515 invoked by uid 99); 18 Apr 2013 14:07:25 -0000
Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230)
    by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 18 Apr 2013 14:07:25 +0000
X-ASF-Spam-Status: No, hits=1.5 required=5.0
	tests=HTML_MESSAGE,RCVD_IN_DNSWL_LOW,SPF_PASS
X-Spam-Check-By: apache.org
Received-SPF: pass (nike.apache.org: domain of jayhutfles@gmail.com designates
 209.85.128.52 as permitted sender)
Received: from [209.85.128.52] (HELO mail-qe0-f52.google.com) (209.85.128.52)
    by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 18 Apr 2013 14:07:19 +0000
Received: by mail-qe0-f52.google.com with SMTP id jy17so1709021qeb.11
        for <user@giraph.apache.org>; Thu, 18 Apr 2013 07:06:58 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20120113;
        h=mime-version:x-received:date:message-id:subject:from:to
         :content-type;
        bh=DBkzigNwBVh9b3v51IiP2L6hw4Ko9ktDyp4k0kqrGf0=;
        b=A9R15uOBMfP3yo/ruToECsc2IdHUcy8zfjrpGV1JDolYYu+LizkPc7f1GfKGCeLFJI
         sTG5A/VAILqAPAB253hOaLmhKBBYIu27q0VGsiyPKGtem0xxZ2KG5Dq5wJ3/efXtdoKf
         oI09yKCpaRjCZ1n6HFS9i99KsZse/Mpt30TXWpwCDLOLFXUuHoH0u8vVeUJqcHloBIza
         DWQQCMpxoY8u5iLdIFS5bRfm740E74t2fQKOTEaKva9/WcOXLzvGaO/twUVta3ecRCBp
         /bvl8oCnSL8aAwVkrI11m13NZN3fOIW82YE/gg8xOlqxiYXGk2QLQALoKhyfzZ4q+BRn
         yJzg==
MIME-Version: 1.0
X-Received: by 10.229.25.7 with SMTP id x7mr3842832qcb.138.1366294018388; Thu,
 18 Apr 2013 07:06:58 -0700 (PDT)
Received: by 10.49.96.104 with HTTP; Thu, 18 Apr 2013 07:06:58 -0700 (PDT)
Date: Thu, 18 Apr 2013 09:06:58 -0500
Message-ID: 
 <CALO52985C4AwqiP1PB34sqVJ_Pydg6QqOtzq2Tp15o66E1d26w@mail.gmail.com>
Subject: Network flow problems in Giraph
From: Jay Hutfles <jayhutfles@gmail.com>
To: user@giraph.apache.org
Content-Type: multipart/alternative; boundary=14dae9d70faea005d404daa31db9
X-Virus-Checked: Checked by ClamAV on apache.org

--14dae9d70faea005d404daa31db9
Content-Type: text/plain; charset=ISO-8859-1

I'm new to Giraph, but am interested in its applications to classic network
flow problems, specifically max flow or min cost problems.  I've looked for
BSP implementations of algorithms for these problems, but I can't find any
discussion regarding this online.  Has anyone had luck implementing such
problems?


The max flow problem seems like it should be adaptable to the BSP model.
 The flow augmenting algorithm developed by Ford and Fulkerson is
essentially:

while the graph contains a path over which flow could be increased,
   increase flow for arcs on the path

Identifying the flow augmenting paths is a simple labeling algorithm, but
I'm not sure how I'd implement the "while the graph contains ..."
condition.  Is that a super step *above* the labeling algorithm's super
steps?


And I have no idea how to start the min cost algorithm.  Anyone have ideas
for how to formulate this?

Thanks for your time, and for the great work on Giraph!

--14dae9d70faea005d404daa31db9
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">I&#39;m new to Giraph, but am interested in its applicatio=
ns to classic network flow problems, specifically max flow or min cost prob=
lems. =A0I&#39;ve looked for BSP implementations of algorithms for these pr=
oblems, but I can&#39;t find any discussion regarding this online. =A0Has a=
nyone had luck implementing such problems?<div>
<br><div><br></div><div style>The max flow problem seems like it should be =
adaptable to the BSP model. =A0The flow augmenting algorithm developed by F=
ord and Fulkerson is essentially:</div><div style><br></div><div style>whil=
e the graph contains a path over which flow could be increased,</div>
<div style>=A0 =A0increase flow for arcs on the path</div><div style><br></=
div><div style>Identifying the flow augmenting paths is a simple labeling a=
lgorithm, but I&#39;m not sure how I&#39;d implement the &quot;while the gr=
aph contains ...&quot; condition. =A0Is that a super step <i>above</i>=A0th=
e labeling algorithm&#39;s super steps?</div>
<div style><br></div><div style><br></div><div style>And I have no idea how=
 to start the min cost algorithm. =A0Anyone have ideas for how to formulate=
 this?</div><div style><br></div><div style>Thanks for your time, and for t=
he great work on Giraph!</div>
</div></div>

--14dae9d70faea005d404daa31db9--