A Graph is a container of references to objects (called objrefs) that may be linked to an arbitrary number of other objects. The objects themselves may be located on other processors, ie the Graph may be distributed. Objects are polymorphic -- the only properties Graph needs to know is how create, copy, and serialise them, as well as what other objects they are linked to.

Because the objects are polymorphic, it is possible to create hypergraphs. Simply have two types of object in the graph -- pins and wires, say. A pin may be connected to multiple wire objects, just as wires may be connected to multiple pins.

The objrefs themselves are stored in a maplike object called an omap, which is replicated across all processors.

A short synopsis of Graph is as follows:

class Graph: public Ptrlist
  omap objects;

  Graph& operator=(const Graph&);

  /* object management */
  objref& AddObject(object* o, GraphID_t id, bool managed=false); 
  template <class T>
  objref& AddObject(GraphID_t id); 
  template <class T>
  objref& AddObject(const T& master_copy, GraphID_t id); 

  /* these methods must be called on all processors simultaneously */
  void Prepare_Neighbours(bool cache_requests=false);
  void Partition_Objects();
  void Distribute_Objects();
  void gather();

  void rebuild_local_list();   
  void clear_non_local()
  void print(int proc) 

(see §14.4) is a list of references to objrefs), pointing to objects stored locally on the current processor.
In the first form, add an already created object to the Graph. In the second form create a new object of type T, and add it to the Graph. T must be derived from the abstract base class object. You must explicitly supply the type of the object to be created as a template argument:
In the third form, create a new object, and initialise its data with the contents of argument master_copy.
For each object on the local processor, ensure that all objects connected to it are brought up to date, by obtaining data from remote processors if necessary. If the network structure has not changed since the last call to this method, set the flag cache_requests to true, which substantially reduces the amount of interprocessor communication required.
Call the ParMETIS partitioner to redistribute the graph in an optimal way over the processors. ParMETIS executes in parallel, and requires that the objects be distributed before this call. One way of achieving this is to make a simple assignment of objects to processors (by setting the proc member of each objref), then call Distribute_Objects().
Broadcast graph data from processor 0, and call
rebuild_local_list() on each processor.
Bring the entire graph on processor 0 up to date, copying information from remote processors as necessary. A gather(), followed by Distribute_Pins() brings all processors' graphs up-to-date. This is, naturally, an expensive operation, and should be done for startup or checkpointing purposes.
Reconstruct the list of objrefs local to the current processor, according to the proc member of the objrefs.
Nullify all objrefs that don't belong to the current processor. This can be used to save memory usage.