jgrapht-users — JGraphT user list.

[jgrapht-users] Please, i need help concerning the SimpleDirectedWeightedGraph Class

[mokhtar a. <ait...@gm...>]

Hello everyone;
I have a project in which i need to implement a graph (directed &
weighted), and i found your work which helped me a lot, but i have a
problem and i want you to help me out.
When i create my SimpleDirectedWeightedGraph object "graph" and insret the
vertexes (type Site in my case) and edges (Type Lien in my case) and apply
the "incomingEdgesOf(Vertex v)" method to the "graph", i put the result in
a Set<Lien> and i find that the size (number of incoming edges) is correct
but when i apply the method again on the resulting set of edges "so that i
can calculate the number of descendants of an Edge" an exception in thrown
which says java.lang.NullPointerException .
-------------------------------------------------------------------------------
Here is my code:
//CALCULATE THE NUMBER OF DESCENDANTS OF AN EDGE (WHERE SITE S IS THE
DESTINATION VERTEX) IN THE GRAPH
    public int nbrDescendants(Site s)
    {
        int i=0;
        Set<Lien> children = graph.incomingEdgesOf(s);
        Iterator<Lien> it = children.iterator();
        while(it.hasNext())
        {
            i+= graph.incomingEdgesOf(it.next().getSlave()).size();
//getSlave() returs in my case the destination vertex of the edge
        }
        i+=children.size();
        return i;
    }
​-----------------------------------------------------------------------------------​
​Here is the error message:
java.lang.NullPointerException
    at
org.jgrapht.graph.AbstractGraph.assertVertexExist(AbstractGraph.java:156)
    at
org.jgrapht.graph.AbstractBaseGraph$DirectedSpecifics.getEdgeContainer(AbstractBaseGraph.java:925)
    at
org.jgrapht.graph.AbstractBaseGraph$DirectedSpecifics.incomingEdgesOf(AbstractBaseGraph.java:885)
    at
org.jgrapht.graph.AbstractBaseGraph.incomingEdgesOf(AbstractBaseGraph.java:411)
    at inwi.capacite.calcul.Reseau.nbrDescendants(Reseau.java:62)
    at inwi.capacite.calcul.Rapport.main(Rapport.java:86)
------------------------------------------------------------------------------------
And finally i'm not sure but i think that the error comes from the
AbstractBaseGraph.java file, where i found this:

   */
        public Set<EE> getUnmodifiableOutgoingEdges()
        {
            if (unmodifiableOutgoing == null) {
                unmodifiableOutgoing =
Collections.unmodifiableSet(outgoing);
            }

            return unmodifiableOutgoing;
        }
​
​i think this methode must return Set<E> and not Set<EE>.​

[jgrapht-users] ECCN for JGraphT

[Beurer, M. (C. - DE/Munich) <mar...@co...>]

Hello,

As we use Jgraph 5.13 and JgraphT 0.9.0 in our netelement manager, we need the export control and compliance number (ECCN) for the products or we need to know:

-        Country of origin (CoO): where is the sw developed mainly

-        Does it contain encryption?

-        If yes, which algorithm(s) and key length?
for self classification.

Thanks in advance.
Mit freundlichen Grüßen / Kind Regards / Com os melhores cumprimentos!
Maria Beurer

[cid:image001.png@01D01091.4F1BD1F0]

Coriant GmbH
Maria Beurer
R&D Engineer
Coriant R&D GmbH
SW OSS&Transnet TNTC DE
St.-Martin-Str. 76
81541 München
Tel: +49 89 5402 15138
mar...@co...<mailto:mar...@co...>
http://www.coriant.com<mailto:mar...@ns...>
[cid:image002.png@01D01091.4F1BD1F0]Think before you print
Coriant GmbH
registered under / registriert unter: HRB 202750 | WEEE-Reg.-No. DE 77603797
Local Court of Munich / Amtsgericht München
Members of the Board / Geschäftsführer: Peter Streit
VAT ID / USt-IdNr.: DE288084869

Re: [jgrapht-users] Edge identity

[Joris K. <de...@gm...>]

That depends on how you define an edge. You can just define a new type of
"Labeled" edge. For an example, refer to:
https://github.com/jgrapht/jgrapht/wiki/LabeledEdges

br,

Joris

On Wed, Jan 28, 2015 at 3:50 PM, Yossi K <yo...@gm...> wrote:

> Hello,
>
>    AbstractBaseGraph.containsEdge() checks whetehr edgeMap contains
>    the edge in its key set.
>
>     public boolean containsEdge(E e)
>     {
>         return edgeMap.containsKey(e);
>     }
>
>    When the edges are strings, this test makes it impossible for a graph
>    to have two edges with the same label. For example, when the edges
>    are words in a sentence and one of the words appears more than once.
>
>   Doesn't the identity of an edge include its start and end vertices as
> well?
>
>     Thanks,
>        Y
>
>
> ------------------------------------------------------------------------------
> Dive into the World of Parallel Programming. The Go Parallel Website,
> sponsored by Intel and developed in partnership with Slashdot Media, is
> your
> hub for all things parallel software development, from weekly thought
> leadership blogs to news, videos, case studies, tutorials and more. Take a
> look and join the conversation now. http://goparallel.sourceforge.net/
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] Edge identity

[Yossi K <yo...@gm...>]

Hello,

   AbstractBaseGraph.containsEdge() checks whetehr edgeMap contains
   the edge in its key set.

    public boolean containsEdge(E e)
    {
        return edgeMap.containsKey(e);
    }

   When the edges are strings, this test makes it impossible for a graph
   to have two edges with the same label. For example, when the edges
   are words in a sentence and one of the words appears more than once.

  Doesn't the identity of an edge include its start and end vertices as
well?

    Thanks,
       Y

Re: [jgrapht-users] Max flow for undirected graphs?

[Mads J. <mj...@in...>]

On 01/24/2015 08:54 PM, Mads Jensen wrote:
> Hi,
> 
> I only see that the Edmonds Karp implementation takes a directed graph
> as input. However, some algorithms, such as Gomory Hu take an undirected
> graph as input, and make calls to a flow algorithm.
> 
> In the Boost Graph library, the implementation for Edmonds Karp works on
> both directed and undirected graphs. Is there a way to quickly get
> around this issue?

Please disregard this. I found out that Stoer Wagner can do this.
-- 
Med Venlig Hilsen / Kind regards,
Mads Jensen

Max Jerry Horovitz: "Unfortunately, in America, babies are not found in
cola cans. I asked my mother when I was four and she said they came from
eggs laid by rabbis. If you aren't Jewish, they're laid by Catholic
nuns. If you're an atheist, they're laid by dirty, lonely prostitutes."
         -- Mary and Max (2009)

[jgrapht-users] Max flow for undirected graphs?

[Mads J. <mj...@in...>]

Hi,

I only see that the Edmonds Karp implementation takes a directed graph
as input. However, some algorithms, such as Gomory Hu take an undirected
graph as input, and make calls to a flow algorithm.

In the Boost Graph library, the implementation for Edmonds Karp works on
both directed and undirected graphs. Is there a way to quickly get
around this issue?

Thank you,
-- 
Med Venlig Hilsen / Kind regards,
Mads Jensen

Max Jerry Horovitz: "Unfortunately, in America, babies are not found in
cola cans. I asked my mother when I was four and she said they came from
eggs laid by rabbis. If you aren't Jewish, they're laid by Catholic
nuns. If you're an atheist, they're laid by dirty, lonely prostitutes."
         -- Mary and Max (2009)

Re: [jgrapht-users] Limited edges number?

[Rushang K. <rus...@ho...>]

I am not sure if this is the solution but does JGraphT provide another identification for an Edge.
 
Say 
 
addEdge(V a, V b)
addEdge(V a, V b, E) where E is the type of edge?
 
addEdge(V a, V b) will add an edge only if there does not exist an edge in the graph already with those objects.
 
Integer a = 42;
Integer b = 50; (add the constructors)
 
addEdge(a, b) will add an edge. 
 
Now if you do
a = 100;
b = 40;
 
addEdge(a,b) it will not add the edge.
 
I would try using the second type of method.
 
String x = ""
 
for total number of edges
{
addEdge(a, b, x)
x += " ";
}
 
I would first see if this fixes the problem. If yes then the problem is that your object references are not changing.
 
Again I do not remember clearly( Long time since I used jgrapht)
 
From: jul...@gm...
Date: Sun, 18 Jan 2015 11:17:15 -0500
To: bor...@gm...
CC: jgr...@li...
Subject: Re: [jgrapht-users] Limited edges number?

Hi Boris,
I'd take a guess that you're using Integer objects to identify nodes, and being caught by Java's curious habit of autoboxing Integers up to 127 only. See this reference: http://bexhuff.com/2006/11/java-1-5-autoboxing-wackyness.
This wouldn't explain why your limit is 50 and not 127, but there may be some arithmetic jiggery-pokery in your code that pushes some important integer into the 127 / 128 range.
My apologies if you're my grandmother and you already know how to suck eggs.
Julian Tuck
On Fri, Jan 16, 2015 at 9:07 AM, Bartek Borucki <bor...@gm...> wrote:
Hi,I've creating an Android project using JgraphT. It works fine except one thing, why can't I add more than 50 edges to WightedGraph like this:
defaultWeightedEdge = (DefaultWeightedEdge) graph.addEdge(fromNode, toNode); ?

Thanks in advance for all replies.Bartek

------------------------------------------------------------------------------

New Year. New Location. New Benefits. New Data Center in Ashburn, VA.

GigeNET is offering a free month of service with a new server in Ashburn.

Choose from 2 high performing configs, both with 100TB of bandwidth.

Higher redundancy.Lower latency.Increased capacity.Completely compliant.

http://p.sf.net/sfu/gigenet
_______________________________________________

jgrapht-users mailing list

jgr...@li...

https://lists.sourceforge.net/lists/listinfo/jgrapht-users





------------------------------------------------------------------------------
New Year. New Location. New Benefits. New Data Center in Ashburn, VA.
GigeNET is offering a free month of service with a new server in Ashburn.
Choose from 2 high performing configs, both with 100TB of bandwidth.
Higher redundancy.Lower latency.Increased capacity.Completely compliant.
http://p.sf.net/sfu/gigenet
_______________________________________________
jgrapht-users mailing list
jgr...@li...
https://lists.sourceforge.net/lists/listinfo/jgrapht-users 		 	   		  

Re: [jgrapht-users] Limited edges number?

[Julian T. <jul...@gm...>]

Hi Boris,

I'd take a guess that you're using Integer objects to identify nodes, and
being caught by Java's curious habit of autoboxing Integers up to 127 only.
See this reference: http://bexhuff.com/2006/11/java-1-5-autoboxing-wackyness
.

This wouldn't explain why your limit is 50 and not 127, but there may be
some arithmetic jiggery-pokery in your code that pushes some important
integer into the 127 / 128 range.

My apologies if you're my grandmother and you already know how to suck eggs.

Julian Tuck

On Fri, Jan 16, 2015 at 9:07 AM, Bartek Borucki <bor...@gm...> wrote:

> Hi,
> I've creating an Android project using JgraphT. It works fine except one
> thing, why can't I add more than 50 edges to WightedGraph like this:
> defaultWeightedEdge = (DefaultWeightedEdge) graph.addEdge(fromNode,
> toNode); ?
>
> Thanks in advance for all replies.
> Bartek
>
>
> ------------------------------------------------------------------------------
> New Year. New Location. New Benefits. New Data Center in Ashburn, VA.
> GigeNET is offering a free month of service with a new server in Ashburn.
> Choose from 2 high performing configs, both with 100TB of bandwidth.
> Higher redundancy.Lower latency.Increased capacity.Completely compliant.
> http://p.sf.net/sfu/gigenet
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

Re: [jgrapht-users] Limited edges number?

[H.N. de R. <hnr...@gr...>]

On Fri, Jan 16, 2015 at 03:07:20PM +0100, Bartek Borucki wrote:

> I've creating an Android project using JgraphT. It works fine except one
> thing, why can't I add more than 50 edges to WightedGraph like this:
> defaultWeightedEdge = (DefaultWeightedEdge) graph.addEdge(fromNode,
> toNode); ?

Out of memory maybe? What's the error and what does your code look like?


-- 
Information System on Graph Classes and their Inclusions (ISGCI)
http://www.graphclasses.org

[jgrapht-users] Limited edges number?

[Bartek B. <bor...@gm...>]

Hi,
I've creating an Android project using JgraphT. It works fine except one
thing, why can't I add more than 50 edges to WightedGraph like this:
defaultWeightedEdge = (DefaultWeightedEdge) graph.addEdge(fromNode,
toNode); ?

Thanks in advance for all replies.
Bartek

Re: [jgrapht-users] Mixed graphs

[Rushang K. <rus...@ho...>]

Hi,
 
The solution proposed by Dimitris could tax your memory if the graph was large. However it is the most easiest solution to implement.
 
What algorithms do you want to run on the graph? Perhaps then it would be more clearer for us to help you.
 
If you are going to develop some of your own algorithms (that suit your problem) let us know those too.
 
Date: Fri, 9 Jan 2015 19:38:05 +0200
From: dma...@cs...
To: mat...@gm...
CC: jgr...@li...
Subject: Re: [jgrapht-users] Mixed graphs


  
    
  
  
    I 'm entirely sure that the formulation of your problem requires
    that both directed and undirected edges have to exist in the same
    graph. However, sometimes, whenever there is such a requirement, it
    is advisable to go back to the problem and consider whether its
    model really requires both kinds of edges. 

    

    If, after reconsidering the problem, it is still absolutely
    necessary to have both kind of edges, consider whether the
    operations you perform on the graph require both kinds of edges. If
    they do, you could built two different graphs (1 directed, 1
    undirected) with the same set of nodes, but a different set of edges
    and adapt your operations to check both graphs. 

    

    Hope that helps a bit.

    

    

    

    On 08/01/2015 01:41 μμ, Matyas Krutsky
      wrote:

    
    
      Thank you for your response, but unfortunately this
        is not applicable for me since I have to distinguish between
        cases where there are actually two directed edges with opposite
        direction between two nodes and where there is an undirected
        edge. I would have to keep track of undirected edges somewhere
        and treat both directed edges which forms the undirected edge as
        one when changing some property or removing the edge. This seems
        more difficult and error-prone then creating a sort of
        "semidirected view" over undirected graph as I suggested... 
      

        2015-01-08 12:26 GMT+01:00 Dimitris
          Mavroeidis <dma...@cs...>:

          This is a
            more general answer and applies to any graph implementation.
            It is often used in situations such as the one you describe.

            

            You can use a directed graph and simply represent any
            undirected edge with two directed edges. So, if you have an
            undirected edge between node A and node B, you would create
            an edge from node A to node B and another from node B to
            node A.

            

            If you think of it, an undirected graph is a generalization
            of a directed graph containing both directions between
            nodes.

            

            Dimitris

            

            On 08/01/2015 11:50 πμ, krutor wrote:

            
              Hi, I'm considering using JGraphT as general graphstore in
              my project, but I

              need to represent graph as Mixed graph

              (http://mathworld.wolfram.com/MixedGraph.html)
              - using directed and

              undirected edges together in  one graph. Is there any way
              to simulate this

              behaviour in JGraphT?

              

              The best I came up with yet, is to hide JGraphT behind my
              own interface, use

              custom edges with DIRECTED flag and undirected graph
              implementation

              overriding methods behavior where needed. When using
              algorithms, it is

              usually ok for me that graph is treated like undirected,
              so I will just use

              them with the underlying undirected graph...

              

              Cleaner implementation may be implementing my own

              AbstractBaseGraph.Specifics, but that is impossible to do
              since Specifics

              class is private. Is there any special reason for it to be
              private?

              

              Is there any better way to do it? Am I missing something
              important?

              

              Thanks for response

              

              

              

              

              --

              View this message in context: http://jgrapht-users.107614.n3.nabble.com/Mixed-graphs-tp4024952.html

              Sent from the jgrapht-users mailing list archive at
              Nabble.com.

              

              ------------------------------------------------------------------------------

              Dive into the World of Parallel Programming! The Go
              Parallel Website,

              sponsored by Intel and developed in partnership with
              Slashdot Media, is your

              hub for all things parallel software development, from
              weekly thought

              leadership blogs to news, videos, case studies, tutorials
              and more. Take a

              look and join the conversation now. http://goparallel.sourceforge.net

              _______________________________________________

              jgrapht-users mailing list

              jgr...@li...

              https://lists.sourceforge.net/lists/listinfo/jgrapht-users

            
            

          
        
        

      
    
    

  


------------------------------------------------------------------------------
Dive into the World of Parallel Programming! The Go Parallel Website,
sponsored by Intel and developed in partnership with Slashdot Media, is your
hub for all things parallel software development, from weekly thought
leadership blogs to news, videos, case studies, tutorials and more. Take a
look and join the conversation now. http://goparallel.sourceforge.net
_______________________________________________
jgrapht-users mailing list
jgr...@li...
https://lists.sourceforge.net/lists/listinfo/jgrapht-users 		 	   		  

Re: [jgrapht-users] Mixed graphs

[Dimitris M. <dma...@cs...>]

I 'm entirely sure that the formulation of your problem requires that 
both directed and undirected edges have to exist in the same graph. 
However, sometimes, whenever there is such a requirement, it is 
advisable to go back to the problem and consider whether its model 
really requires both kinds of edges.

If, after reconsidering the problem, it is still absolutely necessary to 
have both kind of edges, consider whether the operations you perform on 
the graph require both kinds of edges. If they do, you could built two 
different graphs (1 directed, 1 undirected) with the same set of nodes, 
but a different set of edges and adapt your operations to check both 
graphs.

Hope that helps a bit.



On 08/01/2015 01:41 μμ, Matyas Krutsky wrote:
> Thank you for your response, but unfortunately this is not applicable 
> for me since I have to distinguish between cases where there are 
> actually two directed edges with opposite direction between two nodes 
> and where there is an undirected edge. I would have to keep track of 
> undirected edges somewhere and treat both directed edges which forms 
> the undirected edge as one when changing some property or removing the 
> edge. This seems more difficult and error-prone then creating a sort 
> of "semidirected view" over undirected graph as I suggested...
>
> 2015-01-08 12:26 GMT+01:00 Dimitris Mavroeidis <dma...@cs... 
> <mailto:dma...@cs...>>:
>
>     This is a more general answer and applies to any graph
>     implementation. It is often used in situations such as the one you
>     describe.
>
>     You can use a directed graph and simply represent any undirected
>     edge with two directed edges. So, if you have an undirected edge
>     between node A and node B, you would create an edge from node A to
>     node B and another from node B to node A.
>
>     If you think of it, an undirected graph is a generalization of a
>     directed graph containing both directions between nodes.
>
>     Dimitris
>
>     On 08/01/2015 11:50 πμ, krutor wrote:
>
>         Hi, I'm considering using JGraphT as general graphstore in my
>         project, but I
>         need to represent graph as Mixed graph
>         (http://mathworld.wolfram.com/MixedGraph.html) - using
>         directed and
>         undirected edges together in  one graph. Is there any way to
>         simulate this
>         behaviour in JGraphT?
>
>         The best I came up with yet, is to hide JGraphT behind my own
>         interface, use
>         custom edges with DIRECTED flag and undirected graph
>         implementation
>         overriding methods behavior where needed. When using
>         algorithms, it is
>         usually ok for me that graph is treated like undirected, so I
>         will just use
>         them with the underlying undirected graph...
>
>         Cleaner implementation may be implementing my own
>         AbstractBaseGraph.Specifics, but that is impossible to do
>         since Specifics
>         class is private. Is there any special reason for it to be
>         private?
>
>         Is there any better way to do it? Am I missing something
>         important?
>
>         Thanks for response
>
>
>
>
>         --
>         View this message in context:
>         http://jgrapht-users.107614.n3.nabble.com/Mixed-graphs-tp4024952.html
>         Sent from the jgrapht-users mailing list archive at Nabble.com.
>
>         ------------------------------------------------------------------------------
>         Dive into the World of Parallel Programming! The Go Parallel
>         Website,
>         sponsored by Intel and developed in partnership with Slashdot
>         Media, is your
>         hub for all things parallel software development, from weekly
>         thought
>         leadership blogs to news, videos, case studies, tutorials and
>         more. Take a
>         look and join the conversation now.
>         http://goparallel.sourceforge.net
>         _______________________________________________
>         jgrapht-users mailing list
>         jgr...@li...
>         <mailto:jgr...@li...>
>         https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>

Re: [jgrapht-users] Mixed graphs

[krutor <mat...@gm...>]

Thanks for your suggestion, GraphUnion (or simmilar class) of one directed
graph and one undirected graph surely looks promissing. The only problem I
see is that the resulting union would have to act like a Directed graph, so
it could be a bit tricky to fake this behaviour properly with undirected
edges...

2015-01-08 21:55 GMT+01:00 H.N. de Ridder [via jgrapht-users] <
ml-...@n3...>:

> On Thu, Jan 08, 2015 at 12:41:41PM +0100, Matyas Krutsky wrote:
>
> Maybe it is possible to use a GraphUnion of a directed and an undirected
> graph?
>
> > Thank you for your response, but unfortunately this is not applicable
> for
> > me since I have to distinguish between cases where there are actually
> two
> > directed edges with opposite direction between two nodes and where there
> is
> > an undirected edge. I would have to keep track of undirected edges
> > somewhere and treat both directed edges which forms the undirected edge
> as
> > one when changing some property or removing the edge. This seems more
> > difficult and error-prone then creating a sort of "semidirected view"
> over
> > undirected graph as I suggested...
> >
> > 2015-01-08 12:26 GMT+01:00 Dimitris Mavroeidis <[hidden email]
> <http:///user/SendEmail.jtp?type=node&node=4024956&i=0>>:
> >
> > > This is a more general answer and applies to any graph implementation.
> It
> > > is often used in situations such as the one you describe.
> > >
> > > You can use a directed graph and simply represent any undirected edge
> with
> > > two directed edges. So, if you have an undirected edge between node A
> and
> > > node B, you would create an edge from node A to node B and another
> from
> > > node B to node A.
> > >
> > > If you think of it, an undirected graph is a generalization of a
> directed
> > > graph containing both directions between nodes.
> > >
> > > Dimitris
> > >
> > > On 08/01/2015 11:50 πμ, krutor wrote:
> > >
> > >> Hi, I'm considering using JGraphT as general graphstore in my
> project,
> > >> but I
> > >> need to represent graph as Mixed graph
> > >> (http://mathworld.wolfram.com/MixedGraph.html) - using directed and
> > >> undirected edges together in  one graph. Is there any way to simulate
> this
> > >> behaviour in JGraphT?
> > >>
> > >> The best I came up with yet, is to hide JGraphT behind my own
> interface,
> > >> use
> > >> custom edges with DIRECTED flag and undirected graph implementation
> > >> overriding methods behavior where needed. When using algorithms, it
> is
> > >> usually ok for me that graph is treated like undirected, so I will
> just
> > >> use
> > >> them with the underlying undirected graph...
> > >>
> > >> Cleaner implementation may be implementing my own
> > >> AbstractBaseGraph.Specifics, but that is impossible to do since
> Specifics
> > >> class is private. Is there any special reason for it to be private?
> > >>
> > >> Is there any better way to do it? Am I missing something important?
> > >>
> > >> Thanks for response
> > >>
> > >>
> > >>
> > >>
> > >> --
> > >> View this message in context: http://jgrapht-users.107614.
> > >> n3.nabble.com/Mixed-graphs-tp4024952.html
> > >> Sent from the jgrapht-users mailing list archive at Nabble.com.
> > >>
> > >> ------------------------------------------------------------
> > >> ------------------
> > >> Dive into the World of Parallel Programming! The Go Parallel Website,
> > >> sponsored by Intel and developed in partnership with Slashdot Media,
> is
> > >> your
> > >> hub for all things parallel software development, from weekly thought
> > >> leadership blogs to news, videos, case studies, tutorials and more.
> Take a
> > >> look and join the conversation now. http://goparallel.sourceforge.net
> > >> _______________________________________________
> > >> jgrapht-users mailing list
> > >> [hidden email]
> <http:///user/SendEmail.jtp?type=node&node=4024956&i=1>
> > >> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> > >>
> > >
> > >
>
> >
> ------------------------------------------------------------------------------
>
> > Dive into the World of Parallel Programming! The Go Parallel Website,
> > sponsored by Intel and developed in partnership with Slashdot Media, is
> your
> > hub for all things parallel software development, from weekly thought
> > leadership blogs to news, videos, case studies, tutorials and more. Take
> a
> > look and join the conversation now. http://goparallel.sourceforge.net
>
> > _______________________________________________
> > jgrapht-users mailing list
> > [hidden email] <http:///user/SendEmail.jtp?type=node&node=4024956&i=2>
> > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
> --
> Information System on Graph Classes and their Inclusions (ISGCI)
> http://www.graphclasses.org
>
> ------------------------------------------------------------------------------
>
> Dive into the World of Parallel Programming! The Go Parallel Website,
> sponsored by Intel and developed in partnership with Slashdot Media, is
> your
> hub for all things parallel software development, from weekly thought
> leadership blogs to news, videos, case studies, tutorials and more. Take a
> look and join the conversation now. http://goparallel.sourceforge.net
> _______________________________________________
> jgrapht-users mailing list
> [hidden email] <http:///user/SendEmail.jtp?type=node&node=4024956&i=3>
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
> ------------------------------
>  If you reply to this email, your message will be added to the discussion
> below:
>
> http://jgrapht-users.107614.n3.nabble.com/Mixed-graphs-tp4024952p4024956.html
>  To unsubscribe from Mixed graphs, click here
> <http://jgrapht-users.107614.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=4024952&code=bWF0eWFzLmtydXRza3lAZ21haWwuY29tfDQwMjQ5NTJ8MTE3ODc3Njc1NQ==>
> .
> NAML
> <http://jgrapht-users.107614.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
>




--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Mixed-graphs-tp4024952p4024957.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Mixed graphs

[H.N. de R. <hnr...@gr...>]

On Thu, Jan 08, 2015 at 12:41:41PM +0100, Matyas Krutsky wrote:

Maybe it is possible to use a GraphUnion of a directed and an undirected graph?

> Thank you for your response, but unfortunately this is not applicable for
> me since I have to distinguish between cases where there are actually two
> directed edges with opposite direction between two nodes and where there is
> an undirected edge. I would have to keep track of undirected edges
> somewhere and treat both directed edges which forms the undirected edge as
> one when changing some property or removing the edge. This seems more
> difficult and error-prone then creating a sort of "semidirected view" over
> undirected graph as I suggested...
> 
> 2015-01-08 12:26 GMT+01:00 Dimitris Mavroeidis <dma...@cs...>:
> 
> > This is a more general answer and applies to any graph implementation. It
> > is often used in situations such as the one you describe.
> >
> > You can use a directed graph and simply represent any undirected edge with
> > two directed edges. So, if you have an undirected edge between node A and
> > node B, you would create an edge from node A to node B and another from
> > node B to node A.
> >
> > If you think of it, an undirected graph is a generalization of a directed
> > graph containing both directions between nodes.
> >
> > Dimitris
> >
> > On 08/01/2015 11:50 πμ, krutor wrote:
> >
> >> Hi, I'm considering using JGraphT as general graphstore in my project,
> >> but I
> >> need to represent graph as Mixed graph
> >> (http://mathworld.wolfram.com/MixedGraph.html) - using directed and
> >> undirected edges together in  one graph. Is there any way to simulate this
> >> behaviour in JGraphT?
> >>
> >> The best I came up with yet, is to hide JGraphT behind my own interface,
> >> use
> >> custom edges with DIRECTED flag and undirected graph implementation
> >> overriding methods behavior where needed. When using algorithms, it is
> >> usually ok for me that graph is treated like undirected, so I will just
> >> use
> >> them with the underlying undirected graph...
> >>
> >> Cleaner implementation may be implementing my own
> >> AbstractBaseGraph.Specifics, but that is impossible to do since Specifics
> >> class is private. Is there any special reason for it to be private?
> >>
> >> Is there any better way to do it? Am I missing something important?
> >>
> >> Thanks for response
> >>
> >>
> >>
> >>
> >> --
> >> View this message in context: http://jgrapht-users.107614.
> >> n3.nabble.com/Mixed-graphs-tp4024952.html
> >> Sent from the jgrapht-users mailing list archive at Nabble.com.
> >>
> >> ------------------------------------------------------------
> >> ------------------
> >> Dive into the World of Parallel Programming! The Go Parallel Website,
> >> sponsored by Intel and developed in partnership with Slashdot Media, is
> >> your
> >> hub for all things parallel software development, from weekly thought
> >> leadership blogs to news, videos, case studies, tutorials and more. Take a
> >> look and join the conversation now. http://goparallel.sourceforge.net
> >> _______________________________________________
> >> jgrapht-users mailing list
> >> jgr...@li...
> >> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >>
> >
> >

> ------------------------------------------------------------------------------
> Dive into the World of Parallel Programming! The Go Parallel Website,
> sponsored by Intel and developed in partnership with Slashdot Media, is your
> hub for all things parallel software development, from weekly thought
> leadership blogs to news, videos, case studies, tutorials and more. Take a
> look and join the conversation now. http://goparallel.sourceforge.net

> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users


-- 
Information System on Graph Classes and their Inclusions (ISGCI)
http://www.graphclasses.org

Re: [jgrapht-users] Mixed graphs

[Luc H. <luc...@in...>]

Having 2 directed edge objects representing the same single undirected edge implies that the data associated to the edge is duplicated (for example its weight). Doing this then imposes to make sure that such duplication is always consistent!

--
Luc Hogie
COMRED Research Unit (I3S(CNRS-UNS) INRIA)
I3S Laboratory, University of Nice Sophia Antipolis

http://www-sop.inria.fr/members/Luc.Hogie/
luc...@cn...
+33 4 89 73 24 25 (office)
+33 6 80 91 40 71 (mobile)


----- Mail original -----
> De: "Dimitris Mavroeidis" <dma...@cs...>
> À: "krutor" <mat...@gm...>, jgr...@li...
> Envoyé: Jeudi 8 Janvier 2015 12:26:50
> Objet: Re: [jgrapht-users] Mixed graphs
> 
> This is a more general answer and applies to any graph implementation.
> It is often used in situations such as the one you describe.
> 
> You can use a directed graph and simply represent any undirected edge
> with two directed edges. So, if you have an undirected edge between node
> A and node B, you would create an edge from node A to node B and another
> from node B to node A.
> 
> If you think of it, an undirected graph is a generalization of a
> directed graph containing both directions between nodes.
> 
> Dimitris
> 
> On 08/01/2015 11:50 πμ, krutor wrote:
> > Hi, I'm considering using JGraphT as general graphstore in my project, but
> > I
> > need to represent graph as Mixed graph
> > (http://mathworld.wolfram.com/MixedGraph.html) - using directed and
> > undirected edges together in  one graph. Is there any way to simulate this
> > behaviour in JGraphT?
> >
> > The best I came up with yet, is to hide JGraphT behind my own interface,
> > use
> > custom edges with DIRECTED flag and undirected graph implementation
> > overriding methods behavior where needed. When using algorithms, it is
> > usually ok for me that graph is treated like undirected, so I will just use
> > them with the underlying undirected graph...
> >
> > Cleaner implementation may be implementing my own
> > AbstractBaseGraph.Specifics, but that is impossible to do since Specifics
> > class is private. Is there any special reason for it to be private?
> >
> > Is there any better way to do it? Am I missing something important?
> >
> > Thanks for response
> >
> >
> >
> >
> > --
> > View this message in context:
> > http://jgrapht-users.107614.n3.nabble.com/Mixed-graphs-tp4024952.html
> > Sent from the jgrapht-users mailing list archive at Nabble.com.
> >
> > ------------------------------------------------------------------------------
> > Dive into the World of Parallel Programming! The Go Parallel Website,
> > sponsored by Intel and developed in partnership with Slashdot Media, is
> > your
> > hub for all things parallel software development, from weekly thought
> > leadership blogs to news, videos, case studies, tutorials and more. Take a
> > look and join the conversation now. http://goparallel.sourceforge.net
> > _______________________________________________
> > jgrapht-users mailing list
> > jgr...@li...
> > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> 
> 
> ------------------------------------------------------------------------------
> Dive into the World of Parallel Programming! The Go Parallel Website,
> sponsored by Intel and developed in partnership with Slashdot Media, is your
> hub for all things parallel software development, from weekly thought
> leadership blogs to news, videos, case studies, tutorials and more. Take a
> look and join the conversation now. http://goparallel.sourceforge.net
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] Mixed graphs

[Dimitris M. <dma...@cs...>]

This is a more general answer and applies to any graph implementation. 
It is often used in situations such as the one you describe.

You can use a directed graph and simply represent any undirected edge 
with two directed edges. So, if you have an undirected edge between node 
A and node B, you would create an edge from node A to node B and another 
from node B to node A.

If you think of it, an undirected graph is a generalization of a 
directed graph containing both directions between nodes.

Dimitris

On 08/01/2015 11:50 πμ, krutor wrote:
> Hi, I'm considering using JGraphT as general graphstore in my project, but I
> need to represent graph as Mixed graph
> (http://mathworld.wolfram.com/MixedGraph.html) - using directed and
> undirected edges together in  one graph. Is there any way to simulate this
> behaviour in JGraphT?
>
> The best I came up with yet, is to hide JGraphT behind my own interface, use
> custom edges with DIRECTED flag and undirected graph implementation
> overriding methods behavior where needed. When using algorithms, it is
> usually ok for me that graph is treated like undirected, so I will just use
> them with the underlying undirected graph...
>
> Cleaner implementation may be implementing my own
> AbstractBaseGraph.Specifics, but that is impossible to do since Specifics
> class is private. Is there any special reason for it to be private?
>
> Is there any better way to do it? Am I missing something important?
>
> Thanks for response
>
>
>
>
> --
> View this message in context: http://jgrapht-users.107614.n3.nabble.com/Mixed-graphs-tp4024952.html
> Sent from the jgrapht-users mailing list archive at Nabble.com.
>
> ------------------------------------------------------------------------------
> Dive into the World of Parallel Programming! The Go Parallel Website,
> sponsored by Intel and developed in partnership with Slashdot Media, is your
> hub for all things parallel software development, from weekly thought
> leadership blogs to news, videos, case studies, tutorials and more. Take a
> look and join the conversation now. http://goparallel.sourceforge.net
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users

Re: [jgrapht-users] Mixed graphs

[Matyas K. <mat...@gm...>]

Thank you for your response, but unfortunately this is not applicable for
me since I have to distinguish between cases where there are actually two
directed edges with opposite direction between two nodes and where there is
an undirected edge. I would have to keep track of undirected edges
somewhere and treat both directed edges which forms the undirected edge as
one when changing some property or removing the edge. This seems more
difficult and error-prone then creating a sort of "semidirected view" over
undirected graph as I suggested...

2015-01-08 12:26 GMT+01:00 Dimitris Mavroeidis <dma...@cs...>:

> This is a more general answer and applies to any graph implementation. It
> is often used in situations such as the one you describe.
>
> You can use a directed graph and simply represent any undirected edge with
> two directed edges. So, if you have an undirected edge between node A and
> node B, you would create an edge from node A to node B and another from
> node B to node A.
>
> If you think of it, an undirected graph is a generalization of a directed
> graph containing both directions between nodes.
>
> Dimitris
>
> On 08/01/2015 11:50 πμ, krutor wrote:
>
>> Hi, I'm considering using JGraphT as general graphstore in my project,
>> but I
>> need to represent graph as Mixed graph
>> (http://mathworld.wolfram.com/MixedGraph.html) - using directed and
>> undirected edges together in  one graph. Is there any way to simulate this
>> behaviour in JGraphT?
>>
>> The best I came up with yet, is to hide JGraphT behind my own interface,
>> use
>> custom edges with DIRECTED flag and undirected graph implementation
>> overriding methods behavior where needed. When using algorithms, it is
>> usually ok for me that graph is treated like undirected, so I will just
>> use
>> them with the underlying undirected graph...
>>
>> Cleaner implementation may be implementing my own
>> AbstractBaseGraph.Specifics, but that is impossible to do since Specifics
>> class is private. Is there any special reason for it to be private?
>>
>> Is there any better way to do it? Am I missing something important?
>>
>> Thanks for response
>>
>>
>>
>>
>> --
>> View this message in context: http://jgrapht-users.107614.
>> n3.nabble.com/Mixed-graphs-tp4024952.html
>> Sent from the jgrapht-users mailing list archive at Nabble.com.
>>
>> ------------------------------------------------------------
>> ------------------
>> Dive into the World of Parallel Programming! The Go Parallel Website,
>> sponsored by Intel and developed in partnership with Slashdot Media, is
>> your
>> hub for all things parallel software development, from weekly thought
>> leadership blogs to news, videos, case studies, tutorials and more. Take a
>> look and join the conversation now. http://goparallel.sourceforge.net
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>
>

[jgrapht-users] Mixed graphs

[krutor <mat...@gm...>]

Hi, I'm considering using JGraphT as general graphstore in my project, but I
need to represent graph as Mixed graph
(http://mathworld.wolfram.com/MixedGraph.html) - using directed and
undirected edges together in  one graph. Is there any way to simulate this
behaviour in JGraphT?

The best I came up with yet, is to hide JGraphT behind my own interface, use
custom edges with DIRECTED flag and undirected graph implementation
overriding methods behavior where needed. When using algorithms, it is
usually ok for me that graph is treated like undirected, so I will just use
them with the underlying undirected graph...

Cleaner implementation may be implementing my own
AbstractBaseGraph.Specifics, but that is impossible to do since Specifics
class is private. Is there any special reason for it to be private? 

Is there any better way to do it? Am I missing something important?

Thanks for response




--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Mixed-graphs-tp4024952.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Bizarre issue with TopologicalOrderIterator

[Alexander H. <ale...@my...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

The DAG internally uses HashSets/Maps to store vertices and edges,
these cause the non determinism when iterating, so it is nothing you
do :) Basically anything you compute by iterating over items in the
set (or the key in the map) is non deterministic.
The TopolOrderIterator uses these operations to compute the order, so
it is non deterministic.

Alex

On 12/04/2014 03:43 PM, org...@io... wrote:
>> On 2014-12-04T14:02:52 +0100 Alexander Herz
>> <ale...@my...> wrote:
>> 
>> That is java for you, data structures using hashes often use the
>> value of references to compute the hash. Since the pointer values
>> may change every run, the order things are iterated over may
>> change every run (there is no guarantee that the n-th call to
>> malloc in an application always yields the same address). In
>> order to make your application deterministic and debugable you
>> want to use LinkedHash.. data structures. These guarantee
>> deterministic behaviour (in single threaded execution).
> 
> Is this the case with the TopologicalOrderIterator (or the 
> DirectAcyclicGraph)?
> 
> I only use structural equality and hashes derived from values, as 
> opposed to reference equality or Object.hashCode() in my own code.
> 
> M
> 
> ------------------------------------------------------------------------------
>
> 
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
> from Actuate! Instantly Supercharge Your Business Reports and
> Dashboards with Interactivity, Sharing, Native Excel Exports, App
> Integration & more Get technology previously reserved for
> billion-dollar corporations, FREE 
> http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
>
> 
_______________________________________________
> jgrapht-users mailing list jgr...@li... 
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> 

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)

iQEcBAEBAgAGBQJUgIFvAAoJEGSriSINjxXwGh4IAKYZK+/r/MNh7oQrzxQx1a33
jaQSO7TruSUV76T8BUBI4XvpNNSN1i4MFuZwovSBa+uT434uMc9qLPEAnbrxJmEh
bFpeFJaH9T7SkP5YUqG/9sSkvti6nD7uD/PiYSL7jl4xLZB113hP8nTO/X1YO1Hh
IOhWZe49YMQE3HnNvlxq+UsQKxw9g88guNbpb6dFsZY7DXFcVRjAnmV10NwhiphX
EbHB54RvyeDYij5rOTOrz0CKawGcZUcsQKWOK9mWrJjgITivzXNd5pTfVHTLUN+A
sNdHTnW22cCVsFApJ2iBPNM5kdSN9zNctsBn4mm+omi/VRAmhKKI9G7qWLam/pk=
=xlh5
-----END PGP SIGNATURE-----

Re: [jgrapht-users] Bizarre issue with TopologicalOrderIterator

[<org...@io...>]

> On 2014-12-04T14:02:52 +0100
> Alexander Herz <ale...@my...> wrote:
> 
> That is java for you,
> data structures using hashes often use the value of references to
> compute the hash. Since the pointer values may change every run, the
> order things are iterated over may change every run (there is no
> guarantee that the n-th call to malloc in an application always yields
> the same address).
> In order to make your application deterministic and debugable you want
> to use LinkedHash.. data structures. These guarantee deterministic
> behaviour (in single threaded execution).
 
Is this the case with the TopologicalOrderIterator (or the
DirectAcyclicGraph)?
 
I only use structural equality and hashes derived from values, as
opposed to reference equality or Object.hashCode() in my own code.
 
M

Re: [jgrapht-users] Bizarre issue with TopologicalOrderIterator

[Alexander H. <ale...@my...>]

That is java for you,
data structures using hashes often use the value of references to
compute the hash. Since the pointer values may change every run, the
order things are iterated over may change every run (there is no
guarantee that the n-th call to malloc in an application always yields
the same address).
In order to make your application deterministic and debugable you want
to use LinkedHash.. data structures. These guarantee deterministic
behaviour (in single threaded execution).

Alex

On 04.12.2014 13:50, org...@io... wrote:
> On 2014-12-03T22:18:50 -0800
> John Sichi <js...@gm...> wrote:
>
>> I don't see any dependency between Q and N in your code, so why do you
>> think their relative order would be deterministic?
> Hah, I guess that'd be the "question my own sanity" part - I had no idea
> the algorithm even could be nondeterministic. Out of idle curiousity,
> how does this happen? I didn't notice any concurrency or anything along
> those lines.
>
> I see that the lack of dependency between Q and N does allow that
> returned order to make sense! I'll fix the test.
>
> M
>
> ------------------------------------------------------------------------------
> Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
> from Actuate! Instantly Supercharge Your Business Reports and Dashboards
> with Interactivity, Sharing, Native Excel Exports, App Integration & more
> Get technology previously reserved for billion-dollar corporations, FREE
> http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users

Re: [jgrapht-users] Bizarre issue with TopologicalOrderIterator

[<org...@io...>]

On 2014-12-03T22:18:50 -0800
John Sichi <js...@gm...> wrote:

> I don't see any dependency between Q and N in your code, so why do you
> think their relative order would be deterministic?

Hah, I guess that'd be the "question my own sanity" part - I had no idea
the algorithm even could be nondeterministic. Out of idle curiousity,
how does this happen? I didn't notice any concurrency or anything along
those lines.

I see that the lack of dependency between Q and N does allow that
returned order to make sense! I'll fix the test.

M

Re: [jgrapht-users] Bizarre issue with TopologicalOrderIterator

[John S. <js...@gm...>]

I don't see any dependency between Q and N in your code, so why do you
think their relative order would be deterministic?
On Dec 3, 2014 2:10 PM, <org...@io...> wrote:

> Hi.
>
> I've been using jgrapht for over a year now to handle various tasks in
> the implementation of a compiler. Today, I've started having an issue
> that's
> causing me to question my own sanity.
>
> I use jgrapht to handle the graph of dependencies between terms, types,
> and modules in a shading language I've developed:
>
>   http://mvn.io7m.com/io7m-jparasol
>
> When attempting to run the test suite today (despite the code not having
> been changed since the last commit on 2014-11-15), I suddenly find that
> there's a test failing.
>
> Specifically, I use jgrapht to handle module dependencies. The language
> allows the programmer to define modules/terms/types in any order, but
> the target language (GLSL) requires things to be declared in the order
> of their dependencies (like C/C++). So, using a directed acyclic graph
> to detect circular imports, I then sort modules topologically in
> preparation for emitting GLSL declarations. I actually use the reverse
> of the topological order for declarations, but that makes no difference
> here.
>
> So, for example:
>
> --8<--
>
> module N is
>   import x.y.M;
> end;
>
> module M is
>
> end;
>
> module Q is
>   import x.y.P;
> end;
>
> module P is
>   import x.y.M;
> end;
>
> --8<--
>
> The expected topological order for the above is something like:
>
>   [Q, N, P, M]
>
>   M has no dependencies, so it should probably be declared first.
>   Because Q depends on P, it must be declared after P.
>   Because P depends on M, it must be declared after M.
>   Because N depends on M, it must be declared after M.
>   P and N could be declared in either order, obviously.
>
> Reversing this gives me the order that I'd need to use for declarations
> in the target language.
>
> However, I'm suddenly getting the order [N, Q, P, M] from the
> test suite, which doesn't really make sense whatever way I try to look
> at it. The code that handles imports is pretty simple, and I've
> extracted it (and the test case) to this easy example:
>
> --8<--
> package com.io7m.graphtbug;
>
> import java.util.ArrayList;
> import java.util.List;
>
> import org.jgrapht.experimental.dag.DirectedAcyclicGraph;
> import
> org.jgrapht.experimental.dag.DirectedAcyclicGraph.CycleFoundException;
> import org.jgrapht.traverse.TopologicalOrderIterator;
> import org.junit.Assert;
> import org.junit.Test;
>
> public final class JGraphTBugTest
> {
>   static final class Import
>   {
>     private final ModulePath importer;
>     private final ModulePath target;
>
>     public Import(
>       final ModulePath in_importer,
>       final ModulePath in_target)
>     {
>       this.importer = in_importer;
>       this.target = in_target;
>     }
>
>     @Override public int hashCode()
>     {
>       final int prime = 31;
>       int result = 1;
>       result = (prime * result) + this.importer.hashCode();
>       result = (prime * result) + this.target.hashCode();
>       return result;
>     }
>
>     @Override public boolean equals(
>       final Object obj)
>     {
>       if (this == obj) {
>         return true;
>       }
>       if (obj == null) {
>         return false;
>       }
>       if (this.getClass() != obj.getClass()) {
>         return false;
>       }
>       final Import other = (Import) obj;
>       if (!this.importer.equals(other.importer)) {
>         return false;
>       }
>       if (!this.target.equals(other.target)) {
>         return false;
>       }
>       return true;
>     }
>
>     @Override public String toString()
>     {
>       final StringBuilder builder = new StringBuilder();
>       builder.append("[Import ");
>       builder.append(this.importer);
>       builder.append(" → ");
>       builder.append(this.target);
>       builder.append("]");
>       return builder.toString();
>     }
>
>   }
>
>   static final class ModulePath
>   {
>     private final String name;
>
>     ModulePath(
>       final String in_name)
>     {
>       this.name = in_name;
>     }
>
>     @Override public String toString()
>     {
>       final StringBuilder builder = new StringBuilder();
>       builder.append("[");
>       builder.append(this.name);
>       builder.append("]");
>       return builder.toString();
>     }
>
>     @Override public int hashCode()
>     {
>       return this.name.hashCode();
>     }
>
>     @Override public boolean equals(
>       final Object obj)
>     {
>       if (this == obj) {
>         return true;
>       }
>       if (obj == null) {
>         return false;
>       }
>       if (this.getClass() != obj.getClass()) {
>         return false;
>       }
>       final ModulePath other = (ModulePath) obj;
>       return this.name.equals(other.name);
>     }
>   }
>
>   @Test public void testTopology()
>     throws CycleFoundException
>   {
>     final DirectedAcyclicGraph<ModulePath, Import> g =
>       new DirectedAcyclicGraph<ModulePath, Import>(Import.class);
>
>     final ModulePath mm = new ModulePath("x.y.M");
>     final ModulePath mn = new ModulePath("x.y.N");
>     final ModulePath mp = new ModulePath("x.y.P");
>     final ModulePath mq = new ModulePath("x.y.Q");
>
>     g.addVertex(mn);
>     g.addVertex(mm);
>     g.addVertex(mp);
>     g.addVertex(mq);
>
>     g.addDagEdge(mn, mm, new Import(mn, mm));
>     g.addDagEdge(mp, mm, new Import(mp, mm));
>     g.addDagEdge(mq, mp, new Import(mq, mp));
>
>     final TopologicalOrderIterator<ModulePath, Import> iter =
>       new TopologicalOrderIterator<ModulePath, Import>(g);
>
>     final List<ModulePath> ordered = new ArrayList<ModulePath>();
>
>     while (iter.hasNext()) {
>       final ModulePath p = iter.next();
>       ordered.add(p);
>     }
>
>     System.out.println(ordered);
>     Assert.assertEquals(mq, ordered.get(0));
>     Assert.assertEquals(mn, ordered.get(1));
>     Assert.assertEquals(mp, ordered.get(2));
>     Assert.assertEquals(mm, ordered.get(3));
>   }
> }
> --8<--
>
> The output is:
>
>   [[x.y.N], [x.y.Q], [x.y.P], [x.y.M]]
>
> Followed by an assertion error (expected Q but got N).
>
> What's utterly bizarre about this whole situation is that nothing has
> changed in the environment from two weeks ago. Same Java version, no
> significant OS
> updates, same jgrapht version, no changes to the code. I even have log
> files showing the test output from unit tests executed on 2014-11-15
> that show the output as:
>
>   [[ModulePathFlat x.y.Q], [ModulePathFlat x.y.N], [ModulePathFlat x.y.P],
> [ModulePathFlat x.y.M]]
>
> I'm using Java 8, but have tested on Java 7 too. I'm using jgrapht-core
> 0.9.0 from Maven Central.
>
> Any ideas would be appreciated.
>
> M
>
>
> ------------------------------------------------------------------------------
> Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
> from Actuate! Instantly Supercharge Your Business Reports and Dashboards
> with Interactivity, Sharing, Native Excel Exports, App Integration & more
> Get technology previously reserved for billion-dollar corporations, FREE
>
> http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] Bizarre issue with TopologicalOrderIterator

[<org...@io...>]

Hi.

I've been using jgrapht for over a year now to handle various tasks in
the implementation of a compiler. Today, I've started having an issue that's
causing me to question my own sanity.

I use jgrapht to handle the graph of dependencies between terms, types,
and modules in a shading language I've developed:

  http://mvn.io7m.com/io7m-jparasol

When attempting to run the test suite today (despite the code not having
been changed since the last commit on 2014-11-15), I suddenly find that
there's a test failing.

Specifically, I use jgrapht to handle module dependencies. The language
allows the programmer to define modules/terms/types in any order, but
the target language (GLSL) requires things to be declared in the order
of their dependencies (like C/C++). So, using a directed acyclic graph
to detect circular imports, I then sort modules topologically in
preparation for emitting GLSL declarations. I actually use the reverse
of the topological order for declarations, but that makes no difference
here.

So, for example:

--8<--

module N is
  import x.y.M;
end;

module M is

end;

module Q is
  import x.y.P;
end;

module P is
  import x.y.M;
end;

--8<--

The expected topological order for the above is something like:

  [Q, N, P, M]

  M has no dependencies, so it should probably be declared first.
  Because Q depends on P, it must be declared after P. 
  Because P depends on M, it must be declared after M.
  Because N depends on M, it must be declared after M.
  P and N could be declared in either order, obviously.

Reversing this gives me the order that I'd need to use for declarations
in the target language.

However, I'm suddenly getting the order [N, Q, P, M] from the
test suite, which doesn't really make sense whatever way I try to look
at it. The code that handles imports is pretty simple, and I've
extracted it (and the test case) to this easy example:

--8<--
package com.io7m.graphtbug;

import java.util.ArrayList;
import java.util.List;

import org.jgrapht.experimental.dag.DirectedAcyclicGraph;
import org.jgrapht.experimental.dag.DirectedAcyclicGraph.CycleFoundException;
import org.jgrapht.traverse.TopologicalOrderIterator;
import org.junit.Assert;
import org.junit.Test;

public final class JGraphTBugTest
{
  static final class Import
  {
    private final ModulePath importer;
    private final ModulePath target;

    public Import(
      final ModulePath in_importer,
      final ModulePath in_target)
    {
      this.importer = in_importer;
      this.target = in_target;
    }

    @Override public int hashCode()
    {
      final int prime = 31;
      int result = 1;
      result = (prime * result) + this.importer.hashCode();
      result = (prime * result) + this.target.hashCode();
      return result;
    }

    @Override public boolean equals(
      final Object obj)
    {
      if (this == obj) {
        return true;
      }
      if (obj == null) {
        return false;
      }
      if (this.getClass() != obj.getClass()) {
        return false;
      }
      final Import other = (Import) obj;
      if (!this.importer.equals(other.importer)) {
        return false;
      }
      if (!this.target.equals(other.target)) {
        return false;
      }
      return true;
    }

    @Override public String toString()
    {
      final StringBuilder builder = new StringBuilder();
      builder.append("[Import ");
      builder.append(this.importer);
      builder.append(" → ");
      builder.append(this.target);
      builder.append("]");
      return builder.toString();
    }

  }

  static final class ModulePath
  {
    private final String name;

    ModulePath(
      final String in_name)
    {
      this.name = in_name;
    }

    @Override public String toString()
    {
      final StringBuilder builder = new StringBuilder();
      builder.append("[");
      builder.append(this.name);
      builder.append("]");
      return builder.toString();
    }

    @Override public int hashCode()
    {
      return this.name.hashCode();
    }

    @Override public boolean equals(
      final Object obj)
    {
      if (this == obj) {
        return true;
      }
      if (obj == null) {
        return false;
      }
      if (this.getClass() != obj.getClass()) {
        return false;
      }
      final ModulePath other = (ModulePath) obj;
      return this.name.equals(other.name);
    }
  }

  @Test public void testTopology()
    throws CycleFoundException
  {
    final DirectedAcyclicGraph<ModulePath, Import> g =
      new DirectedAcyclicGraph<ModulePath, Import>(Import.class);

    final ModulePath mm = new ModulePath("x.y.M");
    final ModulePath mn = new ModulePath("x.y.N");
    final ModulePath mp = new ModulePath("x.y.P");
    final ModulePath mq = new ModulePath("x.y.Q");

    g.addVertex(mn);
    g.addVertex(mm);
    g.addVertex(mp);
    g.addVertex(mq);

    g.addDagEdge(mn, mm, new Import(mn, mm));
    g.addDagEdge(mp, mm, new Import(mp, mm));
    g.addDagEdge(mq, mp, new Import(mq, mp));

    final TopologicalOrderIterator<ModulePath, Import> iter =
      new TopologicalOrderIterator<ModulePath, Import>(g);

    final List<ModulePath> ordered = new ArrayList<ModulePath>();

    while (iter.hasNext()) {
      final ModulePath p = iter.next();
      ordered.add(p);
    }

    System.out.println(ordered);
    Assert.assertEquals(mq, ordered.get(0));
    Assert.assertEquals(mn, ordered.get(1));
    Assert.assertEquals(mp, ordered.get(2));
    Assert.assertEquals(mm, ordered.get(3));
  }
}
--8<--

The output is:

  [[x.y.N], [x.y.Q], [x.y.P], [x.y.M]]
  
Followed by an assertion error (expected Q but got N).

What's utterly bizarre about this whole situation is that nothing has
changed in the environment from two weeks ago. Same Java version, no significant OS
updates, same jgrapht version, no changes to the code. I even have log
files showing the test output from unit tests executed on 2014-11-15
that show the output as:

  [[ModulePathFlat x.y.Q], [ModulePathFlat x.y.N], [ModulePathFlat x.y.P], [ModulePathFlat x.y.M]]

I'm using Java 8, but have tested on Java 7 too. I'm using jgrapht-core 0.9.0 from Maven Central.

Any ideas would be appreciated.

M

Re: [jgrapht-users] On extracting a directedsubgraph containing only elements reachable from a given vertex

[Szabolcs B. <bes...@gm...>]

I'm glad I could help.

Regards,

Szabolcs

2014-11-03 15:26 GMT+01:00 Davide Cavestro <dav...@gm...>:

> I guess *strongly connected
> <http://en.wikipedia.org/wiki/Strongly_connected_component>* means that *every
> vertex is reachable from every other vertex*, but this condition would be
> far too strict for my needs.
> I've managed to obtain the subgraph with:
>
>    1. an in-depth visit to determine the subgraph *vertexSet*
>    2. then filtering the graph *edgeSet* to keep only the ones for which
>    both vertex belongs to the subgraph vertexSet.
>
> Many thanks
> Davide
>
> PS: Follows a working groovy snippet for later reference... just my two
> cents
>
> import org.jgrapht.*
> import org.jgrapht.graph.*
> import org.jgrapht.alg.*
> import org.jgrapht.traverse.*
> import org.jgrapht.experimental.dag.*
>
> @Grab(group='org.jgrapht', module='jgrapht-core', version='0.9.0')
> DirectedGraph graph = new DirectedAcyclicGraph(DefaultEdge)
> graph.addVertex ('A')
> graph.addVertex ('B')
> graph.addVertex ('C')
> graph.addVertex ('D')
> graph.addVertex ('E')
> graph.addVertex ('F')
> graph.addEdge ('A', 'B')
> graph.addEdge ('B', 'C')
> graph.addEdge ('B', 'D')
> graph.addEdge ('D', 'C')
> graph.addEdge ('A', 'E')
> graph.addEdge ('E', 'F')
> graph.addEdge ('F', 'D')
>
> //println "graph: $graph"
>
> Iterator iterator = new DepthFirstIterator (graph, 'B')
> Set vertexSubset = [] as LinkedHashSet
> //determine the vertexset for the subgraph
> while (iterator.hasNext()) {
>     vertexSubset << iterator.next()
> }
> //filter the full graph edgeset to obtain the subgraph one
> Set edgeSubset = graph.edgeSet().findAll {edge->
>     graph.getEdgeSource (edge) in vertexSubset && graph.getEdgeTarget
> (edge) in vertexSubset
> }
> //create the subgraph
> DirectedSubgraph subgraph = new DirectedSubgraph (graph, vertexSubset,
> edgeSubset)
> //println "subgraph: $subgraph"
>
>
>
>
> 2014-11-03 13:31 GMT+01:00 Szabolcs Besenyei <bes...@gm...>:
>
>> Given the problem a little bit more thought I think what you are trying
>> to achieve is the same as determining the strongly connected components
>> <http://en.wikipedia.org/wiki/Strongly_connected_component> of a given
>> directed graph. The strongly connected components of an arbitrary directed
>> graph form a partition into subgraphs that are themselves strongly
>> connected.
>> So the functionality of org.jgrapht.alg.StrongConnectivityInspector<V, E>
>> meets the requirements of your problem.
>>
>>
>> Regards,
>>
>> Szabolcs
>>
>> 2014-11-03 12:58 GMT+01:00 Davide Cavestro <dav...@gm...>:
>>
>>> Thankyou for the quick hint... but It seems that org.jgrapht.alg.ConnectivityInspector#pathExists
>>> ignores edges direction (as  it is based on
>>> org.jgrapht.alg.ConnectivityInspector#connectedSetOf)
>>> Is there any way to determine the set of paths reachable from a given
>>> vertex of a directed graph? This way I could use the results to create a
>>> DirectedSubGraph
>>>
>>> 2014-11-01 1:04 GMT+01:00 Szabolcs Besenyei <bes...@gm...>:
>>>
>>>>
>>>>
>>>> 2014-10-31 18:23 GMT+01:00 Davide Cavestro <dav...@gm...>:
>>>> > I'm trying to figure out a way to extract from a DirectedGraph
>>>> instance a
>>>> > DirectedSubgraph containing only the subset of vertex/edges reachable
>>>> from a
>>>> > given vertex (of the original graph).
>>>> > Any help appreciated.
>>>>
>>>> ​Ta​
>>>> ke a look at org.jgrapht.alg.ConnectivityInspector#pathExists.
>>>>
>>>> --
>>>> Regards,
>>>>
>>>> Szabolcs
>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>>
>>>> _______________________________________________
>>>> jgrapht-users mailing list
>>>> jgr...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>>
>>>>
>>>
>>
>