ListDigraph

Declared in lemon/list_graph.h, in the group Graph Structures; the same class on the Doxygen site.

class ListDigraph : public DigraphExtender< ListDigraphBase >

A general directed graph structure.

ListDigraph is a versatile and fast directed graph implementation based on linked lists that are stored in std::vector structures.

This type fully conforms to the Digraph concept and it also provides several useful additional functionalities. Most of its member functions and nested classes are documented only in the concept class.

This class provides only linear time counting for nodes and arcs.

See also

ListGraph

Public Functions

inline ListDigraph()

Constructor.

inline Node addNode()

Add a new node to the digraph.

This function adds a new node to the digraph.

Returns:

The new node.

inline Arc addArc( Node s , Node t )

Add a new arc to the digraph.

This function adds a new arc to the digraph with source node s and target node t.

Returns:

The new arc.

inline void erase( Node n )

Erase a node from the digraph.

This function erases the given node along with its outgoing and incoming arcs from the digraph.

Note

All iterators referencing the removed node or the connected arcs are invalidated, of course.

inline void erase( Arc a )

Erase an arc from the digraph.

This function erases the given arc from the digraph.

Note

All iterators referencing the removed arc are invalidated, of course.

inline bool valid( Node n ) const

Node validity check.

This function gives back true if the given node is valid, i.e. it is a real node of the digraph.

Warning

A removed node could become valid again if new nodes are added to the digraph.

inline bool valid( Arc a ) const

Arc validity check.

This function gives back true if the given arc is valid, i.e. it is a real arc of the digraph.

Warning

A removed arc could become valid again if new arcs are added to the digraph.

inline void changeTarget( Arc a , Node n )

Change the target node of an arc.

This function changes the target node of the given arc a to n.

Note

ArcIt and OutArcIt iterators referencing the changed arc remain valid, but InArcIt iterators are invalidated.

Warning

This functionality cannot be used together with the Snapshot feature.

inline void changeSource( Arc a , Node n )

Change the source node of an arc.

This function changes the source node of the given arc a to n.

Note

InArcIt iterators referencing the changed arc remain valid, but ArcIt and OutArcIt iterators are invalidated.

Warning

This functionality cannot be used together with the Snapshot feature.

inline void reverseArc( Arc a )

Reverse the direction of an arc.

This function reverses the direction of the given arc.

Note

ArcIt, OutArcIt and InArcIt iterators referencing the changed arc are invalidated.

Warning

This functionality cannot be used together with the Snapshot feature.

inline void contract( Node u , Node v , bool r = true )

Contract two nodes.

This function contracts the given two nodes. Node v is removed, but instead of deleting its incident arcs, they are joined to node u. If the last parameter r is true (this is the default value), then the newly created loops are removed.

Note

The moved arcs are joined to node u using changeSource() or changeTarget(), thus ArcIt and OutArcIt iterators are invalidated for the outgoing arcs of node v and InArcIt iterators are invalidated for the incoming arcs of v. Moreover all iterators referencing node v or the removed loops are also invalidated. Other iterators remain valid.

Warning

This functionality cannot be used together with the Snapshot feature.

inline Node split( Node n , bool connect = true )

Split a node.

This function splits the given node. First, a new node is added to the digraph, then the source of each outgoing arc of node n is moved to this new node. If the second parameter connect is true (this is the default value), then a new arc from node n to the newly created node is also added.

Note

All iterators remain valid.

Warning

This functionality cannot be used together with the Snapshot feature.

Returns:

The newly created node.

inline Node split( Arc a )

Split an arc.

This function splits the given arc. First, a new node v is added to the digraph, then the target node of the original arc is set to v. Finally, an arc from v to the original target is added.

Note

InArcIt iterators referencing the original arc are invalidated. Other iterators remain valid.

Warning

This functionality cannot be used together with the Snapshot feature.

Returns:

The newly created node.

inline void clear()

Clear the digraph.

This function erases all nodes and arcs from the digraph.

Note

All iterators of the digraph are invalidated, of course.

inline void reserveNode( int n )

Reserve memory for nodes.

Using this function, it is possible to avoid superfluous memory allocation: if you know that the digraph you want to build will be large (e.g. it will contain millions of nodes and/or arcs), then it is worth reserving space for this amount before starting to build the digraph.

See also

reserveArc()

inline void reserveArc( int m )

Reserve memory for arcs.

Using this function, it is possible to avoid superfluous memory allocation: if you know that the digraph you want to build will be large (e.g. it will contain millions of nodes and/or arcs), then it is worth reserving space for this amount before starting to build the digraph.

See also

reserveNode()

class Snapshot

Class to make a snapshot of the digraph and restore it later.

The newly added nodes and arcs can be removed using the restore() function.

Note

After a state is restored, you cannot restore a later state, i.e. you cannot add the removed nodes and arcs again using another Snapshot instance.

Warning

Node and arc deletions and other modifications (e.g. reversing, contracting, splitting arcs or nodes) cannot be restored. These events invalidate the snapshot. However, the arcs and nodes that were added to the digraph after making the current snapshot can be removed without invalidating it.

Public Functions

inline Snapshot()

Default constructor. You have to call save() to actually make a snapshot.

inline Snapshot( ListDigraph & gr )

Constructor that immediately makes a snapshot.

This constructor immediately makes a snapshot of the given digraph.

inline void save( ListDigraph & gr )

Make a snapshot.

This function makes a snapshot of the given digraph. It can be called more than once. In case of a repeated call, the previous snapshot gets lost.

inline void restore()

Undo the changes until the last snapshot.

This function undos the changes until the last snapshot created by save() or Snapshot(ListDigraph&).

Warning

This method invalidates the snapshot, i.e. repeated restoring is not supported unless you call save() again.

inline bool valid() const

Returns true if the snapshot is valid.

This function returns true if the snapshot is valid.

Protected Types

typedef Parent::NodeNotifier NodeNotifier

Protected Functions

inline void addNode( const Node & node )
inline void eraseNode( const Node & node )
inline void addArc( const Arc & arc )
inline void eraseArc( const Arc & arc )
inline void attach( ListDigraph & _digraph )
inline void detach()
inline bool attached() const
inline void clear()

Protected Attributes

ListDigraph * digraph
NodeObserverProxy node_observer_proxy
ArcObserverProxy arc_observer_proxy
std::list< Node > added_nodes
std::list< Arc > added_arcs
class NodeObserverProxy : public AlterationNotifier< DigraphExtender , Node >::ObserverBase

Public Functions

inline NodeObserverProxy( Snapshot & _snapshot )

Protected Functions

inline virtual void add( const Node & node )
inline virtual void add( const std::vector< Node > & nodes )
inline virtual void erase( const Node & node )
inline virtual void erase( const std::vector< Node > & nodes )
inline virtual void build()
inline virtual void clear()

Protected Attributes

Snapshot & snapshot
class ArcObserverProxy : public ObserverBase

Public Functions

inline ArcObserverProxy( Snapshot & _snapshot )

Protected Functions

inline virtual void add( const Arc & arc )
inline virtual void add( const std::vector< Arc > & arcs )
inline virtual void erase( const Arc & arc )
inline virtual void erase( const std::vector< Arc > & arcs )
inline virtual void build()
inline virtual void clear()

Protected Attributes

Snapshot & snapshot