How to programmatically traverse a street network

Summary This topic shows how to programmatically traverse a street network using the public ArcObjects application programming interface (API) for the geodatabase. For more information about network datasets and Network Analyst, refer to the "See Also" links at the bottom of this topic.

About programmatically traversing a street network

This topic shows how to code a search algorithm that can traverse a network dataset. The code performs a breadth-first search (BFS) traversal of a network from an origin junction to a destination junction, finding the path with the fewest number of edges between the origin and the destination.
Do the following steps to programmatically traverse a street network:
  1. Set up a helper structure and the search method signature—This method takes an INetworkDataset as a parameter. For more information about obtaining a reference to a dataset, see How to open a network dataset. See the following code example:
[C#] 
public struct SearchStruct
{
    public int junctionEID;
    public int numberOfHops;
    public int fromEdgeEID;
    public ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection fromEdgeDirection;
    public int lastExteriorEdgeEID;
    public ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection
        lastExteriorEdgeDirection;
} 

public int BreadthFirstSearch(ESRI.ArcGIS.Geodatabase.INetworkDataset networkDataset,
    int startingJunctionEID, int destinationJunctionEID, string[]
    restrictionAttributeNames)
{
    // You are doing a breadth-first search to determine how many edges away a destination junction
    // is from an origin junction.
[VB.NET] 
Public Structure SearchStruct
Public junctionEID As Integer
Public numberOfHops As Integer
Public fromEdgeEID As Integer
Public fromEdgeDirection As ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection
Public lastExteriorEdgeEID As Integer
Public lastExteriorEdgeDirection As ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection
End Structure

Public Function BreadthFirstSearch(ByVal networkDataset As ESRI.ArcGIS.Geodatabase.INetworkDataset, ByVal startingJunctionEID As Integer, ByVal destinationJunctionEID As Integer, ByVal restrictionAttributeNames As String()) As Integer
    ' You are doing a breadth-first search to find out how many edges away a destination junction
    ' is from an origin junction.
  1. Prepare the NetworkForwardStar object—Before traversing the network, the NetworkForwardStar object needs to be properly created and configured. See the following code example:
[C#] 

// Get the forward star and query adjacency objects.
var networkQuery = networkDataset as ESRI.ArcGIS.Geodatabase.INetworkQuery;
var fStarEx = networkQuery.CreateForwardStar()as
    ESRI.ArcGIS.Geodatabase.INetworkForwardStarEx;
ESRI.ArcGIS.Geodatabase.INetworkForwardStarAdjacencies fStarAdj =
    networkQuery.CreateForwardStarAdjacencies();
var searchQueue = new System.Collections.Queue();

// Prepare the forward star settings.
fStarEx.BacktrackPolicy =
    ESRI.ArcGIS.Geodatabase.esriNetworkForwardStarBacktrack.esriNFSBNoBacktrack; 
    // No u-turns allowed.
fStarEx.IsForwardTraversal = true; // Searching in a forward direction.

// The search will be an "exact" search and not use the hierarchy settings.
// However, hierarchy settings can be set. See the following:
// fStarEx.HierarchyAttribute = your hierarchy attribute.
// fStarEx.MaxTraversableHierarchyValue = max value.

// Add the restriction attributes that need to be honored.
foreach (string restrictionAttributeName in restrictionAttributeNames)
{
    ESRI.ArcGIS.Geodatabase.INetworkAttribute restrictionAttribute =
        networkDataset.get_AttributeByName(restrictionAttributeName);
    fStarEx.AddRestrictionAttribute(restrictionAttribute);
}

// Add attribute adjustments.
// Some sample adjustments are shown as follows:
/*
fStarEx.AddEdgeRestriction(myEdge, 0.0, 0.5); // Restrict half an edge.
fStarEx.AddJunctionRestriction(myJunction); // Restrict a junction.
fStarEx.AddTurnRestriction(myTurn); // Restrict a single turn.
fStarEx.AdjustEdgeAttributeValue(myEdge, 0.0, 1.0, myAttribute, esriNetworkAttributeAdjustmentType.esriNAATScale, 2.0); // Scale a whole edge attribute value by 2x.
fStarEx.AdjustJunctionAttributeValue(myJunction, myAttribute, esriNetworkAttributeAdjustmentType.esriNAATReplace, 15.0); // Replace a junction attribute value.
fStarEx.AdjustEdgeAttributeValue(myEdge, 0.5, 0.5, myAttribute, esriNetworkAttributeAdjustmentType.esriNAATAdd, 1.0); // Add 1.0 to the midway point of an edge.
      */
[VB.NET] 

' Get the forward star and query adjacency objects.
Dim networkQuery = TryCast(networkDataset, ESRI.ArcGIS.Geodatabase.INetworkQuery)
Dim fStarEx = TryCast(networkQuery.CreateForwardStar(), ESRI.ArcGIS.Geodatabase.INetworkForwardStarEx)
Dim fStarAdj As ESRI.ArcGIS.Geodatabase.INetworkForwardStarAdjacencies = networkQuery.CreateForwardStarAdjacencies()
Dim searchQueue = New System.Collections.Queue()

' Prepare the forward star settings.
fStarEx.BacktrackPolicy = ESRI.ArcGIS.Geodatabase.esriNetworkForwardStarBacktrack.esriNFSBNoBacktrack
' No u-turns allowed.
fStarEx.IsForwardTraversal = True
' Searching in a forward direction.

' The search will be an "exact" search and not use the hierarchy settings.
' However, hierarchy settings can be set. See the following:
' fStarEx.HierarchyAttribute = your hierarchy attribute.
' fStarEx.MaxTraversableHierarchyValue = max value.

' Add the restriction attributes that need to be honored.
For Each restrictionAttributeName As String In restrictionAttributeNames
    Dim restrictionAttribute As ESRI.ArcGIS.Geodatabase.INetworkAttribute = networkDataset.get_AttributeByName(restrictionAttributeName)
    fStarEx.AddRestrictionAttribute(restrictionAttribute)
Next

' Add attribute adjustments.
' Some sample adjustments are shown as follows:
'
' fStarEx.AddEdgeRestriction(myEdge, 0.0, 0.5); ' Restrict half an edge.
' fStarEx.AddJunctionRestriction(myJunction); ' Restrict a junction.
' fStarEx.AddTurnRestriction(myTurn); ' Restrict a single turn.
' fStarEx.AdjustEdgeAttributeValue(myEdge, 0.0, 1.0, myAttribute, esriNetworkAttributeAdjustmentType.esriNAATScale, 2.0); ' Scale a whole edge attribute value by 2x.
' fStarEx.AdjustJunctionAttributeValue(myJunction, myAttribute, esriNetworkAttributeAdjustmentType.esriNAATReplace, 15.0); ' Replace a junction attribute value.
' fStarEx.AdjustEdgeAttributeValue(myEdge, 0.5, 0.5, myAttribute, esriNetworkAttributeAdjustmentType.esriNAATAdd, 1.0); ' Add 1.0 to the midway point of an edge.
  1. Set up network element objects and other required structures—Network element objects and search structures need to be created and initialized. See the following code example:
[C#] 
// Get the starting junction.
var junction = networkQuery.CreateNetworkElement
    (ESRI.ArcGIS.Geodatabase.esriNetworkElementType.esriNETJunction)as
    ESRI.ArcGIS.Geodatabase.INetworkJunction;

var fromEdge = networkQuery.CreateNetworkElement
    (ESRI.ArcGIS.Geodatabase.esriNetworkElementType.esriNETEdge)as
    ESRI.ArcGIS.Geodatabase.INetworkEdge;
var toEdge = networkQuery.CreateNetworkElement
    (ESRI.ArcGIS.Geodatabase.esriNetworkElementType.esriNETEdge)as
    ESRI.ArcGIS.Geodatabase.INetworkEdge;
var lastExteriorEdge = networkQuery.CreateNetworkElement
    (ESRI.ArcGIS.Geodatabase.esriNetworkElementType.esriNETEdge)as
    ESRI.ArcGIS.Geodatabase.INetworkEdge;
double fromPosition, toPosition;

// Queue up the starting junction.
searchQueue.Enqueue(new SearchStruct
{
    junctionEID = startingJunctionEID, numberOfHops = 0, fromEdgeEID =  - 1,
        fromEdgeDirection =
        ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection.esriNEDNone,
        lastExteriorEdgeEID =  - 1, lastExteriorEdgeDirection =
        ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection.esriNEDNone
}

);

// Use an edge based array to properly handle turns in the network dataset (see the following logic).
bool[] isAlongReached = new bool[networkQuery.get_MaxEID
    (ESRI.ArcGIS.Geodatabase.esriNetworkElementType.esriNETEdge) + 1];
bool[] isAgainstReached = new bool[networkQuery.get_MaxEID
    (ESRI.ArcGIS.Geodatabase.esriNetworkElementType.esriNETEdge) + 1];
[VB.NET] 
' Get the starting junction.
Dim junction = TryCast(networkQuery.CreateNetworkElement(ESRI.ArcGIS.Geodatabase.esriNetworkElementType.esriNETJunction), ESRI.ArcGIS.Geodatabase.INetworkJunction)

Dim fromEdge = TryCast(networkQuery.CreateNetworkElement(ESRI.ArcGIS.Geodatabase.esriNetworkElementType.esriNETEdge), ESRI.ArcGIS.Geodatabase.INetworkEdge)
Dim toEdge = TryCast(networkQuery.CreateNetworkElement(ESRI.ArcGIS.Geodatabase.esriNetworkElementType.esriNETEdge), ESRI.ArcGIS.Geodatabase.INetworkEdge)
Dim lastExteriorEdge = TryCast(networkQuery.CreateNetworkElement(ESRI.ArcGIS.Geodatabase.esriNetworkElementType.esriNETEdge), ESRI.ArcGIS.Geodatabase.INetworkEdge)
Dim fromPosition As Double, toPosition As Double

' Queue up the starting junction.
searchQueue.Enqueue(New SearchStruct())

' Use an edge based array to properly handle turns in the network dataset (see the following logic).
Dim isAlongReached As Boolean() = New Boolean(networkQuery.get_MaxEID(ESRI.ArcGIS.Geodatabase.esriNetworkElementType.esriNETEdge)) {}
Dim isAgainstReached As Boolean() = New Boolean(networkQuery.get_MaxEID(ESRI.ArcGIS.Geodatabase.esriNetworkElementType.esriNETEdge)) {}
  1. Traverse the network—Perform the search algorithm by traversing the network until the destination is found. See the following code example:
[C#] 
// Iterate over the queue until the destination is found or the queue is empty.
while (searchQueue.Count > 0)
{
    SearchStruct currentSearchStruct = (SearchStruct)searchQueue.Dequeue();

    // Check if this is the destination.
    if (currentSearchStruct.junctionEID == destinationJunctionEID)
        return currentSearchStruct.numberOfHops;
    // Return the final hop count.

    // Populate the edges to indicate the path taken to reach this junction. This is 
    //  necessary for detecting and tracking turns.
    bool hasFromEdge = false;
    bool hasLastExteriorEdge = false;

    if (currentSearchStruct.fromEdgeEID !=  - 1)
    {
        hasFromEdge = true;

        // If there was a previous edge in the search, then populate the fromEdge 
        //  with that edge's values.
        networkQuery.QueryEdge(currentSearchStruct.fromEdgeEID,
            currentSearchStruct.fromEdgeDirection, fromEdge);
        if (currentSearchStruct.lastExteriorEdgeEID !=  - 1)
        {
            hasLastExteriorEdge = true;
            networkQuery.QueryEdge(currentSearchStruct.lastExteriorEdgeEID,
                currentSearchStruct.lastExteriorEdgeDirection, lastExteriorEdge);
        }
    }

    // Find the adjacencies from the current junction. The NetworkForwardStar relies on 
    //  the fromEdge and lastExteriorEdge objects to detect turns. Any restricted turns
    //   exclude the appropriate edges from being returned in the NetworkForwardStarAdjacencies object.
    fStarEx.QueryJunction(currentSearchStruct.junctionEID, junction);
    fStarEx.QueryAdjacencies(junction, (hasFromEdge) ? fromEdge : null, 
        (hasLastExteriorEdge) ? lastExteriorEdge : null, fStarAdj);

    // Iterate the adjacencies adding them to the search queue.
    bool isJunctionFiltered;
    for (int index = 0; index < fStarAdj.Count; index++)
    {
        fStarAdj.QueryEdge(index, toEdge, out fromPosition, out toPosition);
        fStarAdj.QueryToJunction(index, junction, out isJunctionFiltered);

        // If this edge has already been marked as "reached" in the search, don't search it again.
        // If the junction is filtered (that is, inaccessible/restricted), skip this entry, since 
        //  it won't provide a valid path to the destination.               
        if ((toEdge.Direction ==
            ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection.esriNEDAlongDigitized
            && isAlongReached[toEdge.EID]) || (toEdge.Direction ==
            ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection.esriNEDAgainstDigitized
            && isAgainstReached[toEdge.EID]) || isJunctionFiltered)
            continue;

        // Prepare the struct for the next junction.
        SearchStruct nextRecord = new SearchStruct();
        nextRecord.numberOfHops = currentSearchStruct.numberOfHops + 1; 
            // The hop count!
        nextRecord.junctionEID = junction.EID;
        nextRecord.fromEdgeEID = toEdge.EID;
        nextRecord.fromEdgeDirection = toEdge.Direction;
        nextRecord.lastExteriorEdgeEID =  - 1;
        nextRecord.lastExteriorEdgeDirection =
            ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection.esriNEDNone;

        // Establish the last exterior edge information based on the current edge's 
        //  turn participation type.
        if (toEdge.TurnParticipationType ==
            ESRI.ArcGIS.Geodatabase.esriNetworkTurnParticipationType.esriNTPTExterior)
        {
            nextRecord.lastExteriorEdgeEID = toEdge.EID;
            nextRecord.lastExteriorEdgeDirection = toEdge.Direction;
        }
        else if (toEdge.TurnParticipationType ==
            ESRI.ArcGIS.Geodatabase.esriNetworkTurnParticipationType.esriNTPTInterior)
        {
            nextRecord.lastExteriorEdgeEID = currentSearchStruct.lastExteriorEdgeEID;
            nextRecord.lastExteriorEdgeDirection =
                currentSearchStruct.lastExteriorEdgeDirection;
        }

        // Queue the search element.
        searchQueue.Enqueue(nextRecord);

        // If this edge is not an interior edge, mark the edge as "reached." You do not 
        //  mark interior edges as "reached," since they might participate in a restricted turn
        // and you want to allow other (potentially unrestricted) search paths to reach
        // this edge, just in case.
        if (toEdge.TurnParticipationType !=
            ESRI.ArcGIS.Geodatabase.esriNetworkTurnParticipationType.esriNTPTInterior)
        {
            if (toEdge.Direction ==
                ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection.esriNEDAlongDigitized)
                isAlongReached[toEdge.EID] = true;
            else if (toEdge.Direction ==
                ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection.esriNEDAgainstDigitized)
                isAgainstReached[toEdge.EID] = true;
            else
                throw new System.Exception("Invalid edge direction");
        }
    }
}

// The search completed, and the destination was never found.
throw new System.Exception("Destination unreachable");
}
[VB.NET] 
' Iterate over the queue until the destination is found or the queue is empty.
While searchQueue.Count > 0
    Dim currentSearchStruct As SearchStruct = DirectCast(searchQueue.Dequeue(), SearchStruct)
    
    ' Check if this is the destination.
    If currentSearchStruct.junctionEID = destinationJunctionEID Then
        Return currentSearchStruct.numberOfHops
    End If
    ' Return the final hop count.
    ' Populate the edges to indicate the path taken to reach this junction. This is necessary for
    ' detecting and tracking turns.
    Dim hasFromEdge As Boolean = False
    Dim hasLastExteriorEdge As Boolean = False
    
    If currentSearchStruct.fromEdgeEID <> -1 Then
        hasFromEdge = True
        
        ' If there was a previous edge in the search, populate the fromEdge with that edge's values.
        networkQuery.QueryEdge(currentSearchStruct.fromEdgeEID, currentSearchStruct.fromEdgeDirection, fromEdge)
        If currentSearchStruct.lastExteriorEdgeEID <> -1 Then
            hasLastExteriorEdge = True
            networkQuery.QueryEdge(currentSearchStruct.lastExteriorEdgeEID, currentSearchStruct.lastExteriorEdgeDirection, lastExteriorEdge)
        End If
    End If
    
    ' Find the adjacencies from the current junction. The NetworkForwardStar relies on the
    ' fromEdge and lastExteriorEdge objects to detect turns. Any restricted turns exclude
    ' the appropriate edges from being returned in the NetworkForwardStarAdjacencies object.
    fStarEx.QueryJunction(currentSearchStruct.junctionEID, junction)
    fStarEx.QueryAdjacencies(junction, If((hasFromEdge), fromEdge, Nothing), If((hasLastExteriorEdge), lastExteriorEdge, Nothing), fStarAdj)
    
    ' Iterate the adjacencies adding them to the search queue.
    Dim isJunctionFiltered As Boolean
    For index As Integer = 0 To fStarAdj.Count - 1
        fStarAdj.QueryEdge(index, toEdge, fromPosition, toPosition)
        fStarAdj.QueryToJunction(index, junction, isJunctionFiltered)
        
        ' If this edge has already been marked as "reached" in the search, don't search it again.
        ' If the junction is filtered (that is, inaccessible/restricted), skip this entry, since it
        ' won't provide a valid path to the destination.
        If (toEdge.Direction = ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection.esriNEDAlongDigitized AndAlso isAlongReached(toEdge.EID)) OrElse (toEdge.Direction = ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection.esriNEDAgainstDigitized AndAlso isAgainstReached(toEdge.EID)) OrElse isJunctionFiltered Then
            Continue For
        End If
        
        ' Prepare the struct for the next junction.
        Dim nextRecord As New SearchStruct()
        nextRecord.numberOfHops = currentSearchStruct.numberOfHops + 1
        ' The hop count!
        nextRecord.junctionEID = junction.EID
        nextRecord.fromEdgeEID = toEdge.EID
        nextRecord.fromEdgeDirection = toEdge.Direction
        nextRecord.lastExteriorEdgeEID = -1
        nextRecord.lastExteriorEdgeDirection = ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection.esriNEDNone
        
        ' Establish the last exterior edge information based on the current edge's turn
        ' participation type.
        If toEdge.TurnParticipationType = ESRI.ArcGIS.Geodatabase.esriNetworkTurnParticipationType.esriNTPTExterior Then
            nextRecord.lastExteriorEdgeEID = toEdge.EID
            nextRecord.lastExteriorEdgeDirection = toEdge.Direction
        ElseIf toEdge.TurnParticipationType = ESRI.ArcGIS.Geodatabase.esriNetworkTurnParticipationType.esriNTPTInterior Then
            nextRecord.lastExteriorEdgeEID = currentSearchStruct.lastExteriorEdgeEID
            nextRecord.lastExteriorEdgeDirection = currentSearchStruct.lastExteriorEdgeDirection
        End If
        
        ' Queue the search element.
        searchQueue.Enqueue(nextRecord)
        
        ' If this edge is not an interior edge, mark the edge as "reached." You do not mark
        ' interior edges as "reached" since they might participate in a restricted turn and you
        ' want to allow other (potentially unrestricted) search paths to reach this edge, just
        ' in case.
        If toEdge.TurnParticipationType <> ESRI.ArcGIS.Geodatabase.esriNetworkTurnParticipationType.esriNTPTInterior Then
            If toEdge.Direction = ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection.esriNEDAlongDigitized Then
                isAlongReached(toEdge.EID) = True
            ElseIf toEdge.Direction = ESRI.ArcGIS.Geodatabase.esriNetworkEdgeDirection.esriNEDAgainstDigitized Then
                isAgainstReached(toEdge.EID) = True
            Else
                Throw New System.Exception("Invalid edge direction")
            End If
        End If
    Next
End While

' The search completed and the destination was never found.
Throw New System.Exception("Destination unreachable")
End Function


See Also:

What is Network Analyst?
About the Network Analyst tutorial
Essential Network Analyst vocabulary
NetworkAnalyst
Network Analyst object model diagram
Network Analyst user interface object model diagram
An overview of the Network Analyst toolbox
What is a network dataset?
Geodatabase
What are geometric networks?
How to open a network dataset



To use the code in this topic, reference the following assemblies in your Visual Studio project. In the code files, you will need using (C#) or Imports (VB .NET) directives for the corresponding namespaces (given in parenthesis below if different from the assembly name):
Development licensing Deployment licensing
Engine Developer Kit Engine Runtime: Network
ArcInfo: Network Analyst ArcInfo: Network Analyst
ArcEditor: Network Analyst ArcEditor: Network Analyst
ArcView: Network Analyst ArcView: Network Analyst