Mixed graphs

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Mixed graphs

krutor
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Mixed graphs

Dimitris Mavroeidis
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]
> 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]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

dmavroeidis.vcf (386 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Mixed graphs

krutor
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]>:
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]
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]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Mixed graphs

Luc Hogie
In reply to this post by Dimitris Mavroeidis
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/
[hidden email]
+33 4 89 73 24 25 (office)
+33 6 80 91 40 71 (mobile)


----- Mail original -----

> De: "Dimitris Mavroeidis" <[hidden email]>
> À: "krutor" <[hidden email]>, [hidden email]
> 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
> > [hidden email]
> > 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]
> 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]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Mixed graphs

H.N. de Ridder
In reply to this post by krutor
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]>:
>
> > 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]
> >> 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]
> 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]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Mixed graphs

krutor
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] <[hidden email]>:
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]>:
>
> > 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]
> >> 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]
> 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]
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.
NAML

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Mixed graphs

Dimitris Mavroeidis
In reply to this post by krutor
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 <[hidden email]>:
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]
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]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

dmavroeidis.vcf (386 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Mixed graphs

Rushang Karia
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: [hidden email]
To: [hidden email]
CC: [hidden email]
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 <[hidden email]>:
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]
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] 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]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Mixed graphs

krutor
This post has NOT been accepted by the mailing list yet.
Thank you all for responding!

In the end I did exactly as Dimitris said and take a few steps back and realized that in most cases I want graph to behave as undirected and there will be probably just a few algorithms where I need truly mixed graph. So I did my own implementation of graph that is backed by WeightedPseudograph with my implementation of Edge which has "directed" flag. This representation should be almost identical as having two graphs but with less memory consumption. As far as algorithms go, I will probably need only the basics like DFS, BFS, shortest path... and it should be fairly simple to implement mixed versions of these algorithms which take into account the "directed" flag on edge (at least I hope). 

Thank you all again for your advice, it's great to see so active community around this library. I considered a few other libraries like JUNG, Grph or Tinkerpop but in the end I liked JGraphT implementation most because it's lightweight, fairly simple and well documented. BTW is there any effort to make 1.0.0 release? I woluld be happy to contribute...

2015-01-09 18:54 GMT+01:00 Rushang Karia [via jgrapht-users] <[hidden email]>:
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: [hidden email]
To: [hidden email]
CC: [hidden email]
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 <[hidden email]>:
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]
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] 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]
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-tp4024952p4024959.html
To unsubscribe from Mixed graphs, click here.
NAML

Loading...