Re: [jgrapht-users] Implement composition of graphs

[J K. <j.k...@gm...>]

So if edge (x,y) exists in S and edge (y,z) exists in T, then (x,z) must
exist in U=S*T.
The following simple algorithm would work:

for edge (x,y) in S.edgeSet():
    for z in T.neighborsOf(y):
        if (x != z):
            U.addEdge(x,z)

Consider using the following function:
Graphs.addEdgeWithVertices(x,z)


On Thu, Dec 28, 2017 at 12:38 PM, Victor Porton <po...@na...> wrote:

> Let R and S be directed graphs.
>
> I will denote xTy iff there is an edge from x to y (for digraph T).
>
> Now I want to calculate the graph R*S defined by the formula:
>
> x(R*S)z <=> exists y: (xSy and yRz)
>
> It seems that this is not implemented in JGraphT.
>
> It seems that I will implement this in near future (unless somebody does
> it quicker than me [image: :-)]).
>
> On Thu, 2017-12-28 at 12:19 -0500, J Kinable wrote:
>
> You need to be a bit more explicit as what you want/need. I have no idea
> what you mean by "composition of binary relations as digraph". There is no
> representation of "binary relations". Obviously, there are plenty of
> different digraphs and algorithms available. Many algorithms can be easily
> implemented using the building blocks that are already present in the
> library.
>
> On Thu, Dec 28, 2017 at 8:55 AM, Victor Porton <po...@na...> wrote:
>
> I need composition of digraphs (I mean composition of binary relations
> represented as digraphs.) in my project. It seems that JGraphT is
> missing this operation.
>
> Is it really missing?
>
> If it is missing I want to implement it.
>
> I remind that composition is defined by the formula
>
> x(R*S)z <=> exists y: (xSy and yRz)
>
> ------------------------------------------------------------
> ------------------
> Check out the vibrant tech community on one of the world's most
> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
> ------------------------------------------------------------
> ------------------
> Check out the vibrant tech community on one of the world's most
> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>