Re: [jgrapht-users] add edge to directed graph in both directions

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

Hm, I remember seeing that thread. The two solutions proposed were:

1. Create 2 graphs, a directed and an undirected graph, and create a
GraphUnion from these two graphs. This approach has 2 major disadvantages:
-The GraphUnion is read-only, so removing a vertex or edge (which are both
well defined operations in 'mixed' graphs) are not supported
-Several algorithms in JgraphT won't work well. For example, one may be
interested in finding all Strongly Connected Components in the graph (which
again is well-defined for mixed graphs). The StrongConnectivityInspector
class for example in JgraphT expects a DirectedGraph as input, and hence,
will not accept the GraphUnion.

2. To represent an undirected edge e=(i,j) in a directed graph, create 2
edge objects, say e1 and e2, which contain the same information, and add
them to the directed graph:
directedGraph.addEdge(i,j,e1);
directedGraph.addEdge(j,i,e2);
This approach has again 2 major disadvantages:
-e1 and e2 duplicate the same information, thereby causing a lot of memory
overhead
-It may prove very difficult to keep the information in the objects e1 and
e2 synchronized.

So far, neither of these approaches seem desirable. Any remarks on this?

Joris


On Tue, Jun 23, 2015 at 12:52 PM, Szabolcs Besenyei <bes...@gm...>
wrote:

> http://jgrapht-users.107614.n3.nabble.com/Mixed-graphs-td4024952.html
>
> Üdvözlettel,
>
> Besenyei Szabolcs
>
> 2015-06-23 18:30 GMT+02:00 Joris Kinable <de...@gm...>:
>
>> Say I have a list of directed and undirected edges which I would like to
>> represent in the same graph. Every undirected edge (i,j) can be represented
>> in a directed graph by adding two arcs: (i,j) and (j,i). The following code
>> does however *not* achieve this:
>>
>> public  static void main(String[] args){
>>     DirectedGraph<Integer, String> directedGraph=new
>> SimpleDirectedGraph<Integer, String>(String.class);
>>     String s="UndirectedEdge";
>>     directedGraph.addVertex(1);
>>     directedGraph.addVertex(2);
>>     System.out.println(directedGraph.addEdge(1,2,s));
>>     System.out.println(directedGraph.addEdge(2,1,s));
>> }
>>
>> The second addEdge call will return false because edge s is already in
>> the graph. What would be a clean way to resolve this issue?
>>
>> Thanks,
>>
>> Joris
>>
>>
>> ------------------------------------------------------------------------------
>> Monitor 25 network devices or servers for free with OpManager!
>> OpManager is web-based network management software that monitors
>> network devices and physical & virtual servers, alerts via email & sms
>> for fault. Monitor 25 devices for free with no restriction. Download now
>> http://ad.doubleclick.net/ddm/clk/292181274;119417398;o
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>>
>