network analysis

FC-19 - Networks Defined

A network is a widely used term with different definitions and methodologies depending on the applications. In GIS, a network refers to an arrangement of elements (i.e., nodes, links) and information on their connections and interactions. There are two types of networks: physical and logical. While a physical network has tangible objects (e.g., road segments), a logical network represents logical connections among nodes and links. A network can be represented with a mathematical notion called graph theory. Different network components are utilized to describe characteristics of a network including loops, walks, paths, circuits, and parallel edges. Network data are commonly organized in a vector format with network topology, specifically connectivity among nodes and links, whereas raster data can be also utilized for a least-cost problem over continuous space. Network data is utilized in a wide range of network analyses, including the classic shortest path problem.

FC-19 - Networks defined
  • Define different interpretations of “cost” in various routing applications
  • Describe networks that apply to specific applications or industries
  • Create a data set with network attributes and topology
  • Define the following terms pertaining to a network: Loops, multiple edges, the degree of a vertex, walk, trail, path, cycle, fundamental cycle
AM-44 - Modelling Accessibility

Modelling accessibility involves combining ideas about destinations, distance, time, and impedances to measure the relative difficulty an individual or aggregate region faces when attempting to reach a facility, service, or resource. In its simplest form, modelling accessibility is about quantifying movement opportunity. Crucial to modelling accessibility is the calculation of the distance, time, or cost distance between two (or more) locations, which is an operation that geographic information systems (GIS) have been designed to accomplish. Measures and models of accessibility thus draw heavily on the algorithms embedded in a GIS and represent one of the key applied areas of GIS&T.

AM-43 - Other classic network problems
  • Describe several classic problems to which network analysis is applied (e.g., the traveling salesman problem, the Chinese postman problem)
  • Explain why heuristic solutions are generally used to address the combinatorially complex nature of these problems and the difficulty of solving them optimally
AM-41 - Flow modeling
  • Describe practical situations in which flow is conserved while splitting or joining at nodes of the network
  • Apply a maximum flow algorithm to calculate the largest flow from a source to a sink, using the edges of the network, subject to capacity constraints on the arcs and the conservation of flow
  • Explain how the concept of capacity represents an upper limit on the amount of flow through the network
  • Demonstrate how capacity is assigned to edges in a network using the appropriate data structure
AM-40 - Least-cost (shortest) path analysis
  • Describe some variants of Dijkstra’s algorithm that are even more efficient
  • Discuss the difference of implementing Dijkstra’s algorithm in raster and vector modes
  • Demonstrate how K-shortest path algorithms can be implemented to find many efficient alternate paths across the network
  • Compute the optimum path between two points through a network with Dijkstra’s algorithm
  • Explain how a leading World Wide Web-based routing system works (e.g., MapQuest, Yahoo Maps, Google)
FC-19 - Networks defined
  • Define different interpretations of “cost” in various routing applications
  • Describe networks that apply to specific applications or industries
  • Create a data set with network attributes and topology
  • Define the following terms pertaining to a network: Loops, multiple edges, the degree of a vertex, walk, trail, path, cycle, fundamental cycle
AM-44 - Modelling Accessibility

Modelling accessibility involves combining ideas about destinations, distance, time, and impedances to measure the relative difficulty an individual or aggregate region faces when attempting to reach a facility, service, or resource. In its simplest form, modelling accessibility is about quantifying movement opportunity. Crucial to modelling accessibility is the calculation of the distance, time, or cost distance between two (or more) locations, which is an operation that geographic information systems (GIS) have been designed to accomplish. Measures and models of accessibility thus draw heavily on the algorithms embedded in a GIS and represent one of the key applied areas of GIS&T.

AM-43 - Other classic network problems
  • Describe several classic problems to which network analysis is applied (e.g., the traveling salesman problem, the Chinese postman problem)
  • Explain why heuristic solutions are generally used to address the combinatorially complex nature of these problems and the difficulty of solving them optimally
AM-41 - Flow modeling
  • Describe practical situations in which flow is conserved while splitting or joining at nodes of the network
  • Apply a maximum flow algorithm to calculate the largest flow from a source to a sink, using the edges of the network, subject to capacity constraints on the arcs and the conservation of flow
  • Explain how the concept of capacity represents an upper limit on the amount of flow through the network
  • Demonstrate how capacity is assigned to edges in a network using the appropriate data structure

Pages