#include <Bpp/Graph/TreeGraphImpl.h>

Inheritance diagram for bpp::TreeGraphImpl< GraphImpl >:

Collaboration diagram for bpp::TreeGraphImpl< GraphImpl >:

Public Types
typedef unsigned int	NodeId

typedef unsigned int	EdgeId

Public Member Functions
	TreeGraphImpl ()

	TreeGraphImpl (bool rooted=true)

bool	isValid () const

bool	isRooted () const

Graph::NodeId	getFatherOfNode (Graph::NodeId nodeid) const

Graph::EdgeId	getEdgeToFather (Graph::NodeId node) const

bool	hasFather (Graph::NodeId node) const

bool	isLeaf (Graph::NodeId node) const

std::vector< Graph::NodeId >	getLeavesUnderNode (Graph::NodeId node) const

std::vector< Graph::NodeId >	getSons (Graph::NodeId node) const

std::vector< Graph::EdgeId >	getBranches (Graph::NodeId node) const

std::unique_ptr< Graph::NodeIterator >	sonsIterator (Graph::NodeId node)

std::unique_ptr< Graph::NodeIterator >	sonsIterator (Graph::NodeId node) const

std::unique_ptr< Graph::EdgeIterator >	branchesIterator (Graph::NodeId node)

std::unique_ptr< Graph::EdgeIterator >	branchesIterator (Graph::NodeId node) const

size_t	getNumberOfSons (Graph::NodeId node) const
	Get the number of sons node. More...

void	setFather (Graph::NodeId node, Graph::NodeId fatherNode)

void	setFather (Graph::NodeId node, Graph::NodeId fatherNode, Graph::EdgeId edgeId)

void	addSon (Graph::NodeId node, Graph::NodeId sonNode)

void	addSon (Graph::NodeId node, Graph::NodeId sonNode, Graph::EdgeId edgeId)

std::vector< Graph::NodeId >	removeSons (Graph::NodeId node)

void	removeSon (Graph::NodeId node, Graph::NodeId son)

void	rootAt (Graph::NodeId newRoot)

void	unRoot (bool joinRootSons)

void	setOutGroup (Graph::NodeId newOutGroup)

std::vector< Graph::NodeId >	getSubtreeNodes (Graph::NodeId localRoot) const

std::vector< Graph::EdgeId >	getSubtreeEdges (Graph::NodeId localRoot) const

std::vector< Graph::NodeId >	getNodePathBetweenTwoNodes (Graph::NodeId nodeA, Graph::NodeId nodeB, bool includeAncestor=true) const

std::vector< Graph::EdgeId >	getEdgePathBetweenTwoNodes (Graph::NodeId nodeA, Graph::NodeId nodeB) const

Graph::NodeId	MRCA (const std::vector< Graph::NodeId > &nodes) const

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 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

Private Member Functions
void	topologyHasChanged_ () const

void	mustBeValid_ () const

void	mustBeRooted_ () const

bool	validate_ () const

void	propagateDirection_ (Graph::NodeId node)

void	fillSubtreeMetNodes_ (std::vector< Graph::NodeId > &metNodes, Graph::NodeId localRoot) const

void	fillSubtreeMetEdges_ (std::vector< Graph::EdgeId > &metEdges, Graph::NodeId localRoot) const

void	fillListOfLeaves_ (Graph::NodeId startingNode, std::vector< Graph::NodeId > &foundLeaves) const

Private Attributes
bool	isValid_

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
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

template<class GraphImpl>
class bpp::TreeGraphImpl< GraphImpl >

Definition at line 21 of file TreeGraphImpl.h.

Member Typedef Documentation

◆ EdgeId

typedef unsigned int bpp::Graph::EdgeId

inherited

Definition at line 31 of file Graph.h.

◆ NodeId

typedef unsigned int bpp::Graph::NodeId

inherited

Definition at line 30 of file Graph.h.

Constructor & Destructor Documentation

◆ TreeGraphImpl() [1/2]

template<class GraphImpl >

bpp::TreeGraphImpl< GraphImpl >::TreeGraphImpl ( )

◆ TreeGraphImpl() [2/2]

template<class GraphImpl >

bpp::TreeGraphImpl< GraphImpl >::TreeGraphImpl ( bool rooted = true )

Definition at line 229 of file TreeGraphImpl.h.

Member Function Documentation

◆ addSon() [1/2]

template<class GraphImpl >

void bpp::TreeGraphImpl< GraphImpl >::addSon	(	Graph::NodeId	node,
		Graph::NodeId	sonNode
	)

virtual

Add a son to a node in a rooted tree

Implements bpp::TreeGraph.

Definition at line 375 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::topologyHasChanged_().

◆ addSon() [2/2]

template<class GraphImpl >

void bpp::TreeGraphImpl< GraphImpl >::addSon	(	Graph::NodeId	node,
		Graph::NodeId	sonNode,
		Graph::EdgeId	edgeId
	)

virtual

Implements bpp::TreeGraph.

Definition at line 382 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::topologyHasChanged_().

◆ allEdgesIterator()

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

pure virtualinherited

Implemented in bpp::GlobalGraph.

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

◆ allNodesIterator() [1/2]

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

pure virtualinherited

Implemented in bpp::GlobalGraph.

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

◆ allNodesIterator() [2/2]

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

pure virtualinherited

Implemented in bpp::GlobalGraph.

◆ branchesIterator() [1/2]

template<class GraphImpl >

std::unique_ptr< Graph::EdgeIterator > bpp::TreeGraphImpl< GraphImpl >::branchesIterator ( Graph::NodeId node )

virtual

Get a iterator on the branches to sons of a node

Implements bpp::TreeGraph.

Definition at line 430 of file TreeGraphImpl.h.

◆ branchesIterator() [2/2]

template<class GraphImpl >

std::unique_ptr< Graph::EdgeIterator > bpp::TreeGraphImpl< GraphImpl >::branchesIterator ( Graph::NodeId node ) const

virtual

Implements bpp::TreeGraph.

Definition at line 436 of file TreeGraphImpl.h.

◆ containsReciprocalRelations()

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

pure virtualinherited

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 virtualinherited

Creates an orphaned node.

Returns: the index of the new node

Implemented in bpp::GlobalGraph.

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

◆ createNodeFromEdge()

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

pure virtualinherited

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 bpp::Graph::~Graph().

◆ createNodeFromNode()

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

pure virtualinherited

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 bpp::Graph::~Graph().

◆ createNodeOnEdge()

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

pure virtualinherited

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 bpp::Graph::~Graph().

◆ deleteNode()

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

pure virtualinherited

Delete one node

Parameters

node	node to be deleted

Implemented in bpp::GlobalGraph.

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

◆ fillListOfLeaves_()

template<class GraphImpl >

void bpp::TreeGraphImpl< GraphImpl >::fillListOfLeaves_	(	Graph::NodeId	startingNode,
		std::vector< Graph::NodeId > &	foundLeaves
	)		const

private

Definition at line 273 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::getSons().

Referenced by bpp::TreeGraphImpl< GraphImpl >::getLeavesUnderNode().

◆ fillSubtreeMetEdges_()

template<class GraphImpl >

void bpp::TreeGraphImpl< GraphImpl >::fillSubtreeMetEdges_	(	std::vector< Graph::EdgeId > &	metEdges,
		Graph::NodeId	localRoot
	)		const

private

Definition at line 568 of file TreeGraphImpl.h.

Referenced by bpp::TreeGraphImpl< GraphImpl >::getSubtreeEdges().

◆ fillSubtreeMetNodes_()

template<class GraphImpl >

void bpp::TreeGraphImpl< GraphImpl >::fillSubtreeMetNodes_	(	std::vector< Graph::NodeId > &	metNodes,
		Graph::NodeId	localRoot
	)		const

private

Definition at line 557 of file TreeGraphImpl.h.

Referenced by bpp::TreeGraphImpl< GraphImpl >::getSubtreeNodes().

◆ getAllEdges()

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

pure virtualinherited

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 virtualinherited

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 virtualinherited

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 virtualinherited

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 virtualinherited

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 virtualinherited

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.

◆ getBranches()

template<class GraphImpl >

std::vector< Graph::EdgeId > bpp::TreeGraphImpl< GraphImpl >::getBranches ( Graph::NodeId node ) const

virtual

Get the branches to the sons node of a node

Implements bpp::TreeGraph.

Definition at line 412 of file TreeGraphImpl.h.

◆ getDegree()

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

pure virtualinherited

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 virtualinherited

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().

◆ getEdgePathBetweenTwoNodes()

template<class GraphImpl >

std::vector< Graph::EdgeId > bpp::TreeGraphImpl< GraphImpl >::getEdgePathBetweenTwoNodes	(	Graph::NodeId	nodeA,
		Graph::NodeId	nodeB
	)		const

virtual

Implements bpp::TreeGraph.

Definition at line 526 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::getNodePathBetweenTwoNodes().

◆ getEdges()

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

pure virtualinherited

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().

◆ getEdgeToFather()

template<class GraphImpl >

Graph::EdgeId bpp::TreeGraphImpl< GraphImpl >::getEdgeToFather ( Graph::NodeId node ) const

virtual

Get the branch leading to the father in a rooted tree

Returns: the branch between a node and its father

Implements bpp::TreeGraph.

Definition at line 253 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::getFatherOfNode().

◆ getFatherOfNode()

template<class GraphImpl >

Graph::NodeId bpp::TreeGraphImpl< GraphImpl >::getFatherOfNode ( Graph::NodeId nodeid ) const

virtual

Get the father node of a node in a rooted tree

Returns: the father node

Implements bpp::TreeGraph.

Definition at line 242 of file TreeGraphImpl.h.

References bpp::Graph::getIncomingNeighbors(), bpp::VectorTools::paste(), and bpp::TextTools::toString().

Referenced by bpp::TreeGraphImpl< GraphImpl >::getEdgeToFather(), bpp::TreeGraphImpl< GraphImpl >::getNodePathBetweenTwoNodes(), bpp::TreeGraphImpl< GraphImpl >::MRCA(), bpp::TreeGraphImpl< GraphImpl >::propagateDirection_(), bpp::TreeGraphImpl< GraphImpl >::setFather(), and bpp::TreeGraphImpl< GraphImpl >::setOutGroup().

◆ getIncomingEdges()

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

pure virtualinherited

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 virtualinherited

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 virtualinherited

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.

◆ getLeavesUnderNode()

template<class GraphImpl >

std::vector< Graph::NodeId > bpp::TreeGraphImpl< GraphImpl >::getLeavesUnderNode ( Graph::NodeId node ) const

virtual

Get the leaves under a node

Parameters

node	the starting node

Returns: a vector containing the leaves

Implements bpp::TreeGraph.

Definition at line 290 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::fillListOfLeaves_().

◆ getNeighbors()

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

pure virtualinherited

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.

◆ getNodePathBetweenTwoNodes()

template<class GraphImpl >

std::vector< Graph::NodeId > bpp::TreeGraphImpl< GraphImpl >::getNodePathBetweenTwoNodes	(	Graph::NodeId	nodeA,
		Graph::NodeId	nodeB,
		bool	includeAncestor = `true`
	)		const

virtual

Implements bpp::TreeGraph.

Definition at line 476 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::getFatherOfNode(), and bpp::TreeGraphImpl< GraphImpl >::hasFather().

Referenced by bpp::TreeGraphImpl< GraphImpl >::getEdgePathBetweenTwoNodes().

◆ getNodes()

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

pure virtualinherited

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 virtualinherited

Get the number of edges in the graph.

Implemented in bpp::GlobalGraph.

◆ getNumberOfIncomingNeighbors()

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

pure virtualinherited

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 virtualinherited

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 virtualinherited

Get the number of nodes in the graph.

Implemented in bpp::GlobalGraph.

◆ getNumberOfOutgoingNeighbors()

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

pure virtualinherited

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.

◆ getNumberOfSons()

template<class GraphImpl >

size_t bpp::TreeGraphImpl< GraphImpl >::getNumberOfSons ( Graph::NodeId node ) const

virtual

Get the number of sons node.

Implements bpp::TreeGraph.

Definition at line 442 of file TreeGraphImpl.h.

◆ getOutgoingEdges()

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

pure virtualinherited

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 virtualinherited

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 virtualinherited

get the root node

Implemented in bpp::GlobalGraph.

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

◆ getSetOfAllLeaves()

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

pure virtualinherited

Implemented in bpp::GlobalGraph.

◆ getSons()

template<class GraphImpl >

std::vector< Graph::NodeId > bpp::TreeGraphImpl< GraphImpl >::getSons ( Graph::NodeId node ) const

virtual

Get the sons node of a node

Implements bpp::TreeGraph.

Definition at line 406 of file TreeGraphImpl.h.

Referenced by bpp::TreeGraphImpl< GraphImpl >::fillListOfLeaves_(), bpp::TreeGraphImpl< GraphImpl >::removeSons(), and bpp::TreeGraphImpl< GraphImpl >::unRoot().

◆ getSubtreeEdges()

template<class GraphImpl >

std::vector< Graph::EdgeId > bpp::TreeGraphImpl< GraphImpl >::getSubtreeEdges ( Graph::NodeId localRoot ) const

virtual

Get all the branches of a subtree

Implements bpp::TreeGraph.

Definition at line 547 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::fillSubtreeMetEdges_(), and bpp::TreeGraphImpl< GraphImpl >::mustBeValid_().

◆ getSubtreeNodes()

template<class GraphImpl >

std::vector< Graph::NodeId > bpp::TreeGraphImpl< GraphImpl >::getSubtreeNodes ( Graph::NodeId localRoot ) const

virtual

Get all the nodes of a subtree

Implements bpp::TreeGraph.

Definition at line 538 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::fillSubtreeMetNodes_(), and bpp::TreeGraphImpl< GraphImpl >::mustBeValid_().

◆ getTop()

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

pure virtualinherited

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.

◆ hasFather()

template<class GraphImpl >

bool bpp::TreeGraphImpl< GraphImpl >::hasFather ( Graph::NodeId node ) const

virtual

Check if node has a father

Implements bpp::TreeGraph.

Definition at line 260 of file TreeGraphImpl.h.

Referenced by bpp::TreeGraphImpl< GraphImpl >::getNodePathBetweenTwoNodes(), bpp::TreeGraphImpl< GraphImpl >::MRCA(), bpp::TreeGraphImpl< GraphImpl >::propagateDirection_(), and bpp::TreeGraphImpl< GraphImpl >::setFather().

◆ incomingEdgesIterator()

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

pure virtualinherited

Implemented in bpp::GlobalGraph.

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

◆ incomingNeighborNodesIterator()

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

pure virtualinherited

Implemented in bpp::GlobalGraph.

◆ isDA()

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

pure virtualinherited

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 virtualinherited

Is the graph directed?

Returns: true the type of the graph is directed

Implemented in bpp::GlobalGraph.

◆ isLeaf()

template<class GraphImpl >

bool bpp::TreeGraphImpl< GraphImpl >::isLeaf ( Graph::NodeId node ) const

virtual

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

Implements bpp::TreeGraph.

Definition at line 266 of file TreeGraphImpl.h.

◆ isRooted()

template<class GraphImpl >

bool bpp::TreeGraphImpl< GraphImpl >::isRooted ( ) const

Is the tree rooted?

Returns: true if rooted, ie is directed.

Definition at line 313 of file TreeGraphImpl.h.

Referenced by bpp::TreeGraphImpl< GraphImpl >::mustBeRooted_().

◆ isTree()

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

pure virtualinherited

Is the graph a tree?

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

Implemented in bpp::GlobalGraph.

◆ isValid()

template<class GraphImpl >

bool bpp::TreeGraphImpl< GraphImpl >::isValid ( ) const

virtual

Is the graph a tree? A tree must be acyclic and with no isolated node.

Returns: true if valid tree

Implements bpp::TreeGraph.

Definition at line 236 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::isValid_, and bpp::TreeGraphImpl< GraphImpl >::validate_().

Referenced by bpp::TreeGraphImpl< GraphImpl >::mustBeValid_(), and bpp::TreeGraphImpl< GraphImpl >::rootAt().

◆ link() [1/2]

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

protectedpure virtualinherited

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 bpp::Graph::~Graph().

◆ link() [2/2]

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

protectedpure virtualinherited

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 virtualinherited

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 bpp::Graph::~Graph().

◆ makeUndirected()

virtual void bpp::Graph::makeUndirected ( )

pure virtualinherited

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 bpp::Graph::~Graph().

◆ MRCA()

template<class GraphImpl >

Graph::NodeId bpp::TreeGraphImpl< GraphImpl >::MRCA ( const std::vector< Graph::NodeId > & nodes ) const

virtual

Implements bpp::TreeGraph.

Definition at line 579 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::getFatherOfNode(), bpp::Graph::getRoot(), bpp::TreeGraphImpl< GraphImpl >::hasFather(), and bpp::TreeGraphImpl< GraphImpl >::mustBeRooted_().

◆ mustBeRooted_()

template<class GraphImpl >

void bpp::TreeGraphImpl< GraphImpl >::mustBeRooted_ ( ) const

private

Definition at line 299 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::isRooted().

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

◆ mustBeValid_()

template<class GraphImpl >

void bpp::TreeGraphImpl< GraphImpl >::mustBeValid_ ( ) const

private

Definition at line 306 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::isValid().

Referenced by bpp::TreeGraphImpl< GraphImpl >::getSubtreeEdges(), and bpp::TreeGraphImpl< GraphImpl >::getSubtreeNodes().

◆ notifyDeletedEdges()

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

protectedpure virtualinherited

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 virtualinherited

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 virtualinherited

Orientates the graph hanging from the root

Implemented in bpp::GlobalGraph.

◆ outgoingEdgesIterator()

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

pure virtualinherited

Implemented in bpp::GlobalGraph.

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

◆ outgoingNeighborNodesIterator()

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

pure virtualinherited

Implemented in bpp::GlobalGraph.

◆ outputToDot()

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

pure virtualinherited

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().

◆ propagateDirection_()

template<class GraphImpl >

void bpp::TreeGraphImpl< GraphImpl >::propagateDirection_ ( Graph::NodeId node )

private

Reorient all the edges starting from a node: the father node becomes a son, and so on.

Definition at line 345 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::getFatherOfNode(), and bpp::TreeGraphImpl< GraphImpl >::hasFather().

Referenced by bpp::TreeGraphImpl< GraphImpl >::rootAt().

◆ registerObserver()

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

pure virtualinherited

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 bpp::Graph::~Graph().

◆ removeSon()

template<class GraphImpl >

void bpp::TreeGraphImpl< GraphImpl >::removeSon	(	Graph::NodeId	node,
		Graph::NodeId	son
	)

virtual

Remove one son

Implements bpp::TreeGraph.

Definition at line 459 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::topologyHasChanged_().

Referenced by bpp::TreeGraphImpl< GraphImpl >::removeSons().

◆ removeSons()

template<class GraphImpl >

std::vector< Graph::NodeId > bpp::TreeGraphImpl< GraphImpl >::removeSons ( Graph::NodeId node )

Remove all the sons

Definition at line 448 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::getSons(), and bpp::TreeGraphImpl< GraphImpl >::removeSon().

◆ rootAt()

template<class GraphImpl >

void bpp::TreeGraphImpl< GraphImpl >::rootAt ( Graph::NodeId newRoot )

virtual

Re-root the tree with the new root

Implements bpp::TreeGraph.

Definition at line 332 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::isValid(), and bpp::TreeGraphImpl< GraphImpl >::propagateDirection_().

Referenced by bpp::TreeGraphImpl< GraphImpl >::setOutGroup().

◆ setFather() [1/2]

template<class GraphImpl >

void bpp::TreeGraphImpl< GraphImpl >::setFather	(	Graph::NodeId	node,
		Graph::NodeId	fatherNode
	)

virtual

set the father node of a node in a rooted tree

Implements bpp::TreeGraph.

Definition at line 356 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::getFatherOfNode(), bpp::TreeGraphImpl< GraphImpl >::hasFather(), and bpp::TreeGraphImpl< GraphImpl >::topologyHasChanged_().

◆ setFather() [2/2]

template<class GraphImpl >

void bpp::TreeGraphImpl< GraphImpl >::setFather	(	Graph::NodeId	node,
		Graph::NodeId	fatherNode,
		Graph::EdgeId	edgeId
	)

virtual

Implements bpp::TreeGraph.

Definition at line 365 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::getFatherOfNode(), bpp::TreeGraphImpl< GraphImpl >::hasFather(), and bpp::TreeGraphImpl< GraphImpl >::topologyHasChanged_().

◆ setOutGroup()

template<class GraphImpl >

void bpp::TreeGraphImpl< GraphImpl >::setOutGroup ( Graph::NodeId newOutGroup )

virtual

Set a node as a new outgroup in a rooted tree, will make a root between the given node and its father.

Implements bpp::TreeGraph.

Definition at line 466 of file TreeGraphImpl.h.

References bpp::Graph::deleteNode(), bpp::Graph::getEdge(), bpp::TreeGraphImpl< GraphImpl >::getFatherOfNode(), bpp::TreeGraphImpl< GraphImpl >::mustBeRooted_(), and bpp::TreeGraphImpl< GraphImpl >::rootAt().

◆ setRoot()

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

protectedpure virtualinherited

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

Parameters

newRoot the new root

Implemented in bpp::GlobalGraph.

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

◆ sonsIterator() [1/2]

template<class GraphImpl >

std::unique_ptr< Graph::NodeIterator > bpp::TreeGraphImpl< GraphImpl >::sonsIterator ( Graph::NodeId node )

virtual

Get a iterator on the sons node of a node

Implements bpp::TreeGraph.

Definition at line 418 of file TreeGraphImpl.h.

◆ sonsIterator() [2/2]

template<class GraphImpl >

std::unique_ptr< Graph::NodeIterator > bpp::TreeGraphImpl< GraphImpl >::sonsIterator ( Graph::NodeId node ) const

virtual

Implements bpp::TreeGraph.

Definition at line 424 of file TreeGraphImpl.h.

◆ topologyHasChanged_()

template<class GraphImpl >

void bpp::TreeGraphImpl< GraphImpl >::topologyHasChanged_ ( ) const

private

Definition at line 326 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::isValid_.

Referenced by bpp::TreeGraphImpl< GraphImpl >::addSon(), bpp::TreeGraphImpl< GraphImpl >::removeSon(), and bpp::TreeGraphImpl< GraphImpl >::setFather().

◆ unlink()

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

protectedpure virtualinherited

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 bpp::Graph::~Graph().

◆ unregisterObserver()

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

pure virtualinherited

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

Implemented in bpp::GlobalGraph.

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

◆ unRoot()

template<class GraphImpl >

void bpp::TreeGraphImpl< GraphImpl >::unRoot ( bool joinRootSons )

virtual

Set the tree to its flat unrooted version. As an algorithmical convenience, a root node is kept, but it has no logical significance.

Implements bpp::TreeGraph.

Definition at line 389 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::getSons().

◆ validate_()

template<class GraphImpl >

bool bpp::TreeGraphImpl< GraphImpl >::validate_ ( ) const

private

Definition at line 319 of file TreeGraphImpl.h.

References bpp::TreeGraphImpl< GraphImpl >::isValid_.

Referenced by bpp::TreeGraphImpl< GraphImpl >::isValid().

Member Data Documentation

◆ isValid_

template<class GraphImpl >

bool bpp::TreeGraphImpl< GraphImpl >::isValid_

mutableprivate

Is the graph a tree? Set to false when structure is modified, true after validation.

Definition at line 29 of file TreeGraphImpl.h.

Referenced by bpp::TreeGraphImpl< GraphImpl >::isValid(), bpp::TreeGraphImpl< GraphImpl >::topologyHasChanged_(), and bpp::TreeGraphImpl< GraphImpl >::validate_().

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

Bpp/Graph/TreeGraphImpl.h

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Relations management

Updating the changes on the observers

Detailed Description

template<class GraphImpl> class bpp::TreeGraphImpl< GraphImpl >

Member Typedef Documentation

◆ EdgeId

◆ NodeId

Constructor & Destructor Documentation

◆ TreeGraphImpl() [1/2]

◆ TreeGraphImpl() [2/2]

Member Function Documentation

◆ addSon() [1/2]

◆ addSon() [2/2]

◆ allEdgesIterator()

◆ allNodesIterator() [1/2]

◆ allNodesIterator() [2/2]

◆ branchesIterator() [1/2]

◆ branchesIterator() [2/2]

◆ containsReciprocalRelations()

◆ createNode()

◆ createNodeFromEdge()

◆ createNodeFromNode()

◆ createNodeOnEdge()

◆ deleteNode()

◆ fillListOfLeaves_()

◆ fillSubtreeMetEdges_()

◆ fillSubtreeMetNodes_()

◆ getAllEdges()

◆ getAllInnerNodes()

◆ getAllLeaves()

◆ getAllNodes()

◆ getAnyEdge()

◆ getBottom()

◆ getBranches()

◆ getDegree()

◆ getEdge()

◆ getEdgePathBetweenTwoNodes()

◆ getEdges()

◆ getEdgeToFather()

◆ getFatherOfNode()

◆ getIncomingEdges()

◆ getIncomingNeighbors()

◆ getLeavesFromNode()

◆ getLeavesUnderNode()

◆ getNeighbors()

◆ getNodePathBetweenTwoNodes()

◆ getNodes()

◆ getNumberOfEdges()

◆ getNumberOfIncomingNeighbors()

◆ getNumberOfNeighbors()

◆ getNumberOfNodes()

◆ getNumberOfOutgoingNeighbors()

◆ getNumberOfSons()

◆ getOutgoingEdges()

◆ getOutgoingNeighbors()

◆ getRoot()

◆ getSetOfAllLeaves()

◆ getSons()

◆ getSubtreeEdges()

◆ getSubtreeNodes()

◆ getTop()

◆ hasFather()

◆ incomingEdgesIterator()

◆ incomingNeighborNodesIterator()

◆ isDA()

◆ isDirected()

◆ isLeaf()

◆ isRooted()

◆ isTree()

◆ isValid()

◆ link() [1/2]

◆ link() [2/2]

◆ makeDirected()

◆ makeUndirected()

◆ MRCA()

template<class GraphImpl>
class bpp::TreeGraphImpl< GraphImpl >