GraphStream Users

Archives de la liste Aide


Re: Question about the unoriented edges


Chronologique Discussions 
  • From: Antoine Dutot <antoine.dutot AT gmail.com>
  • To: graphstream-users AT litislab.fr
  • Subject: Re: Question about the unoriented edges
  • Date: Thu, 9 Jun 2011 18:25:45 +0200
  • Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; b=ulXl9n0V0n9bdDqokl3dm18PbBD0Pz19mWiQ0whLkTmAqPq1nkqFJJH/cIcn4o5Scp Ij2XB5pfFaEWm+KeYY1qENm0mOqKx1grmaUYmPKv657Kxd5qauMylS5gb5ZEqJPdp8lc xZ+gEuzhZdG7Hdbn1Rq3gEKDroh5zGcqRNpGM=

Hi,

I am not sure to clearly understand the question, so I will try to give a potential answer ;-) Bear with me if this is not what you expect.

First : this is normal functioning. But as said on the tracker, we should probably document this a little more ;-)

When you create an edge, the edge remembers the order of the nodes you given at construction, even if the edge is not directed. When one accesses the nodes of an edge, there must be a way to differentiate them, therefore, GraphStream names the accessors getSourceNode and getTargetNode, or getNode0 and getNode1. The two first accessors are more clear when dealing with directed graphs but getSourceNode can be used interchangeably with getNode0 and the same for getTargetNode and getNode1.

However the accessor getNode0 will always return the same node and getNode1 will do the same, independently of any algorithm returning a list of nodes.

APSP merely returns you paths that reference nodes of the graph, it does not create a copy of these nodes with the getNode0 and getNode1 ordered to follow the path direction.

It you intend to iterate on nodes and not on edges, you can use p.getNodePath().iterator() instead of p.getEdgePath().iterator(). It will naturally give you nodes in order. If you want to obtain the edges between two nodes, the Node interface provides a getEdgeBetween method (or getEdgeToward or getEdgeFrom in the directed case).

I did not understood why you used the apsp.setDirected(true) call since your graph is not directed ?

Hope this helps, if not, do not hesitate to repost !

Antoine

2011/6/9 guilhelm savin <guilhelm.savin AT gmail.com>
From NicolasSys:
--------------------------------

I try to find the shortest path with the algorithm APSP on a simple graph composed by 3 nodes and
2 unorientend edges.

Here is my code :

public class BugEdgeNonOriented {

       static Graph g;

       public static void main(String args[]) {
               new BugEdgeNonOriented();
               shortestPath(g, "A", "C");
       }

       public BugEdgeNonOriented() {
               g = new SingleGraph("test");
               g.setAutoCreate(true);
               g.setStrict(false);
               g.display();

               g.addEdge("AB", "A", "B");
               g.addEdge("BC", "C", "B");
               for (Node node : g) {
                       node.addAttribute("ui.label", node.getId());
               }
       }

       private static void shortestPath(Graph g, String source, String dest) {
               APSP apsp = new APSP();
               apsp.init(g);
               apsp.setDirected(true);
               apsp.compute();
               APSPInfo info = g.getNode(source).getAttribute(APSPInfo.ATTRIBUTE_NAME);
               Path p = info.getShortestPathTo(dest);
               // Print
               System.out.println("Path's lenght : " + p.size());
               System.out.println("Path : " + p);
               Iterator<Edge> ie = p.getEdgePath().iterator();
               while (ie.hasNext()) {
                       Edge e = ie.next();
                       System.out.println(e);
                       System.out.println("Edge's end node : " + e.getNode1());
               }
       }
}
```
And here are the results displayed in the console and the generated graph :

bugedge.png

Is this a normal functioning ? Because it does not allow to display a shortest path’s nodes for example. I can do
it differently (by using a multigraph and insert 2 edges between the 2 nodes) but I didn’t managed to do it this way
and I am simply wondering if that’s normal ?
It’s like if the edges are oriented by the way we construct them or maybe I did not use the option getnode0() and
getnode1 properly but I can't know when to use one or the other since I just want to follow the generated path
I found and display some of its informations.

Nicolas




Archives gérées par MHonArc 2.6.16.

Top of page