Quantcast

add edge to directed graph in both directions

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

add edge to directed graph in both directions

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

Re: add edge to directed graph in both directions

Szabolcs Besenyei

Üdvözlettel,

Besenyei Szabolcs

2015-06-23 18:30 GMT+02:00 Joris Kinable <[hidden email]>:
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users



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

Re: add edge to directed graph in both directions

Joris Kinable
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 <[hidden email]> wrote:

Üdvözlettel,

Besenyei Szabolcs

2015-06-23 18:30 GMT+02:00 Joris Kinable <[hidden email]>:
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users




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

Re: add edge to directed graph in both directions

Daniels, Troy (US SSA)

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:[hidden email]]
Sent: Tuesday, June 23, 2015 1:27 PM
To: Szabolcs Besenyei
Cc: [hidden email]
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. If you feel the email is suspicious, please follow this process.

 

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 <[hidden email]> wrote:


Üdvözlettel,

Besenyei Szabolcs

 

2015-06-23 18:30 GMT+02:00 Joris Kinable <[hidden email]>:

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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

 

 


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

Re: add edge to directed graph in both directions

Dimitris Mavroeidis
In reply to this post by Joris Kinable
Hi Joris,

I remember that in the last entry on the referred thread (http://jgrapht-users.107614.n3.nabble.com/Mixed-graphs-td4024952.html), krutor said something about creating his/her own implementation to solve this exact problem. It would be awesome if krutor could share the code with everyone by contributing to the project's github repository!

Best,
Dimitris


On 23/06/2015 08:27 μμ, Joris Kinable wrote:
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 <[hidden email]> wrote:

Üdvözlettel,

Besenyei Szabolcs

2015-06-23 18:30 GMT+02:00 Joris Kinable <[hidden email]>:
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users





------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


------------------------------------------------------------------------------
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
[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: add edge to directed graph in both directions

krutor
Hi everyone, I ended up using undirected graph (WeightedPseudograph) with my Edge Implementation that has "directed" flag. I hid this WeightedPseudograph behind my own interface that knows about mixed nature of the graph and modifies graph behaviour for its clients (it also deals with multithreading and other staff...). For example I had to modify computation of In Edges for vertex to account for edges directed flag like this:
public Set getInEdges(Node node) {
    Set inEdges = new HashSet<>();
    try {
        readLock();        
        Set edges = graphImpl.edgesOf(node); // graphImpl = WeightedPseudograph<Node, Edge>
        for (Edge edge : edges) {
              if (!edge.isDirected() || edge.getTarget().equals(node)) {
                inEdges.add(edge);
            }
        }
        return Collections.unmodifiableSet(inEdges);
    } finally {
        readUnlock();
    }
}
However this way you are not able to use JGraphT algorithms for directed graphs - for example DFS algorithm now treats the graph as undirected, so it finds path between target and source node even on directed edge (which is ok in my case)... I chose this implementation only because I need to differentiate between case when there is undirected edge between two nodes and when there is actually two opposite directed edges between them... Otherwise I would use directed graph and represent undirected edge as two opposite directed edges, which is IMHO cleaner solution.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: add edge to directed graph in both directions

H.N. de Ridder
In reply to this post by Joris Kinable
On Tue, Jun 23, 2015 at 01:27:23PM -0400, Joris Kinable wrote:
> 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:
>
> 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
>
> So far, neither of these approaches seem desirable. Any remarks on this?

What is your actual goal? Create a mixed graph without going through the
hassle of implementing a MixedGraph class, or using the same object for two
edges in a graph, as the original post said?

Ernst


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

------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...