wiki:CgcComponents

What does Cgc provide?

Template graph containers

Cgc provides template containers that are parameterized on the Node info and Arc info data implemented by the user. Once again following the example above, and assuming a Static Network is suitable, the user might create a Cgc 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.

  • Directed and Undirected

A directed graph allows traversal of the "arcs" only in the direction they point. Storage only occurs for the "head" end of the arc. For "undirected" graphs, one likely needs to traverse the graph in either direction. this may be achieved by creating arcs in both directions in a directed graph, but that may incur some overhead of arc storage. It may also increase the complexity of the code required to do the arc storage properly. To avoid this, there is a static bi-directional graph: StaticFBNet the FB stands for Forward and Back. It is fast and compact similar to the StaticNetwork?, but the back arcs add a little more cost. Further, there are additional methods for traversing back arcs: back_arc_begin(), back_arc_end()

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 the Shortest Path problem. One can 'enable' and 'disable' nodes without reconstructing the graph. (LayerSPSolver)
  • 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.

This solver finds all components in a graph (or subgraph defined by a start and end iterator).

  • Min Cost Flow using Successive Shortest Paths (SSPSolver)

This implementation uses successive shortest paths to solve a Min Cost Flow problem.

Utilities

Last modified 12 years ago Last modified on Nov 10, 2006 9:38:11 PM