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
>