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

[Daniels, T. (US) <tro...@ba...>]

For option 2, one solution to both issues is to only associate a single piece of data with each edge, which is a reference to a shared object containing all of the information.  Now updating the information of one automatically updates the other.  The memory overhead is two references plus the additional arc.

The case where it will not work is if there are algorithms that build internal data structures that store information about the arc.  Those algorithms will not know that the two arcs are the same and need their data shared.

Troy

From: Joris Kinable [mailto:de...@gm...]
Sent: Tuesday, June 23, 2015 1:27 PM
To: Szabolcs Besenyei
Cc: jgr...@li...
Subject: Re: [jgrapht-users] add edge to directed graph in both directions

*** WARNING ***
This message originates from outside our organization, either from an external partner or the internet. Consider carefully whether you should click on any links, open any attachments or reply. For additional information about Spearphishing, click here<http://intranet.ent.baesystems.com/howwework/security/spotlights/Pages/SpearphishingTips.aspx>. If you feel the email is suspicious, please follow this process.<http://intranet.ent.baesystems.com/howwework/security/spotlights/Documents/Dealing%20With%20Suspicious%20Emails.pdf>

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...<mailto: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...<mailto: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...<mailto:jgr...@li...>
https://lists.sourceforge.net/lists/listinfo/jgrapht-users