#include <Bpp/Graph/Graph.h>

Inheritance diagram for bpp::Graph:

Classes
struct	ALLGRAPHITER
	define categories of iterators More...

class	EdgeIterator

struct	INCOMINGNEIGHBORITER

class	NodeIterator

struct	OUTGOINGNEIGHBORITER

Public Types
typedef unsigned int	NodeId

typedef unsigned int	EdgeId

Public Member Functions
virtual	~Graph ()

virtual NodeId	getRoot () const =0

virtual void	makeDirected ()=0

virtual void	makeUndirected ()=0

Observers Management
Managing communication with the observers: subscribe, unsubscribe.
virtual void	registerObserver (GraphObserver *observer)=0

virtual void	unregisterObserver (GraphObserver *observer)=0

Iterator interface on Nodes
virtual std::unique_ptr< NodeIterator >	allNodesIterator ()=0

virtual std::unique_ptr< NodeIterator >	allNodesIterator () const =0

virtual std::unique_ptr< NodeIterator >	outgoingNeighborNodesIterator (NodeId node)=0

virtual std::unique_ptr< NodeIterator >	incomingNeighborNodesIterator (NodeId node)=0

virtual size_t	getNumberOfNodes () const =0

virtual size_t	getNumberOfEdges () const =0

virtual size_t	getDegree (NodeId node) const =0

virtual bool	isLeaf (NodeId node) const =0

virtual size_t	getNumberOfNeighbors (NodeId node) const =0

virtual size_t	getNumberOfOutgoingNeighbors (NodeId node) const =0

virtual size_t	getNumberOfIncomingNeighbors (const NodeId node) const =0

virtual std::vector< NodeId >	getNeighbors (const NodeId node) const =0

virtual std::vector< NodeId >	getOutgoingNeighbors (const NodeId node) const =0

virtual std::vector< NodeId >	getIncomingNeighbors (NodeId node) const =0

virtual std::vector< NodeId >	getLeavesFromNode (NodeId node, unsigned int maxDepth) const =0

virtual std::vector< NodeId >	getAllLeaves () const =0

virtual std::set< NodeId >	getSetOfAllLeaves () const =0

virtual std::vector< NodeId >	getAllInnerNodes () const =0

virtual std::vector< NodeId >	getAllNodes () const =0

virtual std::pair< NodeId, NodeId >	getNodes (EdgeId edge) const =0

virtual NodeId	getTop (EdgeId edge) const =0

virtual NodeId	getBottom (EdgeId edge) const =0

virtual std::unique_ptr< EdgeIterator >	allEdgesIterator ()=0

virtual std::unique_ptr< EdgeIterator >	outgoingEdgesIterator (NodeId node)=0

virtual std::unique_ptr< EdgeIterator >	incomingEdgesIterator (NodeId node)=0

virtual std::vector< EdgeId >	getEdges (const NodeId node) const =0

virtual std::vector< EdgeId >	getOutgoingEdges (const NodeId node) const =0

virtual std::vector< EdgeId >	getIncomingEdges (NodeId node) const =0

virtual std::vector< EdgeId >	getAllEdges () const =0

virtual EdgeId	getEdge (NodeId nodeA, NodeId nodeB) const =0

virtual EdgeId	getAnyEdge (NodeId nodeA, NodeId nodeB) const =0

Topological Properties
These methodes check some topological properties.
virtual bool	isTree () const =0

virtual bool	isDA () const =0

virtual void	orientate ()=0

virtual bool	isDirected () const =0

virtual bool	containsReciprocalRelations () const =0

Protected Member Functions
virtual void	setRoot (NodeId newRoot)=0

Relations management
Modificating the structure of the graph.
virtual NodeId	createNode ()=0

virtual NodeId	createNodeFromNode (NodeId origin)=0

virtual NodeId	createNodeOnEdge (NodeId edge)=0

virtual NodeId	createNodeFromEdge (NodeId origin)=0

virtual void	deleteNode (NodeId node)=0

virtual EdgeId	link (NodeId nodeA, NodeId nodeB)=0

virtual void	link (Graph::NodeId nodeA, Graph::NodeId nodeB, Graph::EdgeId edgeID)=0

virtual std::vector< EdgeId >	unlink (NodeId nodeA, NodeId nodeB)=0

Updating the changes on the observers
These methodes aim to trigger some changes to the observers
template<class N , class E , class GraphImpl >
class	AssociationGraphImplObserver

virtual void	outputToDot (std::ostream &out, const std::string &name) const =0

virtual void	notifyDeletedEdges (const std::vector< EdgeId > &edgesToDelete) const =0

virtual void	notifyDeletedNodes (const std::vector< NodeId > &nodesToDelete) const =0

Detailed Description

Definition at line 27 of file Graph.h.

Member Typedef Documentation

◆ EdgeId

typedef unsigned int bpp::Graph::EdgeId

Definition at line 31 of file Graph.h.

◆ NodeId

typedef unsigned int bpp::Graph::NodeId

Definition at line 30 of file Graph.h.

Constructor & Destructor Documentation

◆ ~Graph()

virtual bpp::Graph::~Graph ( )

inlinevirtual

Definition at line 34 of file Graph.h.

References createNode(), createNodeFromEdge(), createNodeFromNode(), createNodeOnEdge(), deleteNode(), getRoot(), link(), makeDirected(), makeUndirected(), registerObserver(), setRoot(), unlink(), and unregisterObserver().

Member Function Documentation

◆ allEdgesIterator()

virtual std::unique_ptr<EdgeIterator> bpp::Graph::allEdgesIterator ( )

pure virtual

Implemented in bpp::GlobalGraph.

Referenced by bpp::Graph::EdgeIterator::~EdgeIterator().

◆ allNodesIterator() [1/2]

virtual std::unique_ptr<NodeIterator> bpp::Graph::allNodesIterator ( )

pure virtual

Implemented in bpp::GlobalGraph.

Referenced by bpp::DAGraphImpl< GraphImpl >::isRooted().

◆ allNodesIterator() [2/2]

virtual std::unique_ptr<NodeIterator> bpp::Graph::allNodesIterator ( ) const

pure virtual

Implemented in bpp::GlobalGraph.

◆ containsReciprocalRelations()

virtual bool bpp::Graph::containsReciprocalRelations ( ) const

pure virtual

Does the graph contain reciprocal relations such as A->B and B->A?

Returns: true if one of them is seen in the structure

Implemented in bpp::GlobalGraph.

◆ createNode()

virtual NodeId bpp::Graph::createNode ( )

pure virtual

Creates an orphaned node.

Returns: the index of the new node

Implemented in bpp::GlobalGraph.

Referenced by ~Graph().

◆ createNodeFromEdge()

virtual NodeId bpp::Graph::createNodeFromEdge ( NodeId origin )

pure virtual

Creates a node linked to new node.

Parameters

origin existing edge. In a directed graph: origin -> newNode.

Returns: the index of the new node

Implemented in bpp::GlobalGraph.

Referenced by ~Graph().

◆ createNodeFromNode()

virtual NodeId bpp::Graph::createNodeFromNode ( NodeId origin )

pure virtual

Creates a node linked to an existing node.

Parameters

origin existing node. In a directed graph: origin -> newNode.

Returns: the index of the new node

Implemented in bpp::GlobalGraph.

Referenced by ~Graph().

◆ createNodeOnEdge()

virtual NodeId bpp::Graph::createNodeOnEdge ( NodeId edge )

pure virtual

Creates new node on an existing Edge, splitting an edge0. A -> B will be A -> N -> B

Parameters

edge	existing edge.

Returns: the index of the new node

Implemented in bpp::GlobalGraph.

Referenced by ~Graph().

◆ deleteNode()

virtual void bpp::Graph::deleteNode ( NodeId node )

pure virtual

Delete one node

Parameters

node	node to be deleted

Implemented in bpp::GlobalGraph.

Referenced by bpp::TreeGraphImpl< GraphImpl >::setOutGroup(), and ~Graph().

◆ getAllEdges()

virtual std::vector<EdgeId> bpp::Graph::getAllEdges ( ) const

pure virtual

Get all edges of a graph.

Returns: a vector containing the edges

Implemented in bpp::GlobalGraph.

Referenced by bpp::Graph::EdgeIterator::~EdgeIterator().

◆ getAllInnerNodes()

virtual std::vector<NodeId> bpp::Graph::getAllInnerNodes ( ) const

pure virtual

Get all the inner nodes, ie, nodes with degree > 1.

Returns: a vector containing the nodes

Implemented in bpp::GlobalGraph.

◆ getAllLeaves()

virtual std::vector<NodeId> bpp::Graph::getAllLeaves ( ) const

pure virtual

Get all leaves of a graph, ie, nodes with no son (or only one neighbor is not directet).

Returns: a vector containing the leaves

Implemented in bpp::GlobalGraph.

◆ getAllNodes()

virtual std::vector<NodeId> bpp::Graph::getAllNodes ( ) const

pure virtual

Get all the nodes.

Returns: a vector containing the nodes

Implemented in bpp::GlobalGraph.

◆ getAnyEdge()

virtual EdgeId bpp::Graph::getAnyEdge	(	NodeId	nodeA,
		NodeId	nodeB
	)		const

pure virtual

Returns the Edge between two nodes, trying both directions

Parameters

nodeA	any node implied in the relation
nodeB	any other node implied in the relation

Returns: the edge between these two nodes

Implemented in bpp::GlobalGraph.

Referenced by bpp::Graph::EdgeIterator::~EdgeIterator().

◆ getBottom()

virtual NodeId bpp::Graph::getBottom ( EdgeId edge ) const

pure virtual

Get node located at the bottom of an edge

Returns: the Node at the bottom the edge example : N1–E1–>N2; getBottom(E1) will return N2;

Implemented in bpp::GlobalGraph.

◆ getDegree()

virtual size_t bpp::Graph::getDegree ( NodeId node ) const

pure virtual

Get the degree of a node (ie the number of neighbors) in the graph.

Parameters

node	the node one wants to count its neighbors

Returns: the number of neighbors

Implemented in bpp::GlobalGraph.

◆ getEdge()

virtual EdgeId bpp::Graph::getEdge	(	NodeId	nodeA,
		NodeId	nodeB
	)		const

pure virtual

Returns the Edge between two nodes

Parameters

nodeA	if directed, origin node
nodeB	if directed, destination node

Returns: the edge between these two nodes

Implemented in bpp::GlobalGraph.

Referenced by bpp::TreeGraphImpl< GraphImpl >::setOutGroup(), and bpp::Graph::EdgeIterator::~EdgeIterator().

◆ getEdges()

virtual std::vector<EdgeId> bpp::Graph::getEdges ( const NodeId node ) const

pure virtual

Get all the edges to/from a node in the graph.

Parameters

node	the node one wants to get its edges

Returns: a vector containing the ID of the edges

Implemented in bpp::GlobalGraph.

Referenced by bpp::Graph::EdgeIterator::~EdgeIterator().

◆ getIncomingEdges()

virtual std::vector<EdgeId> bpp::Graph::getIncomingEdges ( NodeId node ) const

pure virtual

In an directed graph, get all the edges which are coming to a node in the graph.

Parameters

node	the node one wants to get its edges

Returns: a vector containing the incoming edges

Implemented in bpp::GlobalGraph.

Referenced by bpp::Graph::EdgeIterator::~EdgeIterator().

◆ getIncomingNeighbors()

virtual std::vector<NodeId> bpp::Graph::getIncomingNeighbors ( NodeId node ) const

pure virtual

In an directed graph, get all the neighbors which are coming to a node in the graph.

Parameters

node	the node one wants to get its neighbors

Returns: a vector containing the incoming neighbors

Implemented in bpp::GlobalGraph.

Referenced by bpp::TreeGraphImpl< GraphImpl >::getFatherOfNode(), and bpp::DAGraphImpl< GraphImpl >::getFathers().

◆ getLeavesFromNode()

virtual std::vector<NodeId> bpp::Graph::getLeavesFromNode	(	NodeId	node,
		unsigned int	maxDepth
	)		const

pure virtual

Get the leaves of a graph, ie, nodes with only one neighbor, starting from a peculiar node.

Parameters

node	the starting node
maxDepth	the maximum number of allowed depth.

Returns: a vector containing the leaves

Implemented in bpp::GlobalGraph.

◆ getNeighbors()

virtual std::vector<NodeId> bpp::Graph::getNeighbors ( const NodeId node ) const

pure virtual

Get all the neighbors of a node in the graph.

Parameters

node	the node one wants to get its neighbors

Returns: a vector containing the ID of the neighbors

Implemented in bpp::GlobalGraph.

◆ getNodes()

virtual std::pair<NodeId, NodeId> bpp::Graph::getNodes ( EdgeId edge ) const

pure virtual

Get nodes located at the extremities of an edge

Returns: a pair of the Nodes at each extremity of the edge example : N1–E1–>N2; getNodes(E1) will return (N1,N2);

Implemented in bpp::GlobalGraph.

◆ getNumberOfEdges()

virtual size_t bpp::Graph::getNumberOfEdges ( ) const

pure virtual

Get the number of edges in the graph.

Implemented in bpp::GlobalGraph.

◆ getNumberOfIncomingNeighbors()

virtual size_t bpp::Graph::getNumberOfIncomingNeighbors ( const NodeId node ) const

pure virtual

Get the number of incoming neighbors of a node (ie the number of fathers) in the graph.

Parameters

node	the node one wants to count its fathers

Returns: the number of incoming neighbors

Implemented in bpp::GlobalGraph.

Referenced by bpp::DAGraphImpl< GraphImpl >::removeFather().

◆ getNumberOfNeighbors()

virtual size_t bpp::Graph::getNumberOfNeighbors ( NodeId node ) const

pure virtual

Get the number of neighbors of a node in the graph.

Parameters

node	the node one wants to count its sons

Returns: the number of neighbors

Implemented in bpp::GlobalGraph.

◆ getNumberOfNodes()

virtual size_t bpp::Graph::getNumberOfNodes ( ) const

pure virtual

Get the number of nodes in the graph.

Implemented in bpp::GlobalGraph.

◆ getNumberOfOutgoingNeighbors()

virtual size_t bpp::Graph::getNumberOfOutgoingNeighbors ( NodeId node ) const

pure virtual

Get the number of outgoing neighbors of a node (ie the number of sons) in the graph.

Parameters

node	the node one wants to count its sons

Returns: the number of outgoing neighbors

Implemented in bpp::GlobalGraph.

◆ getOutgoingEdges()

virtual std::vector<EdgeId> bpp::Graph::getOutgoingEdges ( const NodeId node ) const

pure virtual

In an directed graph, get all the edges which are leaving a node in the graph.

Parameters

node	the node one wants to get its edges

Returns: a vector containing the ID of the outgoing edges

Implemented in bpp::GlobalGraph.

Referenced by bpp::Graph::EdgeIterator::~EdgeIterator().

◆ getOutgoingNeighbors()

virtual std::vector<NodeId> bpp::Graph::getOutgoingNeighbors ( const NodeId node ) const

pure virtual

In an directed graph, get all the neighbors which are leaving a node in the graph.

Parameters

node	the node one wants to get its neighbors

Returns: a vector containing the ID of the outgoing neighbors

Implemented in bpp::GlobalGraph.

◆ getRoot()

virtual NodeId bpp::Graph::getRoot ( ) const

pure virtual

get the root node

Implemented in bpp::GlobalGraph.

Referenced by bpp::TreeGraphImpl< GraphImpl >::MRCA(), and ~Graph().

◆ getSetOfAllLeaves()

virtual std::set<NodeId> bpp::Graph::getSetOfAllLeaves ( ) const

pure virtual

Implemented in bpp::GlobalGraph.

◆ getTop()

virtual NodeId bpp::Graph::getTop ( EdgeId edge ) const

pure virtual

Get node located at the top of an edge

Returns: the Node at the top the edge example : N1–E1–>N2; getTop(E1) will return N1;

Implemented in bpp::GlobalGraph.

◆ incomingEdgesIterator()

virtual std::unique_ptr<EdgeIterator> bpp::Graph::incomingEdgesIterator ( NodeId node )

pure virtual

Implemented in bpp::GlobalGraph.

Referenced by bpp::Graph::EdgeIterator::~EdgeIterator().

◆ incomingNeighborNodesIterator()

virtual std::unique_ptr<NodeIterator> bpp::Graph::incomingNeighborNodesIterator ( NodeId node )

pure virtual

Implemented in bpp::GlobalGraph.

◆ isDA()

virtual bool bpp::Graph::isDA ( ) const

pure virtual

Is the graph directed acyclic?

Returns: true if an edge is met more than one time browsing the graph

Implemented in bpp::GlobalGraph.

◆ isDirected()

virtual bool bpp::Graph::isDirected ( ) const

pure virtual

Is the graph directed?

Returns: true the type of the graph is directed

Implemented in bpp::GlobalGraph.

◆ isLeaf()

virtual bool bpp::Graph::isLeaf ( NodeId node ) const

pure virtual

Says if a node is a leaf (ie has at most one neighbor).

Implemented in bpp::GlobalGraph, bpp::TreeGraphImpl< GraphImpl >, bpp::DAGraphImpl< GraphImpl >, and bpp::TreeGraph.

◆ isTree()

virtual bool bpp::Graph::isTree ( ) const

pure virtual

Is the graph a tree?

Returns: false if a node is met more than one time browsing the graph

Implemented in bpp::GlobalGraph.

◆ link() [1/2]

virtual EdgeId bpp::Graph::link	(	NodeId	nodeA,
		NodeId	nodeB
	)

protectedpure virtual

Creates a link between two existing nodes. If directed graph: nodeA -> nodeB.

Parameters

nodeA	source node (or first node if undirected)
nodeB	target node (or second node if undirected)

Returns: the index of the new edge

Implemented in bpp::GlobalGraph.

Referenced by ~Graph().

◆ link() [2/2]

virtual void bpp::Graph::link	(	Graph::NodeId	nodeA,
		Graph::NodeId	nodeB,
		Graph::EdgeId	edgeID
	)

protectedpure virtual

Sets a link between two existing nodes, using existing edge. If directed graph: nodeA -> nodeB.

Parameters

nodeA	source node (or first node if undirected)
nodeB	target node (or second node if undirected)
edgeID	the used edge

Implemented in bpp::GlobalGraph.

◆ makeDirected()

virtual void bpp::Graph::makeDirected ( )

pure virtual

Make the graph directed

changes the property
de-duplicate the relations: eg: A - B in undirected is represented as A->B and B->A in directed, becomes A->B only

Please note that the resulting directions are totaly arbritrary. One might consider to use the makeLocalRoot method.

Implemented in bpp::GlobalGraph.

Referenced by ~Graph().

◆ makeUndirected()

virtual void bpp::Graph::makeUndirected ( )

pure virtual

Make the graph directed

changes the property
de-duplicate the relations: eg: A - B in directed is represented as A->B in undirected, becomes A->B and B->A If the directed graph already contains reciprocal relations, such as A->B and B->A, the method will throw an exception.

Implemented in bpp::GlobalGraph.

Referenced by ~Graph().

◆ notifyDeletedEdges()

virtual void bpp::Graph::notifyDeletedEdges ( const std::vector< EdgeId > & edgesToDelete ) const

protectedpure virtual

Trigger E objects deleting on the observers

Parameters

edgesToDelete list of edges to delete

Implemented in bpp::GlobalGraph.

Referenced by bpp::Graph::EdgeIterator::~EdgeIterator().

◆ notifyDeletedNodes()

virtual void bpp::Graph::notifyDeletedNodes ( const std::vector< NodeId > & nodesToDelete ) const

protectedpure virtual

Trigger N objects deleting on the observers

Parameters

nodesToDelete list of edges to delete

Implemented in bpp::GlobalGraph.

Referenced by bpp::Graph::EdgeIterator::~EdgeIterator().

◆ orientate()

virtual void bpp::Graph::orientate ( )

pure virtual

Orientates the graph hanging from the root

Implemented in bpp::GlobalGraph.

◆ outgoingEdgesIterator()

virtual std::unique_ptr<EdgeIterator> bpp::Graph::outgoingEdgesIterator ( NodeId node )

pure virtual

Implemented in bpp::GlobalGraph.

Referenced by bpp::Graph::EdgeIterator::~EdgeIterator().

◆ outgoingNeighborNodesIterator()

virtual std::unique_ptr<NodeIterator> bpp::Graph::outgoingNeighborNodesIterator ( NodeId node )

pure virtual

Implemented in bpp::GlobalGraph.

◆ outputToDot()

virtual void bpp::Graph::outputToDot	(	std::ostream &	out,
		const std::string &	name
	)		const

pure virtual

Output the graph in DOT format

Parameters

out	a ostream where the DOT format will be output
name	a string naming the graph

Implemented in bpp::GlobalGraph.

Referenced by bpp::Graph::EdgeIterator::~EdgeIterator().

◆ registerObserver()

virtual void bpp::Graph::registerObserver ( GraphObserver * observer )

pure virtual

Attach a new observer to this Graph. As a subscriber, the observer will be warned of all the changes.

Implemented in bpp::GlobalGraph.

Referenced by ~Graph().

◆ setRoot()

virtual void bpp::Graph::setRoot ( NodeId newRoot )

protectedpure virtual

set the root node to an existing node. Will not affect the topology.

Parameters

newRoot the new root

Implemented in bpp::GlobalGraph.

Referenced by ~Graph().

◆ unlink()

virtual std::vector<EdgeId> bpp::Graph::unlink	(	NodeId	nodeA,
		NodeId	nodeB
	)

protectedpure virtual

Remove all links between two existing nodes. If directed graph: nodeA -> nodeB.

Parameters

nodeA	source node (or first node if undirected)
nodeB	target node (or second node if undirected)

Returns: vector of IDs to de-assigned edges

Implemented in bpp::GlobalGraph.

Referenced by ~Graph().

◆ unregisterObserver()

virtual void bpp::Graph::unregisterObserver ( GraphObserver * observer )

pure virtual

Detach an observer from this Graph. The observer will not be warned of changes anymore.

Implemented in bpp::GlobalGraph.

Referenced by ~Graph().

Friends And Related Function Documentation

◆ AssociationGraphImplObserver

template<class N , class E , class GraphImpl >

friend class AssociationGraphImplObserver

friend

Definition at line 544 of file Graph.h.

The documentation for this class was generated from the following file:

Bpp/Graph/Graph.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Relations management

Updating the changes on the observers

Detailed Description

Member Typedef Documentation

◆ EdgeId

◆ NodeId

Constructor & Destructor Documentation

◆ ~Graph()

Member Function Documentation

◆ allEdgesIterator()

◆ allNodesIterator() [1/2]

◆ allNodesIterator() [2/2]

◆ containsReciprocalRelations()

◆ createNode()

◆ createNodeFromEdge()

◆ createNodeFromNode()

◆ createNodeOnEdge()

◆ deleteNode()

◆ getAllEdges()

◆ getAllInnerNodes()

◆ getAllLeaves()

◆ getAllNodes()

◆ getAnyEdge()

◆ getBottom()

◆ getDegree()

◆ getEdge()

◆ getEdges()

◆ getIncomingEdges()

◆ getIncomingNeighbors()

◆ getLeavesFromNode()

◆ getNeighbors()

◆ getNodes()

◆ getNumberOfEdges()

◆ getNumberOfIncomingNeighbors()

◆ getNumberOfNeighbors()

◆ getNumberOfNodes()

◆ getNumberOfOutgoingNeighbors()

◆ getOutgoingEdges()

◆ getOutgoingNeighbors()

◆ getRoot()

◆ getSetOfAllLeaves()

◆ getTop()

◆ incomingEdgesIterator()

◆ incomingNeighborNodesIterator()

◆ isDA()

◆ isDirected()

◆ isLeaf()

◆ isTree()

◆ link() [1/2]

◆ link() [2/2]

◆ makeDirected()

◆ makeUndirected()

◆ notifyDeletedEdges()

◆ notifyDeletedNodes()

◆ orientate()

◆ outgoingEdgesIterator()

◆ outgoingNeighborNodesIterator()

◆ outputToDot()

◆ registerObserver()

◆ setRoot()

◆ unlink()

◆ unregisterObserver()

Friends And Related Function Documentation

◆ AssociationGraphImplObserver