graph

std/graph.h

• Member Types
• Member Variables
• Member Functions
  • Constructor
  • Utility
  • Iterators
  • Modifiers

---

template <class value_type>
struct graph

This structure implements a graph of labeled nodes with unlabeled arcs. The nodes are stored as a linked list and the arcs are stored as an array of iterators at each graph node.

We use a linked list to store the nodes so that the arcs aren't invalidated every time we add or remove a node. Furthermore, the arcs are unlabeled because a graph with labeled arcs can be implemented by a bipartite graph with unlabeled arcs.

Member Types

• struct iterator
• struct const_iterator
• typedef array<iterator> links
• typedef array<const_iterator> const_links
• typedef array<iterator>::iterator link_iterator
• typedef array<const_iterator>::iterator const_link_iterator
• typedef array<iterator>::const_iterator link_const_iterator
• typedef array<const_iterator>::const_iterator const_link_const_iterator
• struct end_node
• struct node

Member Variables

• end_node left, right implements the linked list of nodes

Member Functions

Constructor

graph()

The default constructor sets up the linked list of nodes the same way index_list does.

graph(const graph<value_type> &copy)

Copy the contents of another graph into this one.

Utility

void clear() Deletes all of the nodes in this graph, making it empty.

int size() Returns the number of nodes in this graph.

Iterators

iterator begin()
const_iterator begin() const

Returns an iterator to the first node in the list.

iterator end()
const_iterator end() const

returns an iterator to one after the last node in the list.

iterator rbegin()
const_iterator rbegin() const

returns an iterator to the last node in the list.

iterator rend()
const_iterator rend() const

returns an iterator to one before the first node in the list.

links next(const links &curr)
const_links next(const const_links &curr)

Get the nodes proceeding one or more nodes in curr in the graph by following outgoing arcs.

links prev(const links &curr)
const_links prev(const const_links &curr)

Get the nodes preceding one or more nodes in curr in the graph by following incoming arcs.

map<iterator, array<link_iterator> > next_conj(links curr)

Map each node proceeding one or more nodes in curr to the nodes it proceeds.

map<iterator, array<link_iterator> > prev_conj(links curr)

Map each node preceding one or more nodes in curr to the nodes it preceeds.

Modifiers

iterator insert(const value_type &value)

Create a new node in the graph.

graph<value_type> &operator=(const graph<value_type> &copy)

Copy one graph to another.

void update_index(end_node *loc)

Update the node indices after modifying the graph.