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
