3

I have a road network shapefile.

After creating Network dataset I get a graph with vertices and edges. I need to create a tool for ArcGIS (through a Python code) which enables to calculate depth of all vertices in a network according to the formula:

Number of neighbours one step away multiplied by number of steps + neighbours two step away multiplied by number of steps + three steps away...

For example see image: red point on the picture has 3 neighbours one step away, 2 neighbour 2 steps away. So the depth for the red point will be: 3x1+2x2=7.

I need to calculate this for all vertices in my network. It's quite easy but unfortunately I don't have any experience with Python.

enter image description here

  • 1
    I'm not sure Network Analyst would be able to solve this. I can't think of any solver that would address the point count part rather than a distance or could be adapted short of routes to every point. It might be better to look at it as a geometric network, because some of those tools might be more easily adapted. There's the implication of flow direction with a geometric, but the idea of sinks and traces seems like it could be used. Are all edges two point lines? If not you're looking for nodes, not vertices. – Chris W Jun 5 '15 at 19:14
4

it is not a GIS question and you need to know the Graph Theory algorithms (as graph traversal, etc.), look at How to count the number of lines connected to a point?)

Guido Van Rossum, the creator of Python, was the first (in 1998) to implement the Graph Theory algorithms in Python (Python Patterns - Implementing Graphs) and you can still use them.

I don't know if you can easily install external Python modules in ArcPy but there are many dealing with graphs (PyPi: Graph Theory) and one of the most popular an easiest to use is Networkx (in Python it is often unnecessary to reinvent the wheel)

enter image description here

import networkx as nx
G = nx.Graph() # one undirected an unweighted simple graph
G.add_edges_from([(1,2),(1,3),(1,4),(2,3),(3,5),(3,6)]
G.nodes()
[1, 2, 3, 4, 5, 6]
G.edges()
[(1, 2), (1, 3), (1, 4), (2, 3), (3, 5), (3, 6)]
# node 1 = your red point
nx.degree(G)
{1: 3, 2: 2, 3: 4, 4: 1, 5: 1, 6: 1}
G.degree(1)
3
G.degree(4)
1

Graph traversal with depth-first-search (DFS) or.breadth-first-search (BFS)

print(nx.dfs_successors(G,1))
{1: [2, 4], 2: [3], 3: [5, 6]}
print(nx.dfs_successors(G,4))
{1: [2], 2: [3], 3: [5, 6], 4: [1]}
print(nx.bfs_successors(G,1))
{1: [2, 3, 4], 3: [5, 6]}
print(nx.bfs_successors(G,4))
{1: [2, 3], 3: [5, 6], 4: [1]}

And, for example:.

a = nx.bfs_successors(G,1)
nb = 0
for i,j in enumerate(a.keys()):
  nb +=  (i+1) * len(a[j])
print nb
7
  • thanks for the example, but in your code you add edges and then number them. But I have a huge road network of city, do I need to number all of nodes (there are thousands of them)?? – Martin Jun 8 '15 at 9:46
3

You don't need to build a network dataset (ND) to get this kind of information. Building a ND won't let you access this type of properties as the adjacency matrix / connectivity matrix are not exposed to the end user in ArcGIS.

I strongly recommend instead using networkx Python library when working with graphs. It can build graphs directly from shapefiles. Most of the graph theory operations you can think of are already implemented (including depth), but you can easily tweak the functions and develop some new code on top of that.

I've been working with networkx for around a year and I think it's just great. I've developed some custom tools in ArcGIS by loading street networks into networkx Graph object and was able to do all kinds of analysis I needed in my project. I've also seen igraph and python-graph, seems to be popular too, but I didn't try.

If you would decide to build your own data structure for representing graphs and implement graph processing tools, consider reading more about graphs and their properties specifically with Python here at Problem Solving with Algorithms and Data Structures book.

More useful resources on graphs in GIS:

Pure graph theory resources:

  • About Network Dataset - I meant that by using this tool Network Analyst creates undirected graph (as I understood from discription of this tool), after this we can analyze our network and find shortest distances, service area, etc... I'll try NetworkX, I heard about it, but I need to analyze a network with my own formulas. – Martin Jun 8 '15 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.