Obtain the node set about graphhopper HOT 10 CLOSED

We could add this to GraphUtility.

Two questions:

• why do you need it :)? I mean, the nodes should be simply 0-maxNode, also when importing possible unused small networks are removed from the node set.
• again, as the nodes should be nearly incident you should use a BitSet (more memory efficient) and to avoid implementation deps use the MyBitSet interface with the MyBitSetImpl.

from graphhopper.

1. I construct my graph using the edge method. A bi-product of edge creation is node creation, and the nodes are created according to their ids passed to edge. Nothing requires the node ids to be labeled in sequential order, so (as far as I understand) we can't use a simple for loop to cycle through the nodes -- at a certain index i, node i might not exist.
2. Thanks for the tip! I'll look into this.

from graphhopper.

I don't understand 1.

In graphhopper it is - per definition - that node ids are in sequential order. Of course you can create holes via setNode or edge method but I don't understand your use case why you need to do that.

Why is it sequential? Because:

• to avoid hash lookups and use direct 'pointer' lookup in GraphStorage itself but in a lot other datastructures for the graph. Indeed this definition is the key to make GraphHopper faster and more mem efficient
• to make use of efficient boolean storage like BitSet (again instead of a more expensive map ala Map<Integer, Boolean>)

from graphhopper.

This is not indispensable; I think we can close the issue.

However, just to be clear, let me explain by an example. If I add edges

graph.edge(2, 5, 1, false);
graph.edge(3, 2, 1, false);
graph.edge(3, 7, 1, false);
graph.edge(7, 2, 1, false);

then I have indirectly created the nodes 2, 3, 5, 7.

Say, for example, that I implement my own version of Dijkstra's algorithm for use in calculating betweenness centrality (where I need to calculate the number and length of all possible shortest paths).

At the end of the calculation I want to print, for each node, the number of shortest paths their length to every other node. This looks something like the following:

protected void printSPInfo(
            int startNode) {
        System.out.println("       d           SP pred");
        TIntIterator it = nodeSet.iterator();
        while (it.hasNext()) {
            int node = it.next();
            final NodeBetweennessInfo nodeNBInfo = nodeBetweenness.get(node);
            System.out.print("(" + startNode + "," + node + ")  ");
            System.out.format("%-12f%-3d%-12s",
                              nodeNBInfo.getDistance(),
                              nodeNBInfo.getSPCount(),
                              nodeNBInfo.getPredecessors().toString());
            System.out.println("");
        }
    }

If I have the nodeSet() method, then it is easy to go through all the nodes using an iterator and print out the appropriate information. However, without this method, I don't see an easy way to go through all the nodes.

A possible (and simple) solution would be to add a method

int node(int index);

to Graph which returns the node id (passed to edge as at the start of this post) at the given index, assuming that the indices go from 0 to graph.nodes() - 1.

from graphhopper.

Probably still some missunderstanding on your or my side.

In graphhopper you don't have a mapping between an 'index' and the 'node'. They are synonyms.
If you do graph.edge(7, 2, 1, false) you'll indirectly increase the underlying node array to make it accepting at least 8 nodes with indices 0 to 7.

E.g. when importing data from OSM then I'm using a temporary BigLongIntMap object to map long-osm-ids to integer-graphhopper-nodes. And when an unknown osm ids comes through I'm creating a new mapping with an increased counter. Then I do not create a hole in the nodes array or similar ...

from graphhopper.

I confirm, still some misunderstanding on my side.

I'm looking at your diagram in section "2. The Graph" of your wiki's Developers page.

Could you show me how you would write a method

void printNodes(Graph graph);

such that if the graph in your example were passed to this method, the output would be

0
1
2
3
5
7

?

from graphhopper.

Oh, is this misunderstanding coming from my illustration? oh no :( -> I'll improve that

The nodes 4 and 6 just do not have edges but it does not mean that they are invalid. They could e.g. have associated node properties like lat+lon etc. For your method you could then just check if a node has an edge:

for(int i = 0; i < graph.nodes(); i++) {
    if(graph.getEdges(i).next())
        println(i);
}

from graphhopper.

Ah okay, I think I understand better now.

What this means is that if we wanted to create a (theoretical) graph consisting of only the edges in your illustration and only nodes that have edges, this is technically not possible. I.e., the nodes 4 and 6 exist even though we have not added them to the graph. I don't think this will pose a problem for me now that I understand the test if(graph.getEdges(i).next().

However, this also means that if we create a graph and execute, for example, the single instruction

graph.edge(0, 999999999, 1, false);

then the graph will contain 1 billion nodes (and one edge), even though we have only indirectly added two nodes (connected by the single edge).

from graphhopper.

Yes, this is one 'disadvantage' of this design. Which is ok as we get a fast+memory efficient storage if we follow some simple rules.

from graphhopper.

Ok, thanks for your replies and insight!

from graphhopper.