Ok. We will look into this option as well. On Thu, Aug 11, 2016 at 6:57 PM, Sajith Ravindra <[email protected]> wrote:
> Actually what I suggested was to use a graph library to keep the graph > data structure and implement these algorithms(i.e. maximum clique, largest > connected component) on top of it rather than having our own implementation > of the data structure. > > But, if it's required to have complete control over underlying data > structure then obviously there's no other option than having our own > implementation. > > Thanks > *,Sajith Ravindra* > Senior Software Engineer > WSO2 Inc.; http://wso2.com > lean.enterprise.middleware > > mobile: +94 77 2273550 > blog: http://sajithr.blogspot.com/ > <http://lk.linkedin.com/pub/shani-ranasinghe/34/111/ab> > > On Thu, Aug 11, 2016 at 6:43 PM, Malith Jayasinghe <[email protected]> > wrote: > >> Yes there were performance issues with certain graph libraries in >> relation to certain operations. For example, largest connected component in >> some libraries were calculated using depth-first-search which had poor >> performance (note that some recently proposed algorithms with better >> performance only exists in published papers they have not really been >> implemented in these libraries). >> >> Other libraries did not have functionalities that we wanted (i.e. maximum >> clique, largest connected component, strongly connected component etc). >> >> If you can suggest one then we can test it out and use it here? >> >> >> We also want the ability change the underlying data structure of the >> graph (i.e. adjacency matrix, adjacency list) which requires different >> implementations. So that we can chose the implementation we want depending >> on the scenario (note: these implementations have different time and space >> complexities). >> >> >> On Thu, Aug 11, 2016 at 2:48 PM, Sajith Ravindra <[email protected]> >> wrote: >> >>> Hi Bhagya, >>> >>> I think it would be a good idea to do a performance evalluvation to see >>> if the simple implemntation can fulfill the performance requirment. With >>> our own implementation we have the overhead of maintaing the grpah >>> implementation as we go foward with new requirments. >>> >>> IMO, unless there's a really good reason (e.g. bad performance, license >>> incompatilbiliity of libararies available, etc..s) we should use a already >>> widly used liibrary for this as it could possibly give us a roboust >>> implemnation of grpahs with better performance without any maintainace >>> overhead. >>> >>> >>> >>> >>> Thanks >>> *,Sajith Ravindra* >>> Senior Software Engineer >>> WSO2 Inc.; http://wso2.com >>> lean.enterprise.middleware >>> >>> mobile: +94 77 2273550 >>> blog: http://sajithr.blogspot.com/ >>> <http://lk.linkedin.com/pub/shani-ranasinghe/34/111/ab> >>> >>> On Thu, Aug 11, 2016 at 1:26 PM, Bhagya Rupasinghe <[email protected]> >>> wrote: >>> >>>> Hi Sajith, >>>> >>>> There is a possibility of doing this. However, the effort required to >>>> implement a graph is minimal. For example, a graph can be implemented using >>>> adjacency list and basic operations on a graph are very simple to >>>> implement. >>>> >>>> Regards, >>>> Bhagya Rupasinghe >>>> Software Engineer Intern >>>> Mobile : 0711274536 >>>> [email protected] >>>> >>>> >>>> >>>> >>>> >>>> On Thu, Aug 11, 2016 at 12:39 PM, Sajith Ravindra <[email protected]> >>>> wrote: >>>> >>>>> Hi Bhagya, >>>>> >>>>> Wouldn't it be easy if we use a library for the graph implementation >>>>> instead of implementing your won graph implementation? IMO, if you try to >>>>> implement you own graph you will have put more effort into that than the >>>>> core functionality itself. Also, as we go on our requirements might also >>>>> evolve which in turn possibly result in a change in the graph >>>>> implementation. >>>>> >>>>> I came across [1] which is an open source graph implementation library >>>>> available under LGPL license . I think it's better if we can evaluate such >>>>> graph implementation in terms of usability, performance, and license and >>>>> use it if possible. >>>>> >>>>> [1] - http://jgrapht.org/ >>>>> >>>>> Thanks >>>>> *,Sajith Ravindra* >>>>> Senior Software Engineer >>>>> WSO2 Inc.; http://wso2.com >>>>> lean.enterprise.middleware >>>>> >>>>> mobile: +94 77 2273550 >>>>> blog: http://sajithr.blogspot.com/ >>>>> <http://lk.linkedin.com/pub/shani-ranasinghe/34/111/ab> >>>>> >>>>> On Thu, Aug 11, 2016 at 12:02 PM, Bhagya Rupasinghe <[email protected]> >>>>> wrote: >>>>> >>>>>> Hi Sasikala, >>>>>> >>>>>> Input stream is not a set of vertices.The input stream contains a >>>>>> pair of vertices adjacent to each other. The siddhi extension accepts two >>>>>> adjacent vertices as the input. I have used a Hashmap to create an >>>>>> adjacency list to generate the graph. >>>>>> >>>>>> Regards, >>>>>> Bhagya Rupasinghe >>>>>> Software Engineer Intern >>>>>> Mobile : 0711274536 >>>>>> [email protected] >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> On Thu, Aug 11, 2016 at 7:16 AM, Sasikala Kottegoda < >>>>>> [email protected]> wrote: >>>>>> >>>>>>> Hi Bhagya, >>>>>>> >>>>>>> How are we going to create the edges given an input stream of >>>>>>> userIDs as a set of vertices? >>>>>>> >>>>>>> Thank you, >>>>>>> Sasikala >>>>>>> >>>>>>> On Wed, Aug 10, 2016 at 10:14 PM, Bhagya Rupasinghe < >>>>>>> [email protected]> wrote: >>>>>>> >>>>>>>> Hi Malith, >>>>>>>> >>>>>>>> 1.Algorithm for finding largest connected component: >>>>>>>> http://www.iosrjen.org/Papers/vol4_issue2%20(part-6)/E04263542.pdf >>>>>>>> >>>>>>>> 2.Algorithm for largest clique : 2016 DEBS Grand Challenge Winning >>>>>>>> Paper >>>>>>>> >>>>>>>> Regards, >>>>>>>> Bhagya Rupasinghe >>>>>>>> Software Engineer Intern >>>>>>>> Mobile : 0711274536 >>>>>>>> [email protected] >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> On Wed, Aug 10, 2016 at 9:12 PM, Malith Jayasinghe < >>>>>>>> [email protected]> wrote: >>>>>>>> >>>>>>>>> Hi Bhagya, >>>>>>>>> >>>>>>>>> Please provide the references for maximum clique and largest >>>>>>>>> connected component (i.e. pegasus) algorithms. >>>>>>>>> >>>>>>>>> Thanks >>>>>>>>> >>>>>>>>> Malith >>>>>>>>> >>>>>>>>> On Wed, Aug 10, 2016 at 9:04 PM, Bhagya Rupasinghe < >>>>>>>>> [email protected]> wrote: >>>>>>>>> >>>>>>>>>> Hi all, >>>>>>>>>> Implementation in Siddhi >>>>>>>>>> >>>>>>>>>> Maximum clique is used to identify the largest number of vertices >>>>>>>>>> in the same entity which are connected to each other.In the Siddhi >>>>>>>>>> implementation, input stream containing user IDs are added into a >>>>>>>>>> graph as >>>>>>>>>> vertices. And then edge is created between them to show that they are >>>>>>>>>> linked.Finally largest clique size is calculated and send as output >>>>>>>>>> stream. >>>>>>>>>> >>>>>>>>>> This implementation can be used to identify largest customer >>>>>>>>>> collection when it comes to marketing by providing their >>>>>>>>>> relationships.We >>>>>>>>>> can use social media data to find the relationships. >>>>>>>>>> >>>>>>>>>> Largest Connected component is the largest number of vertices >>>>>>>>>> which connect to the vertex next to them.But they are not inter >>>>>>>>>> connected.This is a big chain with respect to the largest clique.In >>>>>>>>>> siddhi >>>>>>>>>> we used user IDs of users who are connected with each other as input >>>>>>>>>> data >>>>>>>>>> and calculated largest connected component using pegasus >>>>>>>>>> algorithm.Finally >>>>>>>>>> largest connected component will be send to the output stream. >>>>>>>>>> On Aug 10, 2016 12:15 PM, "Malith Jayasinghe" <[email protected]> >>>>>>>>>> wrote: >>>>>>>>>> >>>>>>>>>>> Hi All, >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> We are implementing 2 Siddhi Extensions 1) Largest Connected >>>>>>>>>>> Component and 2) Maximum Clique. >>>>>>>>>>> >>>>>>>>>>> Using these extensions we can identify/detect the largest >>>>>>>>>>> connected component and the maximum clique in a (large) undirected >>>>>>>>>>> graph. A >>>>>>>>>>> connected component/clique could represent a community that are >>>>>>>>>>> currently involved in a particular topic etc. In the initial >>>>>>>>>>> implementation we are considering only the undirected graphs in >>>>>>>>>>> which edges have no orientation (direction). >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> 1) Connected component: a connected component of an undirected >>>>>>>>>>> graph is a subgraph in which any two vertices are connected to >>>>>>>>>>> each other by paths. The following figure shows a graph with 3 >>>>>>>>>>> connected >>>>>>>>>>> components >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> 2) Clique: The clique is an important concept in graph theory >>>>>>>>>>> (also called a complete graph). It is defined as a graph where >>>>>>>>>>> every vertex is connected to every other. This means that every >>>>>>>>>>> vertex is >>>>>>>>>>> reachable <https://en.wikipedia.org/wiki/Reachability> from >>>>>>>>>>> every other vertex. In the graph below the maximal clique is >>>>>>>>>>> 6-clique containing the vertices {A, G, H, J, K, M}. >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> [1] https://en.wikipedia.org/wiki/Clique_(graph_theory) >>>>>>>>>>> [2] https://en.wikipedia.org/wiki/Connected_component_(graph >>>>>>>>>>> _theory) >>>>>>>>>>> >>>>>>>>>>> -- >>>>>>>>>>> Malith Jayasinghe >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> WSO2, Inc. (http://wso2.com) >>>>>>>>>>> Email : [email protected] >>>>>>>>>>> Mobile : 0770704040 >>>>>>>>>>> Lean . Enterprise . Middleware >>>>>>>>>>> >>>>>>>>>>> _______________________________________________ >>>>>>>>>>> Architecture mailing list >>>>>>>>>>> [email protected] >>>>>>>>>>> https://mail.wso2.org/cgi-bin/mailman/listinfo/architecture >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>> _______________________________________________ >>>>>>>>>> Architecture mailing list >>>>>>>>>> [email protected] >>>>>>>>>> https://mail.wso2.org/cgi-bin/mailman/listinfo/architecture >>>>>>>>>> >>>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> -- >>>>>>>>> Malith Jayasinghe >>>>>>>>> >>>>>>>>> >>>>>>>>> WSO2, Inc. (http://wso2.com) >>>>>>>>> Email : [email protected] >>>>>>>>> Mobile : 0770704040 >>>>>>>>> Lean . Enterprise . Middleware >>>>>>>>> >>>>>>>>> _______________________________________________ >>>>>>>>> Architecture mailing list >>>>>>>>> [email protected] >>>>>>>>> https://mail.wso2.org/cgi-bin/mailman/listinfo/architecture >>>>>>>>> >>>>>>>>> >>>>>>>> >>>>>>>> _______________________________________________ >>>>>>>> Architecture mailing list >>>>>>>> [email protected] >>>>>>>> https://mail.wso2.org/cgi-bin/mailman/listinfo/architecture >>>>>>>> >>>>>>>> >>>>>>> >>>>>>> >>>>>>> -- >>>>>>> Sasikala Kottegoda >>>>>>> *Software Engineer* >>>>>>> WSO2 Inc., http://wso2.com/ >>>>>>> lean. enterprise. middleware >>>>>>> Mobile: +94 774835928 >>>>>>> >>>>>>> [image: https://wso2.com/signature] <https://wso2.com/signature> >>>>>>> >>>>>> >>>>>> >>>>>> _______________________________________________ >>>>>> Architecture mailing list >>>>>> [email protected] >>>>>> https://mail.wso2.org/cgi-bin/mailman/listinfo/architecture >>>>>> >>>>>> >>>>> >>>>> _______________________________________________ >>>>> Architecture mailing list >>>>> [email protected] >>>>> https://mail.wso2.org/cgi-bin/mailman/listinfo/architecture >>>>> >>>>> >>>> >>>> _______________________________________________ >>>> Architecture mailing list >>>> [email protected] >>>> https://mail.wso2.org/cgi-bin/mailman/listinfo/architecture >>>> >>>> >>> >>> _______________________________________________ >>> Architecture mailing list >>> [email protected] >>> https://mail.wso2.org/cgi-bin/mailman/listinfo/architecture >>> >>> >> >> >> -- >> Malith Jayasinghe >> >> >> WSO2, Inc. (http://wso2.com) >> Email : [email protected] >> Mobile : 0770704040 >> Lean . Enterprise . Middleware >> >> _______________________________________________ >> Architecture mailing list >> [email protected] >> https://mail.wso2.org/cgi-bin/mailman/listinfo/architecture >> >> > > _______________________________________________ > Architecture mailing list > [email protected] > https://mail.wso2.org/cgi-bin/mailman/listinfo/architecture > > -- Malith Jayasinghe WSO2, Inc. (http://wso2.com) Email : [email protected] Mobile : 0770704040 Lean . Enterprise . Middleware
_______________________________________________ Architecture mailing list [email protected] https://mail.wso2.org/cgi-bin/mailman/listinfo/architecture
