jgrapht-users — JGraphT user list.

Re: [jgrapht-users] Usage question

[David J. <djo...@gm...>]

Thank you very much!

It really helps to be looking at the right algorithm, and finding the
tutorials with code samples has been huge benefit.

On Fri, Oct 16, 2020 at 6:25 AM Dimitrios Michail <
dim...@gm...> wrote:

> Hi David,
>
> If you are trying to compute shortest paths, you should look in the
> `org/jgrapht/alg/shortestpath` package where class `DijkstraShortestPath`
> provides this algorithm.
> Similarly you can use `org.jgrapht.traverse.ClosestFirstIterator` to do
> the same thing but with an iterator API.
>
> Generally we have a lot of examples in the test classes. So assuming that
> you first somehow find the algorithm you want to use, its test class will
> contain a lot of examples.
>
> Regards,
> Dimitrios
>
>
> On Thu, Oct 15, 2020 at 11:26 PM David Johnson <djo...@gm...>
> wrote:
>
>> Hi everyone,
>>
>> Thank you in advance.
>>
>> i am trying to understand how to use this library to accomplish what I
>> believe to be a basic task, but i am completely lost without some tutorials.
>>
>> I am loading a graph of nodes and edges (tables and relationships), and
>> trying to pull back the shortest path for navigating from a beginning node
>> to a terminating node. I see Dijkstra's least-cost algorithm is built into
>> the CapacityScalingMinimumCostFlow class, so I believe this is the correct
>> component to be using to navigate the graph.
>>
>> My difficulty is that the entirety of the library documentation appears
>> to be written for the mathematician, so I don't speak the jargon, and have
>> not been able to leverage any pre-existing code samples to understand the
>> class and its setup requirements.
>>
>> Assuming I have built the graph correctly from the backing datastore, I
>> expected that this should have navigated the graph and returned the shorted
>> path in the flow variable for unmarshalling. However, it fails with the not
>> very informative o the lay person message "Total node supply isn't equal to
>> 0".  Any hints, tutorial references, or sample code would be greatly
>> appreciated. I suspect that I don't understand the nodeSupplies() function.
>>
>> Thank you in advance,
>>
>> *Code Snip:*
>>
>>
>> private void findLeastCostPath(Graph<TableMetadata,
>> ColumnMetadataGraphEdge> graph, TableMetadata identityTable,
>> Map<Long, TableMetadata> tablesToLink) {
>>
>> // return +1 for origin, -1 for target, 0 for anything intermediate
>> Function<TableMetadata, Integer> nodeSupplies = (TableMetadata t) -> {
>> if (t == identityTable) {
>> return 1;
>> } else if (tablesToLink.containsKey(t.getId())) {
>> return -1;
>> } else {
>> return 0;
>> }
>> };
>>
>> Function<ColumnMetadataGraphEdge, Integer> arcCapacityLowerBounds =
>> (ColumnMetadataGraphEdge t) -> {
>> return 0;
>> };
>>
>> Function<ColumnMetadataGraphEdge, Integer> arcCapacityUpperBounds =
>> (ColumnMetadataGraphEdge t) -> {
>> return CapacityScalingMinimumCostFlow.CAP_INF;
>> };
>>
>> MinimumCostFlowProblem<TableMetadata, ColumnMetadataGraphEdge>
>> flowProblem = new MinimumCostFlowProblemImpl<TableMetadata,
>> ColumnMetadataGraphEdge>(
>> graph, nodeSupplies, arcCapacityLowerBounds, arcCapacityUpperBounds);
>>
>> CapacityScalingMinimumCostFlow<TableMetadata, ColumnMetadataGraphEdge>
>> minCostflow = new CapacityScalingMinimumCostFlow<>();
>> MinimumCostFlow<ColumnMetadataGraphEdge> flow =
>> minCostflow.getMinimumCostFlow(flowProblem);
>>
>> logger.debug(flow.getFlowMap().toString());
>>
>> }
>>
>>
>>
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>

Re: [jgrapht-users] Usage question

[Dimitrios M. <dim...@gm...>]

Hi David,

If you are trying to compute shortest paths, you should look in the
`org/jgrapht/alg/shortestpath` package where class `DijkstraShortestPath`
provides this algorithm.
Similarly you can use `org.jgrapht.traverse.ClosestFirstIterator` to do the
same thing but with an iterator API.

Generally we have a lot of examples in the test classes. So assuming that
you first somehow find the algorithm you want to use, its test class will
contain a lot of examples.

Regards,
Dimitrios


On Thu, Oct 15, 2020 at 11:26 PM David Johnson <djo...@gm...>
wrote:

> Hi everyone,
>
> Thank you in advance.
>
> i am trying to understand how to use this library to accomplish what I
> believe to be a basic task, but i am completely lost without some tutorials.
>
> I am loading a graph of nodes and edges (tables and relationships), and
> trying to pull back the shortest path for navigating from a beginning node
> to a terminating node. I see Dijkstra's least-cost algorithm is built into
> the CapacityScalingMinimumCostFlow class, so I believe this is the correct
> component to be using to navigate the graph.
>
> My difficulty is that the entirety of the library documentation appears to
> be written for the mathematician, so I don't speak the jargon, and have not
> been able to leverage any pre-existing code samples to understand the class
> and its setup requirements.
>
> Assuming I have built the graph correctly from the backing datastore, I
> expected that this should have navigated the graph and returned the shorted
> path in the flow variable for unmarshalling. However, it fails with the not
> very informative o the lay person message "Total node supply isn't equal to
> 0".  Any hints, tutorial references, or sample code would be greatly
> appreciated. I suspect that I don't understand the nodeSupplies() function.
>
> Thank you in advance,
>
> *Code Snip:*
>
>
> private void findLeastCostPath(Graph<TableMetadata,
> ColumnMetadataGraphEdge> graph, TableMetadata identityTable,
> Map<Long, TableMetadata> tablesToLink) {
>
> // return +1 for origin, -1 for target, 0 for anything intermediate
> Function<TableMetadata, Integer> nodeSupplies = (TableMetadata t) -> {
> if (t == identityTable) {
> return 1;
> } else if (tablesToLink.containsKey(t.getId())) {
> return -1;
> } else {
> return 0;
> }
> };
>
> Function<ColumnMetadataGraphEdge, Integer> arcCapacityLowerBounds =
> (ColumnMetadataGraphEdge t) -> {
> return 0;
> };
>
> Function<ColumnMetadataGraphEdge, Integer> arcCapacityUpperBounds =
> (ColumnMetadataGraphEdge t) -> {
> return CapacityScalingMinimumCostFlow.CAP_INF;
> };
>
> MinimumCostFlowProblem<TableMetadata, ColumnMetadataGraphEdge> flowProblem
> = new MinimumCostFlowProblemImpl<TableMetadata, ColumnMetadataGraphEdge>(
> graph, nodeSupplies, arcCapacityLowerBounds, arcCapacityUpperBounds);
>
> CapacityScalingMinimumCostFlow<TableMetadata, ColumnMetadataGraphEdge>
> minCostflow = new CapacityScalingMinimumCostFlow<>();
> MinimumCostFlow<ColumnMetadataGraphEdge> flow =
> minCostflow.getMinimumCostFlow(flowProblem);
>
> logger.debug(flow.getFlowMap().toString());
>
> }
>
>
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] Usage question

[David J. <djo...@gm...>]

Hi everyone,

Thank you in advance.

i am trying to understand how to use this library to accomplish what I
believe to be a basic task, but i am completely lost without some tutorials.

I am loading a graph of nodes and edges (tables and relationships), and
trying to pull back the shortest path for navigating from a beginning node
to a terminating node. I see Dijkstra's least-cost algorithm is built into
the CapacityScalingMinimumCostFlow class, so I believe this is the correct
component to be using to navigate the graph.

My difficulty is that the entirety of the library documentation appears to
be written for the mathematician, so I don't speak the jargon, and have not
been able to leverage any pre-existing code samples to understand the class
and its setup requirements.

Assuming I have built the graph correctly from the backing datastore, I
expected that this should have navigated the graph and returned the shorted
path in the flow variable for unmarshalling. However, it fails with the not
very informative o the lay person message "Total node supply isn't equal to
0".  Any hints, tutorial references, or sample code would be greatly
appreciated. I suspect that I don't understand the nodeSupplies() function.

Thank you in advance,

*Code Snip:*


private void findLeastCostPath(Graph<TableMetadata,
ColumnMetadataGraphEdge> graph, TableMetadata identityTable,
Map<Long, TableMetadata> tablesToLink) {

// return +1 for origin, -1 for target, 0 for anything intermediate
Function<TableMetadata, Integer> nodeSupplies = (TableMetadata t) -> {
if (t == identityTable) {
return 1;
} else if (tablesToLink.containsKey(t.getId())) {
return -1;
} else {
return 0;
}
};

Function<ColumnMetadataGraphEdge, Integer> arcCapacityLowerBounds =
(ColumnMetadataGraphEdge t) -> {
return 0;
};

Function<ColumnMetadataGraphEdge, Integer> arcCapacityUpperBounds =
(ColumnMetadataGraphEdge t) -> {
return CapacityScalingMinimumCostFlow.CAP_INF;
};

MinimumCostFlowProblem<TableMetadata, ColumnMetadataGraphEdge> flowProblem
= new MinimumCostFlowProblemImpl<TableMetadata, ColumnMetadataGraphEdge>(
graph, nodeSupplies, arcCapacityLowerBounds, arcCapacityUpperBounds);

CapacityScalingMinimumCostFlow<TableMetadata, ColumnMetadataGraphEdge>
minCostflow = new CapacityScalingMinimumCostFlow<>();
MinimumCostFlow<ColumnMetadataGraphEdge> flow =
minCostflow.getMinimumCostFlow(flowProblem);

logger.debug(flow.getFlowMap().toString());

}

Re: [jgrapht-users] ContractionHierarchyBidirectionalDijkstra with pgrServer

[Mario B. <mar...@gm...>]

Oh wow, it is fast!

Totally worth using even with the high startup cost. Again I used a very
dense road network to obtain the results below and the returned paths of
both chbDijkstra and Dijkstra are exactly the same:

1.2 km search : 0m0.039s (chbDijkstra) : 0m0.041s (Dijkstra)

 15 km search : 0m0.047s (chbDijkstra) : 0m0.211s (Dijkstra)

 52 km search : 0m0.052s (chbDijkstra) : 0m1.265s (Dijkstra)

109 km search : 0m0.077s (chbDijkstra) : 0m2.020s (Dijkstra)

175 km search : 0m0.083s (chbDijkstra) : 0m2.252s (Dijkstra)

229 km search : 0m0.099s (chbDijkstra) : 0m2.289s (Dijkstra)


Thanks.

On Thu, Oct 8, 2020 at 8:16 PM Dimitrios Michail <
dim...@gm...> wrote:

> Please share your findings. I am rather curious about the speedup. I have
> seen some papers with these techniques
> where each query was more than 2 (if not 3) orders of magnitude faster
> than plain Dijkstra.
>
> Best,
> Dimitrios
>
>
>
> On Wed, Oct 7, 2020 at 5:36 PM Mario Basa <mar...@gm...> wrote:
>
>> But at 13 minutes loading time, the preprocessing is very expensive
>> considering that the entire graph is created in just around 3 minutes. Will
>> test and compare it though with basic Dijkstra to see if it is worth the
>> cost.
>>
>> Thanks,
>>
>> Mario.
>>
>>
>> On Wed, Oct 7, 2020 at 6:45 PM Dimitrios Michail <
>> dim...@gm...> wrote:
>>
>>> Indeed John is right. This is a preprocessing technique which has the
>>> drawback of consuming memory, but is very fast when querying.
>>> Not sure whether the preprocessing is lazily triggered but you should
>>> keep the same instance around, as long as the graph
>>> does not change.
>>>
>>>
>>>
>>> On Wed, Oct 7, 2020 at 6:01 AM John Sichi <js...@gm...> wrote:
>>>
>>>> Does that include the time to precompute the contraction hierarchy?  My
>>>> understanding is that building the hierarchy is a cost to be paid once up
>>>> front, and then after that you can use it to answer queries over and over
>>>> (as long as the graph doesn't change).
>>>>
>>>> On Sun, Oct 4, 2020 at 3:35 PM Mario Basa <mar...@gm...> wrote:
>>>>
>>>>> Hello, I'm new here.
>>>>>
>>>>> I just tried ContractionHierarchyBidirectionalDijkstra and it seems it
>>>>> is more suited for sparse graphs. I got this result with a very dense
>>>>> graph:
>>>>>
>>>>> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
>>>>> http://localhost:8080/pgrServer/api/node/chbDijkstra?source=1015422&target=979173"
>>>>> -H "accept: application/json" > response_1601788501820.json
>>>>>
>>>>>
>>>>> real 13m58.587s
>>>>>
>>>>> user 0m0.117s
>>>>>
>>>>> sys 0m0.168s
>>>>>
>>>>>
>>>>> while I got this result from Dijkstra with the same graph:
>>>>>
>>>>> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
>>>>> http://localhost:8080/pgrServer/api/node/dijkstra?source=1015422&target=979173"
>>>>> -H "accept: application/json" > response_1601788501820.json
>>>>>
>>>>>
>>>>> real 0m0.091s
>>>>>
>>>>> user 0m0.010s
>>>>>
>>>>> sys 0m0.010s
>>>>>
>>>>> and this from A-Star again with the same graph:
>>>>>
>>>>> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
>>>>> http://localhost:8080/pgrServer/api/node/astar?source=1015422&target=979173"
>>>>> -H "accept: application/json" > response_1601788501820.json
>>>>>
>>>>>
>>>>> real 0m0.058s
>>>>>
>>>>> user 0m0.010s
>>>>>
>>>>> sys 0m0.011s
>>>>>
>>>>> Regards,
>>>>>
>>>>> Mario.
>>>>>
>>>>> _______________________________________________
>>>>> jgrapht-users mailing list
>>>>> jgr...@li...
>>>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>>>
>>>> _______________________________________________
>>>> jgrapht-users mailing list
>>>> jgr...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>>
>>>

Re: [jgrapht-users] ContractionHierarchyBidirectionalDijkstra with pgrServer

[Dimitrios M. <dim...@gm...>]

Please share your findings. I am rather curious about the speedup. I have
seen some papers with these techniques
where each query was more than 2 (if not 3) orders of magnitude faster than
plain Dijkstra.

Best,
Dimitrios



On Wed, Oct 7, 2020 at 5:36 PM Mario Basa <mar...@gm...> wrote:

> But at 13 minutes loading time, the preprocessing is very expensive
> considering that the entire graph is created in just around 3 minutes. Will
> test and compare it though with basic Dijkstra to see if it is worth the
> cost.
>
> Thanks,
>
> Mario.
>
>
> On Wed, Oct 7, 2020 at 6:45 PM Dimitrios Michail <
> dim...@gm...> wrote:
>
>> Indeed John is right. This is a preprocessing technique which has the
>> drawback of consuming memory, but is very fast when querying.
>> Not sure whether the preprocessing is lazily triggered but you should
>> keep the same instance around, as long as the graph
>> does not change.
>>
>>
>>
>> On Wed, Oct 7, 2020 at 6:01 AM John Sichi <js...@gm...> wrote:
>>
>>> Does that include the time to precompute the contraction hierarchy?  My
>>> understanding is that building the hierarchy is a cost to be paid once up
>>> front, and then after that you can use it to answer queries over and over
>>> (as long as the graph doesn't change).
>>>
>>> On Sun, Oct 4, 2020 at 3:35 PM Mario Basa <mar...@gm...> wrote:
>>>
>>>> Hello, I'm new here.
>>>>
>>>> I just tried ContractionHierarchyBidirectionalDijkstra and it seems it
>>>> is more suited for sparse graphs. I got this result with a very dense
>>>> graph:
>>>>
>>>> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
>>>> http://localhost:8080/pgrServer/api/node/chbDijkstra?source=1015422&target=979173"
>>>> -H "accept: application/json" > response_1601788501820.json
>>>>
>>>>
>>>> real 13m58.587s
>>>>
>>>> user 0m0.117s
>>>>
>>>> sys 0m0.168s
>>>>
>>>>
>>>> while I got this result from Dijkstra with the same graph:
>>>>
>>>> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
>>>> http://localhost:8080/pgrServer/api/node/dijkstra?source=1015422&target=979173"
>>>> -H "accept: application/json" > response_1601788501820.json
>>>>
>>>>
>>>> real 0m0.091s
>>>>
>>>> user 0m0.010s
>>>>
>>>> sys 0m0.010s
>>>>
>>>> and this from A-Star again with the same graph:
>>>>
>>>> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
>>>> http://localhost:8080/pgrServer/api/node/astar?source=1015422&target=979173"
>>>> -H "accept: application/json" > response_1601788501820.json
>>>>
>>>>
>>>> real 0m0.058s
>>>>
>>>> user 0m0.010s
>>>>
>>>> sys 0m0.011s
>>>>
>>>> Regards,
>>>>
>>>> Mario.
>>>>
>>>> _______________________________________________
>>>> jgrapht-users mailing list
>>>> jgr...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>>
>>> _______________________________________________
>>> jgrapht-users mailing list
>>> jgr...@li...
>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>
>>

Re: [jgrapht-users] ContractionHierarchyBidirectionalDijkstra with pgrServer

[Mario B. <mar...@gm...>]

But at 13 minutes loading time, the preprocessing is very expensive
considering that the entire graph is created in just around 3 minutes. Will
test and compare it though with basic Dijkstra to see if it is worth the
cost.

Thanks,

Mario.


On Wed, Oct 7, 2020 at 6:45 PM Dimitrios Michail <
dim...@gm...> wrote:

> Indeed John is right. This is a preprocessing technique which has the
> drawback of consuming memory, but is very fast when querying.
> Not sure whether the preprocessing is lazily triggered but you should keep
> the same instance around, as long as the graph
> does not change.
>
>
>
> On Wed, Oct 7, 2020 at 6:01 AM John Sichi <js...@gm...> wrote:
>
>> Does that include the time to precompute the contraction hierarchy?  My
>> understanding is that building the hierarchy is a cost to be paid once up
>> front, and then after that you can use it to answer queries over and over
>> (as long as the graph doesn't change).
>>
>> On Sun, Oct 4, 2020 at 3:35 PM Mario Basa <mar...@gm...> wrote:
>>
>>> Hello, I'm new here.
>>>
>>> I just tried ContractionHierarchyBidirectionalDijkstra and it seems it
>>> is more suited for sparse graphs. I got this result with a very dense
>>> graph:
>>>
>>> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
>>> http://localhost:8080/pgrServer/api/node/chbDijkstra?source=1015422&target=979173"
>>> -H "accept: application/json" > response_1601788501820.json
>>>
>>>
>>> real 13m58.587s
>>>
>>> user 0m0.117s
>>>
>>> sys 0m0.168s
>>>
>>>
>>> while I got this result from Dijkstra with the same graph:
>>>
>>> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
>>> http://localhost:8080/pgrServer/api/node/dijkstra?source=1015422&target=979173"
>>> -H "accept: application/json" > response_1601788501820.json
>>>
>>>
>>> real 0m0.091s
>>>
>>> user 0m0.010s
>>>
>>> sys 0m0.010s
>>>
>>> and this from A-Star again with the same graph:
>>>
>>> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
>>> http://localhost:8080/pgrServer/api/node/astar?source=1015422&target=979173"
>>> -H "accept: application/json" > response_1601788501820.json
>>>
>>>
>>> real 0m0.058s
>>>
>>> user 0m0.010s
>>>
>>> sys 0m0.011s
>>>
>>> Regards,
>>>
>>> Mario.
>>>
>>> _______________________________________________
>>> jgrapht-users mailing list
>>> jgr...@li...
>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>

Re: [jgrapht-users] ContractionHierarchyBidirectionalDijkstra with pgrServer

[Dimitrios M. <dim...@gm...>]

Indeed John is right. This is a preprocessing technique which has the
drawback of consuming memory, but is very fast when querying.
Not sure whether the preprocessing is lazily triggered but you should keep
the same instance around, as long as the graph
does not change.



On Wed, Oct 7, 2020 at 6:01 AM John Sichi <js...@gm...> wrote:

> Does that include the time to precompute the contraction hierarchy?  My
> understanding is that building the hierarchy is a cost to be paid once up
> front, and then after that you can use it to answer queries over and over
> (as long as the graph doesn't change).
>
> On Sun, Oct 4, 2020 at 3:35 PM Mario Basa <mar...@gm...> wrote:
>
>> Hello, I'm new here.
>>
>> I just tried ContractionHierarchyBidirectionalDijkstra and it seems it is
>> more suited for sparse graphs. I got this result with a very dense graph:
>>
>> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
>> http://localhost:8080/pgrServer/api/node/chbDijkstra?source=1015422&target=979173"
>> -H "accept: application/json" > response_1601788501820.json
>>
>>
>> real 13m58.587s
>>
>> user 0m0.117s
>>
>> sys 0m0.168s
>>
>>
>> while I got this result from Dijkstra with the same graph:
>>
>> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
>> http://localhost:8080/pgrServer/api/node/dijkstra?source=1015422&target=979173"
>> -H "accept: application/json" > response_1601788501820.json
>>
>>
>> real 0m0.091s
>>
>> user 0m0.010s
>>
>> sys 0m0.010s
>>
>> and this from A-Star again with the same graph:
>>
>> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
>> http://localhost:8080/pgrServer/api/node/astar?source=1015422&target=979173"
>> -H "accept: application/json" > response_1601788501820.json
>>
>>
>> real 0m0.058s
>>
>> user 0m0.010s
>>
>> sys 0m0.011s
>>
>> Regards,
>>
>> Mario.
>>
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] ContractionHierarchyBidirectionalDijkstra with pgrServer

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

Does that include the time to precompute the contraction hierarchy?  My
understanding is that building the hierarchy is a cost to be paid once up
front, and then after that you can use it to answer queries over and over
(as long as the graph doesn't change).

On Sun, Oct 4, 2020 at 3:35 PM Mario Basa <mar...@gm...> wrote:

> Hello, I'm new here.
>
> I just tried ContractionHierarchyBidirectionalDijkstra and it seems it is
> more suited for sparse graphs. I got this result with a very dense graph:
>
> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
> http://localhost:8080/pgrServer/api/node/chbDijkstra?source=1015422&target=979173"
> -H "accept: application/json" > response_1601788501820.json
>
>
> real 13m58.587s
>
> user 0m0.117s
>
> sys 0m0.168s
>
>
> while I got this result from Dijkstra with the same graph:
>
> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
> http://localhost:8080/pgrServer/api/node/dijkstra?source=1015422&target=979173"
> -H "accept: application/json" > response_1601788501820.json
>
>
> real 0m0.091s
>
> user 0m0.010s
>
> sys 0m0.010s
>
> and this from A-Star again with the same graph:
>
> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
> http://localhost:8080/pgrServer/api/node/astar?source=1015422&target=979173"
> -H "accept: application/json" > response_1601788501820.json
>
>
> real 0m0.058s
>
> user 0m0.010s
>
> sys 0m0.011s
>
> Regards,
>
> Mario.
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] ContractionHierarchyBidirectionalDijkstra with pgrServer

[Mario B. <mar...@gm...>]

Hello, I'm new here.

I just tried ContractionHierarchyBidirectionalDijkstra and it seems it is
more suited for sparse graphs. I got this result with a very dense graph:

Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
http://localhost:8080/pgrServer/api/node/chbDijkstra?source=1015422&target=979173"
-H "accept: application/json" > response_1601788501820.json


real 13m58.587s

user 0m0.117s

sys 0m0.168s


while I got this result from Dijkstra with the same graph:

Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
http://localhost:8080/pgrServer/api/node/dijkstra?source=1015422&target=979173"
-H "accept: application/json" > response_1601788501820.json


real 0m0.091s

user 0m0.010s

sys 0m0.010s

and this from A-Star again with the same graph:

Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
http://localhost:8080/pgrServer/api/node/astar?source=1015422&target=979173"
-H "accept: application/json" > response_1601788501820.json


real 0m0.058s

user 0m0.010s

sys 0m0.011s

Regards,

Mario.

Re: [jgrapht-users] Fwd: pgrServer with JGraphT

[Dimitrios M. <dim...@gm...>]

Very nice!

It is probably worth it to try Contraction Hierarchies and Transit Node
Routing to get even faster queries.

D.



On Wed, Sep 30, 2020 at 3:24 PM John Sichi <js...@gm...> wrote:

> Here's a note from the developer of pgrServer, a routing web API built on
> JGraphT.
>
> ---------- Forwarded message ---------
> From: Mario Basa <mar...@gm...>
> Date: Wed, Sep 30, 2020 at 2:32 PM
> Subject: pgrServer with JGraphT
> To: <per...@us...>
>
>
> Greetings.
>
> I am one of the original developers of pgRouting, an Open Source Routing
> engine that resides within the PostgreSQL Database, and have started on a
> new project that sets the functionalities of pgRouting as a Web API
> Service.
>
> I have named this project as pgrServer and this uses JGraphT as its core
> Graph engine. I found JGraphT very robust: it was able to do shortest path
> searches in a dense graph with over 2.3M edges (road network of Tokyo plus
> its surrounding Prefectures) in milliseconds.
>
> pgrServer is under the GPL license, and its source code and other
> information can be found here:
>
> https://github.com/mbasa/pgrServer
>
> Hope this project will become useful for someone.
>
> Regards,
>
> Mario Basa.
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] Fwd: pgrServer with JGraphT

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

Here's a note from the developer of pgrServer, a routing web API built on
JGraphT.

---------- Forwarded message ---------
From: Mario Basa <mar...@gm...>
Date: Wed, Sep 30, 2020 at 2:32 PM
Subject: pgrServer with JGraphT
To: <per...@us...>


Greetings.

I am one of the original developers of pgRouting, an Open Source Routing
engine that resides within the PostgreSQL Database, and have started on a
new project that sets the functionalities of pgRouting as a Web API
Service.

I have named this project as pgrServer and this uses JGraphT as its core
Graph engine. I found JGraphT very robust: it was able to do shortest path
searches in a dense graph with over 2.3M edges (road network of Tokyo plus
its surrounding Prefectures) in milliseconds.

pgrServer is under the GPL license, and its source code and other
information can be found here:

https://github.com/mbasa/pgrServer

Hope this project will become useful for someone.

Regards,

Mario Basa.

Re: [jgrapht-users] Fwd: [jgrapht-developers] Hello, have some questions about porting the project

[Timmy J. <tim...@ya...>]

<div>Hello John,</div><div> </div><div>Thank you for the very helpful response!</div><div> </div><div>Yes, licence-wise, going the way of LGPL should be quite okay for the library I have in mind. :-)</div><div> </div><div>That being said, you do make a very good point of providing a language binding for the C API - both in terms of being much less work, but also being able to keep in sync with jgrapht core. I will have to seriously consider this option in lieu of going for a full port from scratch.</div><div> </div><div>Thank you for sharing the links. I will play around with them a bit and mull over best approach!</div><div> </div><div>Best Regards,</div><div> </div><div>Timmy</div><div> </div><div><br /></div><div><br /></div><div>28.07.2020, 13:57, "John Sichi" &lt;js...@gm...&gt;:</div><blockquote><div dir="ltr"><div dir="ltr"><br /></div><br /><div class="f13ca48719c8a60033905b23b39675agmail_quote"><div class="334d7d341e3233c5b27ca91297445127gmail_attr" dir="ltr">On Tue, Jul 28, 2020 at 7:54 AM Timmy Jose &lt;<a href="mailto:tim...@ya...">tim...@ya...</a>&gt; wrote:<br /></div><div class="334d7d341e3233c5b27ca91297445127gmail_attr" dir="ltr"><br /></div><div class="334d7d341e3233c5b27ca91297445127gmail_attr">Hey Timmy,</div><div class="334d7d341e3233c5b27ca91297445127gmail_attr"><br /></div><div class="334d7d341e3233c5b27ca91297445127gmail_attr">Nice to hear from you.</div><div class="334d7d341e3233c5b27ca91297445127gmail_attr" dir="ltr"><br /></div><blockquote class="f13ca48719c8a60033905b23b39675agmail_quote" style="border-left-color:rgb( 204 , 204 , 204 );border-left-style:solid;border-left-width:1px;margin:0px 0px 0px 0.8ex;padding-left:1ex"><div>I have a question about the licensing aspects of writing a port/derivative work using some of the APIs of jgrapht. Looking at the licensing page, suppose I decided to choose LGPL 2.1, can anyone:<br /></div><div><div>   1. Confirm that a port/using the APIs with custom implementation in a different language (from Java, that is) is all right?</div></div></blockquote><div><br /></div><div>It would depend on how your port is to be licensed.  If you redistributed it as LGPL (or GPL), there should be no issue.  In fact, that's what we've done (keeping the EPL dual licensing as well) with the recently released Python bindings:</div><div> <br /></div><div><a href="https://python-jgrapht.readthedocs.io/en/jgrapht-1.5.0.0/">https://python-jgrapht.readthedocs.io/en/jgrapht-1.5.0.0/</a><br /></div><div><br /></div><div>Those build on top of an underlying C api, which is not a port, but rather a wrapper for the native code compiled ahead of time from Java via GraalVM:</div><div><br /></div><div><a href="https://github.com/jgrapht/jgrapht-capi">https://github.com/jgrapht/jgrapht-capi</a><br /></div><div><br /></div><div>So...maybe instead of all the work of porting, you might want to consider using the above to create bindings for whatever language you're interested in (and perhaps sharing that with the community)?</div><div><br /></div><div>If your port were redistributed under a different license, that would be something to discuss with a lawyer, of which I am not one.</div><div><br /></div></div></div>
</blockquote>

Re: [jgrapht-users] Fwd: [jgrapht-developers] Hello, have some questions about porting the project

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

On Tue, Jul 28, 2020 at 7:54 AM Timmy Jose <tim...@ya...> wrote:

Hey Timmy,

Nice to hear from you.

I have a question about the licensing aspects of writing a port/derivative
> work using some of the APIs of jgrapht. Looking at the licensing page,
> suppose I decided to choose LGPL 2.1, can anyone:
>    1. Confirm that a port/using the APIs with custom implementation in a
> different language (from Java, that is) is all right?
>

It would depend on how your port is to be licensed.  If you redistributed
it as LGPL (or GPL), there should be no issue.  In fact, that's what we've
done (keeping the EPL dual licensing as well) with the recently released
Python bindings:

https://python-jgrapht.readthedocs.io/en/jgrapht-1.5.0.0/

Those build on top of an underlying C api, which is not a port, but rather
a wrapper for the native code compiled ahead of time from Java via GraalVM:

https://github.com/jgrapht/jgrapht-capi

So...maybe instead of all the work of porting, you might want to consider
using the above to create bindings for whatever language you're interested
in (and perhaps sharing that with the community)?

If your port were redistributed under a different license, that would be
something to discuss with a lawyer, of which I am not one.

[jgrapht-users] Fwd: [jgrapht-developers] Hello, have some questions about porting the project

[Timmy J. <tim...@ya...>]

<div> </div><div> </div><div>-------- Beginning of forwarded message --------</div><div>27.07.2020, 07:21, "Timmy Jose" &lt;tim...@ya...&gt;:</div><div> </div><div><div>Hello all,</div><div> </div><div>I came across jgrapht, and have been playing around with it for a few hours now.</div><div> </div><div>I have a question about the licensing aspects of writing a port/derivative work using some of the APIs of jgrapht. Looking at the licensing page, suppose I decided to choose LGPL 2.1, can anyone:</div><div>   1. Confirm that a port/using the APIs with custom implementation in a different language (from Java, that is) is all right?</div><div>   2. Point to to a resource about what exactly I would need to include in my derivative work to be compliant with the licensing terms?  </div><div> </div><div>Thanks!</div><div> </div><div>Timmy</div>,,<p>_______________________________________________<br />jgrapht-developers mailing list<br /><a href="mailto:jgr...@li...">jgr...@li...</a><br /><a href="https://lists.sourceforge.net/lists/listinfo/jgrapht-developers">https://lists.sourceforge.net/lists/listinfo/jgrapht-developers</a></p></div><div> </div><div>-------- End of forwarded message --------</div>

[jgrapht-users] Fwd: [jgrapht-developers] Hello, have some questions about porting the project

[Timmy J. <tim...@ya...>]

<div> </div><div> </div><div>-------- Beginning of forwarded message --------</div><div>27.07.2020, 07:21, "Timmy Jose" &lt;tim...@ya...&gt;:</div><div> </div><div><div>Hello all,</div><div> </div><div>I came across jgrapht, and have been playing around with it for a few hours now.</div><div> </div><div>I have a question about the licensing aspects of writing a port/derivative work using some of the APIs of jgrapht. Looking at the licensing page, suppose I decided to choose LGPL 2.1, can anyone:</div><div>   1. Confirm that a port/using the APIs with custom implementation in a different language (from Java, that is) is all right?</div><div>   2. Point to to a resource about what exactly I would need to include in my derivative work to be compliant with the licensing terms?  </div><div> </div><div>Thanks!</div><div> </div><div>Timmy</div>,,<p>_______________________________________________<br />jgrapht-developers mailing list<br /><a href="mailto:jgr...@li...">jgr...@li...</a><br /><a href="https://lists.sourceforge.net/lists/listinfo/jgrapht-developers">https://lists.sourceforge.net/lists/listinfo/jgrapht-developers</a></p></div><div> </div><div>-------- End of forwarded message --------</div>

Re: [jgrapht-users] Using JgraphT using Pyhton 3.8.3 and ubuntu 14.04

[Dimitrios M. <dim...@gm...>]

Just for future reference, the following post

https://stackoverflow.com/questions/2812520/dealing-with-multiple-python-versions-and-pip

contains answers on how to use pip with different versions of python.

On Wed, Jul 1, 2020 at 12:50 PM Dimitrios Michail <
dim...@gm...> wrote:

> Moreover, you are using an old ubuntu system which has python 2 as the
> default.
> Make sure that you use python3 and pip3.
>
>
>
> On Wed, Jul 1, 2020 at 12:30 PM Dimitrios Michail <
> dim...@gm...> wrote:
>
>> You need to follow the instructions here
>>
>> https://python-jgrapht.readthedocs.io/en/jgrapht-1.5.0.0/install.html
>>
>> Pip version must be >= 19.0, otherwise it tries to build from source.
>> Use `pip install --upgrade pip` before installing
>>
>>
>> On Wed, Jul 1, 2020 at 2:59 AM Muhsin Atto <dar...@gm...> wrote:
>>
>>> Hi Sir,
>>>
>>> I would like to use JgraphT package using Python 3.8.3 and Ubuntu 14.04
>>> When I am typing this: pip install jgrapht
>>>
>>> It says your version must be greater than 3.6. Given error is attached
>>> in this email. But my python version is the blast one (3.8.3).
>>>
>>> When I'm typing this: python --version
>>> This is give:
>>> dlo@Dlo:~$ python --version
>>> Python 3.8.3
>>>
>>>
>>> Could you please help me how to install JgraphT into my Ubuntu.
>>>
>>> Regards
>>> Muhsin
>>> _______________________________________________
>>> jgrapht-users mailing list
>>> jgr...@li...
>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>
>>

Re: [jgrapht-users] Using JgraphT using Pyhton 3.8.3 and ubuntu 14.04

[Dimitrios M. <dim...@gm...>]

Moreover, you are using an old ubuntu system which has python 2 as the
default.
Make sure that you use python3 and pip3.



On Wed, Jul 1, 2020 at 12:30 PM Dimitrios Michail <
dim...@gm...> wrote:

> You need to follow the instructions here
>
> https://python-jgrapht.readthedocs.io/en/jgrapht-1.5.0.0/install.html
>
> Pip version must be >= 19.0, otherwise it tries to build from source.
> Use `pip install --upgrade pip` before installing
>
>
> On Wed, Jul 1, 2020 at 2:59 AM Muhsin Atto <dar...@gm...> wrote:
>
>> Hi Sir,
>>
>> I would like to use JgraphT package using Python 3.8.3 and Ubuntu 14.04
>> When I am typing this: pip install jgrapht
>>
>> It says your version must be greater than 3.6. Given error is attached in
>> this email. But my python version is the blast one (3.8.3).
>>
>> When I'm typing this: python --version
>> This is give:
>> dlo@Dlo:~$ python --version
>> Python 3.8.3
>>
>>
>> Could you please help me how to install JgraphT into my Ubuntu.
>>
>> Regards
>> Muhsin
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>

Re: [jgrapht-users] Using JgraphT using Pyhton 3.8.3 and ubuntu 14.04

[Dimitrios M. <dim...@gm...>]

You need to follow the instructions here

https://python-jgrapht.readthedocs.io/en/jgrapht-1.5.0.0/install.html

Pip version must be >= 19.0, otherwise it tries to build from source.
Use `pip install --upgrade pip` before installing


On Wed, Jul 1, 2020 at 2:59 AM Muhsin Atto <dar...@gm...> wrote:

> Hi Sir,
>
> I would like to use JgraphT package using Python 3.8.3 and Ubuntu 14.04
> When I am typing this: pip install jgrapht
>
> It says your version must be greater than 3.6. Given error is attached in
> this email. But my python version is the blast one (3.8.3).
>
> When I'm typing this: python --version
> This is give:
> dlo@Dlo:~$ python --version
> Python 3.8.3
>
>
> Could you please help me how to install JgraphT into my Ubuntu.
>
> Regards
> Muhsin
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] Using JgraphT using Pyhton 3.8.3 and ubuntu 14.04

[Joris K. <j.k...@gm...>]

Please submit an issue here:
https://github.com/jgrapht/jgrapht/issues

On Tue, Jun 30, 2020 at 4:59 PM Muhsin Atto <dar...@gm...> wrote:

> Hi Sir,
>
> I would like to use JgraphT package using Python 3.8.3 and Ubuntu 14.04
> When I am typing this: pip install jgrapht
>
> It says your version must be greater than 3.6. Given error is attached in
> this email. But my python version is the blast one (3.8.3).
>
> When I'm typing this: python --version
> This is give:
> dlo@Dlo:~$ python --version
> Python 3.8.3
>
>
> Could you please help me how to install JgraphT into my Ubuntu.
>
> Regards
> Muhsin
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] Using JgraphT using Pyhton 3.8.3 and ubuntu 14.04

[Muhsin A. <dar...@gm...>]

Hi Sir,

I would like to use JgraphT package using Python 3.8.3 and Ubuntu 14.04
When I am typing this: pip install jgrapht

It says your version must be greater than 3.6. Given error is attached in
this email. But my python version is the blast one (3.8.3).

When I'm typing this: python --version
This is give:
dlo@Dlo:~$ python --version
Python 3.8.3


Could you please help me how to install JgraphT into my Ubuntu.

Regards
Muhsin

[jgrapht-users] Python Bindings for JGraphT 1.5.0

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

Hello everyone,

We're very pleased to announce the initial release of python bindings for
JGraphT:

https://medium.com/@dimitrios.michail/announcing-the-python-bindings-of-jgrapht-918d0cf386de

Although the JGraphT library itself remains firmly based on the Java
platform, we're cognizant that python is a very popular competing
environment, especially for areas such as data science and machine
learning.  So, we wanted to bring the benefits of JGraphT's power and
breadth to python developers as well.  The new bindings allow us to do this
seamlessly and efficiently.

You can learn more about how this works in Dimitrios' medium post above.

It's worthing noting that the python bindings build on an underlying C api
which bridges to the Java interfaces, so if you are interested in
developing bindings for other languages as well, that should now be
possible.

Re: [jgrapht-users] [jgrapht-dev] please welcome our newest committer

[Joris K. <j.k...@gm...>]

Congratulations Semen! Well deserved!

Just to give a personal anecdote: in 2015 I was working on large scale
vehicle routing applications, where I used JGraphT to represent entire road
networks of some major US cities. The data came from Open Street Maps. The
graph representation was simple: a road intersection was represented as a
vertex, an arc represented a directed connection between a pair of
intersections. Each arc stored information such as distance, shape, travel
speed, number of lanes etc. Within this large road network I had about 3000
Points of Interest (POIs). These POIs formed a small subset of the
vertices. For my application I had to compute all-pairs shortest paths
between my POIs using the underlying road network. Back in 2015, JGraphT
had limited support for routing algorithms. With a modified version of
Johnsons shortest path algorithm I was able to compute the desired distance
matrix in 30-60 minutes. Recently I had to revisit this application. For a
food delivery application for students affected by COVID-19 I had to
compute a shortest path distance matrix for 3500 POIs (the students) in a
road network graph with 35296 vertices, 84887 edges. Using the Contraction
Hierarchy algorithm (CHManyToManyShortestPaths) implemented by Semen in
2019, I was able to solve this problem in just 15 seconds! So the same
application that took 30-60 min in 2015, is now solved in 15 seconds.
Personally I'm very impressed by the talented developers that have
contributed to JGraphT over the years, as well as the level of maturity
that this library has reached.

Joris Kinable

On Fri, Jun 19, 2020 at 8:12 PM John Sichi <js...@gm...> wrote:

> We've been receiving a lot of significant contributions from Semen
> Chudakov over the last year and a half, so we're very happy to announce
> that we're adding him as a committer on the project (joining me, Joris,
> Dimitrios, and Timofey).  This means if you submit a pull request, he may
> be one of your reviewers helping you get it ready for merge.
>
> --
> You received this message because you are subscribed to the Google Groups
> "jgrapht-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to jgr...@go....
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/jgrapht-dev/ee952350-3b40-4438-8184-f91dc73f0439o%40googlegroups.com
> <https://groups.google.com/d/msgid/jgrapht-dev/ee952350-3b40-4438-8184-f91dc73f0439o%40googlegroups.com?utm_medium=email&utm_source=footer>
> .
>

[jgrapht-users] please welcome our newest committer

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

We've been receiving a lot of significant contributions from Semen Chudakov
over the last year and a half, so we're very happy to announce that we're
adding him as a committer on the project (joining me, Joris, Dimitrios, and
Timofey).  This means if you submit a pull request, he may be one of your
reviewers helping you get it ready for merge.

Re: [jgrapht-users] [jgrapht-dev] JGraphT 1.5.0 released

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

Thanks Joris!

One release note:  as part of moving to module support, we had to drop
support for the jgrapht-bundle jar in the distribution.  We used to provide
this as a convenience for non-Maven users, but in the modern era, we
suspect it's unlikely that anyone was actually using it.  If you *were*
using it, and you want to upgrade to JGraphT 1.5.0, let us know and we can
help you figure out how to use individual jars instead.

On Mon, Jun 15, 2020 at 4:13 PM Joris Kinable <j.k...@gm...> wrote:

> Hi all,
>
> With a little bit of a delay, JGraphT 1.5.0 has been released! Since JDK 8
> is reaching an end-of-life status at the end of the year, we changed the
> minimum requirements for JGraphT 1.5.0 to JDK 11. Java 9 introduced a new
> level of abstraction above packages: modules. In migragrating the code base
> from JDK 8 to 11, we added support for modularity in JGraphT as well.
> JGraphT 1.5.0 will be an important milestone in the history of JGraphT as
> it unblocks the development of a new, ambitious project led by Dimitrios
> Michail: jgrapht-python! More details on the jgrapht-python project will be
> unveiled upon its official release.
> Finally, for those who missed the previous announcement, our academic
> paper 'JGraphT--A Java library for graph data structures and algorithms'
> has been published last month. To read the paper:
> https://doi.org/10.1145/3381449, and to cite the paper:
> https://github.com/jgrapht/jgrapht/wiki/Users%3A-How-to-cite-JGraphT
> Thanks again to all the contributors, users and supporters of JGraphT,
>
> br,
>
> Joris Kinable
>
> --
> You received this message because you are subscribed to the Google Groups
> "jgrapht-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to jgr...@go....
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/jgrapht-dev/CAPEkHr7%2BNQbt%3DNHxOvCivdD3JV3ntwf76kiedqxWQRXxHcynsA%40mail.gmail.com
> <https://groups.google.com/d/msgid/jgrapht-dev/CAPEkHr7%2BNQbt%3DNHxOvCivdD3JV3ntwf76kiedqxWQRXxHcynsA%40mail.gmail.com?utm_medium=email&utm_source=footer>
> .
>

[jgrapht-users] JGraphT 1.5.0 released

[Joris K. <j.k...@gm...>]

Hi all,

With a little bit of a delay, JGraphT 1.5.0 has been released! Since JDK 8
is reaching an end-of-life status at the end of the year, we changed the
minimum requirements for JGraphT 1.5.0 to JDK 11. Java 9 introduced a new
level of abstraction above packages: modules. In migragrating the code base
from JDK 8 to 11, we added support for modularity in JGraphT as well.
JGraphT 1.5.0 will be an important milestone in the history of JGraphT as
it unblocks the development of a new, ambitious project led by Dimitrios
Michail: jgrapht-python! More details on the jgrapht-python project will be
unveiled upon its official release.
Finally, for those who missed the previous announcement, our academic paper
'JGraphT--A Java library for graph data structures and algorithms' has been
published last month. To read the paper: https://doi.org/10.1145/3381449,
and to cite the paper:
https://github.com/jgrapht/jgrapht/wiki/Users%3A-How-to-cite-JGraphT
Thanks again to all the contributors, users and supporters of JGraphT,

br,

Joris Kinable