wiki:WikiStart

Version 2 (modified by hpwalton, 15 years ago) (diff)

--

Purpose of CoinGraphClasses?

The purpose of the CoinGraphClasses? collection of Network Representations and Algorithms is to facilitate the development and implementation of Network Algorithms. The library was designed with some key ideas in mind:

Key ideas

  • Use STL and STL-like interfaces
  • Allow for common iteration through the network containers regardless of representation
  • Provide the ability to access the data structures named "nodes" and "arcs" for clarity
  • Any Network representation should be able to survive more than one Algorithm
  • Any Algorithm should be able to survive more than one Network Representation
  • Make the representations as compact as possible without sacrificing speed or time complexity

Terminology

  • Node:Often called a vertex, or point. It is normally represented by a circle. In a transportation Network, these might be locations or cities on a map
  • Arc:Often called an edge, or arrow. It may be either directed or undirected. The head is the destination, the tail is the origin. The head and tail are Nodes that are at either end. In a transportation network, the Arcs might be roads, or navigation channels in rivers, or aircraft flight patterns. They supply connectivity between the Nodes. A one-way street might be represented by a directed arc. A two-way street might be an undirected arc or by two directed arcs that point in opposite directions.
  • iterator:An iterator provides a mechanism for accessing Nodes sequentially. With STL, you can have a collection of ints in an array called: vector < int > myVector. An iterator to this collection would be declared vector < int > ::iterator ;
  • const_iterator:A constant reference version of an iterator. The user cannot alter the value referred to by the iterator.
  • arc_iterator: An arc_iterator allows the user to access arcs of the network sequentially. The arcs may be accessed using two different means. One way is to sequentially access all the arcs in the network. The other is to access all the arcs at one node. Both have a common iterator type. The only real difference is the test for the end of iteration. If you want to iterate across a node's arcs, you use begin() and end() member functions of the node. If you wish to iterate through a network's arcs, you use the arc_begin() and arc_end() member functions.
  • const_arc_iterator: A constant reference version of an arc_iterator. The user cannot alter the arc referred to by the iterator.
  • algorithm:An algorithm is a series of steps that will accomplish a certain task with some (hopefully known) space and time complexity. A solver using the CoinGraphClasses? collections can be implemented similar to STL algorithms. This means that if you follow the common interface between different CoinGraphClasses? collections, then the algorithm can perform (maybe with different complexity) on any appropriate CoinGraphClasses? network with very little modification. A demonstration is included to show how this might be accomplished.

C++ and the Standard C++ Library

The introduction of STL into the C++ library will have significant impact on algorithm developers using C++. With the advent of common containers and basic Computer Science algorithms as part of the standard, code (hence algorithms) may be shared more readily and used with data types that more difficult to use in the past.

More information on STL is available either from books, or the web. This will not assist in teaching you STL. However, if you are familiar with STL and C++, then you should find using CoinGraphClasses? will be second nature.

Network Containers

There are some difficulties in building containers for Networks that do not arise with normal containers. Normal containers have a single data type (or structure or class) that are collected together and maybe compared or sorted, etc. In the case of a Network, there are two related/distinct types: Nodes and Arcs. The Arcs refer to Nodes, but otherwise, they are somewhat independent.

In the implementation of Networks in CoinGraphClasses?, every CoinGraphClasses? container has a collection of Nodes. The Nodes are containers for their outbound Arcs. (In some implementations, there are back-arcs too). Also, there may be data on the Nodes and there may be data on the arcs. Unlike normal containers, this may be different data types.

Maybe a simple example would help. In a simple Shortest Path problem, there are locations (nodes) and distances between them (represented by durations or distances on the arcs). The goal is to find the shortest way between two locations using only the distances specified(arcs). Clearly, there must be some way of storing the duration/distance of the arc on the arc. Also, in most algorithms, there must be some way of storing information regarding the 'current status of a solution at the nodes.

Users of CoinGraphClasses? containers must implement Node and Arc content classes for thier problem. In the example above, the user may create a Miles and a NodeStatus? for the Arc cost data and the Node label data.

What does CoinGraphClasses? provide?

CoinGraphClasses? provides template containers that are parameterized on the Node and Arc data implemented by the user. Once again following the example above, and assuming a Static Network is suitable, the user might create a CoinGraphClasses? container using:

typedef StaticNet?< NodeStatus?,Miles > MyNetType?; MyNetType? myNetwork;

Things in common Each of the network representations have a few things in common. Few of the containers have special functions. The main things are storage and retrieval of nodes and arcs in the graph. Similar to STL containers, the complexity of retrieving one node or one arc depends on the implementation of the graph.

Node Ids are used to specify distinct nodes. The default comparison for nodes is by Node Id. For Arcs, there is no real default comparison.

Iterators over nodes and arcs and arcs at a node are available with each collection. Also, the complexity of iterating is constant. (i.e. getting the 'next' is performed in constant time complexity.

Algorithms can be applied to any of the network implementations without knowing the particular implementation. There are some times when incompatibilities exist. Great care was taken to ensure that a StaticNet? did not pay penalties on complexity just to fit the interface with a DynNet?. But, even though the interface is the same, care must still be taken. The StaticNet? must be created in a particular order. If the order is wrong, the Static Net will not load properly.

Network Container classifications Performance in many conditions was a primary concern in the design. The StaticNet? is really fast. However, it cannot be resized after load time. The DynNet? is fairly fast as well, but some operations are not as quick and the memory demand is higher. Some networks are truly directed and there is no purpose in having back-pointers. However, there is a need in some cases to be able to traverse both directions along an arc, regardless of whether it is directed or undirected. These needs motivated the creation of two classifications of Networks: One classification is based on Static versus Dynamic. The other is based on single versus both directions stored on an arc.

Static Network vs Dynamic Network The Static Network was born out of the need for a very fast network implementation. Essentially, it is a Forward Star representation where the nodes and arcs are both stored in STL vectors. The complexity for getting a node given a NodeId? is constant. This is important in some algorithms. However, this quickness is paid for in the lack of ability to delete arcs or to add arcs even in a non-standard order. If you are willing to pay the price of careful construction and post-load dynamic behavior, StaticNet? is the network representation for the greatest speed.

The Dynamic Network (DynNet?) allows for creation and deletion of arcs and nodes. You can freely create and destroy nodes randomly. However, this freedom comes at a price. The complexity for lookup of a Node given a Node Id is O(log(|V|)). where |V| is the number of vertices in the graph. Also, there is a higher space requirement. Although it is a constant factor based on the size of the graph, it may still be much larger than the StaticNet? for large graphs.

Network Algorithms Shortest Path (DijkSolver?, LayerSPSolver) The shortest path algorithm implementation mostly follows the original Dijkstra style. It is based on that strategy. It uses a heap to hold potentially 'active' nodes. There is a label at each node. The particular implmentation was inspired by an algorithm in "Network Flows" book by Ahuja, Mangnanti, and Orlin.

The Shortest Path Problem is the problem of finding the minimum "sum of weights" path through a network with weights on each arc. There is a distinct source and the solver finds minimum cost paths to all other nodes. They are extracted from the solver object using a collection of Path objects. (In rough terms Path object is a collection of Node Ids + a cost.)

The Layered Shortest Path solver solves a variant of this problem. ShortestPath?

Minimum Cost Spanning Tree (MSTSolver) The Minimum Cost Spanning Tree Problem involves finding the minimum cost collection of arcs such that all nodes are connected into a tree. Note that this requires an undirected graph (in examples, I chose a StaticFBNet). MinCostSpan?

Exhaustive Depth First Traversal (DFTraversal) There are several ways to traverse a graph. This is an exhaustive Depth first search into the graph. It uses recursion.

Note that this implementation is exhaustive in that it doesn't stop if a node has previously been visited. If the graph has cycles, this will be an infinite loop!

It is implemented in the form of an iterator. Each time the iterator is incremented (++), the object moves on to the next node in the sequence. It could be extended to be non-repeating if data is added at the nodes that indicate the node has previously been visited. Traversals

Exhaustive Breadth First Traversal (BFTraversal) Similar to DFS, but uses a queue as storage of active nodes. This can be fairly painful in terms of storage....so beware. Traversals

All Paths between source and sink (PathFind?) This exhaustive algorithm is similar to DFS, except it stores all paths that happen to run into the sink. more details can be viewed at: PathFind? An example is the PathFindExample?.cpp example code. Some Sample Code: Simple Simple construction of a graph with just a few nodes and arcs. SimpleShortestPath? This is a simple example that tests the network as well as the simple algorithm to solve the Shortest Path problem in a directed acyclic network. PathFindExample? This is a little more complex, but not overwhelming. There are 3 main points to this example: @li Demonstrate the use of the PathFind? algorithm @li Demonstrate having "empty data" on the graph thus reducing ram consumption @li Demonstrate the use of a DynNet? and a destructive example of removing a node on the fly SSPSolver This is a comprehensive example showing much more complex usage of the graph @li more complex data storage on nodes @li more complex data storea on arcs @li implements a well known algorithm for solving min cost network flow problems (Successive Shortest Paths) There is a reference in the code to the source of the algorithm. More detailed code information See the doxygen generated comments for more information on the particular classes. In particular, peruse the "Public Interface" module comments.