jgrapht-users — JGraphT user list.

Re: [jgrapht-users] GraphUnion does not play well with algorithm implementation(s)

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

That's quite a viper's nest you've stepped into.

Since the code snippet erroneously assumes that every graph that is not directed must be undirected, my first thought was simply changing the if statement to

if (graph instanceof UndirectedGraph)

Although this correction would be a good idea anyhow, it is not enough: For mixed graphs we need to check for every edge independently whether it is undirected or not and therefore cannot do so by looking at the type of the graph. However, in Jgrapht edges themselves don't have a directed/undirected property: it's the graph that determines this.

So my second thought was introducing a MixedGraph type that stores this knowledge per edge. Thinking where this type should go in the hierachy (common supertype of Directed/UndirectedGraph, common subtype or a sibling?), made me realize what (IMHO) the proper solution would be and what the disadvantages of your suggestion are:

Pushing outGoingEdges/incomingEdges into the Graph interface effectively locks the equivalence undirected == bidirectional in the library at a very basic level. Making MixedGrapUnion implement DirectedGraph also reflects this equivalence. But undirected and birectional need not be equivalent in every situation. They are apparently in your problem frame.  So my suggestion is to solve this issue not by changing jgrapht, but by using what's there to make the code model your problem. And this can be done, I think, by running Floyd-Warshall on a directed view of the mixed graph. Simple, flexible and without difficult changes to jgrapht itself.

Regards,
   Ernst


----- Reply message -----
From: "Joris Kinable" <de...@gm...>
To: "jgr...@li..." <jgr...@li...>
Subject: [jgrapht-users] GraphUnion does not play well with algorithm implementation(s)
Date: Wed, Aug 19, 2015 18:57
Hi,
I'm encountering some problems with jgrapht's graph union and (at least one) algorithm implementation. I wanted to hear your opinion about a possible fix to this issue.

Given two graphs (the actual implementation of V, E is irrelevant):Graph<V,E> myUndirectedGraph=new SimpleGraph<>(E.class);Graph<V,E> myDirectedGraph=new SimpleDirectedGraph<>(E.class);

We can now create a mixed graph through the graph union interface (this is a legal operation!):Graph<V,E> mixedGraph=new GraphUnion<>(myUndirectedGraph, myDirectedGraph);
So far so good, the mixedGraph works as expected. If I for example query an edge between vertices i and j, then the mixed graph will only return an edge if either myUndirectedGraph or myDirectedGraph has an edge/arc (i,j); an arc (j,i) in myDirectedGraph is never returned. 
If we would now plugin the mixedGraph into for example the FloydWarshallShortestPaths algorithm implementation, we run into runtime issues. Why? Because of the following code segment:
// initialize matrix, 2        Set<E> edges = graph.edgeSet();        for (E edge : edges) {            V v1 = graph.getEdgeSource(edge);            V v2 = graph.getEdgeTarget(edge);
            int v_1 = vertices.indexOf(v1);            int v_2 = vertices.indexOf(v2);
            d[v_1][v_2] = graph.getEdgeWeight(edge);            if (!(graph instanceof DirectedGraph<?, ?>)) {                d[v_2][v_1] = graph.getEdgeWeight(edge);            }        }
Due to the implementation of the GraphUnion, our mixedGraph is *not* an instance of DirectedGraph<?,?>, so the algorithm will incorrectly set the distance d_ij=d_ji, independent of whether arcs (i,j) and (j,i) exist. This is obviously due to the fact that FloydWarshallShortestPaths thinks we are dealing with a undirected graph. A possible solution would be:
for(V v1 : graph.vertexSet()){
    int v_1 = vertices.indexOf(v1);
    for(E edge : graph.outgoingEdgesOf(v1)){
        V v2=Graphs.getOppositeVertex(graph, edge, v1);
        int v_2 = vertices.indexOf(v2);
        d[v_1][v_2] = graph.getEdgeWeight(edge);
    }
}

However, the method outgoingEdgesOf(V v) is not accessible through the interface "Graph", so this won't work.
Furthermore, we cannot use Graph<V,E> mixedGraph2=new DirectedGraphUnion<>(G g1, G g2) because a DirectedGraphUnion expects 2 *Directed* graphs in its constructor. Hence, the cleanest possible solution I could come up with is the following:
1. Create a new class MixedGraphUnion which takes an undirected and a directed graph as input. The MixedGraphUnion is an instance of a DirectedGraph and implements all methods as expected.2. Add methods outgoingEdgesOf(V v), incomingEdgesOf(V v), inDegreeOf(V v), outDegreeOf(V v) to the graph interface. All of these methods make sense, even in the context of undirected graphs 3. Rewrite the Initialize matrix code in FloydWarshallShortestPaths implementation as suggested above.
Some of you may ask: why do you want a MixedGraph? Why don't you create a DirectedGraph and add two arcs (i,j) and (j,i) for each undirected edge? Unfortunately, as pointed out by some other users, there are applications where you actually want to distinguish between an edge {i,j} and two directed arcs (i,j),(j,i) as they may have different meaning. A simple example commonly arises in street networks: an edge represents a residential street which may be driven in both directions, an arc represents a one-way street and two arcs in opposite direction represents a street consisting of two lanes in opposite direction. 
best regards,
Joris Kinable

[jgrapht-users] GraphUnion does not play well with algorithm implementation(s)

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

Hi,

I'm encountering some problems with jgrapht's graph union and (at least
one) algorithm implementation. I wanted to hear your opinion about a
possible fix to this issue.


Given two graphs (the actual implementation of V, E is irrelevant):
Graph<V,E> myUndirectedGraph=new SimpleGraph<>(E.class);
Graph<V,E> myDirectedGraph=new SimpleDirectedGraph<>(E.class);

We can now create a mixed graph through the graph union interface (this is
a legal operation!):
Graph<V,E> mixedGraph=new GraphUnion<>(myUndirectedGraph, myDirectedGraph);

So far so good, the mixedGraph works as expected. If I for example query an
edge between vertices i and j, then the mixed graph will only return an
edge if either myUndirectedGraph or myDirectedGraph has an edge/arc (i,j);
an arc (j,i) in myDirectedGraph is never returned.

If we would now plugin the mixedGraph into for example the
FloydWarshallShortestPaths algorithm implementation, we run into runtime
issues. Why? Because of the following code segment:

// initialize matrix, 2
        Set<E> edges = graph.edgeSet();
        for (E edge : edges) {
            V v1 = graph.getEdgeSource(edge);
            V v2 = graph.getEdgeTarget(edge);

            int v_1 = vertices.indexOf(v1);
            int v_2 = vertices.indexOf(v2);

            d[v_1][v_2] = graph.getEdgeWeight(edge);
            if (!(graph instanceof DirectedGraph<?, ?>)) {
                d[v_2][v_1] = graph.getEdgeWeight(edge);
            }
        }

Due to the implementation of the GraphUnion, our mixedGraph is *not* an
instance of DirectedGraph<?,?>, so the algorithm will incorrectly set the
distance d_ij=d_ji, independent of whether arcs (i,j) and (j,i) exist. This
is obviously due to the fact that FloydWarshallShortestPaths thinks we are
dealing with a undirected graph. A possible solution would be:

for(V v1 : graph.vertexSet()){
    int v_1 = vertices.indexOf(v1);
    for(E edge : graph.outgoingEdgesOf(v1)){
        V v2=Graphs.getOppositeVertex(graph, edge, v1);
        int v_2 = vertices.indexOf(v2);
        d[v_1][v_2] = graph.getEdgeWeight(edge);
    }
}

However, the method outgoingEdgesOf(V v) is not accessible through the
interface "Graph", so this won't work.
Furthermore, we cannot use Graph<V,E> mixedGraph2=new
DirectedGraphUnion<>(G g1, G g2) because a DirectedGraphUnion expects 2
*Directed* graphs in its constructor. Hence, the cleanest possible solution
I could come up with is the following:

1. Create a new class MixedGraphUnion which takes an undirected and a
directed graph as input. The MixedGraphUnion is an instance of a
DirectedGraph and implements all methods as expected.
2. Add methods outgoingEdgesOf(V v), incomingEdgesOf(V v), inDegreeOf(V v),
outDegreeOf(V v) to the graph interface. All of these methods make sense,
even in the context of undirected graphs
3. Rewrite the Initialize matrix code in FloydWarshallShortestPaths
implementation as suggested above.

Some of you may ask: why do you want a MixedGraph? Why don't you create a
DirectedGraph and add two arcs (i,j) and (j,i) for each undirected edge?
Unfortunately, as pointed out by some other users, there are applications
where you actually want to distinguish between an edge {i,j} and two
directed arcs (i,j),(j,i) as they may have different meaning. A simple
example commonly arises in street networks: an edge represents a
residential street which may be driven in both directions, an arc
represents a one-way street and two arcs in opposite direction represents a
street consisting of two lanes in opposite direction.

best regards,

Joris Kinable

Re: [jgrapht-users] DirectedGraph equality testing

[Aidan D. <ai...@on...>]

John,
Thanks a lot for the clarification. Of course I was too wrapped up in what
I was trying to do to consider the multigraph case. I'll modify my approach.

-- 
Aidan Delaney
On Aug 13, 2015 12:56 AM, "John Sichi" <js...@gm...> wrote:

> For multigraphs, e1 and e2 may both have source v1 and target v2, and yet
> they are two distinct edges.
>
> In general, "equality" for a graph isn't a very useful concept due to the
> fact that g1 and g2 may be isomorphic even though !g1.equals(g2).
>
>
> On Wed, Aug 12, 2015 at 2:30 PM, Aidan Delaney <
> ai...@on...> wrote:
>
>> Dear all,
>>         I've been trying to test for deep vertex & edge equality in a
>> DirectedGraph.  An example is below.  It appears that this fails
>> because, I think, DefaultEdge needs a non-default hashCode
>> implementation.  My GitHub pull-request is at [1], but it causes more
>> problems than it solves.
>>
>> Am I just incorrect in trying to use JGraphT in this way to check graph
>> equality?  Is there some other way I should be doing this?
>>
>> DirectedGraph<String, DefaultEdge> g1 =
>>             new SimpleDirectedGraph<String,
>> DefaultEdge>(DefaultEdge.class);
>>         DirectedGraph<String, DefaultEdge> g2 =
>>             new SimpleDirectedGraph<String,
>> DefaultEdge>(DefaultEdge.class);
>>
>>         g1.addVertex("A");
>>         g2.addVertex("A");
>>
>>         assertEquals(g1, g2);
>>
>>         g1.addVertex("B");
>>         g2.addVertex("B");
>>
>>         assertEquals(g1, g2);
>>
>> [1] https://github.com/jgrapht/jgrapht/pull/148
>>
>> --
>> Dr Aidan Delaney
>> Principal Lecturer
>> Computing, Engineering & Maths
>> University of Brighton
>>
>> @aidandelaney
>>
>>
>> ------------------------------------------------------------------------------
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>
>

Re: [jgrapht-users] DirectedGraph equality testing

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

For multigraphs, e1 and e2 may both have source v1 and target v2, and yet
they are two distinct edges.

In general, "equality" for a graph isn't a very useful concept due to the
fact that g1 and g2 may be isomorphic even though !g1.equals(g2).


On Wed, Aug 12, 2015 at 2:30 PM, Aidan Delaney <
ai...@on...> wrote:

> Dear all,
>         I've been trying to test for deep vertex & edge equality in a
> DirectedGraph.  An example is below.  It appears that this fails
> because, I think, DefaultEdge needs a non-default hashCode
> implementation.  My GitHub pull-request is at [1], but it causes more
> problems than it solves.
>
> Am I just incorrect in trying to use JGraphT in this way to check graph
> equality?  Is there some other way I should be doing this?
>
> DirectedGraph<String, DefaultEdge> g1 =
>             new SimpleDirectedGraph<String,
> DefaultEdge>(DefaultEdge.class);
>         DirectedGraph<String, DefaultEdge> g2 =
>             new SimpleDirectedGraph<String,
> DefaultEdge>(DefaultEdge.class);
>
>         g1.addVertex("A");
>         g2.addVertex("A");
>
>         assertEquals(g1, g2);
>
>         g1.addVertex("B");
>         g2.addVertex("B");
>
>         assertEquals(g1, g2);
>
> [1] https://github.com/jgrapht/jgrapht/pull/148
>
> --
> Dr Aidan Delaney
> Principal Lecturer
> Computing, Engineering & Maths
> University of Brighton
>
> @aidandelaney
>
>
> ------------------------------------------------------------------------------
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] DirectedGraph equality testing

[Aidan D. <ai...@on...>]

Dear all,
	I've been trying to test for deep vertex & edge equality in a
DirectedGraph.  An example is below.  It appears that this fails
because, I think, DefaultEdge needs a non-default hashCode
implementation.  My GitHub pull-request is at [1], but it causes more
problems than it solves.

Am I just incorrect in trying to use JGraphT in this way to check graph
equality?  Is there some other way I should be doing this?

DirectedGraph<String, DefaultEdge> g1 =
            new SimpleDirectedGraph<String,
DefaultEdge>(DefaultEdge.class);
        DirectedGraph<String, DefaultEdge> g2 =
            new SimpleDirectedGraph<String,
DefaultEdge>(DefaultEdge.class);

        g1.addVertex("A");
        g2.addVertex("A");

        assertEquals(g1, g2);

        g1.addVertex("B");
        g2.addVertex("B");

        assertEquals(g1, g2);

[1] https://github.com/jgrapht/jgrapht/pull/148

-- 
Dr Aidan Delaney
Principal Lecturer
Computing, Engineering & Maths
University of Brighton

@aidandelaney

Re: [jgrapht-users] Is the target vertex of an edge stored differently than the same vertex in the vertex set?

[Steven B. <ste...@sa...>]

Thanks - the HashMap solved my problem.   I really appreciate your taking
the time to look at my program.

On Sun, Aug 9, 2015 at 8:43 PM, Joris Kinable <de...@gm...> wrote:

> Your problem is in this part of your code:
>
> String sourceToken = tokenizer.nextToken();
> int sourceNum = Integer.parseInt(sourceToken);
> SteveVertex sourceVertex = new SteveVertex(sourceNum);
> boolean success = graph.addVertex(sourceVertex);
> System.out.println("added "+sourceVertex.ID()+" success: "+success);
>
> String destToken = tokenizer.nextToken();
> int destNum = Integer.parseInt(destToken);
> SteveVertex destVertex = new SteveVertex(destNum);
> success = graph.addVertex(destVertex);  /* may already exist */
> System.out.println("added "+destVertex.ID()+" success: "+success);
>
>
> if (sourceNum != destNum) {
>     graph.addEdge(sourceVertex, destVertex);
>     numEdges++;
>     if (numEdges % 1000 == 0)
>         StdOut.printf("Edge count: %d\n", numEdges);
> }
>
>
> You create 2 new objects, source and target vertices, and add them to the
> graph. Jgrapht won't add them if they are already present. Next you add a
> new edge using graph.addEdge(sourceVertex, destVertex). Jgrapht will first
> check whether source and the target vertices are already present. Lets
> assume that your code does the following:
>
> SteveVertex object1=new SteveVertex(1);
>
> SteveVertex object2=new SteveVertex(2);
>
> graph.addVertex(object1); //success
>
> graph.addVertex(object2); //success
>
>
> SteveVertex object3=new SteveVertex(1);
>
> SteveVertex object4=new SteveVertex(2);
>
> graph.addVertex(object3); //fail
>
> graph.addVertex(object4); //fail
>
> graph.addEdge(object3,object4); //Incorrect
>
>
> In the last step, the addEdge method will check whether object3 and object4 are already in the graph. Because you incorrectly overrode the hashCode and equals methods, it will think that these vertices are already in the graph, and the method will modify the internal edge structure using the objects you provided. Even though object1.hashCode()==object3.hashCode() and object1.equals(object3), object1==object3 fails. By doing so, you violate the equals contract between two objects:
>
> "The equals method for class Object implements the most discriminating possible equivalence relation on objects; that is, for any non-null reference values x and y, this method returns true if and only if x and y refer to the same object (x == y has the value true)."
>
> see: https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#equals-java.lang.Object-
>
>
> An easy fix to your problem would be to use a map:
>
> Map<Integer, SteveVertex> vertexMap=new HashMap<>();
>
> ...
>
> int sourceToken = Integer.parseInt(tokenizer.nextToken());
> SteveVertex sourceVertex;
> if(vertexMap.containsKey(sourceToken){
>   sourceVertex=vertexMap.get(sourceToken);
> }else{
>   sourceVertex = new SteveVertex(sourceToken);
>   vertexMap.put(sourceToken, sourceVertex);
>   graph.addVertex(sourceVertex);
> }
>
> int targetToken = Integer.parseInt(tokenizer.nextToken());
> SteveVertex targetVertex;
> if(vertexMap.containsKey(targetToken){
>   targetVertex=vertexMap.get(targetToken);
> }else{
>   targetVertex = new SteveVertex(targetToken);
>   vertexMap.put(targetToken, targetVertex);
>   graph.addVertex(targetVertex);
> }
>
> graph.addEdge(sourceVertex, destVertex);
>
>
> br,
>
>
> Joris Kinable
> Ps. Please don't set messages directly to me, instead, use the mailing
> list.
>
> On Sun, Aug 9, 2015 at 5:38 PM, Steven Barkin <ste...@sa...>
> wrote:
>
>> Thanks Joris.  Would you be open to reviewing my two Java source files
>> plus the input text file with the graph info?  They are fairly simple.  I'm
>> attaching them here if you be willing to take a look.  These are related to
>> a Coursera class I am taking (Stanford Algorithms Design and Analysis).
>>
>> On Sun, Aug 9, 2015 at 2:22 PM, Joris Kinable <de...@gm...> wrote:
>>
>>> The problem doesn't seem to be in the section of code you posted. Check
>>> whether your visited() method actually does something.
>>>
>>> "I seem to have come across a non-intuitive discrepancy between how
>>> vertexes are stored in jgrapht graphs (in this case a SimpleDirectedGraph)
>>> in the vertexSet, vs. how they are stored as the target of an edge (see
>>> below for my usage of getEdgeTarget)." Also, check whether your isVisited()
>>> method returns the correct result.
>>>
>>> I'm not sure where you get this idea from? This is not true. All methods
>>> use the same vertex or edge objects. Furthermore, none of the methods
>>> you've shown use equals/hashCode, so even if you had implemented them
>>> wrong, I don't see why this would effect your result. Btw, I would
>>> encourage you to have a look at the jgrapht graph source code. It is very
>>> clear and gives you a good understanding of how the graph package works.
>>>
>>> It will not make a difference, but in your code I would find it cleaner
>>> to write:
>>>
>>> for (SteveVertex neighborVertex : Graphs.outgoingNeighborsOf(graph,startVertex)
>>>
>>>              SteveDepthFirstSearch(neighborVertex);
>>>
>>> instead of:
>>>
>>> for (DefaultEdge e : graph.outgoingEdgesOf(startVertex))
>>>              SteveDepthFirstSearch(graph.getEdgeTarget(e));
>>>
>>>
>>>
>>> br,
>>>
>>> Joris Kinable
>>>
>>> On Sun, Aug 9, 2015 at 3:00 PM, Steven Barkin <ste...@sa...>
>>> wrote:
>>>
>>>> I seem to have come across a non-intuitive discrepancy between how
>>>> vertexes are stored in jgrapht graphs (in this case a SimpleDirectedGraph)
>>>> in the vertexSet, vs. how they are stored as the target of an edge (see
>>>> below for my usage of getEdgeTarget). I had thought they were identical -
>>>> i.e. they point to the same object (a SteveVertex in this case) and have
>>>> the same hash code - but they seem to be located in different places
>>>> somehow, per symptom below.
>>>>
>>>> When my code below comes across a loop, in which it encounters the
>>>> original start vertex as the target of an edge, it does not show this
>>>> vertex as having been visited, even though the hashCode (SteveVertex@vertex1)
>>>> is identical to the first entry of the vertexSet which DOES show the vertex
>>>> as having been visited.
>>>>
>>>> Any help would be greatly appreciated in diagnosing this.
>>>>
>>>> private static SimpleDirectedGraph<SteveVertex, DefaultEdge> graph;
>>>> private static void SteveDepthFirstSearch(SteveVertex startVertex)
>>>>  {
>>>>      if (!startVertex.visited()) {
>>>>          startVertex.visit();
>>>>          for (DefaultEdge e : graph.outgoingEdgesOf(startVertex))
>>>>              SteveDepthFirstSearch(graph.getEdgeTarget(e));
>>>>
>>>>          startVertex.setFinishOrder(counter);
>>>>          counter++;
>>>>      }
>>>>
>>>>  }
>>>>
>>>> public static void main(String[] args) {
>>>>
>>>>     ...
>>>>
>>>>     for (SteveVertex v: graph.vertexSet())
>>>>         SteveDepthFirstSearch(v);
>>>>
>>>>     ...
>>>> }
>>>>
>>>>
>>>> This communication is confidential and subject to and governed by the
>>>> confidentiality and use restrictions contained in Saama’s Electronic
>>>> Communications Disclaimer. <http://www.saama.com/disclaimer>
>>>>
>>>>
>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>>
>>>> _______________________________________________
>>>> jgrapht-users mailing list
>>>> jgr...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>>
>>>>
>>>
>>
>> This communication is confidential and subject to and governed by the
>> confidentiality and use restrictions contained in Saama’s Electronic
>> Communications Disclaimer. <http://www.saama.com/disclaimer>
>>
>>
>>
>
>

-- 


This communication is confidential and subject to and governed by the 
confidentiality and use restrictions contained in Saama’s Electronic 
Communications Disclaimer. <http://www.saama.com/disclaimer>

 

Re: [jgrapht-users] Is the target vertex of an edge stored differently than the same vertex in the vertex set?

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

Your problem is in this part of your code:

String sourceToken = tokenizer.nextToken();
int sourceNum = Integer.parseInt(sourceToken);
SteveVertex sourceVertex = new SteveVertex(sourceNum);
boolean success = graph.addVertex(sourceVertex);
System.out.println("added "+sourceVertex.ID()+" success: "+success);

String destToken = tokenizer.nextToken();
int destNum = Integer.parseInt(destToken);
SteveVertex destVertex = new SteveVertex(destNum);
success = graph.addVertex(destVertex);  /* may already exist */
System.out.println("added "+destVertex.ID()+" success: "+success);


if (sourceNum != destNum) {
    graph.addEdge(sourceVertex, destVertex);
    numEdges++;
    if (numEdges % 1000 == 0)
        StdOut.printf("Edge count: %d\n", numEdges);
}


You create 2 new objects, source and target vertices, and add them to the
graph. Jgrapht won't add them if they are already present. Next you add a
new edge using graph.addEdge(sourceVertex, destVertex). Jgrapht will first
check whether source and the target vertices are already present. Lets
assume that your code does the following:

SteveVertex object1=new SteveVertex(1);

SteveVertex object2=new SteveVertex(2);

graph.addVertex(object1); //success

graph.addVertex(object2); //success


SteveVertex object3=new SteveVertex(1);

SteveVertex object4=new SteveVertex(2);

graph.addVertex(object3); //fail

graph.addVertex(object4); //fail

graph.addEdge(object3,object4); //Incorrect


In the last step, the addEdge method will check whether object3 and
object4 are already in the graph. Because you incorrectly overrode the
hashCode and equals methods, it will think that these vertices are
already in the graph, and the method will modify the internal edge
structure using the objects you provided. Even though
object1.hashCode()==object3.hashCode() and object1.equals(object3),
object1==object3 fails. By doing so, you violate the equals contract
between two objects:

"The equals method for class Object implements the most discriminating
possible equivalence relation on objects; that is, for any non-null
reference values x and y, this method returns true if and only if x
and y refer to the same object (x == y has the value true)."

see: https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#equals-java.lang.Object-


An easy fix to your problem would be to use a map:

Map<Integer, SteveVertex> vertexMap=new HashMap<>();

...

int sourceToken = Integer.parseInt(tokenizer.nextToken());
SteveVertex sourceVertex;
if(vertexMap.containsKey(sourceToken){
  sourceVertex=vertexMap.get(sourceToken);
}else{
  sourceVertex = new SteveVertex(sourceToken);
  vertexMap.put(sourceToken, sourceVertex);
  graph.addVertex(sourceVertex);
}

int targetToken = Integer.parseInt(tokenizer.nextToken());
SteveVertex targetVertex;
if(vertexMap.containsKey(targetToken){
  targetVertex=vertexMap.get(targetToken);
}else{
  targetVertex = new SteveVertex(targetToken);
  vertexMap.put(targetToken, targetVertex);
  graph.addVertex(targetVertex);
}

graph.addEdge(sourceVertex, destVertex);


br,


Joris Kinable
Ps. Please don't set messages directly to me, instead, use the mailing list.

On Sun, Aug 9, 2015 at 5:38 PM, Steven Barkin <ste...@sa...>
wrote:

> Thanks Joris.  Would you be open to reviewing my two Java source files
> plus the input text file with the graph info?  They are fairly simple.  I'm
> attaching them here if you be willing to take a look.  These are related to
> a Coursera class I am taking (Stanford Algorithms Design and Analysis).
>
> On Sun, Aug 9, 2015 at 2:22 PM, Joris Kinable <de...@gm...> wrote:
>
>> The problem doesn't seem to be in the section of code you posted. Check
>> whether your visited() method actually does something.
>>
>> "I seem to have come across a non-intuitive discrepancy between how
>> vertexes are stored in jgrapht graphs (in this case a SimpleDirectedGraph)
>> in the vertexSet, vs. how they are stored as the target of an edge (see
>> below for my usage of getEdgeTarget)." Also, check whether your isVisited()
>> method returns the correct result.
>>
>> I'm not sure where you get this idea from? This is not true. All methods
>> use the same vertex or edge objects. Furthermore, none of the methods
>> you've shown use equals/hashCode, so even if you had implemented them
>> wrong, I don't see why this would effect your result. Btw, I would
>> encourage you to have a look at the jgrapht graph source code. It is very
>> clear and gives you a good understanding of how the graph package works.
>>
>> It will not make a difference, but in your code I would find it cleaner
>> to write:
>>
>> for (SteveVertex neighborVertex : Graphs.outgoingNeighborsOf(graph,startVertex)
>>
>>              SteveDepthFirstSearch(neighborVertex);
>>
>> instead of:
>>
>> for (DefaultEdge e : graph.outgoingEdgesOf(startVertex))
>>              SteveDepthFirstSearch(graph.getEdgeTarget(e));
>>
>>
>>
>> br,
>>
>> Joris Kinable
>>
>> On Sun, Aug 9, 2015 at 3:00 PM, Steven Barkin <ste...@sa...>
>> wrote:
>>
>>> I seem to have come across a non-intuitive discrepancy between how
>>> vertexes are stored in jgrapht graphs (in this case a SimpleDirectedGraph)
>>> in the vertexSet, vs. how they are stored as the target of an edge (see
>>> below for my usage of getEdgeTarget). I had thought they were identical -
>>> i.e. they point to the same object (a SteveVertex in this case) and have
>>> the same hash code - but they seem to be located in different places
>>> somehow, per symptom below.
>>>
>>> When my code below comes across a loop, in which it encounters the
>>> original start vertex as the target of an edge, it does not show this
>>> vertex as having been visited, even though the hashCode (SteveVertex@vertex1)
>>> is identical to the first entry of the vertexSet which DOES show the vertex
>>> as having been visited.
>>>
>>> Any help would be greatly appreciated in diagnosing this.
>>>
>>> private static SimpleDirectedGraph<SteveVertex, DefaultEdge> graph;
>>> private static void SteveDepthFirstSearch(SteveVertex startVertex)
>>>  {
>>>      if (!startVertex.visited()) {
>>>          startVertex.visit();
>>>          for (DefaultEdge e : graph.outgoingEdgesOf(startVertex))
>>>              SteveDepthFirstSearch(graph.getEdgeTarget(e));
>>>
>>>          startVertex.setFinishOrder(counter);
>>>          counter++;
>>>      }
>>>
>>>  }
>>>
>>> public static void main(String[] args) {
>>>
>>>     ...
>>>
>>>     for (SteveVertex v: graph.vertexSet())
>>>         SteveDepthFirstSearch(v);
>>>
>>>     ...
>>> }
>>>
>>>
>>> This communication is confidential and subject to and governed by the
>>> confidentiality and use restrictions contained in Saama’s Electronic
>>> Communications Disclaimer. <http://www.saama.com/disclaimer>
>>>
>>>
>>>
>>>
>>> ------------------------------------------------------------------------------
>>>
>>> _______________________________________________
>>> jgrapht-users mailing list
>>> jgr...@li...
>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>
>>>
>>
>
> This communication is confidential and subject to and governed by the
> confidentiality and use restrictions contained in Saama’s Electronic
> Communications Disclaimer. <http://www.saama.com/disclaimer>
>
>
>

Re: [jgrapht-users] Is the target vertex of an edge stored differently than the same vertex in the vertex set?

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

The problem doesn't seem to be in the section of code you posted. Check
whether your visited() method actually does something.

"I seem to have come across a non-intuitive discrepancy between how
vertexes are stored in jgrapht graphs (in this case a SimpleDirectedGraph)
in the vertexSet, vs. how they are stored as the target of an edge (see
below for my usage of getEdgeTarget)." Also, check whether your isVisited()
method returns the correct result.

I'm not sure where you get this idea from? This is not true. All methods
use the same vertex or edge objects. Furthermore, none of the methods
you've shown use equals/hashCode, so even if you had implemented them
wrong, I don't see why this would effect your result. Btw, I would
encourage you to have a look at the jgrapht graph source code. It is very
clear and gives you a good understanding of how the graph package works.

It will not make a difference, but in your code I would find it cleaner to
write:

for (SteveVertex neighborVertex :
Graphs.outgoingNeighborsOf(graph,startVertex)

             SteveDepthFirstSearch(neighborVertex);

instead of:

for (DefaultEdge e : graph.outgoingEdgesOf(startVertex))
             SteveDepthFirstSearch(graph.getEdgeTarget(e));



br,

Joris Kinable

On Sun, Aug 9, 2015 at 3:00 PM, Steven Barkin <ste...@sa...>
wrote:

> I seem to have come across a non-intuitive discrepancy between how
> vertexes are stored in jgrapht graphs (in this case a SimpleDirectedGraph)
> in the vertexSet, vs. how they are stored as the target of an edge (see
> below for my usage of getEdgeTarget). I had thought they were identical -
> i.e. they point to the same object (a SteveVertex in this case) and have
> the same hash code - but they seem to be located in different places
> somehow, per symptom below.
>
> When my code below comes across a loop, in which it encounters the
> original start vertex as the target of an edge, it does not show this
> vertex as having been visited, even though the hashCode (SteveVertex@vertex1)
> is identical to the first entry of the vertexSet which DOES show the vertex
> as having been visited.
>
> Any help would be greatly appreciated in diagnosing this.
>
> private static SimpleDirectedGraph<SteveVertex, DefaultEdge> graph;
> private static void SteveDepthFirstSearch(SteveVertex startVertex)
>  {
>      if (!startVertex.visited()) {
>          startVertex.visit();
>          for (DefaultEdge e : graph.outgoingEdgesOf(startVertex))
>              SteveDepthFirstSearch(graph.getEdgeTarget(e));
>
>          startVertex.setFinishOrder(counter);
>          counter++;
>      }
>
>  }
>
> public static void main(String[] args) {
>
>     ...
>
>     for (SteveVertex v: graph.vertexSet())
>         SteveDepthFirstSearch(v);
>
>     ...
> }
>
>
> This communication is confidential and subject to and governed by the
> confidentiality and use restrictions contained in Saama’s Electronic
> Communications Disclaimer. <http://www.saama.com/disclaimer>
>
>
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] Is the target vertex of an edge stored differently than the same vertex in the vertex set?

[Steven B. <ste...@sa...>]

I seem to have come across a non-intuitive discrepancy between how vertexes
are stored in jgrapht graphs (in this case a SimpleDirectedGraph) in the
vertexSet, vs. how they are stored as the target of an edge (see below for
my usage of getEdgeTarget). I had thought they were identical - i.e. they
point to the same object (a SteveVertex in this case) and have the same
hash code - but they seem to be located in different places somehow, per
symptom below.

When my code below comes across a loop, in which it encounters the original
start vertex as the target of an edge, it does not show this vertex as
having been visited, even though the hashCode (SteveVertex@vertex1) is
identical to the first entry of the vertexSet which DOES show the vertex as
having been visited.

Any help would be greatly appreciated in diagnosing this.

private static SimpleDirectedGraph<SteveVertex, DefaultEdge> graph;
private static void SteveDepthFirstSearch(SteveVertex startVertex)
 {
     if (!startVertex.visited()) {
         startVertex.visit();
         for (DefaultEdge e : graph.outgoingEdgesOf(startVertex))
             SteveDepthFirstSearch(graph.getEdgeTarget(e));

         startVertex.setFinishOrder(counter);
         counter++;
     }

 }

public static void main(String[] args) {

    ...

    for (SteveVertex v: graph.vertexSet())
        SteveDepthFirstSearch(v);

    ...
}

-- 


This communication is confidential and subject to and governed by the 
confidentiality and use restrictions contained in Saama’s Electronic 
Communications Disclaimer. <http://www.saama.com/disclaimer>

 

Re: [jgrapht-users] How to color or label vertices using jgrapht libraries?

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

The graph libraries are generic and very well designed, so you can create
your own objects as vertices or edges. Simple (untested) example:

public class Example{
  public static void main(String[] args){
    SimpleGraph<ColorableVertex, DefaultEdge> graph=new SimpleGraph<>();
    graph.addVertex(new ColorableVertex(0));
    for(ColorableVertex v : graph.vertexSet(){
      v.setColor(Color.PINK);
    }
}

public class ColorableVertex{
  Color color;
  int id;
  public ColorableVertex(int id){ ... }
  public setColor(Color color){this.color=color;}
}

br,

Joris Kinable

On Thu, Aug 6, 2015 at 7:49 PM, Steven Barkin <ste...@sa...>
wrote:

> I am interested in writing a graph coloring algorithm using various types
> of directed and undirected graph classes provided by jgrapht. None of them
> seem to have an easy ability to do this within the graph class itself (e.g.
> DirectedSimpleGraph).
>
> My goal is to be able to traverse the graph object, and add/change various
> labels or colors to the vertices, without the need to store the vertex
> information outside the object itself - i.e. I would like to use or create
> methods such as "DirectedSimpleGraph.setColorToVertex(v, c), where v is a
> vertex. and c is the color which perhaps would be defined as an integer.
> Any leads or best practices advice would be greatly appreciated.
>
> This communication is confidential and subject to and governed by the
> confidentiality and use restrictions contained in Saama’s Electronic
> Communications Disclaimer. <http://www.saama.com/disclaimer>
>
>
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] How to color or label vertices using jgrapht libraries?

[Steven B. <ste...@sa...>]

 I am interested in writing a graph coloring algorithm using various types
of directed and undirected graph classes provided by jgrapht. None of them
seem to have an easy ability to do this within the graph class itself (e.g.
DirectedSimpleGraph).

My goal is to be able to traverse the graph object, and add/change various
labels or colors to the vertices, without the need to store the vertex
information outside the object itself - i.e. I would like to use or create
methods such as "DirectedSimpleGraph.setColorToVertex(v, c), where v is a
vertex. and c is the color which perhaps would be defined as an integer.
Any leads or best practices advice would be greatly appreciated.

-- 


This communication is confidential and subject to and governed by the 
confidentiality and use restrictions contained in Saama’s Electronic 
Communications Disclaimer. <http://www.saama.com/disclaimer>

 

Re: [jgrapht-users] JGraphT cycle algorithms

[Rushang K. <rus...@ho...>]

I guess your graph has too many cycles?

I looked at the source code for the Tarjan's cycle and it tries to find all cycles of the graph.
The algorithm is still efficient.

I think its just that the input size is very large (the # of cycles in your graph is too damn high) and the memory you provide is not enough given the input size.

Even if you have the most efficient algorithm in the world, if you provide an input size that is much larger than the resources you have it will still give an out of memory error!

I would try to give it a graph with 216 vertices but fewer # of cycles. Try using DIMACS graph examples. They have sample graphs with a fixed # of cycles and a fixed chromatic number.

> From: fee...@gm...
> Date: Tue, 4 Aug 2015 10:53:34 -0400
> To: jgr...@li...
> Subject: [jgrapht-users] JGraphT cycle algorithms
> 
> Hi there,
> 
> Has anyone used any of the cycle algorithms provided by org.jgrapht.alg.cycle (Tarjan, Johnson, etc)??? 
> 
> I’m running a code to detect cycles on a graph with 216 vertices and 1861 edges. Unfortunately, I’ve not been able to get an answer  because of a Java heap space error….it's just running out memory very quickly!!
> 
> Have you guys gone through a similar situation??? …..or just my graph is too large?? 
> 
> As far as I know Tarjan, Johnson, Tiernan, and the others are very efficient procedures.
> 
> Thanks.
> 
> 
> Phil
> ------------------------------------------------------------------------------
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
 		 	   		  

[jgrapht-users] JGraphT cycle algorithms

[<fee...@gm...>]

Hi there,

Has anyone used any of the cycle algorithms provided by org.jgrapht.alg.cycle (Tarjan, Johnson, etc)??? 

I’m running a code to detect cycles on a graph with 216 vertices and 1861 edges. Unfortunately, I’ve not been able to get an answer  because of a Java heap space error….it's just running out memory very quickly!!

Have you guys gone through a similar situation??? …..or just my graph is too large?? 

As far as I know Tarjan, Johnson, Tiernan, and the others are very efficient procedures.

Thanks.


Phil

Re: [jgrapht-users] Weighted Matching general graphs

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

As far as I know, nobody did this. It's actually rather involved. Here's a
page from a Dutch researcher on Matching implementations:
http://jorisvr.nl/maximummatching.html
I would be very happy if you implement one of the state of the art
implementations in Jgraph though :).
I'm not really up to date anymore when it comes to matching
implementations, but I remember there are 2 main flavors: one for sparse
graphs, and one for dense graphs, each having different runtime
complexities.

Joris

On Wed, Jul 29, 2015 at 10:04 PM, Ali Muhammad <ale...@ho...>
wrote:

> Hi All,
>
> Did anyone worked on weighted matching for general graphs? I could find
> the implementation of weighted matching for Bipartite graphs but not
> general graphs.  (Edmonds Blossom algorithm)
>
> Can anyone guide?
>
> Thanks,
>
> Alee
>
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] Weighted Matching general graphs

[Ali M. <ale...@ho...>]

Hi All,
Did anyone worked on weighted matching for general graphs? I could find the implementation of weighted matching for Bipartite graphs but not general graphs.  (Edmonds Blossom algorithm)
Can anyone guide?
Thanks,
Alee
 		 	   		  

Re: [jgrapht-users] Question on JGraphT

[SSovine <so...@gm...>]

I see that this is a fairly old post, but hopefully this will be useful
anyway. 

I have experimented with this same algorithm, and unfortunately I think it
may not always correctly produce the K shortest paths.

Consider a graph with the following edges (posted as .dot file for
graphviz), where we are searching for the 3-shortest paths from S to U:

graph G {
autosize=false;
size="20,12!";
rankdir=LR;

S -- U [label="1"];
S -- a1 [label="1"];
a1 -- a2 [label="1"];
a2 -- a3 [label="1"];
a3 -- a4 [label="1"];
a4 -- V [label="1"];
S -- b1 [label="3"];
b1 -- b2 [label="1"];
b2 -- b3 [label="1"];
b3 -- b4 [label="1"];
b4 -- b5 [label="1"];
b5 -- U [label="1"];
S -- c1 [label="2"];
c1 -- b2 [label="1"];

V -- U [label="1"];
V -- d1 [label="1"];
d1 -- U [label="1"];
V -- e1 [label="1"];
e1 -- e2 [label="1"];
e2 -- U [label="1"];
}

The path (S, a1, a2, a3, a4, V, U) should be one of the 3-shortest paths
from S to U. However, after four iterations, the three shortest paths stored
for V will be {(S, U, V), (S, U, d1, V), (S, U, e2, e1, V)}. This will
prevent the path {(S, a1, a2, a3, a4, V)} from being stored for V at the
fifth iteration, which will prevent it from being passed on to U at the
sixth iteration.

The problem comes from the fact that we only store simple paths for each
vertex at each iteration. If we allow paths to have loops, then we can prove
correctness for the algorithm using essentially the same method that is used
to prove correctness for Bellman-Ford.

SRS



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Re-Question-on-JGraphT-tp107942p4025031.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far

[Rushang K. <rus...@ho...>]

Thanks for the paper. I also did not know about such objects.
 
Yeah, I think you might need to implement the method on your own. If memory serves me right,  the shortest path implementation uses an iterator which cannot be modified. So changing the shortest path method to use this might be difficult.
Date: Fri, 24 Jul 2015 16:31:48 -0700
From: fle...@gm...
To: rus...@ho...
CC: jgr...@li...
Subject: Re: [jgrapht-users] pathfinding: edge weight dependent on	path-taken-so-far

Just found this paper: http://www.win.tue.nl/~jfg/articles/CSR-08-28.pdf
It seems to describe the type of graph I need but surprisingly declares: "switching
graphs ... have hardly been studied"
I'll see about modifying the shortest-path algorithm. Thanks for that suggestion.
On Fri, Jul 24, 2015 at 4:00 PM, Rushang Karia <rus...@ho...> wrote:
Yes. As I said it may allow for that situation. If you do not want it then you will need to modify the shortest path algorithm in Jgrapht and account for this. You can change the edge weights but when the already implemented algorithm is executed it will not account for something like what you are needing to achieve. It should be relatively easy to do. I hope somebody else can share some light in case my suggestion is not optimal. From: Robert Fleming [mailto:fle...@gm...] 
Sent: Friday, July 24, 2015 3:10 PM
To: Rushang Karia
Cc: jgr...@li...
Subject: Re: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far
 Hmm, does that Inf edge somehow prevent an algorithm from returning a path like L2->COM->L1? I can see that the Inf will discourage the algorithm from jumping straight from L2 to L1, but will it not still allow L2->COM->L1? On Fri, Jul 24, 2015 at 3:00 PM, Rushang Karia <rus...@ho...> wrote:Ah. This makes the mutually exclusive thing more clear. Well one solution might be to just form the complete graph adding infinity edges between terminals that cannot be connected. This will I guess ensure that you never take an invalid path. Lets consider your example below, By forming a complete graph it would look like the figure below. When you formed the graph you added an infinity edge between L1 and L2. So when the method executes it will never have a path of the form ABxxL1 L2 xx CD. It may however have a path that looks like AB L1xxCDxxL2xx Does this look like a solution. The  dotted lines represent the rest of the graph which we are not concerned about. From: Robert Fleming [mailto:fle...@gm...] 
Sent: Friday, July 24, 2015 1:35 PM
To: Rushang Karia
Cc: jgr...@li...
Subject: Re: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far Hi Rushang,

Thanks for your quick response! Maybe the traffic analogy isn't the best one.

More to the point: a SPCO/SPTT electrical switch such as https://en.wikipedia.org/wiki/Switch#/media/File:SPDT-Switch.svg

I'm representing this switch as two edges: one connecting L1 to COM and one connecting L2 to COM. Both of those edges are available for path traversal, but the switch can't be in both positions simultaneously. I.e., the switch cannot not allow L1 to connect to L2.

I was thinking of somehow using edge weights dynamically, such that if an algorithm uses the L1-COM edge, then the L2-COM edge would have a very high weight. What do you think? Thanks,Robert On Fri, Jul 24, 2015 at 1:19 PM, Rushang Karia <rus...@ho...> wrote:I guess this classifies as an online algorithm. As for mutually exclusive events, they mean independent events, I do not see how you are relating it to edge weights in a shortest path scenario? Could you please explain it so that I can be sure of my assumption? And to answer your question, you will need to implement an online algorithm for the shortest path that changes the graph as data of each vertex (stoplight) changes. Is this something what you wanted to achieve? Lets suppose you have a graph A-B-C where A-B-C and A-C. Further A-B = 1, A-C = 10, B-C=2. Obviously the shortest path is A-B-C from A to C. But lets suppose that when you were inspecting distances at point B, a stoplight turned on and now B-C = 100 because of the stoplight. Then the new shortest path is A-C at that point in time? But this means you need to backtrack all the way back to the source node. Let me know if my assumption of your problem is correct? From: Robert Fleming [mailto:fle...@gm...] 
Sent: Friday, July 24, 2015 12:15 PM
To: jgr...@li...
Subject: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far Sorry if this has already been asked/answered on the list. When finding the shortest path between two vertices in a directed graph, is there any way for the weight of an edge to be dependent on which other edges are in the path? E.g. as a way to implement mutually exclusive edges. Example: an intersection of two roads, controlled by stoplights. At any given moment, traffic is allowed through in one direction. *Because* of that, the other paths through that intersection are unavailable (i.e. very high weight). Thanks!Robert  


------------------------------------------------------------------------------
_______________________________________________
jgrapht-users mailing list
jgr...@li...
https://lists.sourceforge.net/lists/listinfo/jgrapht-users 		 	   		  

Re: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far

[Robert F. <fle...@gm...>]

Just found this paper: http://www.win.tue.nl/~jfg/articles/CSR-08-28.pdf

It seems to describe the type of graph I need but surprisingly declares:
"switching graphs ... have hardly been studied"

I'll see about modifying the shortest-path algorithm. Thanks for that
suggestion.

On Fri, Jul 24, 2015 at 4:00 PM, Rushang Karia <rus...@ho...>
wrote:

> Yes. As I said it may allow for that situation. If you do not want it then
> you will need to modify the shortest path algorithm in Jgrapht and account
> for this. You can change the edge weights but when the already implemented
> algorithm is executed it will not account for something like what you are
> needing to achieve.
>
>
>
> It should be relatively easy to do. I hope somebody else can share some
> light in case my suggestion is not optimal.
>
>
>
> *From:* Robert Fleming [mailto:fle...@gm...]
> *Sent:* Friday, July 24, 2015 3:10 PM
>
> *To:* Rushang Karia
> *Cc:* jgr...@li...
> *Subject:* Re: [jgrapht-users] pathfinding: edge weight dependent on
> path-taken-so-far
>
>
>
> Hmm, does that Inf edge somehow prevent an algorithm from returning a path
> like L2->COM->L1? I can see that the Inf will discourage the algorithm from
> jumping straight from L2 to L1, but will it not still allow L2->COM->L1?
>
>
>
> On Fri, Jul 24, 2015 at 3:00 PM, Rushang Karia <rus...@ho...>
> wrote:
>
> Ah. This makes the mutually exclusive thing more clear.
>
>
>
> Well one solution might be to just form the complete graph adding infinity
> edges between terminals that cannot be connected. This will I guess ensure
> that you never take an invalid path.
>
>
>
> Lets consider your example below, By forming a complete graph it would
> look like the figure below.
>
>
>
> When you formed the graph you added an infinity edge between L1 and L2. So
> when the method executes it will never have a path of the form ABxxL1 L2 xx
> CD. It may however have a path that looks like
>
> AB L1xxCDxxL2xx
>
>
>
> Does this look like a solution. The  dotted lines represent the rest of
> the graph which we are not concerned about.
>
>
>
> *From:* Robert Fleming [mailto:fle...@gm...]
> *Sent:* Friday, July 24, 2015 1:35 PM
> *To:* Rushang Karia
> *Cc:* jgr...@li...
> *Subject:* Re: [jgrapht-users] pathfinding: edge weight dependent on
> path-taken-so-far
>
>
>
> Hi Rushang,
>
> Thanks for your quick response! Maybe the traffic analogy isn't the best
> one.
>
> More to the point: a SPCO/SPTT electrical switch such as
> https://en.wikipedia.org/wiki/Switch#/media/File:SPDT-Switch.svg
>
> I'm representing this switch as two edges: one connecting L1 to COM and
> one connecting L2 to COM. Both of those edges are available for path
> traversal, but the switch can't be in both positions simultaneously. I.e.,
> the switch cannot not allow L1 to connect to L2.
>
> I was thinking of somehow using edge weights dynamically, such that if an
> algorithm uses the L1-COM edge, then the L2-COM edge would have a very high
> weight.
>
>
>
> What do you think?
>
>
>
> Thanks,
>
> Robert
>
>
>
> On Fri, Jul 24, 2015 at 1:19 PM, Rushang Karia <rus...@ho...>
> wrote:
>
> I guess this classifies as an online algorithm. As for mutually exclusive
> events, they mean independent events, I do not see how you are relating it
> to edge weights in a shortest path scenario? Could you please explain it so
> that I can be sure of my assumption?
>
>
>
> And to answer your question, you will need to implement an online
> algorithm for the shortest path that changes the graph as data of each
> vertex (stoplight) changes. Is this something what you wanted to achieve?
>
>
>
> Lets suppose you have a graph A-B-C where A-B-C and A-C. Further A-B = 1,
> A-C = 10, B-C=2. Obviously the shortest path is A-B-C from A to C. But lets
> suppose that when you were inspecting distances at point B, a stoplight
> turned on and now B-C = 100 because of the stoplight. Then the new shortest
> path is A-C at that point in time? But this means you need to backtrack all
> the way back to the source node.
>
>
>
> Let me know if my assumption of your problem is correct?
>
>
>
> *From:* Robert Fleming [mailto:fle...@gm...]
> *Sent:* Friday, July 24, 2015 12:15 PM
> *To:* jgr...@li...
> *Subject:* [jgrapht-users] pathfinding: edge weight dependent on
> path-taken-so-far
>
>
>
> Sorry if this has already been asked/answered on the list.
>
>
>
> When finding the shortest path between two vertices in a directed graph,
> is there any way for the weight of an edge to be dependent on which other
> edges are in the path? E.g. as a way to implement mutually exclusive edges.
>
>
>
> Example: an intersection of two roads, controlled by stoplights. At any
> given moment, traffic is allowed through in one direction. *Because* of
> that, the other paths through that intersection are unavailable (i.e. very
> high weight).
>
>
>
> Thanks!
>
> Robert
>
>
>
>
>

Re: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far

[Rushang K. <rus...@ho...>]

Yes. As I said it may allow for that situation. If you do not want it then you will need to modify the shortest path algorithm in Jgrapht and account for this. You can change the edge weights but when the already implemented algorithm is executed it will not account for something like what you are needing to achieve.

 

It should be relatively easy to do. I hope somebody else can share some light in case my suggestion is not optimal.

 

From: Robert Fleming [mailto:fle...@gm...] 
Sent: Friday, July 24, 2015 3:10 PM
To: Rushang Karia
Cc: jgr...@li...
Subject: Re: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far

 

Hmm, does that Inf edge somehow prevent an algorithm from returning a path like L2->COM->L1? I can see that the Inf will discourage the algorithm from jumping straight from L2 to L1, but will it not still allow L2->COM->L1?

 

On Fri, Jul 24, 2015 at 3:00 PM, Rushang Karia <rus...@ho...> wrote:

Ah. This makes the mutually exclusive thing more clear.

 

Well one solution might be to just form the complete graph adding infinity edges between terminals that cannot be connected. This will I guess ensure that you never take an invalid path.

 

Lets consider your example below, By forming a complete graph it would look like the figure below.



 

When you formed the graph you added an infinity edge between L1 and L2. So when the method executes it will never have a path of the form ABxxL1 L2 xx CD. It may however have a path that looks like 

AB L1xxCDxxL2xx

 

Does this look like a solution. The  dotted lines represent the rest of the graph which we are not concerned about.

 

From: Robert Fleming [mailto:fle...@gm...] 
Sent: Friday, July 24, 2015 1:35 PM
To: Rushang Karia
Cc: jgr...@li...
Subject: Re: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far

 

Hi Rushang,

Thanks for your quick response! Maybe the traffic analogy isn't the best one.

More to the point: a SPCO/SPTT electrical switch such as https://en.wikipedia.org/wiki/Switch#/media/File:SPDT-Switch.svg

I'm representing this switch as two edges: one connecting L1 to COM and one connecting L2 to COM. Both of those edges are available for path traversal, but the switch can't be in both positions simultaneously. I.e., the switch cannot not allow L1 to connect to L2.

I was thinking of somehow using edge weights dynamically, such that if an algorithm uses the L1-COM edge, then the L2-COM edge would have a very high weight.

 

What do you think?

 

Thanks,

Robert

 

On Fri, Jul 24, 2015 at 1:19 PM, Rushang Karia <rus...@ho...> wrote:

I guess this classifies as an online algorithm. As for mutually exclusive events, they mean independent events, I do not see how you are relating it to edge weights in a shortest path scenario? Could you please explain it so that I can be sure of my assumption?

 

And to answer your question, you will need to implement an online algorithm for the shortest path that changes the graph as data of each vertex (stoplight) changes. Is this something what you wanted to achieve?

 

Lets suppose you have a graph A-B-C where A-B-C and A-C. Further A-B = 1, A-C = 10, B-C=2. Obviously the shortest path is A-B-C from A to C. But lets suppose that when you were inspecting distances at point B, a stoplight turned on and now B-C = 100 because of the stoplight. Then the new shortest path is A-C at that point in time? But this means you need to backtrack all the way back to the source node.

 

Let me know if my assumption of your problem is correct?

 

From: Robert Fleming [mailto:fle...@gm...] 
Sent: Friday, July 24, 2015 12:15 PM
To: jgr...@li...
Subject: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far

 

Sorry if this has already been asked/answered on the list.

 

When finding the shortest path between two vertices in a directed graph, is there any way for the weight of an edge to be dependent on which other edges are in the path? E.g. as a way to implement mutually exclusive edges.

 

Example: an intersection of two roads, controlled by stoplights. At any given moment, traffic is allowed through in one direction. *Because* of that, the other paths through that intersection are unavailable (i.e. very high weight).

 

Thanks!

Robert

 

 

Re: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far

[Robert F. <fle...@gm...>]

Hmm, does that Inf edge somehow prevent an algorithm from returning a path
like L2->COM->L1? I can see that the Inf will discourage the algorithm from
jumping straight from L2 to L1, but will it not still allow L2->COM->L1?

On Fri, Jul 24, 2015 at 3:00 PM, Rushang Karia <rus...@ho...>
wrote:

> Ah. This makes the mutually exclusive thing more clear.
>
>
>
> Well one solution might be to just form the complete graph adding infinity
> edges between terminals that cannot be connected. This will I guess ensure
> that you never take an invalid path.
>
>
>
> Lets consider your example below, By forming a complete graph it would
> look like the figure below.
>
>
>
> When you formed the graph you added an infinity edge between L1 and L2. So
> when the method executes it will never have a path of the form ABxxL1 L2 xx
> CD. It may however have a path that looks like
>
> AB L1xxCDxxL2xx
>
>
>
> Does this look like a solution. The  dotted lines represent the rest of
> the graph which we are not concerned about.
>
>
>
> *From:* Robert Fleming [mailto:fle...@gm...]
> *Sent:* Friday, July 24, 2015 1:35 PM
> *To:* Rushang Karia
> *Cc:* jgr...@li...
> *Subject:* Re: [jgrapht-users] pathfinding: edge weight dependent on
> path-taken-so-far
>
>
>
> Hi Rushang,
>
> Thanks for your quick response! Maybe the traffic analogy isn't the best
> one.
>
> More to the point: a SPCO/SPTT electrical switch such as
> https://en.wikipedia.org/wiki/Switch#/media/File:SPDT-Switch.svg
>
> I'm representing this switch as two edges: one connecting L1 to COM and
> one connecting L2 to COM. Both of those edges are available for path
> traversal, but the switch can't be in both positions simultaneously. I.e.,
> the switch cannot not allow L1 to connect to L2.
>
> I was thinking of somehow using edge weights dynamically, such that if an
> algorithm uses the L1-COM edge, then the L2-COM edge would have a very high
> weight.
>
>
>
> What do you think?
>
>
>
> Thanks,
>
> Robert
>
>
>
> On Fri, Jul 24, 2015 at 1:19 PM, Rushang Karia <rus...@ho...>
> wrote:
>
> I guess this classifies as an online algorithm. As for mutually exclusive
> events, they mean independent events, I do not see how you are relating it
> to edge weights in a shortest path scenario? Could you please explain it so
> that I can be sure of my assumption?
>
>
>
> And to answer your question, you will need to implement an online
> algorithm for the shortest path that changes the graph as data of each
> vertex (stoplight) changes. Is this something what you wanted to achieve?
>
>
>
> Lets suppose you have a graph A-B-C where A-B-C and A-C. Further A-B = 1,
> A-C = 10, B-C=2. Obviously the shortest path is A-B-C from A to C. But lets
> suppose that when you were inspecting distances at point B, a stoplight
> turned on and now B-C = 100 because of the stoplight. Then the new shortest
> path is A-C at that point in time? But this means you need to backtrack all
> the way back to the source node.
>
>
>
> Let me know if my assumption of your problem is correct?
>
>
>
> *From:* Robert Fleming [mailto:fle...@gm...]
> *Sent:* Friday, July 24, 2015 12:15 PM
> *To:* jgr...@li...
> *Subject:* [jgrapht-users] pathfinding: edge weight dependent on
> path-taken-so-far
>
>
>
> Sorry if this has already been asked/answered on the list.
>
>
>
> When finding the shortest path between two vertices in a directed graph,
> is there any way for the weight of an edge to be dependent on which other
> edges are in the path? E.g. as a way to implement mutually exclusive edges.
>
>
>
> Example: an intersection of two roads, controlled by stoplights. At any
> given moment, traffic is allowed through in one direction. *Because* of
> that, the other paths through that intersection are unavailable (i.e. very
> high weight).
>
>
>
> Thanks!
>
> Robert
>
>
>

Re: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far

[Rushang K. <rus...@ho...>]

Ah. This makes the mutually exclusive thing more clear.

 

Well one solution might be to just form the complete graph adding infinity edges between terminals that cannot be connected. This will I guess ensure that you never take an invalid path.

 

Lets consider your example below, By forming a complete graph it would look like the figure below.

cid:image001.png@01D0C621.7A212F80

 

When you formed the graph you added an infinity edge between L1 and L2. So when the method executes it will never have a path of the form ABxxL1 L2 xx CD. It may however have a path that looks like 

AB L1xxCDxxL2xx

 

Does this look like a solution. The  dotted lines represent the rest of the graph which we are not concerned about.

 

 

From: Robert Fleming [mailto:fle...@gm...] 
Sent: Friday, July 24, 2015 1:35 PM
To: Rushang Karia
Cc: jgr...@li...
Subject: Re: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far

 

Hi Rushang,

Thanks for your quick response! Maybe the traffic analogy isn't the best one.

More to the point: a SPCO/SPTT electrical switch such as https://en.wikipedia.org/wiki/Switch#/media/File:SPDT-Switch.svg

I'm representing this switch as two edges: one connecting L1 to COM and one connecting L2 to COM. Both of those edges are available for path traversal, but the switch can't be in both positions simultaneously. I.e., the switch cannot not allow L1 to connect to L2.

I was thinking of somehow using edge weights dynamically, such that if an algorithm uses the L1-COM edge, then the L2-COM edge would have a very high weight.

 

What do you think?

 

Thanks,

Robert

 

On Fri, Jul 24, 2015 at 1:19 PM, Rushang Karia <rus...@ho...> wrote:

I guess this classifies as an online algorithm. As for mutually exclusive events, they mean independent events, I do not see how you are relating it to edge weights in a shortest path scenario? Could you please explain it so that I can be sure of my assumption?

 

And to answer your question, you will need to implement an online algorithm for the shortest path that changes the graph as data of each vertex (stoplight) changes. Is this something what you wanted to achieve?

 

Lets suppose you have a graph A-B-C where A-B-C and A-C. Further A-B = 1, A-C = 10, B-C=2. Obviously the shortest path is A-B-C from A to C. But lets suppose that when you were inspecting distances at point B, a stoplight turned on and now B-C = 100 because of the stoplight. Then the new shortest path is A-C at that point in time? But this means you need to backtrack all the way back to the source node.

 

Let me know if my assumption of your problem is correct?

 

From: Robert Fleming [mailto:fle...@gm...] 
Sent: Friday, July 24, 2015 12:15 PM
To: jgr...@li...
Subject: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far

 

Sorry if this has already been asked/answered on the list.

 

When finding the shortest path between two vertices in a directed graph, is there any way for the weight of an edge to be dependent on which other edges are in the path? E.g. as a way to implement mutually exclusive edges.

 

Example: an intersection of two roads, controlled by stoplights. At any given moment, traffic is allowed through in one direction. *Because* of that, the other paths through that intersection are unavailable (i.e. very high weight).

 

Thanks!

Robert

 

Re: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far

[Robert F. <fle...@gm...>]

Hi Rushang,

Thanks for your quick response! Maybe the traffic analogy isn't the best
one.

More to the point: a SPCO/SPTT electrical switch such as
https://en.wikipedia.org/wiki/Switch#/media/File:SPDT-Switch.svg

I'm representing this switch as two edges: one connecting L1 to COM and one
connecting L2 to COM. Both of those edges are available for path traversal,
but the switch can't be in both positions simultaneously. I.e., the switch
cannot not allow L1 to connect to L2.

I was thinking of somehow using edge weights dynamically, such that if an
algorithm uses the L1-COM edge, then the L2-COM edge would have a very high
weight.

What do you think?

Thanks,
Robert

On Fri, Jul 24, 2015 at 1:19 PM, Rushang Karia <rus...@ho...>
wrote:

> I guess this classifies as an online algorithm. As for mutually exclusive
> events, they mean independent events, I do not see how you are relating it
> to edge weights in a shortest path scenario? Could you please explain it so
> that I can be sure of my assumption?
>
>
>
> And to answer your question, you will need to implement an online
> algorithm for the shortest path that changes the graph as data of each
> vertex (stoplight) changes. Is this something what you wanted to achieve?
>
>
>
> Lets suppose you have a graph A-B-C where A-B-C and A-C. Further A-B = 1,
> A-C = 10, B-C=2. Obviously the shortest path is A-B-C from A to C. But lets
> suppose that when you were inspecting distances at point B, a stoplight
> turned on and now B-C = 100 because of the stoplight. Then the new shortest
> path is A-C at that point in time? But this means you need to backtrack all
> the way back to the source node.
>
>
>
> Let me know if my assumption of your problem is correct?
>
>
>
> *From:* Robert Fleming [mailto:fle...@gm...]
> *Sent:* Friday, July 24, 2015 12:15 PM
> *To:* jgr...@li...
> *Subject:* [jgrapht-users] pathfinding: edge weight dependent on
> path-taken-so-far
>
>
>
> Sorry if this has already been asked/answered on the list.
>
>
>
> When finding the shortest path between two vertices in a directed graph,
> is there any way for the weight of an edge to be dependent on which other
> edges are in the path? E.g. as a way to implement mutually exclusive edges.
>
>
>
> Example: an intersection of two roads, controlled by stoplights. At any
> given moment, traffic is allowed through in one direction. *Because* of
> that, the other paths through that intersection are unavailable (i.e. very
> high weight).
>
>
>
> Thanks!
>
> Robert
>

[jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far

[Robert F. <fle...@gm...>]

Sorry if this has already been asked/answered on the list.

When finding the shortest path between two vertices in a directed graph, is
there any way for the weight of an edge to be dependent on which other
edges are in the path? E.g. as a way to implement mutually exclusive edges.

Example: an intersection of two roads, controlled by stoplights. At any
given moment, traffic is allowed through in one direction. *Because* of
that, the other paths through that intersection are unavailable (i.e. very
high weight).

Thanks!
Robert

Re: [jgrapht-users] ismorphism

[Rushang K. <rus...@ho...>]

My bad. Thanks for letting me know.
 
Date: Sun, 12 Jul 2015 14:22:06 -0700
From: js...@gm...
To: rus...@ho...
CC: jgr...@li...; fab...@un...
Subject: Re: [jgrapht-users] ismorphism

Isn't there one already?
http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/vf2_sub_graph_iso.html

On Sun, Jul 12, 2015 at 2:21 PM, Rushang Karia <rus...@ho...> wrote:



Thanks Fabian!!
 
Are you going to contributing a C++ port in Boost as well?
 
Date: Sun, 12 Jul 2015 14:19:00 -0700
From: js...@gm...
To: jgr...@li...
CC: fab...@un...
Subject: [jgrapht-users] ismorphism

Hey folks,
Fabian Späh and his colleagues at the University of Constance have contributed an implementation of the VF2 graph isomorphism and subgraph isomorphism matching algorithm.
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1323804

I've merged it into trunk.  I've also deleted the old isomorphism implementation from the experimental package.  Although the world still waits in breathless anticipation to learn whether there exists a guaranteed polynomial-time solution for isomorphism over arbitrary graphs, the VF2 algorithm should beat the old brute-force implementation in just about any case you can think of.
Thanks Fabian!
JVS



------------------------------------------------------------------------------
Don't Limit Your Business. Reach for the Cloud.
GigeNET's Cloud Solutions provide you with the tools and support that
you need to offload your IT needs and focus on growing your business.
Configured For All Businesses. Start Your Cloud Today.
https://www.gigenetcloud.com/
_______________________________________________
jgrapht-users mailing list
jgr...@li...
https://lists.sourceforge.net/lists/listinfo/jgrapht-users 		 	   		  



------------------------------------------------------------------------------
Don't Limit Your Business. Reach for the Cloud.
GigeNET's Cloud Solutions provide you with the tools and support that
you need to offload your IT needs and focus on growing your business.
Configured For All Businesses. Start Your Cloud Today.
https://www.gigenetcloud.com/
_______________________________________________
jgrapht-users mailing list
jgr...@li...
https://lists.sourceforge.net/lists/listinfo/jgrapht-users 		 	   		  

Re: [jgrapht-users] ismorphism

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

Isn't there one already?

http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/vf2_sub_graph_iso.html

On Sun, Jul 12, 2015 at 2:21 PM, Rushang Karia <rus...@ho...>
wrote:

> Thanks Fabian!!
>
> Are you going to contributing a C++ port in Boost as well?
>
> ------------------------------
> Date: Sun, 12 Jul 2015 14:19:00 -0700
> From: js...@gm...
> To: jgr...@li...
> CC: fab...@un...
> Subject: [jgrapht-users] ismorphism
>
>
> Hey folks,
>
> Fabian Späh and his colleagues at the University of Constance have
> contributed an implementation of the VF2 graph isomorphism and subgraph
> isomorphism matching algorithm.
>
> http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1323804
>
> I've merged it into trunk.  I've also deleted the old isomorphism
> implementation from the experimental package.  Although the world still
> waits in breathless anticipation to learn whether there exists a guaranteed
> polynomial-time solution for isomorphism over arbitrary graphs, the VF2
> algorithm should beat the old brute-force implementation in just about any
> case you can think of.
>
> Thanks Fabian!
>
> JVS
>
>
>
> ------------------------------------------------------------------------------
> Don't Limit Your Business. Reach for the Cloud. GigeNET's Cloud Solutions
> provide you with the tools and support that you need to offload your IT
> needs and focus on growing your business. Configured For All Businesses.
> Start Your Cloud Today. https://www.gigenetcloud.com/
> _______________________________________________ jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>