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
