flink-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Saumitra Shahapure <saumitra.offic...@gmail.com>
Subject Re: Design document for FLINK-2254
Date Thu, 22 Oct 2015 11:00:53 GMT
Hi Vasia,

Here
<https://docs.google.com/document/d/1SChonW4bXNiqU2Pz9PPjuKDuKrBGmESrPcJXamj4dlI/edit?usp=sharing>
is the Google doc.

-- Saumitra S. Shahapure

On Thu, Oct 22, 2015 at 11:10 AM, Vasiliki Kalavri <
vasilikikalavri@gmail.com> wrote:

> Hi Saumitra,
>
> could you maybe add your ideas above in a google doc and share the link, so
> we can easily comment and/or edit?
>
> Thank you!
> -Vasia.
>
> On 22 October 2015 at 10:53, Andra Lungu <lungu.andra@gmail.com> wrote:
>
> > Hi Saumitra,
> >
> > As you already noticed, the first version (with duplicates) is highly
> > inefficient and consumes a lot of memory. So, I suggest we drop it for
> now.
> > The version with the label makes a lot of modifications on the base Graph
> > class, and this, in my opinion would make it more difficult to grasp.
> > Bipartite Graphs are not as common as regular graphs. And then, when you
> > would add an Isomorphic Graph class (stupid example), you'll need to
> strip
> > stuff out again.
> >
> > I believe we should go with a BipartiteGraph class which extends Graph
> and
> > which has a DataSet of topVertices and a DataSet of bottomVertices. Apart
> > from getTopVertices() methods, we would still need functions such as
> > getNumberOfTopVertices(). For the time being, just support the funstiones
> > mentiones as well as the basics: fromCollection, fromDataSet, etc, get*,
> > join*, map*, filter*.
> >
> > Wait for a few more opinions and dig in. I believe we should discuss this
> > even further and propose Jiras for examples of algos for bipartite
> graphs.
> >
> > Once we have the design specs well figured out, and if I find some time
> > I'll gladly chime in :)
> >
> > Cheers!
> > Andra
> >
> > On Wed, Oct 21, 2015 at 8:45 PM, Saumitra Shahapure <
> > saumitra.official@gmail.com> wrote:
> >
> > > In FLINK-2254 <https://issues.apache.org/jira/browse/FLINK-2254> , we
> > > want to extend Graph API of Gelly by adding support for bipartite
> graphs
> > > too. In the long term, the support for newer graph types can be added
> in
> > > the same way. Also specialised algorithms for special types of graphs
> > > should be implemented.
> > >
> > > For bipartite graph, a new class BipartiteGraph can be implemented
> which
> > > extends Graph. Other graph algorithms which are written for Graph can
> be
> > > used for BipartiteGraph too, because of inheritance.
> > > Initialisation functions like  public static <K, VV, EV> Graph<K,
VV,
> EV>
> > > fromCollection(Collection<Vertex<K, VV>> vertices,Collection<Edge<K,
> EV>>
> > > edges, ExecutionEnvironment context) need to be duplicated as public
> > static
> > > <K, VV, EV> BipartiteGraph<K, VV, EV>
> fromCollection(Collection<Vertex<K,
> > > VV>> topVertices,Collection<Vertex<K, VV>> bottomVertices,
> > > Collection<Edge<K, EV>> edges, ExecutionEnvironment context)
> > > Graph validation does not need to happen implicitly. user can call
> > > BipartiteGraph.validate() in case he wants to check sanity of data.
> > > Vertex modes is primary requirement. BipartiteGraph should have
> > functions,
> > > getTopVertices() and getBottomVertices(). There are three ways to
> > implement
> > > it:
> > > Simplest and least efficient way is to maintain vertices variable in
> > Graph
> > > in addition to two more Datasets topVertices, bottomVertices. Benefit
> of
> > > this approach is that Graph class would not need any modification at
> all.
> > > this.vertices variable access inside Graph class would work correctly.
> > > Disadvantage is that multiple copies of vertex dataset are created and
> > > maintained. So this is inefficient in terms of memory.
> > > Another way is to keep topVertices and bottomVertices variables in
> > > BipartiteGraph. vertices variable in Graph would stay empty.
> > getVertices()
> > > function of Graph would be overloaded by BipartiteGraph and
> reimplemented
> > > as union of of topVertices and bottomVertices. Since, vertices is a
> > private
> > > variable, external view of vertices stays unaffected. All functions of
> > > Graph class which use vertices local variable (e.g.
> > getVerticesAsTuple2())
> > > need to use getVertices() instead of this.vertices. Disadvantage of
> this
> > > method is Graph.vertices variable would have invalid value throughout
> for
> > > BipartiteGraph.
> > > Another way is to ‘label’ vertices with an integer. So public class
> > > BipartiteGraph<K,VV,EV> extends Graph<K, Tuple2<VV,Integer>,
EV> would
> be
> > > the signature. Initialisers would tag the vertices according to their
> > mode.
> > > getVertices() should be overridden to strip-off the tag values so that
> > > users would get consistent view of vertex dataset for Graph and
> > > BipartiteGraph. getTopVertices/getBottomVertices would be filter
> > functions
> > > on vertex tags.
> > > I personally feel method 2 to be most elegant.
> > > Functions like addVertices(vertexList) are not relevant without
> > specifying
> > > whether they are top or bottom. A possibility could be to add them to
> > > topVertices by default. And have overloaded function
> > > addVertices(vertexList, mode) to add them to specific partition.
> > > Specialised algorithms for Bipartite graphs can implement new
> > > BipartiteGraphAlgorithm interface. It would be similar to
> GraphAlgorithm.
> > > In future, newer types of graphs can be similarly derived from Graph
> and
> > > type hierarchy of Graph can be created. Class hierarchy would be better
> > > here rather than interface hierarchy, because the functions which are
> > > applicable to all derived classes can be implemented in the base class.
> > > As a part of future refactoring, Graph transformation functions should
> > > rather be a new class implementing GraphAlgorithm rather than function
> in
> > > Graph class. This may make implementing complex graph types easier.
> > > PS. Do I need to add it in wiki too? I can copy the contents to wiki if
> > > you say so,
> > > -- Saumitra Shahapure
> > >
> > >
> >
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message