jgrapht-users — JGraphT user list.

[jgrapht-users] closeSimpleDirectedGraph() doesn't return

[Yi L. <qi...@gm...>]

Hi all,

I am trying to use JGraphT in my project.

I used SimpleDirectedGraph to store my graph (the graph is dynamically 
generated, and huge). All the vertices and edges are added to the graph, 
it seems fine - no warning to say there is a loop.

Then I tried to get transitive closure on the graph. So I called 
TransitiveClosure.INSTANCE.closeSimpleDirectedGraph(myGraph);
However, the execution got stuck in this method and it didn't return.

I tried to call new CycleDetector<V, E>(myGraph).detectCycles() before 
computing transitive closure, and it returns true.

It seems weird to me now, since SimpleDirectedGraph should prompt a 
warning if there is any loop when an edge is added. There wasn't any 
warning, but CycleDectector reported cycles.

Thus I am not sure what the problem is now. Possible cycles in the 
graph, or I used those APIs in a wrong way, or any known implementation 
problem with JGraphT (with 
CycleDetector/TransitiveClosure/SimpleDirectedGraph)?

I could dump the graph, and check through it. But the graph is huge, I 
would rather not to walk through it unless I have to.
I think I would better ask the question here for some suggestions. Any 
help would be appreciated. Thank you very much.

Regards,
Yi

[jgrapht-users] Represent a city Map with JGRAPHT

[misticini <mis...@ho...>]

Hello,

Im doing a work for my master in informatics engineering.

I need to represent a city with roads with only a direction (unidirectional
edge) and 2 directions (bidirectional edge) with weights on this edges. Its
possible to use only a WeightedGraph for doing this? 

Regards



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Represent-a-city-Map-with-JGRAPHT-tp4024805.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] "graph must contain the start vertex" when running KShortestPaths

[John S. <js...@gm...>]

Guillaume:  thanks for looking into this!

Sebastian:  you're right about the non-simple paths.  Looking at the same
isSimplePath method, it looks like it should be using a do/while construct
instead of a while/do construct.  If I make that change, then with your
test case, I get back only simple paths (which are longer than the
"cheating by running around in circles" non-simple paths).  Guillaume, do
you think I should make this change?  If so do I need to make a
corresponding change in the PathMask constructor?


On Wed, Apr 17, 2013 at 3:49 AM, Sebastian Müller <woo...@gm...>wrote:

>  Hi all,
>
> I can confirm that the exception is now gone. Thanks for the quick fix!
> Just one more thing. The javadoc for KShortestPaths states 'The algorithm
> determines the k shortest simple paths [...]'. According to my
> understanding the paths calculated by KShortestPaths are not simple. See my
> example below.
>
> [code]
> <M042    M013    0.90>    : 0.90
> <M042    M043    0.76>    <M043    M042    0.76>    <M042    M013
> 0.909439166411278>    : 2.43
> <M042    M029    0.87>    <M029    M042    0.96>    <M042    M013
> 0.90>    : 2.74
> <M042    M044    0.92>    <M044    M043    0.76>    <M043    M042
> 0.76>    <M042    M013    0.90>    : 3.36
> <M042    M028    0.91>    <M028    M043    0.81>    <M043    M042
> 0.76>    <M042    M013    0.90>    : 3.39
> [/code]
>
>
> Thanks for the great work with JGraphT, all!
>
> Sebastian
>
>
> Am 17.04.2013 11:52, schrieb gu boulmi:
>
> Hi all,
> I just made a debug thanks to the test provided by Sebastian.
> See attached the correction.
>
> I came to the conclusion that was a mistake in the way to test whether
> there is a loop in a path (i.e. two of the same vertex in the path) in the
> method org.jgrapht.alg.RankingPathElementList#isSimplePath
>
> Actually, the test failed when testing the simple path property of a path
> resulting from adding the edge M004-D007 at the end of path
> M014-D010-D007-M004. Of course the resulting path is not simple (twice
> D007), however it returned true.
> When debugging, it appears that the id of the D007 vertex of the edge
> M004-D007 and the id of the D007 vertex of the path M014-D010-D007-M004
> were not the same, although they represent the same vertex (namely D007).
> The existing implementation wrongly returned true because the ids of D007
> were not the same while it tested the equality with the == method.
>
> I changed it by replacing the == by the equals method and it just works.
> New implementation is now :
>  private boolean isSimplePath(
>         RankingPathElement<V, E> prevPathElement,
>         E edge)
>     {
>         RankingPathElement<V, E> pathElementToTest = prevPathElement;
>         while (pathElementToTest.getPrevEdge() != null) {
>             if (pathElementToTest.getVertex().equals(this.vertex)) {
>                 return false;
>             } else {
>                 pathElementToTest = pathElementToTest.getPrevPathElement();
>             }
>         }
>
>         return true;
>     }
>
> Strange anyway : no guess why a String vertex like D007 would change id
> during the execution of the algorithm.
>
> Best regards,
> Guillaume
>
>   ------------------------------
>  *De :* John Sichi <js...@gm...> <js...@gm...>
> *À :* Osama Elswah <osa...@gm...><osa...@gm...>
> *Cc :* "jgr...@li..."<jgr...@li...>
> <jgr...@li...><jgr...@li...>
> *Envoyé le :* Mardi 16 avril 2013 23h04
> *Objet :* Re: [jgrapht-users] "graph must contain the start vertex" when
> running KShortestPaths
>
>  Before my previous reply, I reproduced Sebastian's problem by running
> his code, which is why I say it's a bug.  His input graph is correctly
> constructed, so there's no reason that assertion should be hit.
>
>
> On Tue, Apr 16, 2013 at 7:48 AM, Osama Elswah <osa...@gm...>wrote:
>
>   I have been using KShortestPath for some time now, and it has been
> doing its purpose. I am not sure it has a bug.
>  This is how I use it
>
> for(V n : network.vertexSet())
>         {
>             KShortestPaths<V, E> k = new KShortestPaths<V, E>(network, n,
> k);
>             for(Demand<V> d : demands.getAllDemands())
>             {
>                 if((d.getSourceNode().equals(n)))
>                 {
>                     demand_paths = k.getPaths(d.getTargetNode());
>                     pathsMap.put(d.getSourceNode(), d.getTargetNode(),
> demand_paths);
>                 }
>             }
>         }
>     }
>
>  What is the output of this line ?
>
> DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>
>  I believe if you debug more there you will find the problem
>
>  good luck
>
>
> On Tue, Apr 16, 2013 at 10:03 AM, John Sichi <js...@gm...> wrote:
>
> Looks like a bug in KShortestPaths.  Internally, the algorithm uses a
> masked version of the original graph, and the mask omits a vertex on which
> the algorithm attempts the connectivity test, leading to the assertion
> failure.  Anyone know the algorithm well enough to submit a fix with
> confidence?
>
>  JVS
>
>
>
> On Mon, Apr 15, 2013 at 1:29 PM, Sebastian Müller <woo...@gm...>wrote:
>
> Hello,
>
> sorry this is such a long mail, but I included a test program, and my
> graph is quite large.
>
> I am using JGraphT to create graphs of my data with great success so far.
> However, now I am trying to calculate the shortest paths between two nodes
> using KShortestPaths, and I only receive the following exception:
>
> [code]
> java.lang.IllegalArgumentException: graph must contain the start vertex
>     at
> org.jgrapht.traverse.CrossComponentIterator.<init>(CrossComponentIterator.java:170)
>     at
> org.jgrapht.traverse.BreadthFirstIterator.<init>(BreadthFirstIterator.java:92)
>     at
> org.jgrapht.alg.ConnectivityInspector.connectedSetOf(ConnectivityInspector.java:142)
>     at
> org.jgrapht.alg.ConnectivityInspector.pathExists(ConnectivityInspector.java:208)
>     at
> org.jgrapht.alg.RankingPathElementList.isGuardVertexDisconnected(RankingPathElementList.java:347)
>     at
> org.jgrapht.alg.RankingPathElementList.isNotValidPath(RankingPathElementList.java:364)
>     at
> org.jgrapht.alg.RankingPathElementList.addPathElements(RankingPathElementList.java:203)
>     at
> org.jgrapht.alg.KShortestPathsIterator.tryToAddNewPaths(KShortestPathsIterator.java:361)
>     at
> org.jgrapht.alg.KShortestPathsIterator.updateOutgoingVertices(KShortestPathsIterator.java:398)
>     at
> org.jgrapht.alg.KShortestPathsIterator.next(KShortestPathsIterator.java:177)
>     at org.jgrapht.alg.KShortestPaths.getPaths(KShortestPaths.java:150)
>     at KShortestPathsMain.main(KShortestPathsMain.java:97)
> [/code]
>
> Note that I am only getting this exception with that one, large graph I
> created from my data. When I create a graph by hand, it does not occur.
> Here is my test program. The graph is attached.
>
> [code]
> import java.io.BufferedReader;
> import java.io.FileNotFoundException;
> import java.io.FileReader;
> import java.io.IOException;
> import java.util.List;
>
> import org.jgrapht.GraphPath;
> import org.jgrapht.alg.KShortestPaths;
> import org.jgrapht.graph.DefaultWeightedEdge;
> import org.jgrapht.graph.SimpleWeightedGraph;
>
> public class KShortestPathsMain {
>
>     public KShortestPathsMain() {}
>
>     public static void main(String[] args) {
>
>         SimpleWeightedGraph<String, DefaultWeightedEdge> graph = new
> SimpleWeightedGraph<>(DefaultWeightedEdge.class);
>
>             FileReader fstream = null;
>             try {
>                 fstream = new FileReader("edges.txt");
>             } catch (FileNotFoundException e1) {
>                 e1.printStackTrace();
>             }
>             BufferedReader in = new BufferedReader(fstream);
>
>             String[] edgeText;
>             DefaultWeightedEdge ed;
>             String line = null;
>             try {
>                 line = in.readLine();
>             } catch (IOException e1) {
>                 // TODO Auto-generated catch block
>                 e1.printStackTrace();
>             }
>             while(line != null) {
>                 edgeText = line.split("\t");
>
>                 graph.addVertex(edgeText[0]);
>                 graph.addVertex(edgeText[1]);
>                 ed = graph.addEdge(edgeText[0], edgeText[1]);
>                 graph.setEdgeWeight(ed, Double.parseDouble(edgeText[2]));
>
>                 try {
>                     line = in.readLine();
>                 } catch (IOException e) {
>                     e.printStackTrace();
>                 }
>             }
>
>             // Close the input stream
>             try {
>                 in.close();
>             } catch (IOException e1) {
>                 e1.printStackTrace();
>             }
>
>         DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>
>         KShortestPaths<String, DefaultWeightedEdge> kPaths = new
> KShortestPaths<String, DefaultWeightedEdge>(
>                 graph, graph.getEdgeSource(src), 5);
>         List<GraphPath<String,DefaultWeightedEdge>> paths = null;
>
>         try {
>             paths = kPaths.getPaths(graph.getEdgeTarget(src));
>             for (GraphPath<String, DefaultWeightedEdge> path : paths) {
>                 for (DefaultWeightedEdge edge : path.getEdgeList()) {
>                     System.out.print("<" + graph.getEdgeSource(edge) + "\t"
>                             + graph.getEdgeTarget(edge) + "\t" + edge +
> ">\t");
>                 }
>                 System.out.println(": " + path.getWeight());
>             }
>         } catch (IllegalArgumentException e) {
>             e.printStackTrace();
>         }
>     }
> }
>
> [/code]
>
> I tried different edges, and directed and undirected graphs. Same result.
> If anyone has a clue what might be going on here, I'd very much appreciate
> help.
>
>
> Sebastian
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!http://www2.precog.com/precogplatform/slashdotnewsletter
>
>
>
> _______________________________________________
> jgrapht-users mailing lis...@li...https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

Re: [jgrapht-users] "graph must contain the start vertex" when running KShortestPaths

[Sebastian M. <woo...@gm...>]

Hi all,

I can confirm that the exception is now gone. Thanks for the quick fix!
Just one more thing. The javadoc for KShortestPaths states 'The 
algorithm determines the k shortest simple paths [...]'. According to my 
understanding the paths calculated by KShortestPaths are not simple. See 
my example below.

[code]
<M042    M013    0.90>    : 0.90
<M042    M043    0.76>    <M043    M042    0.76> <M042    M013    
0.909439166411278>    : 2.43
<M042    M029    0.87>    <M029    M042    0.96> <M042    M013    
0.90>    : 2.74
<M042    M044    0.92>    <M044    M043    0.76> <M043    M042    
0.76>    <M042    M013    0.90>    : 3.36
<M042    M028    0.91>    <M028    M043    0.81> <M043    M042    
0.76>    <M042    M013    0.90>    : 3.39
[/code]


Thanks for the great work with JGraphT, all!

Sebastian


Am 17.04.2013 11:52, schrieb gu boulmi:
> Hi all,
> I just made a debug thanks to the test provided by Sebastian.
> See attached the correction.
>
> I came to the conclusion that was a mistake in the way to test whether 
> there is a loop in a path (i.e. two of the same vertex in the path) in 
> the method org.jgrapht.alg.RankingPathElementList#isSimplePath
>
> Actually, the test failed when testing the simple path property of a 
> path resulting from adding the edge M004-D007 at the end of path 
> M014-D010-D007-M004. Of course the resulting path is not simple (twice 
> D007), however it returned true.
> When debugging, it appears that the id of the D007 vertex of the edge 
> M004-D007 and the id of the D007 vertex of the path 
> M014-D010-D007-M004 were not the same, although they represent the 
> same vertex (namely D007). The existing implementation wrongly 
> returned true because the ids of D007 were not the same while it 
> tested the equality with the ==method.
>
> I changed it by replacing the == by the equals method and it just works.
> New implementation is now :
> private boolean isSimplePath(
>         RankingPathElement<V, E> prevPathElement,
>         E edge)
>     {
>         RankingPathElement<V, E> pathElementToTest = prevPathElement;
> while (pathElementToTest.getPrevEdge() != null) {
> if (pathElementToTest.getVertex().equals(this.vertex)) {
> return false;
>             } else {
>                 pathElementToTest = 
> pathElementToTest.getPrevPathElement();
>             }
>         }
>
> return true;
>     }
>
> Strange anyway : no guess why a String vertex like D007 would change 
> id during the execution of the algorithm.
>
> Best regards,
> Guillaume
>
> ------------------------------------------------------------------------
> *De :* John Sichi <js...@gm...>
> *À :* Osama Elswah <osa...@gm...>
> *Cc :* "jgr...@li..." 
> <jgr...@li...>
> *Envoyé le :* Mardi 16 avril 2013 23h04
> *Objet :* Re: [jgrapht-users] "graph must contain the start vertex" 
> when running KShortestPaths
>
> Before my previous reply, I reproduced Sebastian's problem by running 
> his code, which is why I say it's a bug.  His input graph is correctly 
> constructed, so there's no reason that assertion should be hit.
>
>
> On Tue, Apr 16, 2013 at 7:48 AM, Osama Elswah 
> <osa...@gm... <mailto:osa...@gm...>> wrote:
>
>     I have been using KShortestPath for some time now, and it has been
>     doing its purpose. I am not sure it has a bug.
>     This is how I use it
>
>     for(V n : network.vertexSet())
>             {
>                 KShortestPaths<V, E> k = new KShortestPaths<V,
>     E>(network, n, k);
>                 for(Demand<V> d : demands.getAllDemands())
>                 {
>     if((d.getSourceNode().equals(n)))
>                     {
>                         demand_paths = k.getPaths(d.getTargetNode());
>     pathsMap.put(d.getSourceNode(), d.getTargetNode(), demand_paths);
>                     }
>                 }
>             }
>         }
>
>     What is the output of this line ?
>
>     DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>
>     I believe if you debug more there you will find the problem
>
>     good luck
>
>
>     On Tue, Apr 16, 2013 at 10:03 AM, John Sichi <js...@gm...
>     <mailto:js...@gm...>> wrote:
>
>         Looks like a bug in KShortestPaths.  Internally, the algorithm
>         uses a masked version of the original graph, and the mask
>         omits a vertex on which the algorithm attempts the
>         connectivity test, leading to the assertion failure.  Anyone
>         know the algorithm well enough to submit a fix with confidence?
>
>         JVS
>
>
>
>         On Mon, Apr 15, 2013 at 1:29 PM, Sebastian Müller
>         <woo...@gm... <mailto:woo...@gm...>> wrote:
>
>             Hello,
>
>             sorry this is such a long mail, but I included a test
>             program, and my graph is quite large.
>
>             I am using JGraphT to create graphs of my data with great
>             success so far. However, now I am trying to calculate the
>             shortest paths between two nodes using KShortestPaths, and
>             I only receive the following exception:
>
>             [code]
>             java.lang.IllegalArgumentException: graph must contain the
>             start vertex
>                 at
>             org.jgrapht.traverse.CrossComponentIterator.<init>(CrossComponentIterator.java:170)
>                 at
>             org.jgrapht.traverse.BreadthFirstIterator.<init>(BreadthFirstIterator.java:92)
>                 at
>             org.jgrapht.alg.ConnectivityInspector.connectedSetOf(ConnectivityInspector.java:142)
>                 at
>             org.jgrapht.alg.ConnectivityInspector.pathExists(ConnectivityInspector.java:208)
>                 at
>             org.jgrapht.alg.RankingPathElementList.isGuardVertexDisconnected(RankingPathElementList.java:347)
>                 at
>             org.jgrapht.alg.RankingPathElementList.isNotValidPath(RankingPathElementList.java:364)
>                 at
>             org.jgrapht.alg.RankingPathElementList.addPathElements(RankingPathElementList.java:203)
>                 at
>             org.jgrapht.alg.KShortestPathsIterator.tryToAddNewPaths(KShortestPathsIterator.java:361)
>                 at
>             org.jgrapht.alg.KShortestPathsIterator.updateOutgoingVertices(KShortestPathsIterator.java:398)
>                 at
>             org.jgrapht.alg.KShortestPathsIterator.next(KShortestPathsIterator.java:177)
>                 at
>             org.jgrapht.alg.KShortestPaths.getPaths(KShortestPaths.java:150)
>                 at KShortestPathsMain.main(KShortestPathsMain.java:97)
>             [/code]
>
>             Note that I am only getting this exception with that one,
>             large graph I created from my data. When I create a graph
>             by hand, it does not occur. Here is my test program. The
>             graph is attached.
>
>             [code]
>             import java.io.BufferedReader;
>             import java.io.FileNotFoundException;
>             import java.io.FileReader;
>             import java.io.IOException;
>             import java.util.List;
>
>             import org.jgrapht.GraphPath;
>             import org.jgrapht.alg.KShortestPaths;
>             import org.jgrapht.graph.DefaultWeightedEdge;
>             import org.jgrapht.graph.SimpleWeightedGraph;
>
>             public class KShortestPathsMain {
>
>                 public KShortestPathsMain() {}
>
>                 public static void main(String[] args) {
>
>             SimpleWeightedGraph<String, DefaultWeightedEdge> graph =
>             new SimpleWeightedGraph<>(DefaultWeightedEdge.class);
>
>                         FileReader fstream = null;
>                         try {
>                             fstream = new FileReader("edges.txt");
>                         } catch (FileNotFoundException e1) {
>             e1.printStackTrace();
>                         }
>                         BufferedReader in = new BufferedReader(fstream);
>
>                         String[] edgeText;
>                         DefaultWeightedEdge ed;
>                         String line = null;
>                         try {
>                             line = in.readLine();
>                         } catch (IOException e1) {
>                             // TODO Auto-generated catch block
>             e1.printStackTrace();
>                         }
>                         while(line != null) {
>                             edgeText = line.split("\t");
>
>             graph.addVertex(edgeText[0]);
>             graph.addVertex(edgeText[1]);
>                             ed = graph.addEdge(edgeText[0], edgeText[1]);
>             graph.setEdgeWeight(ed, Double.parseDouble(edgeText[2]));
>
>                             try {
>                                 line = in.readLine();
>                             } catch (IOException e) {
>             e.printStackTrace();
>                             }
>                         }
>
>                         // Close the input stream
>                         try {
>                             in.close();
>                         } catch (IOException e1) {
>             e1.printStackTrace();
>                         }
>
>                     DefaultWeightedEdge src = graph.getEdge("M013",
>             "M014");
>
>                     KShortestPaths<String, DefaultWeightedEdge> kPaths
>             = new KShortestPaths<String, DefaultWeightedEdge>(
>                             graph, graph.getEdgeSource(src), 5);
>             List<GraphPath<String,DefaultWeightedEdge>> paths = null;
>
>                     try {
>                         paths = kPaths.getPaths(graph.getEdgeTarget(src));
>                         for (GraphPath<String, DefaultWeightedEdge>
>             path : paths) {
>                             for (DefaultWeightedEdge edge :
>             path.getEdgeList()) {
>             System.out.print("<" + graph.getEdgeSource(edge) + "\t"
>                                         + graph.getEdgeTarget(edge) +
>             "\t" + edge + ">\t");
>                             }
>             System.out.println(": " + path.getWeight());
>                         }
>                     } catch (IllegalArgumentException e) {
>                         e.printStackTrace();
>                     }
>                 }
>             }
>
>             [/code]
>
>             I tried different edges, and directed and undirected
>             graphs. Same result. If anyone has a clue what might be
>             going on here, I'd very much appreciate help.
>
>
>             Sebastian
>
>             ------------------------------------------------------------------------------
>             Precog is a next-generation analytics platform capable of
>             advanced
>             analytics on semi-structured data. The platform includes
>             APIs for building
>             apps and a phenomenal toolset for data science. Developers
>             can use
>             our toolset for easy data analysis & visualization. Get a
>             free account!
>             http://www2.precog.com/precogplatform/slashdotnewsletter
>             _______________________________________________
>             jgrapht-users mailing list
>             jgr...@li...
>             <mailto:jgr...@li...>
>             https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>         ------------------------------------------------------------------------------
>         Precog is a next-generation analytics platform capable of advanced
>         analytics on semi-structured data. The platform includes APIs
>         for building
>         apps and a phenomenal toolset for data science. Developers can use
>         our toolset for easy data analysis & visualization. Get a free
>         account!
>         http://www2.precog.com/precogplatform/slashdotnewsletter
>         _______________________________________________
>         jgrapht-users mailing list
>         jgr...@li...
>         <mailto:jgr...@li...>
>         https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li... 
> <mailto:jgr...@li...>
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
>
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users

Re: [jgrapht-users] "graph must contain the start vertex" when running KShortestPaths

[John S. <js...@gm...>]

Before my previous reply, I reproduced Sebastian's problem by running his
code, which is why I say it's a bug.  His input graph is correctly
constructed, so there's no reason that assertion should be hit.


On Tue, Apr 16, 2013 at 7:48 AM, Osama Elswah <osa...@gm...>wrote:

> I have been using KShortestPath for some time now, and it has been doing
> its purpose. I am not sure it has a bug.
> This is how I use it
>
> for(V n : network.vertexSet())
>         {
>             KShortestPaths<V, E> k = new KShortestPaths<V, E>(network, n,
> k);
>             for(Demand<V> d : demands.getAllDemands())
>             {
>                 if((d.getSourceNode().equals(n)))
>                 {
>                     demand_paths = k.getPaths(d.getTargetNode());
>                     pathsMap.put(d.getSourceNode(), d.getTargetNode(),
> demand_paths);
>                 }
>             }
>         }
>     }
>
> What is the output of this line ?
>
> DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>
> I believe if you debug more there you will find the problem
>
> good luck
>
>
> On Tue, Apr 16, 2013 at 10:03 AM, John Sichi <js...@gm...> wrote:
>
>> Looks like a bug in KShortestPaths.  Internally, the algorithm uses a
>> masked version of the original graph, and the mask omits a vertex on which
>> the algorithm attempts the connectivity test, leading to the assertion
>> failure.  Anyone know the algorithm well enough to submit a fix with
>> confidence?
>>
>> JVS
>>
>>
>>
>> On Mon, Apr 15, 2013 at 1:29 PM, Sebastian Müller <woo...@gm...>wrote:
>>
>>> Hello,
>>>
>>> sorry this is such a long mail, but I included a test program, and my
>>> graph is quite large.
>>>
>>> I am using JGraphT to create graphs of my data with great success so
>>> far. However, now I am trying to calculate the shortest paths between two
>>> nodes using KShortestPaths, and I only receive the following exception:
>>>
>>> [code]
>>> java.lang.**IllegalArgumentException: graph must contain the start
>>> vertex
>>>     at org.jgrapht.traverse.**CrossComponentIterator.<init>(**
>>> CrossComponentIterator.java:**170)
>>>     at org.jgrapht.traverse.**BreadthFirstIterator.<init>(**
>>> BreadthFirstIterator.java:92)
>>>     at org.jgrapht.alg.**ConnectivityInspector.**connectedSetOf(**
>>> ConnectivityInspector.java:**142)
>>>     at org.jgrapht.alg.**ConnectivityInspector.**pathExists(**
>>> ConnectivityInspector.java:**208)
>>>     at org.jgrapht.alg.**RankingPathElementList.**
>>> isGuardVertexDisconnected(**RankingPathElementList.java:**347)
>>>     at org.jgrapht.alg.**RankingPathElementList.**isNotValidPath(**
>>> RankingPathElementList.java:**364)
>>>     at org.jgrapht.alg.**RankingPathElementList.**addPathElements(**
>>> RankingPathElementList.java:**203)
>>>     at org.jgrapht.alg.**KShortestPathsIterator.**tryToAddNewPaths(**
>>> KShortestPathsIterator.java:**361)
>>>     at org.jgrapht.alg.**KShortestPathsIterator.**
>>> updateOutgoingVertices(**KShortestPathsIterator.java:**398)
>>>     at org.jgrapht.alg.**KShortestPathsIterator.next(**
>>> KShortestPathsIterator.java:**177)
>>>     at org.jgrapht.alg.**KShortestPaths.getPaths(**
>>> KShortestPaths.java:150)
>>>     at KShortestPathsMain.main(**KShortestPathsMain.java:97)
>>> [/code]
>>>
>>> Note that I am only getting this exception with that one, large graph I
>>> created from my data. When I create a graph by hand, it does not occur.
>>> Here is my test program. The graph is attached.
>>>
>>> [code]
>>> import java.io.BufferedReader;
>>> import java.io.FileNotFoundException;
>>> import java.io.FileReader;
>>> import java.io.IOException;
>>> import java.util.List;
>>>
>>> import org.jgrapht.GraphPath;
>>> import org.jgrapht.alg.**KShortestPaths;
>>> import org.jgrapht.graph.**DefaultWeightedEdge;
>>> import org.jgrapht.graph.**SimpleWeightedGraph;
>>>
>>> public class KShortestPathsMain {
>>>
>>>     public KShortestPathsMain() {}
>>>
>>>     public static void main(String[] args) {
>>>
>>>         SimpleWeightedGraph<String, DefaultWeightedEdge> graph = new
>>> SimpleWeightedGraph<>(**DefaultWeightedEdge.class);
>>>
>>>             FileReader fstream = null;
>>>             try {
>>>                 fstream = new FileReader("edges.txt");
>>>             } catch (FileNotFoundException e1) {
>>>                 e1.printStackTrace();
>>>             }
>>>             BufferedReader in = new BufferedReader(fstream);
>>>
>>>             String[] edgeText;
>>>             DefaultWeightedEdge ed;
>>>             String line = null;
>>>             try {
>>>                 line = in.readLine();
>>>             } catch (IOException e1) {
>>>                 // TODO Auto-generated catch block
>>>                 e1.printStackTrace();
>>>             }
>>>             while(line != null) {
>>>                 edgeText = line.split("\t");
>>>
>>>                 graph.addVertex(edgeText[0]);
>>>                 graph.addVertex(edgeText[1]);
>>>                 ed = graph.addEdge(edgeText[0], edgeText[1]);
>>>                 graph.setEdgeWeight(ed, Double.parseDouble(edgeText[2]**
>>> ));
>>>
>>>                 try {
>>>                     line = in.readLine();
>>>                 } catch (IOException e) {
>>>                     e.printStackTrace();
>>>                 }
>>>             }
>>>
>>>             // Close the input stream
>>>             try {
>>>                 in.close();
>>>             } catch (IOException e1) {
>>>                 e1.printStackTrace();
>>>             }
>>>
>>>         DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>>>
>>>         KShortestPaths<String, DefaultWeightedEdge> kPaths = new
>>> KShortestPaths<String, DefaultWeightedEdge>(
>>>                 graph, graph.getEdgeSource(src), 5);
>>>         List<GraphPath<String,**DefaultWeightedEdge>> paths = null;
>>>
>>>         try {
>>>             paths = kPaths.getPaths(graph.**getEdgeTarget(src));
>>>             for (GraphPath<String, DefaultWeightedEdge> path : paths) {
>>>                 for (DefaultWeightedEdge edge : path.getEdgeList()) {
>>>                     System.out.print("<" + graph.getEdgeSource(edge) +
>>> "\t"
>>>                             + graph.getEdgeTarget(edge) + "\t" + edge +
>>> ">\t");
>>>                 }
>>>                 System.out.println(": " + path.getWeight());
>>>             }
>>>         } catch (IllegalArgumentException e) {
>>>             e.printStackTrace();
>>>         }
>>>     }
>>> }
>>>
>>> [/code]
>>>
>>> I tried different edges, and directed and undirected graphs. Same
>>> result. If anyone has a clue what might be going on here, I'd very much
>>> appreciate help.
>>>
>>>
>>> Sebastian
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> Precog is a next-generation analytics platform capable of advanced
>>> analytics on semi-structured data. The platform includes APIs for
>>> building
>>> apps and a phenomenal toolset for data science. Developers can use
>>> our toolset for easy data analysis & visualization. Get a free account!
>>> http://www2.precog.com/precogplatform/slashdotnewsletter
>>> _______________________________________________
>>> jgrapht-users mailing list
>>> jgr...@li...
>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>
>>>
>>
>>
>> ------------------------------------------------------------------------------
>> Precog is a next-generation analytics platform capable of advanced
>> analytics on semi-structured data. The platform includes APIs for building
>> apps and a phenomenal toolset for data science. Developers can use
>> our toolset for easy data analysis & visualization. Get a free account!
>> http://www2.precog.com/precogplatform/slashdotnewsletter
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>>
>

Re: [jgrapht-users] "graph must contain the start vertex" when running KShortestPaths

[Osama E. <osa...@gm...>]

I have been using KShortestPath for some time now, and it has been doing
its purpose. I am not sure it has a bug.
This is how I use it

for(V n : network.vertexSet())
        {
            KShortestPaths<V, E> k = new KShortestPaths<V, E>(network, n,
k);
            for(Demand<V> d : demands.getAllDemands())
            {
                if((d.getSourceNode().equals(n)))
                {
                    demand_paths = k.getPaths(d.getTargetNode());
                    pathsMap.put(d.getSourceNode(), d.getTargetNode(),
demand_paths);
                }
            }
        }
    }

What is the output of this line ?

DefaultWeightedEdge src = graph.getEdge("M013", "M014");

I believe if you debug more there you will find the problem

good luck


On Tue, Apr 16, 2013 at 10:03 AM, John Sichi <js...@gm...> wrote:

> Looks like a bug in KShortestPaths.  Internally, the algorithm uses a
> masked version of the original graph, and the mask omits a vertex on which
> the algorithm attempts the connectivity test, leading to the assertion
> failure.  Anyone know the algorithm well enough to submit a fix with
> confidence?
>
> JVS
>
>
>
> On Mon, Apr 15, 2013 at 1:29 PM, Sebastian Müller <woo...@gm...>wrote:
>
>> Hello,
>>
>> sorry this is such a long mail, but I included a test program, and my
>> graph is quite large.
>>
>> I am using JGraphT to create graphs of my data with great success so far.
>> However, now I am trying to calculate the shortest paths between two nodes
>> using KShortestPaths, and I only receive the following exception:
>>
>> [code]
>> java.lang.**IllegalArgumentException: graph must contain the start vertex
>>     at org.jgrapht.traverse.**CrossComponentIterator.<init>(**
>> CrossComponentIterator.java:**170)
>>     at org.jgrapht.traverse.**BreadthFirstIterator.<init>(**
>> BreadthFirstIterator.java:92)
>>     at org.jgrapht.alg.**ConnectivityInspector.**connectedSetOf(**
>> ConnectivityInspector.java:**142)
>>     at org.jgrapht.alg.**ConnectivityInspector.**pathExists(**
>> ConnectivityInspector.java:**208)
>>     at org.jgrapht.alg.**RankingPathElementList.**
>> isGuardVertexDisconnected(**RankingPathElementList.java:**347)
>>     at org.jgrapht.alg.**RankingPathElementList.**isNotValidPath(**
>> RankingPathElementList.java:**364)
>>     at org.jgrapht.alg.**RankingPathElementList.**addPathElements(**
>> RankingPathElementList.java:**203)
>>     at org.jgrapht.alg.**KShortestPathsIterator.**tryToAddNewPaths(**
>> KShortestPathsIterator.java:**361)
>>     at org.jgrapht.alg.**KShortestPathsIterator.**updateOutgoingVertices(
>> **KShortestPathsIterator.java:**398)
>>     at org.jgrapht.alg.**KShortestPathsIterator.next(**
>> KShortestPathsIterator.java:**177)
>>     at org.jgrapht.alg.**KShortestPaths.getPaths(**
>> KShortestPaths.java:150)
>>     at KShortestPathsMain.main(**KShortestPathsMain.java:97)
>> [/code]
>>
>> Note that I am only getting this exception with that one, large graph I
>> created from my data. When I create a graph by hand, it does not occur.
>> Here is my test program. The graph is attached.
>>
>> [code]
>> import java.io.BufferedReader;
>> import java.io.FileNotFoundException;
>> import java.io.FileReader;
>> import java.io.IOException;
>> import java.util.List;
>>
>> import org.jgrapht.GraphPath;
>> import org.jgrapht.alg.**KShortestPaths;
>> import org.jgrapht.graph.**DefaultWeightedEdge;
>> import org.jgrapht.graph.**SimpleWeightedGraph;
>>
>> public class KShortestPathsMain {
>>
>>     public KShortestPathsMain() {}
>>
>>     public static void main(String[] args) {
>>
>>         SimpleWeightedGraph<String, DefaultWeightedEdge> graph = new
>> SimpleWeightedGraph<>(**DefaultWeightedEdge.class);
>>
>>             FileReader fstream = null;
>>             try {
>>                 fstream = new FileReader("edges.txt");
>>             } catch (FileNotFoundException e1) {
>>                 e1.printStackTrace();
>>             }
>>             BufferedReader in = new BufferedReader(fstream);
>>
>>             String[] edgeText;
>>             DefaultWeightedEdge ed;
>>             String line = null;
>>             try {
>>                 line = in.readLine();
>>             } catch (IOException e1) {
>>                 // TODO Auto-generated catch block
>>                 e1.printStackTrace();
>>             }
>>             while(line != null) {
>>                 edgeText = line.split("\t");
>>
>>                 graph.addVertex(edgeText[0]);
>>                 graph.addVertex(edgeText[1]);
>>                 ed = graph.addEdge(edgeText[0], edgeText[1]);
>>                 graph.setEdgeWeight(ed, Double.parseDouble(edgeText[2]**
>> ));
>>
>>                 try {
>>                     line = in.readLine();
>>                 } catch (IOException e) {
>>                     e.printStackTrace();
>>                 }
>>             }
>>
>>             // Close the input stream
>>             try {
>>                 in.close();
>>             } catch (IOException e1) {
>>                 e1.printStackTrace();
>>             }
>>
>>         DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>>
>>         KShortestPaths<String, DefaultWeightedEdge> kPaths = new
>> KShortestPaths<String, DefaultWeightedEdge>(
>>                 graph, graph.getEdgeSource(src), 5);
>>         List<GraphPath<String,**DefaultWeightedEdge>> paths = null;
>>
>>         try {
>>             paths = kPaths.getPaths(graph.**getEdgeTarget(src));
>>             for (GraphPath<String, DefaultWeightedEdge> path : paths) {
>>                 for (DefaultWeightedEdge edge : path.getEdgeList()) {
>>                     System.out.print("<" + graph.getEdgeSource(edge) +
>> "\t"
>>                             + graph.getEdgeTarget(edge) + "\t" + edge +
>> ">\t");
>>                 }
>>                 System.out.println(": " + path.getWeight());
>>             }
>>         } catch (IllegalArgumentException e) {
>>             e.printStackTrace();
>>         }
>>     }
>> }
>>
>> [/code]
>>
>> I tried different edges, and directed and undirected graphs. Same result.
>> If anyone has a clue what might be going on here, I'd very much appreciate
>> help.
>>
>>
>> Sebastian
>>
>>
>> ------------------------------------------------------------------------------
>> Precog is a next-generation analytics platform capable of advanced
>> analytics on semi-structured data. The platform includes APIs for building
>> apps and a phenomenal toolset for data science. Developers can use
>> our toolset for easy data analysis & visualization. Get a free account!
>> http://www2.precog.com/precogplatform/slashdotnewsletter
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

Re: [jgrapht-users] Spanning Tree - Directed graph

[John S. <js...@gm...>]

I don't think we currently have an MST for directed graphs.


On Sun, Apr 7, 2013 at 2:05 PM, miki <mi...@gm...> wrote:

> Hello.
>
> I would like to ask if it is correct to run KruskalMinimumSpanningTree on
> DirectedWeightedMultigraph. As far as I know Kruskal (in general) only
> works
> on undirected graph. For directed graphs there is Edmond's algorithm.
> Is KruskalMinimumSpanningTree  somehow changed to work on directed graphs ?
> If no, can jgrapht solve spanning tree problem on directed graph ?
>
> Thanks.
>
> Regards,
>
> Milos.
>
>
>
> --
> View this message in context:
> http://jgrapht-users.107614.n3.nabble.com/Spanning-Tree-Directed-graph-tp4024793.html
> Sent from the jgrapht-users mailing list archive at Nabble.com.
>
>
> ------------------------------------------------------------------------------
> Minimize network downtime and maximize team effectiveness.
> Reduce network management and security costs.Learn how to hire
> the most talented Cisco Certified professionals. Visit the
> Employer Resources Portal
> http://www.cisco.com/web/learning/employer_resources/index.html
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] "graph must contain the start vertex" when running KShortestPaths

[John S. <js...@gm...>]

Looks like a bug in KShortestPaths.  Internally, the algorithm uses a
masked version of the original graph, and the mask omits a vertex on which
the algorithm attempts the connectivity test, leading to the assertion
failure.  Anyone know the algorithm well enough to submit a fix with
confidence?

JVS



On Mon, Apr 15, 2013 at 1:29 PM, Sebastian Müller <woo...@gm...>wrote:

> Hello,
>
> sorry this is such a long mail, but I included a test program, and my
> graph is quite large.
>
> I am using JGraphT to create graphs of my data with great success so far.
> However, now I am trying to calculate the shortest paths between two nodes
> using KShortestPaths, and I only receive the following exception:
>
> [code]
> java.lang.**IllegalArgumentException: graph must contain the start vertex
>     at org.jgrapht.traverse.**CrossComponentIterator.<init>(**
> CrossComponentIterator.java:**170)
>     at org.jgrapht.traverse.**BreadthFirstIterator.<init>(**
> BreadthFirstIterator.java:92)
>     at org.jgrapht.alg.**ConnectivityInspector.**connectedSetOf(**
> ConnectivityInspector.java:**142)
>     at org.jgrapht.alg.**ConnectivityInspector.**pathExists(**
> ConnectivityInspector.java:**208)
>     at org.jgrapht.alg.**RankingPathElementList.**
> isGuardVertexDisconnected(**RankingPathElementList.java:**347)
>     at org.jgrapht.alg.**RankingPathElementList.**isNotValidPath(**
> RankingPathElementList.java:**364)
>     at org.jgrapht.alg.**RankingPathElementList.**addPathElements(**
> RankingPathElementList.java:**203)
>     at org.jgrapht.alg.**KShortestPathsIterator.**tryToAddNewPaths(**
> KShortestPathsIterator.java:**361)
>     at org.jgrapht.alg.**KShortestPathsIterator.**updateOutgoingVertices(*
> *KShortestPathsIterator.java:**398)
>     at org.jgrapht.alg.**KShortestPathsIterator.next(**
> KShortestPathsIterator.java:**177)
>     at org.jgrapht.alg.**KShortestPaths.getPaths(**
> KShortestPaths.java:150)
>     at KShortestPathsMain.main(**KShortestPathsMain.java:97)
> [/code]
>
> Note that I am only getting this exception with that one, large graph I
> created from my data. When I create a graph by hand, it does not occur.
> Here is my test program. The graph is attached.
>
> [code]
> import java.io.BufferedReader;
> import java.io.FileNotFoundException;
> import java.io.FileReader;
> import java.io.IOException;
> import java.util.List;
>
> import org.jgrapht.GraphPath;
> import org.jgrapht.alg.**KShortestPaths;
> import org.jgrapht.graph.**DefaultWeightedEdge;
> import org.jgrapht.graph.**SimpleWeightedGraph;
>
> public class KShortestPathsMain {
>
>     public KShortestPathsMain() {}
>
>     public static void main(String[] args) {
>
>         SimpleWeightedGraph<String, DefaultWeightedEdge> graph = new
> SimpleWeightedGraph<>(**DefaultWeightedEdge.class);
>
>             FileReader fstream = null;
>             try {
>                 fstream = new FileReader("edges.txt");
>             } catch (FileNotFoundException e1) {
>                 e1.printStackTrace();
>             }
>             BufferedReader in = new BufferedReader(fstream);
>
>             String[] edgeText;
>             DefaultWeightedEdge ed;
>             String line = null;
>             try {
>                 line = in.readLine();
>             } catch (IOException e1) {
>                 // TODO Auto-generated catch block
>                 e1.printStackTrace();
>             }
>             while(line != null) {
>                 edgeText = line.split("\t");
>
>                 graph.addVertex(edgeText[0]);
>                 graph.addVertex(edgeText[1]);
>                 ed = graph.addEdge(edgeText[0], edgeText[1]);
>                 graph.setEdgeWeight(ed, Double.parseDouble(edgeText[2]**
> ));
>
>                 try {
>                     line = in.readLine();
>                 } catch (IOException e) {
>                     e.printStackTrace();
>                 }
>             }
>
>             // Close the input stream
>             try {
>                 in.close();
>             } catch (IOException e1) {
>                 e1.printStackTrace();
>             }
>
>         DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>
>         KShortestPaths<String, DefaultWeightedEdge> kPaths = new
> KShortestPaths<String, DefaultWeightedEdge>(
>                 graph, graph.getEdgeSource(src), 5);
>         List<GraphPath<String,**DefaultWeightedEdge>> paths = null;
>
>         try {
>             paths = kPaths.getPaths(graph.**getEdgeTarget(src));
>             for (GraphPath<String, DefaultWeightedEdge> path : paths) {
>                 for (DefaultWeightedEdge edge : path.getEdgeList()) {
>                     System.out.print("<" + graph.getEdgeSource(edge) + "\t"
>                             + graph.getEdgeTarget(edge) + "\t" + edge +
> ">\t");
>                 }
>                 System.out.println(": " + path.getWeight());
>             }
>         } catch (IllegalArgumentException e) {
>             e.printStackTrace();
>         }
>     }
> }
>
> [/code]
>
> I tried different edges, and directed and undirected graphs. Same result.
> If anyone has a clue what might be going on here, I'd very much appreciate
> help.
>
>
> Sebastian
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] "graph must contain the start vertex" when running KShortestPaths

[Sebastian M. <woo...@gm...>]

Hello,

sorry this is such a long mail, but I included a test program, and my 
graph is quite large.

I am using JGraphT to create graphs of my data with great success so 
far. However, now I am trying to calculate the shortest paths between 
two nodes using KShortestPaths, and I only receive the following exception:

[code]
java.lang.IllegalArgumentException: graph must contain the start vertex
     at 
org.jgrapht.traverse.CrossComponentIterator.<init>(CrossComponentIterator.java:170)
     at 
org.jgrapht.traverse.BreadthFirstIterator.<init>(BreadthFirstIterator.java:92)
     at 
org.jgrapht.alg.ConnectivityInspector.connectedSetOf(ConnectivityInspector.java:142)
     at 
org.jgrapht.alg.ConnectivityInspector.pathExists(ConnectivityInspector.java:208)
     at 
org.jgrapht.alg.RankingPathElementList.isGuardVertexDisconnected(RankingPathElementList.java:347)
     at 
org.jgrapht.alg.RankingPathElementList.isNotValidPath(RankingPathElementList.java:364)
     at 
org.jgrapht.alg.RankingPathElementList.addPathElements(RankingPathElementList.java:203)
     at 
org.jgrapht.alg.KShortestPathsIterator.tryToAddNewPaths(KShortestPathsIterator.java:361)
     at 
org.jgrapht.alg.KShortestPathsIterator.updateOutgoingVertices(KShortestPathsIterator.java:398)
     at 
org.jgrapht.alg.KShortestPathsIterator.next(KShortestPathsIterator.java:177)
     at org.jgrapht.alg.KShortestPaths.getPaths(KShortestPaths.java:150)
     at KShortestPathsMain.main(KShortestPathsMain.java:97)
[/code]

Note that I am only getting this exception with that one, large graph I 
created from my data. When I create a graph by hand, it does not occur. 
Here is my test program. The graph is attached.

[code]
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.List;

import org.jgrapht.GraphPath;
import org.jgrapht.alg.KShortestPaths;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;

public class KShortestPathsMain {

     public KShortestPathsMain() {}

     public static void main(String[] args) {

         SimpleWeightedGraph<String, DefaultWeightedEdge> graph = new 
SimpleWeightedGraph<>(DefaultWeightedEdge.class);

             FileReader fstream = null;
             try {
                 fstream = new FileReader("edges.txt");
             } catch (FileNotFoundException e1) {
                 e1.printStackTrace();
             }
             BufferedReader in = new BufferedReader(fstream);

             String[] edgeText;
             DefaultWeightedEdge ed;
             String line = null;
             try {
                 line = in.readLine();
             } catch (IOException e1) {
                 // TODO Auto-generated catch block
                 e1.printStackTrace();
             }
             while(line != null) {
                 edgeText = line.split("\t");

                 graph.addVertex(edgeText[0]);
                 graph.addVertex(edgeText[1]);
                 ed = graph.addEdge(edgeText[0], edgeText[1]);
                 graph.setEdgeWeight(ed, Double.parseDouble(edgeText[2]));

                 try {
                     line = in.readLine();
                 } catch (IOException e) {
                     e.printStackTrace();
                 }
             }

             // Close the input stream
             try {
                 in.close();
             } catch (IOException e1) {
                 e1.printStackTrace();
             }

         DefaultWeightedEdge src = graph.getEdge("M013", "M014");

         KShortestPaths<String, DefaultWeightedEdge> kPaths = new 
KShortestPaths<String, DefaultWeightedEdge>(
                 graph, graph.getEdgeSource(src), 5);
         List<GraphPath<String,DefaultWeightedEdge>> paths = null;

         try {
             paths = kPaths.getPaths(graph.getEdgeTarget(src));
             for (GraphPath<String, DefaultWeightedEdge> path : paths) {
                 for (DefaultWeightedEdge edge : path.getEdgeList()) {
                     System.out.print("<" + graph.getEdgeSource(edge) + "\t"
                             + graph.getEdgeTarget(edge) + "\t" + edge + 
">\t");
                 }
                 System.out.println(": " + path.getWeight());
             }
         } catch (IllegalArgumentException e) {
             e.printStackTrace();
         }
     }
}

[/code]

I tried different edges, and directed and undirected graphs. Same 
result. If anyone has a clue what might be going on here, I'd very much 
appreciate help.


Sebastian

[jgrapht-users] Sub-graph isomorphism

[bnastov <bla...@ho...>]

Hi,

I am new to JGraphT. I need an algorithm for sub-graph ismorphism. I
searched in this forum, but all I found are a topics on a simple graph
ispomorphism. 
"The subgraph isomorphism problem asks whether a graph G has a subgraph G′⊂G
that is isomorphmic to a graph P. So basically you have the picture on the
box of a puzzle (G) and want to know where a particular piece (P) fits, if
at all. It is NP-complete because Hamiltonian cycle is a special case."
This problem is solved by Ullman's algorithm (1976) and the VF2 algorithm
(2004).
Are this algorithms implemented? and if so can you propose a simple "how to
use" example?

Thank you,

Blazo



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Sub-graph-isomorphism-tp4024796.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Difference between a directed multigraph and a directed pseudograph

[John S. <js...@gm...>]

I agree; looks like a bug.


On Sun, Apr 7, 2013 at 8:59 PM, H.N. de Ridder <hnr...@gr...>wrote:

> On Fri, Apr 05, 2013 at 02:05:05PM +0200, Adam Gouge wrote:
>
> > What is the difference between a DirectedMultigraph and a
> > DirectedPseudograph? According to the javadoc,
> >
> > * A directed multigraph is a non-simple directed graph
> > * in which loops and multiple edges between any two vertices are
> permitted.
> >
> > * A directed pseudograph is a non-simple directed graph
> > * in which both graph loops and multiple edges are permitted.
> >
> > They both extend AbstractBaseGraph and implement DirectedGraph, and the
> > code consists only of identical constructors.
> >
> > Conclusion: No difference.
>
> I'd say this is a bug. A directed multigraph should not allow loops.
>
> > The definition of a DirectedMultigraph does not seem consistent with the
> > definition of a Multigraph. For one thing, it does not extend Multigraph,
> > and it allows loops while a Multigraph does not.
>
> It is correct that DirectedMultigraph does not extend Multigraph. The plain
> Multigraph is undirected. Directed and undirected graphs are different
> beasts and are therefore not subclasses of one another in JgraphT. For the
> loops, see above.
>
> > DirectedMultigraph has a DirectedWeightedMultigraph subclass, but
> > DirectedPseudograph has no DirectedWeightedPseudograph subclass. This
> seems
> > confusing.
>
> Probably there hasn't been anybody so far who had a need for
> DirectedWeightedPseudographs and bothered to implement them.
>
> Regards,
>    Ernst
>
> --
> Information System on Graph Classes and their Inclusions (ISGCI)
> http://www.graphclasses.org
>
>
> ------------------------------------------------------------------------------
> Minimize network downtime and maximize team effectiveness.
> Reduce network management and security costs.Learn how to hire
> the most talented Cisco Certified professionals. Visit the
> Employer Resources Portal
> http://www.cisco.com/web/learning/employer_resources/index.html
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] stop at node in BFS

[John S. <js...@gm...>]

Another approach would be to first mask the original graph and then run the
BFS on the masked graph.

http://jgrapht.org/javadoc/org/jgrapht/graph/MaskSubgraph.html


On Wed, Apr 3, 2013 at 6:47 PM, Joris Kinable <de...@gm...> wrote:

> Dear Matthias,
>
> This functionality is not included in the JgraphT package, so you'll have
> to program it yourself. What kind of graph do you have? Implementing a BFS
> isn't very difficult. You probably want to maintain a set of 'special
> nodes'.
> So BFS works something like (copied from wiki):
>
> 1  *procedure* BFS(*G*,*v*):
> 2      create a queue *Q*
> 3      enqueue *v* onto *Q*
> 4      mark *v*
> 5      *while* *Q* is not empty:
> 6          *t* ← Q.dequeue()
> 7          *if* *t* is what we are looking for:
> 8              return *t*
> 9          *for all* edges e in G.adjacentEdges(t) *do*
> 12             *u* ← G.adjacentVertex(*t*,*e*)
> 13             *if* *u* is not marked:
> 14                  mark *u*
> 15                  enqueue *u* onto *Q*
> 16     return *none*
>
> So at step 15, you would NOT enqueue a node if it is special. You would
> simply mark it as visited.
>
> br,
>
> Joris
>
>
>
>
> On Wed, Apr 3, 2013 at 11:24 AM, Matthias Kricke <
> mat...@gm...> wrote:
>
>> Hi,
>>
>> I want to do a BFS where some nodes are excluded. To clarify, If BFS
>> accesses such a specified node I want BFS to stop at this node and don't
>> insert it to the results nor giving me the neighbors of the node but I want
>> BFS to go on other nodes.
>>
>> In other words, I want to exclude the subgraphs beneath specified nodes.
>> If another unspecified node is also able to access the subgraph I need the
>> subgraph and it shoudlnt be excluded.
>>
>> is it possible to do so with JGraphT? If yes, how?
>>
>> Hope you understand my desire =)
>>
>> Regards,
>> MK
>>
>>
>> ------------------------------------------------------------------------------
>> Minimize network downtime and maximize team effectiveness.
>> Reduce network management and security costs.Learn how to hire
>> the most talented Cisco Certified professionals. Visit the
>> Employer Resources Portal
>> http://www.cisco.com/web/learning/employer_resources/index.html
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>>
>
>
> ------------------------------------------------------------------------------
> Minimize network downtime and maximize team effectiveness.
> Reduce network management and security costs.Learn how to hire
> the most talented Cisco Certified professionals. Visit the
> Employer Resources Portal
> http://www.cisco.com/web/learning/employer_resources/index.html
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] Spanning Tree - Directed graph

[miki <mi...@gm...>]

Hello.

I would like to ask if it is correct to run KruskalMinimumSpanningTree on
DirectedWeightedMultigraph. As far as I know Kruskal (in general) only works
on undirected graph. For directed graphs there is Edmond's algorithm. 
Is KruskalMinimumSpanningTree  somehow changed to work on directed graphs ?
If no, can jgrapht solve spanning tree problem on directed graph ?

Thanks.

Regards,

Milos.



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Spanning-Tree-Directed-graph-tp4024793.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Displaying multiple edges between two vertices

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

Hey,

JgragphT doesnt have something like that. But JgraphT combines nicely with
JgraphX, which basically is its graphical counterpart. I suggest to use
that package next to JgraphT. JgraphX has several layout optimizers.

br,

Joris


On Sun, Apr 7, 2013 at 4:36 PM, ThatGuy <sch...@gm...> wrote:

> Hi,
> i'm working on a problem that requires me to have at least two edges
> between
> most of the vertices (one forward, one backward). To keep track if the
> algorithms are working, i view them via a JFrame. Right now i've positioned
> the vertices by hand via a function, but that's kind of annoying to do as
> the graph grows. The edges and their labels are also on top of each other,
> so you can't really read them.
> Is there a way to automatically space out the vertices, edges and the
> labels
> on the edges?
> I know that the JUNG framework has Layouts that automatically position the
> graph in a circle and makes sure that the edges aren't on top of each
> other.
> Is there something similar available?
>
>
>
> --
> View this message in context:
> http://jgrapht-users.107614.n3.nabble.com/Displaying-multiple-edges-between-two-vertices-tp4024791.html
> Sent from the jgrapht-users mailing list archive at Nabble.com.
>
>
> ------------------------------------------------------------------------------
> Minimize network downtime and maximize team effectiveness.
> Reduce network management and security costs.Learn how to hire
> the most talented Cisco Certified professionals. Visit the
> Employer Resources Portal
> http://www.cisco.com/web/learning/employer_resources/index.html
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] Displaying multiple edges between two vertices

[ThatGuy <sch...@gm...>]

Hi,
i'm working on a problem that requires me to have at least two edges between
most of the vertices (one forward, one backward). To keep track if the
algorithms are working, i view them via a JFrame. Right now i've positioned
the vertices by hand via a function, but that's kind of annoying to do as
the graph grows. The edges and their labels are also on top of each other,
so you can't really read them. 
Is there a way to automatically space out the vertices, edges and the labels
on the edges? 
I know that the JUNG framework has Layouts that automatically position the
graph in a circle and makes sure that the edges aren't on top of each other.
Is there something similar available?



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Displaying-multiple-edges-between-two-vertices-tp4024791.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Difference between a directed multigraph and a directed pseudograph

[H.N. de R. <hnr...@gr...>]

On Fri, Apr 05, 2013 at 02:05:05PM +0200, Adam Gouge wrote:

> What is the difference between a DirectedMultigraph and a
> DirectedPseudograph? According to the javadoc,
> 
> * A directed multigraph is a non-simple directed graph
> * in which loops and multiple edges between any two vertices are permitted.
> 
> * A directed pseudograph is a non-simple directed graph
> * in which both graph loops and multiple edges are permitted.
> 
> They both extend AbstractBaseGraph and implement DirectedGraph, and the
> code consists only of identical constructors.
> 
> Conclusion: No difference.

I'd say this is a bug. A directed multigraph should not allow loops.

> The definition of a DirectedMultigraph does not seem consistent with the
> definition of a Multigraph. For one thing, it does not extend Multigraph,
> and it allows loops while a Multigraph does not.

It is correct that DirectedMultigraph does not extend Multigraph. The plain
Multigraph is undirected. Directed and undirected graphs are different
beasts and are therefore not subclasses of one another in JgraphT. For the
loops, see above.

> DirectedMultigraph has a DirectedWeightedMultigraph subclass, but
> DirectedPseudograph has no DirectedWeightedPseudograph subclass. This seems
> confusing.

Probably there hasn't been anybody so far who had a need for
DirectedWeightedPseudographs and bothered to implement them.

Regards,
   Ernst

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

Re: [jgrapht-users] JGrapht: Compare two GraphPath

[H.N. de R. <hnr...@gr...>]

On Mon, Apr 01, 2013 at 11:13:23AM -0700, Pankaj2590 wrote:

>     I am writing a customize function to compare two GraphPaths of
> SimpleWeightedGraph, where edges are DefaultWeightedEdge. For the same, when
> the length of the both GraphPths are unequal then i am considering the
> GraphPath which has less length as "smaller". But for the equal length
> GraphPath, i am considering the GraphPath as "smaller" which contains edge,
> that is greater than all the edges of other GraphPath.
>     Here, I am having the Start Vertex of the Graphpath and End Vertex of
> the GraphPath but any how i am not able to get opposite vertex.

What do you meant by "not able to"? Does
org.jgrapht.Graphs.getOppositeVertex throw an error?

>    I have tried also by comparing the vertices by creating graph of
> GraphPath, wheather they are exists in this new graph or not. after that, i
> am not able to find the weight of the edge. Then how i compare those
> weights??
>    Conclusion is how i extract the weight of an edge..because getWeight
> method is not applicable for the same.

If I understand you correctly, you'd have to use getEdgeWeight of the
original graph.

Maybe you can give some small code example to demonstrate the problems you
encounter?

Regards,
   Ernst

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

[jgrapht-users] Difference between a directed multigraph and a directed pseudograph

[Adam G. <ada...@ec...>]

Hello,

What is the difference between a DirectedMultigraph and a
DirectedPseudograph? According to the javadoc,

* A directed multigraph is a non-simple directed graph
* in which loops and multiple edges between any two vertices are permitted.

* A directed pseudograph is a non-simple directed graph
* in which both graph loops and multiple edges are permitted.

They both extend AbstractBaseGraph and implement DirectedGraph, and the
code consists only of identical constructors.

Conclusion: No difference.

The definition of a DirectedMultigraph does not seem consistent with the
definition of a Multigraph. For one thing, it does not extend Multigraph,
and it allows loops while a Multigraph does not.

DirectedMultigraph has a DirectedWeightedMultigraph subclass, but
DirectedPseudograph has no DirectedWeightedPseudograph subclass. This seems
confusing.

Could someone clarify the situation?

Thank you,

Adam

Re: [jgrapht-users] stop at node in BFS

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

Dear Matthias,

This functionality is not included in the JgraphT package, so you'll have
to program it yourself. What kind of graph do you have? Implementing a BFS
isn't very difficult. You probably want to maintain a set of 'special
nodes'.
So BFS works something like (copied from wiki):

1  *procedure* BFS(*G*,*v*):
2      create a queue *Q*
3      enqueue *v* onto *Q*
4      mark *v*
5      *while* *Q* is not empty:
6          *t* ← Q.dequeue()
7          *if* *t* is what we are looking for:
8              return *t*
9          *for all* edges e in G.adjacentEdges(t) *do*
12             *u* ← G.adjacentVertex(*t*,*e*)
13             *if* *u* is not marked:
14                  mark *u*
15                  enqueue *u* onto *Q*
16     return *none*

So at step 15, you would NOT enqueue a node if it is special. You would
simply mark it as visited.

br,

Joris




On Wed, Apr 3, 2013 at 11:24 AM, Matthias Kricke <
mat...@gm...> wrote:

> Hi,
>
> I want to do a BFS where some nodes are excluded. To clarify, If BFS
> accesses such a specified node I want BFS to stop at this node and don't
> insert it to the results nor giving me the neighbors of the node but I want
> BFS to go on other nodes.
>
> In other words, I want to exclude the subgraphs beneath specified nodes.
> If another unspecified node is also able to access the subgraph I need the
> subgraph and it shoudlnt be excluded.
>
> is it possible to do so with JGraphT? If yes, how?
>
> Hope you understand my desire =)
>
> Regards,
> MK
>
>
> ------------------------------------------------------------------------------
> Minimize network downtime and maximize team effectiveness.
> Reduce network management and security costs.Learn how to hire
> the most talented Cisco Certified professionals. Visit the
> Employer Resources Portal
> http://www.cisco.com/web/learning/employer_resources/index.html
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] stop at node in BFS

[Matthias K. <mat...@gm...>]

Hi,

I want to do a BFS where some nodes are excluded. To clarify, If BFS
accesses such a specified node I want BFS to stop at this node and don't
insert it to the results nor giving me the neighbors of the node but I want
BFS to go on other nodes.

In other words, I want to exclude the subgraphs beneath specified nodes. If
another unspecified node is also able to access the subgraph I need the
subgraph and it shoudlnt be excluded.

is it possible to do so with JGraphT? If yes, how?

Hope you understand my desire =)

Regards,
MK

[jgrapht-users] JGrapht: Compare two GraphPath

[Pankaj2590 <kha...@gm...>]

Hi,
    I am writing a customize function to compare two GraphPaths of
SimpleWeightedGraph, where edges are DefaultWeightedEdge. For the same, when
the length of the both GraphPths are unequal then i am considering the
GraphPath which has less length as "smaller". But for the equal length
GraphPath, i am considering the GraphPath as "smaller" which contains edge,
that is greater than all the edges of other GraphPath.
    Here, I am having the Start Vertex of the Graphpath and End Vertex of
the GraphPath but any how i am not able to get opposite vertex.
   I have tried also by comparing the vertices by creating graph of
GraphPath, wheather they are exists in this new graph or not. after that, i
am not able to find the weight of the edge. Then how i compare those
weights??
   Conclusion is how i extract the weight of an edge..because getWeight
method is not applicable for the same.
   Thanks in advance for your reply or valuable suggestions.



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/JGrapht-Compare-two-GraphPath-tp4024785.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] JGraphT Enquiry: KShortestPaths Bug?

[panpan2523 <wan...@ya...>]

This logo has already established a global presence. Ash has attracted
worldwide customers with boots and shoes that are fabulous in design and
made with top quality craftsmanship and materials.
http://ashsale.net/goods-61-Ash-Jalouse-Black-Suede-Ankle-Boot.html website  
>From the Ash headquarters in Northern Italy, their shoes and boots have
spread to European centres and have gained a foothold in the markets of USA.
Customers realise now that the Ash boots and Ash shoes that they wear are an
amalgam of fashion, comfort, style and durability.



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Re-JGraphT-Enquiry-KShortestPaths-Bug-tp4024711p4024784.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] getAllEdges for DirectedGraph

[John S. <js...@gm...>]

Oh, sorry, I forgot about that; the Javadoc is correct.

For the least amount of code, you can use

http://jgrapht.org/javadoc/org/jgrapht/alg/DijkstraShortestPath.html#findPathBetween(org.jgrapht.Graph,
V, V)

If you are going to be making lots of tests on the same graph, then
use FloydWarshallShortestPaths instead.

On Mon, Mar 18, 2013 at 5:35 AM, Robert Manning
<rob...@gm...> wrote:
> That works, sort of.  Reading the javadoc it indicates that edge directions
> are ignored for a DirectedGraph.  And in my test I can flip "A" and "C" and
> pathExists still returns true.  I am trying to model Maven downstream
> project dependencies.  Is there no way to have the path test respect edge
> directions ?
>
> Rob
>
>
> On Fri, Mar 15, 2013 at 9:27 PM, John Sichi <js...@gm...> wrote:
>>
>> Anyway, to get back to your original problem...if you just want to
>> test whether such a sequence of edges exists (without identifying
>> them), you can use ConnectivityInspector.pathExists.  Otherwise, you
>> can use one of the traversal iterators such as DFS or BFS to find an
>> arbitrary path, or one of the shortest-path algorithms if you care
>> about path length.
>>
>> On Fri, Mar 15, 2013 at 5:39 PM, John Sichi <js...@gm...> wrote:
>> > JGraphT is not just for DAG's.
>> >
>> > On Mar 15, 2013 5:33 PM, "Robert Manning" <rob...@gm...>
>> > wrote:
>> >>
>> >> Somehow, in a DAG that makes no sense to me ?
>> >>
>> >> Rob
>> >>
>> >> On Fri, Mar 15, 2013 at 5:35 PM, Tobias Dehling
>> >> <de...@wi...> wrote:
>> >>>
>> >>> There could be multiple edge between two vertices. getEdge will get
>> >>> you
>> >>> one of them and getAllEdges will return all of them.
>> >>>
>> >>> Tobias
>> >>>
>> >>>
>> >>> On 03/15/2013 10:31 PM, Robert Manning wrote:
>> >>>
>> >>> I guess if getAllEdges and getEdge do the same thing, then that's
>> >>> fine.
>> >>> By why the duplication?  Why have getAllEdges when you can simply call
>> >>> getEdge ?
>> >>>
>> >>> Rob
>> >>>
>> >>> On Fri, Mar 15, 2013 at 4:59 PM, Alex Moir
>> >>> <am...@di...> wrote:
>> >>>>
>> >>>> It looks to me like you don’t have an edge from A to C, except
>> >>>> through
>> >>>> B.  And I think getAllEdges() only returns direct links between
>> >>>> vertices.
>> >>>> Maybe you are looking for a getAllPaths() type method?
>> >>>>
>> >>>>
>> >>>>
>> >>>> Alex
>> >>>>
>> >>>>
>> >>>>
>> >>>> From: Robert Manning [mailto:rob...@gm...]
>> >>>> Sent: Friday, March 15, 2013 8:59 AM
>> >>>> To: jgr...@li...
>> >>>> Subject: [jgrapht-users] getAllEdges for DirectedGraph
>> >>>>
>> >>>>
>> >>>>
>> >>>> Hello,
>> >>>>
>> >>>> I am trying to use jgrapht to answer the question : for any two
>> >>>> vertices
>> >>>> in a directed acyclic graph, tell me if there is a set of edges that
>> >>>> connects the two.  Based on the javadoc for getAllEdges in the Graph
>> >>>> interface, it seemed like jgrapht could answer this question for me.
>> >>>> However, my testing seems to prove otherwise:
>> >>>>
>> >>>> @Test
>> >>>> public void testGetAllEdges()  {
>> >>>>
>> >>>>   DirectedGraph<String, DefaultEdge> g = new
>> >>>> DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
>> >>>>
>> >>>>   g.addVertex("A");
>> >>>>   g.addVertex("B");
>> >>>>   g.addVertex("C");
>> >>>>
>> >>>>   g.addEdge("A", "B");
>> >>>>   g.addEdge("B", "C");
>> >>>>
>> >>>>   Set<DefaultEdge> edges = g.getAllEdges("A", "C");
>> >>>>
>> >>>>   assertFalse("There was no set of edges connecting A to C",
>> >>>> edges.isEmpty());
>> >>>>
>> >>>> }
>> >>>>
>> >>>> Of course, "edges" is an empty set in my test.  What am I doing
>> >>>> wrong?
>> >>>>
>> >>>> Rob
>> >>>
>> >>>
>> >>>
>> >>>
>> >>>
>> >>>
>> >>> ------------------------------------------------------------------------------
>> >>> Everyone hates slow websites. So do we.
>> >>> Make your web apps faster with AppDynamics
>> >>> Download AppDynamics Lite for free today:
>> >>> http://p.sf.net/sfu/appdyn_d2d_mar
>> >>>
>> >>>
>> >>>
>> >>> _______________________________________________
>> >>> jgrapht-users mailing list
>> >>> jgr...@li...
>> >>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>> >>>
>> >>>
>> >>>
>> >>> --
>> >>> Dipl.-Wirt.-Inf. Tobias Dehling
>> >>>
>> >>> Universität zu Köln
>> >>> Seminar für Wirtschaftsinformatik und Systementwicklung
>> >>> Juniorprofessur für Information Systems Quality
>> >>> Juniorprofessor Dr. Ali Sunyaev
>> >>> Wirtschafts- und Sozialwissenschaftliche Fakultät
>> >>>
>> >>> Pohligstr. 1, 50969 Köln
>> >>>
>> >>> Tel:  +49 221 470-5383 (Durchwahl)
>> >>>       +49 221 470-5368 (Sekretariat)
>> >>> Fax:  +49 221 470-5386
>> >>> Mail: de...@wi...
>> >>> Web:  www.isq.uni-koeln.de
>> >>>
>> >>>
>> >>>
>> >>>
>> >>> ------------------------------------------------------------------------------
>> >>> Everyone hates slow websites. So do we.
>> >>> Make your web apps faster with AppDynamics
>> >>> Download AppDynamics Lite for free today:
>> >>> http://p.sf.net/sfu/appdyn_d2d_mar
>> >>> _______________________________________________
>> >>> jgrapht-users mailing list
>> >>> jgr...@li...
>> >>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>> >>>
>> >>
>> >>
>> >>
>> >>
>> >> ------------------------------------------------------------------------------
>> >> Everyone hates slow websites. So do we.
>> >> Make your web apps faster with AppDynamics
>> >> Download AppDynamics Lite for free today:
>> >> http://p.sf.net/sfu/appdyn_d2d_mar
>> >> _______________________________________________
>> >> jgrapht-users mailing list
>> >> jgr...@li...
>> >> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>> >>
>> >
>
>

Re: [jgrapht-users] getAllEdges for DirectedGraph

[Robert M. <rob...@gm...>]

That works, sort of.  Reading the javadoc it indicates that edge directions
are ignored for a DirectedGraph.  And in my test I can flip "A" and "C" and
pathExists still returns true.  I am trying to model Maven downstream
project dependencies.  Is there no way to have the path test respect edge
directions ?

Rob

On Fri, Mar 15, 2013 at 9:27 PM, John Sichi <js...@gm...> wrote:

> Anyway, to get back to your original problem...if you just want to
> test whether such a sequence of edges exists (without identifying
> them), you can use ConnectivityInspector.pathExists.  Otherwise, you
> can use one of the traversal iterators such as DFS or BFS to find an
> arbitrary path, or one of the shortest-path algorithms if you care
> about path length.
>
> On Fri, Mar 15, 2013 at 5:39 PM, John Sichi <js...@gm...> wrote:
> > JGraphT is not just for DAG's.
> >
> > On Mar 15, 2013 5:33 PM, "Robert Manning" <rob...@gm...>
> > wrote:
> >>
> >> Somehow, in a DAG that makes no sense to me ?
> >>
> >> Rob
> >>
> >> On Fri, Mar 15, 2013 at 5:35 PM, Tobias Dehling
> >> <de...@wi...> wrote:
> >>>
> >>> There could be multiple edge between two vertices. getEdge will get you
> >>> one of them and getAllEdges will return all of them.
> >>>
> >>> Tobias
> >>>
> >>>
> >>> On 03/15/2013 10:31 PM, Robert Manning wrote:
> >>>
> >>> I guess if getAllEdges and getEdge do the same thing, then that's fine.
> >>> By why the duplication?  Why have getAllEdges when you can simply call
> >>> getEdge ?
> >>>
> >>> Rob
> >>>
> >>> On Fri, Mar 15, 2013 at 4:59 PM, Alex Moir
> >>> <am...@di...> wrote:
> >>>>
> >>>> It looks to me like you don’t have an edge from A to C, except through
> >>>> B.  And I think getAllEdges() only returns direct links between
> vertices.
> >>>> Maybe you are looking for a getAllPaths() type method?
> >>>>
> >>>>
> >>>>
> >>>> Alex
> >>>>
> >>>>
> >>>>
> >>>> From: Robert Manning [mailto:rob...@gm...]
> >>>> Sent: Friday, March 15, 2013 8:59 AM
> >>>> To: jgr...@li...
> >>>> Subject: [jgrapht-users] getAllEdges for DirectedGraph
> >>>>
> >>>>
> >>>>
> >>>> Hello,
> >>>>
> >>>> I am trying to use jgrapht to answer the question : for any two
> vertices
> >>>> in a directed acyclic graph, tell me if there is a set of edges that
> >>>> connects the two.  Based on the javadoc for getAllEdges in the Graph
> >>>> interface, it seemed like jgrapht could answer this question for me.
> >>>> However, my testing seems to prove otherwise:
> >>>>
> >>>> @Test
> >>>> public void testGetAllEdges()  {
> >>>>
> >>>>   DirectedGraph<String, DefaultEdge> g = new
> >>>> DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
> >>>>
> >>>>   g.addVertex("A");
> >>>>   g.addVertex("B");
> >>>>   g.addVertex("C");
> >>>>
> >>>>   g.addEdge("A", "B");
> >>>>   g.addEdge("B", "C");
> >>>>
> >>>>   Set<DefaultEdge> edges = g.getAllEdges("A", "C");
> >>>>
> >>>>   assertFalse("There was no set of edges connecting A to C",
> >>>> edges.isEmpty());
> >>>>
> >>>> }
> >>>>
> >>>> Of course, "edges" is an empty set in my test.  What am I doing wrong?
> >>>>
> >>>> Rob
> >>>
> >>>
> >>>
> >>>
> >>>
> >>>
> ------------------------------------------------------------------------------
> >>> Everyone hates slow websites. So do we.
> >>> Make your web apps faster with AppDynamics
> >>> Download AppDynamics Lite for free today:
> >>> http://p.sf.net/sfu/appdyn_d2d_mar
> >>>
> >>>
> >>>
> >>> _______________________________________________
> >>> jgrapht-users mailing list
> >>> jgr...@li...
> >>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >>>
> >>>
> >>>
> >>> --
> >>> Dipl.-Wirt.-Inf. Tobias Dehling
> >>>
> >>> Universität zu Köln
> >>> Seminar für Wirtschaftsinformatik und Systementwicklung
> >>> Juniorprofessur für Information Systems Quality
> >>> Juniorprofessor Dr. Ali Sunyaev
> >>> Wirtschafts- und Sozialwissenschaftliche Fakultät
> >>>
> >>> Pohligstr. 1, 50969 Köln
> >>>
> >>> Tel:  +49 221 470-5383 (Durchwahl)
> >>>       +49 221 470-5368 (Sekretariat)
> >>> Fax:  +49 221 470-5386
> >>> Mail: de...@wi...
> >>> Web:  www.isq.uni-koeln.de
> >>>
> >>>
> >>>
> >>>
> ------------------------------------------------------------------------------
> >>> Everyone hates slow websites. So do we.
> >>> Make your web apps faster with AppDynamics
> >>> Download AppDynamics Lite for free today:
> >>> http://p.sf.net/sfu/appdyn_d2d_mar
> >>> _______________________________________________
> >>> jgrapht-users mailing list
> >>> jgr...@li...
> >>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >>>
> >>
> >>
> >>
> >>
> ------------------------------------------------------------------------------
> >> Everyone hates slow websites. So do we.
> >> Make your web apps faster with AppDynamics
> >> Download AppDynamics Lite for free today:
> >> http://p.sf.net/sfu/appdyn_d2d_mar
> >> _______________________________________________
> >> jgrapht-users mailing list
> >> jgr...@li...
> >> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >>
> >
>

Re: [jgrapht-users] getAllEdges for DirectedGraph

[John S. <js...@gm...>]

Anyway, to get back to your original problem...if you just want to
test whether such a sequence of edges exists (without identifying
them), you can use ConnectivityInspector.pathExists.  Otherwise, you
can use one of the traversal iterators such as DFS or BFS to find an
arbitrary path, or one of the shortest-path algorithms if you care
about path length.

On Fri, Mar 15, 2013 at 5:39 PM, John Sichi <js...@gm...> wrote:
> JGraphT is not just for DAG's.
>
> On Mar 15, 2013 5:33 PM, "Robert Manning" <rob...@gm...>
> wrote:
>>
>> Somehow, in a DAG that makes no sense to me ?
>>
>> Rob
>>
>> On Fri, Mar 15, 2013 at 5:35 PM, Tobias Dehling
>> <de...@wi...> wrote:
>>>
>>> There could be multiple edge between two vertices. getEdge will get you
>>> one of them and getAllEdges will return all of them.
>>>
>>> Tobias
>>>
>>>
>>> On 03/15/2013 10:31 PM, Robert Manning wrote:
>>>
>>> I guess if getAllEdges and getEdge do the same thing, then that's fine.
>>> By why the duplication?  Why have getAllEdges when you can simply call
>>> getEdge ?
>>>
>>> Rob
>>>
>>> On Fri, Mar 15, 2013 at 4:59 PM, Alex Moir
>>> <am...@di...> wrote:
>>>>
>>>> It looks to me like you don’t have an edge from A to C, except through
>>>> B.  And I think getAllEdges() only returns direct links between vertices.
>>>> Maybe you are looking for a getAllPaths() type method?
>>>>
>>>>
>>>>
>>>> Alex
>>>>
>>>>
>>>>
>>>> From: Robert Manning [mailto:rob...@gm...]
>>>> Sent: Friday, March 15, 2013 8:59 AM
>>>> To: jgr...@li...
>>>> Subject: [jgrapht-users] getAllEdges for DirectedGraph
>>>>
>>>>
>>>>
>>>> Hello,
>>>>
>>>> I am trying to use jgrapht to answer the question : for any two vertices
>>>> in a directed acyclic graph, tell me if there is a set of edges that
>>>> connects the two.  Based on the javadoc for getAllEdges in the Graph
>>>> interface, it seemed like jgrapht could answer this question for me.
>>>> However, my testing seems to prove otherwise:
>>>>
>>>> @Test
>>>> public void testGetAllEdges()  {
>>>>
>>>>   DirectedGraph<String, DefaultEdge> g = new
>>>> DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
>>>>
>>>>   g.addVertex("A");
>>>>   g.addVertex("B");
>>>>   g.addVertex("C");
>>>>
>>>>   g.addEdge("A", "B");
>>>>   g.addEdge("B", "C");
>>>>
>>>>   Set<DefaultEdge> edges = g.getAllEdges("A", "C");
>>>>
>>>>   assertFalse("There was no set of edges connecting A to C",
>>>> edges.isEmpty());
>>>>
>>>> }
>>>>
>>>> Of course, "edges" is an empty set in my test.  What am I doing wrong?
>>>>
>>>> Rob
>>>
>>>
>>>
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> Everyone hates slow websites. So do we.
>>> Make your web apps faster with AppDynamics
>>> Download AppDynamics Lite for free today:
>>> http://p.sf.net/sfu/appdyn_d2d_mar
>>>
>>>
>>>
>>> _______________________________________________
>>> jgrapht-users mailing list
>>> jgr...@li...
>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>
>>>
>>>
>>> --
>>> Dipl.-Wirt.-Inf. Tobias Dehling
>>>
>>> Universität zu Köln
>>> Seminar für Wirtschaftsinformatik und Systementwicklung
>>> Juniorprofessur für Information Systems Quality
>>> Juniorprofessor Dr. Ali Sunyaev
>>> Wirtschafts- und Sozialwissenschaftliche Fakultät
>>>
>>> Pohligstr. 1, 50969 Köln
>>>
>>> Tel:  +49 221 470-5383 (Durchwahl)
>>>       +49 221 470-5368 (Sekretariat)
>>> Fax:  +49 221 470-5386
>>> Mail: de...@wi...
>>> Web:  www.isq.uni-koeln.de
>>>
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> Everyone hates slow websites. So do we.
>>> Make your web apps faster with AppDynamics
>>> Download AppDynamics Lite for free today:
>>> http://p.sf.net/sfu/appdyn_d2d_mar
>>> _______________________________________________
>>> jgrapht-users mailing list
>>> jgr...@li...
>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>
>>
>>
>>
>> ------------------------------------------------------------------------------
>> Everyone hates slow websites. So do we.
>> Make your web apps faster with AppDynamics
>> Download AppDynamics Lite for free today:
>> http://p.sf.net/sfu/appdyn_d2d_mar
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>