Usage question

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Usage question

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

Re: Usage question

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


_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: Usage question

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


_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users