Open Graph Drawing Framework  v.2007.11

Overview Class Hierarchy Class Index Class List Members Namespaces Source Files Search for:

ogdf::Graph Class Reference

Data type for general directed graphs (adjacency list representation). More...

#include <Graph_d.h>

Inheritance diagram for ogdf::Graph:

List of all members.

Public Types
enum	EdgeType { association = 0, generalization = 1, dependency = 2 }
	The type of edges (only used in derived classes). More...
enum	NodeType {   vertex, dummy, generalizationMerger, generalizationExpander,   highDegreeExpander, lowDegreeExpander, associationClass }
	The type of nodes. More...
Public Member Functions
	Graph ()
	Constructs an empty graph.
	Graph (const Graph &G)
	Constructs a graph that is a copy of G.
virtual	~Graph ()
Access methods
bool	empty () const
	Returns true iff the graph is empty, i.e., contains no nodes.
int	numberOfNodes () const
	Returns the number of nodes in the graph.
int	numberOfEdges () const
	Returns the number of edges in the graph.
int	maxNodeIndex () const
	Returns the largest used node index.
int	maxEdgeIndex () const
	Returns the largest used edge index.
int	maxAdjEntryIndex () const
	Returns the largest used adjEntry index.
int	nodeArrayTableSize () const
	Returns the table size of node arrays associated with this graph.
int	edgeArrayTableSize () const
	Returns the table size of edge arrays associated with this graph.
int	adjEntryArrayTableSize () const
	Returns the table size of adjEntry arrays associated with this graph.
node	firstNode () const
	Returns the first node in the list of all nodes.
node	lastNode () const
	Returns the last node in the list of all nodes.
edge	firstEdge () const
	Returns the first edge in the list of all edges.
edge	lastEdge () const
	Returns the last edge in the list of all edges.
node	chooseNode () const
	Returns a randomly chosen node.
edge	chooseEdge () const
	Returns a randomly chosen edge.
template<class NODELIST>
void	allNodes (NODELIST &nodes) const
	Returns a list with all nodes of the graph.
template<class EDGELIST>
void	allEdges (EDGELIST &edges) const
	Returns a list with all edges of the graph.
template<class EDGELIST>
void	adjEdges (node v, EDGELIST &edges) const
	Returns a list with all edges adjacent to node v.
template<class ADJLIST>
void	adjEntries (node v, ADJLIST &entries) const
	Returns a list with all entries in the adjacency list of node v.
template<class EDGELIST>
void	inEdges (node v, EDGELIST &edges) const
	Returns a list with all incoming edges of node v.
template<class EDGELIST>
void	outEdges (node v, EDGELIST &edges) const
	Returns a list with all outgoing edges of node v.
Creation of new nodes and edges
node	newNode ()
	Creates a new node and returns it.
node	newNode (int index)
	Creates a new node with predefined index and returns it.
edge	newEdge (node v, node w)
	Creates a new edge (v,w) and returns it.
edge	newEdge (node v, node w, int index)
	Creates a new edge (v,w) with predefined index and returns it.
edge	newEdge (adjEntry adjSrc, adjEntry adjTgt, Direction dir=ogdf::after)
	Creates a new edge at predefined positions in the adjacency lists.
edge	newEdge (node v, adjEntry adjTgt)
	Creates a new edge at predefined positions in the adjacency lists.
edge	newEdge (adjEntry adjSrc, node w)
	Creates a new edge at predefined positions in the adjacency lists.
Removing nodes and edges
void	delNode (node v)
	Removes node v and all incident edges from the graph.
void	delEdge (edge e)
	Removes edge e from the graph.
void	clear ()
	Removes all nodes and all edges from the graph.
Hiding edges
These methods are used for temporarily hiding edges. Edges are removed from the list of all edges and their corresponding adfjacency entries from the repsective adjacency lists, but the edge objects themselves are not destroyed; hiddenedges can later be reactivated with restoreEdge().
void	hideEdge (edge e)
	Hides the edge e.
void	restoreEdge (edge e)
	Restores a hidden edge e.
void	restoreAllEdges ()
	Restores all hidden edges.
Advanced modification methods
virtual edge	split (edge e)
	Splits edge e into two edges introducing a new node.
void	unsplit (node u)
	Undoes a split operation.
virtual void	unsplit (edge eIn, edge eOut)
	Undoes a split operation.
node	splitNode (adjEntry adjStartLeft, adjEntry adjStartRight)
	Splits a node while preserving the order of adjacency entries.
node	contract (edge e)
	Contracts edge e while preserving the order of adjacency entries.
void	move (edge e, adjEntry adjSrc, Direction dirSrc, adjEntry adjTgt, Direction dirTgt)
void	moveTarget (edge e, node w)
	Moves the target node of edge e to node w.
void	moveTarget (edge e, adjEntry adjTgt, Direction dir)
	Moves the target node of edge e to node w.
void	moveSource (edge e, node w)
	Moves the source node of edge e to node w.
void	moveSource (edge e, adjEntry adjSrc, Direction dir)
	Moves the source node of edge e to node w.
edge	searchEdge (node v, node w) const
	Searches and returns the edge between node v and node w.
void	reverseEdge (edge e)
	Reverses the edge e, i.e., exchanges source and target node.
void	reverseAllEdges ()
	Reverses all edges in the graph.
template<class NODELIST>
void	collaps (NODELIST &nodes)
	Collapses all nodes in the list nodes to the first node in the list.
template<class ADJ_ENTRY_LIST>
void	sort (node v, const ADJ_ENTRY_LIST &newOrder)
	Sorts the adjacency list of node v according to newOrder.
void	reverseAdjEdges (node v)
	Reverses the adjacency list of v.
void	moveAdj (adjEntry adjMove, Direction dir, adjEntry adjPos)
	Moves the adjacency entry adjMove before or after adjPos.
void	moveAdjAfter (adjEntry adjMove, adjEntry adjAfter)
	Moves the adjacency entry adjMove after adjAfter.
void	moveAdjBefore (adjEntry adjMove, adjEntry adjBefore)
	Moves the adjacency entry adjMove before adjBefore.
void	reverseAdjEdges ()
	Reverses all adjacency lists.
void	swapAdjEdges (adjEntry adj1, adjEntry adj2)
	Exchanges two entries in an adjacency list.
Input and output
bool	readGML (const char *fileName)
	Reads a graph in GML format from file fileName.
bool	readGML (istream &is)
	Reads a graph in GML format from input stream is.
void	writeGML (const char *fileName) const
	Writes the graph in GML format to file fileName.
void	writeGML (ostream &os) const
	Writes the graph in GML format to output stream os.
bool	readLEDAGraph (const char *fileName)
	Reads a graph in LEDA format from file fileName.
bool	readLEDAGraph (istream &is)
	Read a graph in LEDA format from input stream is.
Miscellaneous
int	genus () const
	Returns the genus of the graph.
bool	representsCombEmbedding () const
	Returns true iff the graph represents a combinatorial embedding.
bool	consistencyCheck () const
	Checks the consistency of the data structure.
Registering of arrays
These methods are used by various graph array types like NodeArray or EdgeArray. There should be no need to use them directly in user code.
ListIterator< NodeArrayBase * >	registerArray (NodeArrayBase *pNodeArray) const
	Registers a node array.
ListIterator< EdgeArrayBase * >	registerArray (EdgeArrayBase *pEdgeArray) const
	Registers an edge array.
ListIterator< AdjEntryArrayBase * >	registerArray (AdjEntryArrayBase *pAdjArray) const
	Registers an adjEntry array.
ListIterator< GraphObserver * >	registerStructure (GraphObserver *pStructure) const
	Registers a GraphObserver (e.g. a ClusterGraph).
void	unregisterArray (ListIterator< NodeArrayBase * > it) const
	Unregisters a node array.
void	unregisterArray (ListIterator< EdgeArrayBase * > it) const
	Unregisters an edge array.
void	unregisterArray (ListIterator< AdjEntryArrayBase * > it) const
	unregisters an adjEntry array.
void	unregisterStructure (ListIterator< GraphObserver * > it) const
	Unregisters a GraphObserver.
void	resetEdgeIdCount (int maxId)
	Resets the edge id count to maxId.
Operators
Graph &	operator= (const Graph &G)
	Assignment operator.
void *	operator new (size_t nBytes)
void *	operator new (size_t, void *p)
void	operator delete (void *p, size_t nBytes)
Static Public Member Functions
static int	nextPower2 (int start, int idCount)
	Returns the smallest power of 2 which is >= 2^start and > idCount.
Protected Member Functions
void	construct (const Graph &G, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)
void	assign (const Graph &G, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)
void	constructInitByNodes (const Graph &G, const List< node > &nodes, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)
	Constructs a copy of the subgraph of G induced by nodes.
void	constructInitByActiveNodes (const List< node > &nodes, const NodeArray< bool > &activeNodes, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)
Private Member Functions
void	copy (const Graph &G, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)
void	copy (const Graph &G)
edge	createEdgeElement (node v, node w, adjEntry adjSrc, adjEntry adjTgt)
node	pureNewNode ()
void	moveAdj (adjEntry adj, node w)
void	reinitArrays ()
void	reinitStructures ()
void	resetAdjEntryIndex (int newIndex, int oldIndex)
bool	readToEndOfLine (istream &is)
Private Attributes
GraphList< NodeElement >	m_nodes
	The list of all nodes.
GraphList< EdgeElement >	m_edges
	The list of all edges.
int	m_nNodes
	The number of nodes in the graph.
int	m_nEdges
	The number of edges in the graph.
int	m_nodeIdCount
	The Index that will be assigned to the next created node.
int	m_edgeIdCount
	The Index that will be assigned to the next created edge.
int	m_nodeArrayTableSize
	The current table size of node arrays associated with this graph.
int	m_edgeArrayTableSize
	The current table size of edge arrays associated with this graph.
ListPure< NodeArrayBase * >	m_regNodeArrays
	The registered node arrays.
ListPure< EdgeArrayBase * >	m_regEdgeArrays
	The registered edge arrays.
ListPure< AdjEntryArrayBase * >	m_regAdjArrays
	The registered adjEntry arrays.
ListPure< GraphObserver * >	m_regStructures
	The registered graph structures.
GraphList< EdgeElement >	m_hiddenEdges
	The list of hidden edges.

---

Detailed Description

Data type for general directed graphs (adjacency list representation).

Iteration

Besides the usage of iteration macros defined in Graph_d.h, the following code is recommended for further iteration tasks.

• Iteration over all outgoing edges e of node v:

    forall_adj_edges(e,v)
      if(e->source() != v) continue;
  

• Iteration over all ingoing edges e of node v:

    forall_adj_edges(e,v)
        if(e->target() != v) continue;
  

• Iteration over all nodes x reachable by an outgoing edge e of node v (without self-loops):

    forall_adj_edges(e,v)
      if ((x = e->target()) == v) continue;
  

• Iteration over all nodes x reachable by an outgoing edge e of node v (with self-loops):

    forall_adj_edges(e,v) {
      if (e->source() != v) continue;
      x = e->target();
    }
  

• Iteration over all nodes x reachable by an ingoing edge e of node v (without self-loops):

    forall_adj_edges(e,v)
      if ((x = e->source()) == v) continue;
  

• Iteration over all nodes x reachable by an ingoing edge e of node v (with self-loops):

    forall_adj_edges(e,v) {
      if (e->target() != v) continue;
      x = e->source();
    }
  

Definition at line 697 of file Graph_d.h.

---

Member Enumeration Documentation

enum ogdf::Graph::EdgeType

The type of edges (only used in derived classes).

Enumerator:

association
generalization
dependency

Definition at line 723 of file Graph_d.h.

enum ogdf::Graph::NodeType

The type of nodes.

Enumerator:

vertex
dummy
generalizationMerger
generalizationExpander
highDegreeExpander
lowDegreeExpander
associationClass

Reimplemented in ogdf::ExtendedNestingGraph.

Definition at line 730 of file Graph_d.h.

---

Constructor & Destructor Documentation

ogdf::Graph::Graph

(

)

Constructs an empty graph.

ogdf::Graph::Graph

(

const Graph &

G

)

Constructs a graph that is a copy of G.

The constructor assures that the adjacency lists of nodes in the constructed graph are in the same order as the adjacency lists in G. This is in particular important when dealing with embedded graphs.

virtual ogdf::Graph::~Graph

(

)

[virtual]

---

Member Function Documentation

bool ogdf::Graph::empty

(

)

const [inline]

Returns true iff the graph is empty, i.e., contains no nodes.

Definition at line 762 of file Graph_d.h.

int ogdf::Graph::numberOfNodes

(

)

const [inline]

Returns the number of nodes in the graph.

Definition at line 765 of file Graph_d.h.

int ogdf::Graph::numberOfEdges

(

)

const [inline]

Returns the number of edges in the graph.

Definition at line 768 of file Graph_d.h.

int ogdf::Graph::maxNodeIndex

(

)

const [inline]

Returns the largest used node index.

Definition at line 771 of file Graph_d.h.

int ogdf::Graph::maxEdgeIndex

(

)

const [inline]

Returns the largest used edge index.

Definition at line 773 of file Graph_d.h.

int ogdf::Graph::maxAdjEntryIndex

(

)

const [inline]

Returns the largest used adjEntry index.

Definition at line 775 of file Graph_d.h.

int ogdf::Graph::nodeArrayTableSize

(

)

const [inline]

Returns the table size of node arrays associated with this graph.

Definition at line 778 of file Graph_d.h.

int ogdf::Graph::edgeArrayTableSize

(

)

const [inline]

Returns the table size of edge arrays associated with this graph.

Definition at line 780 of file Graph_d.h.

int ogdf::Graph::adjEntryArrayTableSize

(

)

const [inline]

Returns the table size of adjEntry arrays associated with this graph.

Definition at line 782 of file Graph_d.h.

node ogdf::Graph::firstNode

(

)

const [inline]

Returns the first node in the list of all nodes.

Definition at line 785 of file Graph_d.h.

node ogdf::Graph::lastNode

(

)

const [inline]

Returns the last node in the list of all nodes.

Definition at line 787 of file Graph_d.h.

edge ogdf::Graph::firstEdge

(

)

const [inline]

Returns the first edge in the list of all edges.

Definition at line 790 of file Graph_d.h.

edge ogdf::Graph::lastEdge

(

)

const [inline]

Returns the last edge in the list of all edges.

Definition at line 792 of file Graph_d.h.

node ogdf::Graph::chooseNode

(

)

const

Returns a randomly chosen node.

edge ogdf::Graph::chooseEdge

(

)

const

Returns a randomly chosen edge.

template<class NODELIST>

void ogdf::Graph::allNodes

(

NODELIST &

nodes

)

const [inline]

Returns a list with all nodes of the graph.

Definition at line 801 of file Graph_d.h.

template<class EDGELIST>

void ogdf::Graph::allEdges

(

EDGELIST &

edges

)

const [inline]

Returns a list with all edges of the graph.

Definition at line 809 of file Graph_d.h.

template<class EDGELIST>

void ogdf::Graph::adjEdges	(	node	v,
		EDGELIST &	edges
	)			const [inline]

Returns a list with all edges adjacent to node v.

Definition at line 817 of file Graph_d.h.

template<class ADJLIST>

void ogdf::Graph::adjEntries	(	node	v,
		ADJLIST &	entries
	)			const [inline]

Returns a list with all entries in the adjacency list of node v.

Definition at line 826 of file Graph_d.h.

template<class EDGELIST>

void ogdf::Graph::inEdges	(	node	v,
		EDGELIST &	edges
	)			const [inline]

Returns a list with all incoming edges of node v.

Definition at line 835 of file Graph_d.h.

template<class EDGELIST>

void ogdf::Graph::outEdges	(	node	v,
		EDGELIST &	edges
	)			const [inline]

Returns a list with all outgoing edges of node v.

Definition at line 844 of file Graph_d.h.

node ogdf::Graph::newNode

(

)

Creates a new node and returns it.

Reimplemented in ogdf::GraphCopySimple, and ogdf::GraphCopy.

node ogdf::Graph::newNode

(

int

index

)

Creates a new node with predefined index and returns it.

Precondition:

index is currently not the index of any other node in the graph.

Attention:

Passing a node index that is already in use results in an inconsistent data structure. Only use this method if you know what you're doing!

edge ogdf::Graph::newEdge	(	node	v,
		node	w
	)

Creates a new edge (v,w) and returns it.

Reimplemented in ogdf::GraphCopySimple, and ogdf::GraphCopy.

edge ogdf::Graph::newEdge	(	node	v,
		node	w,
		int	index
	)

Creates a new edge (v,w) with predefined index and returns it.

Precondition:

index is currently not the index of any other edge in the graph.

Attention:

Passing an edge index that is already in use results in an inconsistent data structure. Only use this method if you know what you're doing!

edge ogdf::Graph::newEdge	(	adjEntry	adjSrc,
		adjEntry	adjTgt,
		Direction	dir = ogdf::after
	)

Creates a new edge at predefined positions in the adjacency lists.

Let v be the node whose adjacency list contains adjSrc, and w the node whose adjacency list contains adjTgt. Then, the created edge is (v,w).

Parameters:

	adjSrc	is the adjacency entry after which the new edge is inserted in the adjacency list of v.
	adjTgt	is the adjacency entry after which the new edge is inserted in the adjacency list of w.
	dir	specifies if the edge is inserted before or after the given adjacency entries.

Returns:

the created edge.

edge ogdf::Graph::newEdge	(	node	v,
		adjEntry	adjTgt
	)

Creates a new edge at predefined positions in the adjacency lists.

Let w be the node whose adjacency list contains adjTgt. Then, the created edge is (v,w).

Parameters:

	v	is the source node of the new edge; the edge is added at the end of the adjacency list of v.
	adjTgt	is the adjacency entry after which the new edge is inserted in the adjacency list of w.

Reimplemented in ogdf::GraphCopy.

edge ogdf::Graph::newEdge	(	adjEntry	adjSrc,
		node	w
	)

Creates a new edge at predefined positions in the adjacency lists.

Let v be the node whose adjacency list contains adjSrc. Then, the created edge is (v,w).

Parameters:

	adjSrc	is the adjacency entry after which the new edge is inserted in the adjacency list of v.
	w	is the source node of the new edge; the edge is added at the end of the adjacency list of w.

Reimplemented in ogdf::GraphCopy.

void ogdf::Graph::delNode

(

node

v

)

Removes node v and all incident edges from the graph.

void ogdf::Graph::delEdge

(

edge

e

)

Removes edge e from the graph.

void ogdf::Graph::clear

(

)

Removes all nodes and all edges from the graph.

void ogdf::Graph::hideEdge

(

edge

e

)

Hides the edge e.

The edge e is removed from the list of all edges and adjacency lists of nodes, but not deleted; e can be restored by calling restoreEdge(e).

Attention:

If an edge is hidden, its source and target node may not be deleted!

void ogdf::Graph::restoreEdge

(

edge

e

)

Restores a hidden edge e.

Precondition:

e is currently hidden and the source and target not have not been removed!

void ogdf::Graph::restoreAllEdges

(

)

Restores all hidden edges.

virtual edge ogdf::Graph::split

(

edge

e

)

[virtual]

Splits edge e into two edges introducing a new node.

Let e=(v,w). Then, the resulting two edges are e=(v,u) and e'=(u,w), where u is a new node.

Returns:

The edge e'.

Note:

The edge e is modified by this operation.

Reimplemented in ogdf::GraphCopy, ogdf::ClusterPlanRep, ogdf::PlanRep, ogdf::PlanRepExpansion, ogdf::PlanRepInc, and ogdf::PlanRepUML.

void ogdf::Graph::unsplit

(

node

u

)

Undoes a split operation.

Removes node u by joining the two edges adjacent to u. The outgoing edge of u is removed and the incoming edge e is reused

Returns:

The edge e.

Precondition:

u has exactly one incoming and one outgoing edge, and none of them is a self-loop.

virtual void ogdf::Graph::unsplit	(	edge	eIn,
		edge	eOut
	)			[virtual]

Undoes a split operation.

For two edges eIn = (x,u) and eOut = (u,y), removes node u by joining eIn and eOut. Edge eOut is removed and eIn is reused.

Precondition:

eIn and eOut are the only edges incident with u and none of them is a self-loop.

Reimplemented in ogdf::GraphCopy, and ogdf::PlanRepExpansion.

node ogdf::Graph::splitNode	(	adjEntry	adjStartLeft,
		adjEntry	adjStartRight
	)

Splits a node while preserving the order of adjacency entries.

This method splits a node v into two nodes vl and vr. Node vl receives all adjacent edges of v from adjStartLeft until the edge preceding adjStartRight, and vr the remaining nodes (thus adjStartRight is the first edge that goes to vr). The order of adjacency entries is preserved. Additionally, a new edge (vl,vr) is created, such that this edge is inserted before adjStartLeft and adjStartRight in the the adjacency lists of vl and vr.

Node v is modified to become node vl, and node vr is returned. This method is useful when modifying combinatorial embeddings.

Parameters:

	adjStartLeft	is the first entry that goes to the left node.
	adjStartRight	is the first entry that goes to the right node.

Returns:

the newly created node.

node ogdf::Graph::contract

(

edge

e

)

Contracts edge e while preserving the order of adjacency entries.

void ogdf::Graph::move	(	edge	e,
		adjEntry	adjSrc,
		Direction	dirSrc,
		adjEntry	adjTgt,
		Direction	dirTgt
	)

void ogdf::Graph::moveTarget	(	edge	e,
		node	w
	)

Moves the target node of edge e to node w.

If e=(v,u) before, then e=(v,w) afterwards-

void ogdf::Graph::moveTarget	(	edge	e,
		adjEntry	adjTgt,
		Direction	dir
	)

Moves the target node of edge e to node w.

If e=(v,u) before, then e=(v,w) afterwards. Inserts the adjacency entry before or after adjTgt according to dir.

void ogdf::Graph::moveSource	(	edge	e,
		node	w
	)

Moves the source node of edge e to node w.

If e=(v,u) before, then e=(w,u) afterwards.

void ogdf::Graph::moveSource	(	edge	e,
		adjEntry	adjSrc,
		Direction	dir
	)

Moves the source node of edge e to node w.

If e=(v,u) before, then e=(w,u) afterwards. Inserts the adjacency entry before or after adjSrc according to dir.

edge ogdf::Graph::searchEdge	(	node	v,
		node	w
	)			const

Searches and returns the edge between node v and node w.

void ogdf::Graph::reverseEdge

(

edge

e

)

Reverses the edge e, i.e., exchanges source and target node.

void ogdf::Graph::reverseAllEdges

(

)

Reverses all edges in the graph.

template<class NODELIST>

void ogdf::Graph::collaps

(

NODELIST &

nodes

)

[inline]

Collapses all nodes in the list nodes to the first node in the list.

Parallel edges are removed.

Definition at line 1071 of file Graph_d.h.

template<class ADJ_ENTRY_LIST>

void ogdf::Graph::sort	(	node	v,
		const ADJ_ENTRY_LIST &	newOrder
	)			[inline]

Sorts the adjacency list of node v according to newOrder.

Precondition:

newOrder contains exactly the adjacency entries of v!

Definition at line 1098 of file Graph_d.h.

void ogdf::Graph::reverseAdjEdges

(

node

v

)

[inline]

Reverses the adjacency list of v.

Definition at line 1109 of file Graph_d.h.

void ogdf::Graph::moveAdj	(	adjEntry	adjMove,
		Direction	dir,
		adjEntry	adjPos
	)			[inline]

Moves the adjacency entry adjMove before or after adjPos.

Parameters:

	adjMove	is an entry in the adjacency list of a node in this graph.
	adjPos	is an entry in the same adjacency list as adjMove.
	dir	specifies if adjMove is moved before or after adjPos.

Precondition:

adjMove and adjAfter are distinct entries in the same adjacency list.

Definition at line 1120 of file Graph_d.h.

void ogdf::Graph::moveAdjAfter	(	adjEntry	adjMove,
		adjEntry	adjAfter
	)			[inline]

Moves the adjacency entry adjMove after adjAfter.

Parameters:

	adjMove	is an entry in the adjacency list of a node in this graph.
	adjAfter	is an entry in the same adjacency list as adjMove.

Precondition:

adjMove and adjAfter are distinct entries in the same adjacency list.

Definition at line 1133 of file Graph_d.h.

void ogdf::Graph::moveAdjBefore	(	adjEntry	adjMove,
		adjEntry	adjBefore
	)			[inline]

Moves the adjacency entry adjMove before adjBefore.

Parameters:

	adjMove	is an entry in the adjacency list of a node in this graph.
	adjBefore	is an entry in the same adjacency list as adjMove.

Precondition:

adjMove and adjBefore are distinct entries in the same adjacency list.

Definition a