#include <Bpp/Graph/GlobalGraph.h>

Inheritance diagram for bpp::GlobalGraph:

Collaboration diagram for bpp::GlobalGraph:

Public Types
typedef Graph::NodeId	Node

typedef Graph::EdgeId	Edge

typedef std::map< Node, std::pair< std::map< Node, Edge >, std::map< Node, Edge > > >	nodeStructureType

typedef std::map< Edge, std::pair< Node, Node > >	edgeStructureType

typedef unsigned int	NodeId

typedef unsigned int	EdgeId

Public Member Functions
Observers Management
Managing communication with the observers: subscribe, unsubscribe.
void	registerObserver (GraphObserver *observer)

void	unregisterObserver (GraphObserver *observer)

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

bool	isDA () const

void	orientate ()

bool	isDirected () const

bool	containsReciprocalRelations () const

std::unique_ptr< EdgeIterator >	allEdgesIterator ()

std::unique_ptr< EdgeIterator >	allEdgesIterator () const

std::unique_ptr< EdgeIterator >	outgoingEdgesIterator (NodeId node)

std::unique_ptr< EdgeIterator >	outgoingEdgesIterator (NodeId node) const

std::unique_ptr< EdgeIterator >	incomingEdgesIterator (NodeId node)

std::unique_ptr< EdgeIterator >	incomingEdgesIterator (NodeId node) const

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

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

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

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

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

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

Protected Member Functions
void	nodeMustExist_ (const Node &node, std::string name="") const

void	edgeMustExist_ (const Edge &edge, std::string name="") const

Private Member Functions
virtual void	topologyHasChanged_ () const

void	notify_ ()

void	linkInNodeStructure_ (const Node &nodeA, const Node &nodeB, const Edge &edge)

void	linkInEdgeStructure_ (const Node &nodeA, const Node &nodeB, const Edge &edge)

Edge	unlinkInNodeStructure_ (const Node &nodeA, const Node &nodeB)

void	unlinkInEdgeStructure_ (const Edge &edge)

std::vector< Node >	getNeighbors_ (const Node &node, bool outgoing=true) const

std::vector< Edge >	getEdges_ (const Node &node, bool outgoing=true) const

void	isolate_ (Node &node)

void	fillListOfLeaves_ (const Node &startingNode, std::vector< Node > &foundLeaves, const Node &originNode, unsigned int maxRecursions) const

bool	nodesAreMetOnlyOnce_ (const Node &node, std::set< Node > &metNodes, const Node &originNode) const

void	nodeToDot_ (const Node &node, std::ostream &out, std::set< std::pair< Node, Node > > &alreadyFigured) const

Private Attributes
bool	directed_

std::set< GraphObserver * >	observers_

Node	highestNodeID_

Edge	highestEdgeID_

nodeStructureType	nodeStructure_

edgeStructureType	edgeStructure_

Node	root_

Nodes Functions
These methodes of the graph concern the node management.
template<typename T , bool is_const>
class	NodesIteratorClass

template<typename T , bool is_const>
class	EdgesIteratorClass

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

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

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

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

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

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

size_t	getNumberOfNodes () const

size_t	getNumberOfEdges () const

size_t	getDegree (Graph::NodeId node) const

bool	isLeaf (Graph::NodeId node) const

size_t	getNumberOfNeighbors (Graph::NodeId node) const

size_t	getNumberOfOutgoingNeighbors (Graph::NodeId node) const

size_t	getNumberOfIncomingNeighbors (Graph::NodeId node) const

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

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

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

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

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

std::set< NodeId >	getSetOfAllLeaves () const

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

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

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

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

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

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

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

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

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

General Management
Misc & constructors
void	setRoot (Graph::NodeId newRoot)

	GlobalGraph (bool directed=false)

	GlobalGraph (const GlobalGraph &gg)

GlobalGraph &	operator= (const GlobalGraph &gg)

GlobalGraph *	clone () const
	Create a copy of this object and send a pointer to it. More...

	~GlobalGraph ()

Graph::NodeId	getRoot () const

void	makeDirected ()

void	makeUndirected ()

Relations management
Modificating the structure of the graph.
Graph::EdgeId	link (Graph::NodeId nodeA, Graph::NodeId nodeB)

void	link (Graph::NodeId nodeA, Graph::NodeId nodeB, GlobalGraph::Edge edgeID)

void	switchNodes (Graph::NodeId nodeA, Graph::NodeId nodeB)

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

Graph::NodeId	createNode ()

Graph::NodeId	createNodeFromNode (Graph::NodeId origin)

Graph::NodeId	createNodeOnEdge (Graph::EdgeId edge)

Graph::NodeId	createNodeFromEdge (Graph::NodeId origin)

void	deleteNode (Graph::NodeId node)

Detailed Description

Definition at line 55 of file GlobalGraph.h.

Member Typedef Documentation

◆ Edge

typedef Graph::EdgeId bpp::GlobalGraph::Edge

Definition at line 61 of file GlobalGraph.h.

◆ EdgeId

typedef unsigned int bpp::Graph::EdgeId

inherited

Definition at line 67 of file Graph.h.

◆ edgeStructureType

typedef std::map<Edge, std::pair<Node, Node> > bpp::GlobalGraph::edgeStructureType

The edge structure type directed example: N1–E1-->N2 is coded as E1 -> (N1,N2) undirected example: N1–E1–N2 is coded as E1 -> (N1,N2)

Definition at line 82 of file GlobalGraph.h.

◆ Node

typedef Graph::NodeId bpp::GlobalGraph::Node

Definition at line 60 of file GlobalGraph.h.

◆ NodeId

typedef unsigned int bpp::Graph::NodeId

inherited

Definition at line 66 of file Graph.h.

◆ nodeStructureType

typedef std::map<Node, std::pair<std::map<Node, Edge>, std::map<Node, Edge> > > bpp::GlobalGraph::nodeStructureType

The node structure type Node -> ("toNodes" [DestNode,Edge],"fromNodes" [DestNode,Edge]) directed example: (N1)-E1->(N2)-E2->(N3) is coded as N1 -> ((N2:E1),()) N2 -> ((N3:E3),(N1:E1)) N3 -> ((),(N2:E2)) undirected example: (N1)-E1-(N2)-E2->(N3) is coded as N1 -> ((N2:E1),(N2:E1)) N2 -> ((N1:E1, N3:E3),(N1:E1, N3:E3)) N3 -> ((N2:E2),(N2:E2))

Definition at line 75 of file GlobalGraph.h.

Constructor & Destructor Documentation

◆ GlobalGraph() [1/2]

GlobalGraph::GlobalGraph ( bool directed = false )

Constructor

Parameters

directed true if the graph is directed.

Definition at line 54 of file GlobalGraph.cpp.

Referenced by clone().

◆ GlobalGraph() [2/2]

GlobalGraph::GlobalGraph ( const GlobalGraph & gg )

Definition at line 65 of file GlobalGraph.cpp.

◆ ~GlobalGraph()

bpp::GlobalGraph::~GlobalGraph ( )

inline

Definition at line 259 of file GlobalGraph.h.

Member Function Documentation

◆ allEdgesIterator() [1/2]

std::unique_ptr< Graph::EdgeIterator > GlobalGraph::allEdgesIterator ( )

virtual

Implements bpp::Graph.

Definition at line 894 of file GlobalGraph.cpp.

◆ allEdgesIterator() [2/2]

std::unique_ptr< Graph::EdgeIterator > GlobalGraph::allEdgesIterator ( ) const

Definition at line 909 of file GlobalGraph.cpp.

◆ allNodesIterator() [1/2]

std::unique_ptr< Graph::NodeIterator > GlobalGraph::allNodesIterator ( )

virtual

Implements bpp::Graph.

Definition at line 373 of file GlobalGraph.cpp.

Referenced by isDA().

◆ allNodesIterator() [2/2]

std::unique_ptr< Graph::NodeIterator > GlobalGraph::allNodesIterator ( ) const

virtual

Implements bpp::Graph.

Definition at line 378 of file GlobalGraph.cpp.

◆ clone()

GlobalGraph* bpp::GlobalGraph::clone ( ) const

inlinevirtual

Create a copy of this object and send a pointer to it.

Returns: A pointer toward the copy object.

Implements bpp::Clonable.

Definition at line 257 of file GlobalGraph.h.

References GlobalGraph().

◆ containsReciprocalRelations()

bool GlobalGraph::containsReciprocalRelations ( ) const

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

Implements bpp::Graph.

Definition at line 876 of file GlobalGraph.cpp.

References directed_, and nodeStructure_.

Referenced by makeUndirected().

◆ createNode()

Graph::NodeId GlobalGraph::createNode ( )

virtual

Creates an orphaned node.

Returns: the new node

Implements bpp::Graph.

Definition at line 254 of file GlobalGraph.cpp.

References highestNodeID_, nodeStructure_, and topologyHasChanged_().

Referenced by createNodeFromNode(), and createNodeOnEdge().

◆ createNodeFromEdge()

Graph::NodeId GlobalGraph::createNodeFromEdge ( Graph::NodeId origin )

virtual

Creates a node linked to new node, splitting an edge.

Parameters

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

Returns: the new node

Implements bpp::Graph.

Definition at line 291 of file GlobalGraph.cpp.

References createNodeFromNode(), createNodeOnEdge(), edgeMustExist_(), and topologyHasChanged_().

◆ createNodeFromNode()

Graph::NodeId GlobalGraph::createNodeFromNode ( Graph::NodeId origin )

virtual

Creates a node linked to an existing node.

Parameters

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

Returns: the new node

Implements bpp::Graph.

Definition at line 263 of file GlobalGraph.cpp.

References createNode(), link(), and topologyHasChanged_().

Referenced by createNodeFromEdge().

◆ createNodeOnEdge()

Graph::NodeId GlobalGraph::createNodeOnEdge ( Graph::EdgeId edge )

virtual

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

Parameters

edge	existing edge.

Returns: the new node

Implements bpp::Graph.

Definition at line 271 of file GlobalGraph.cpp.

References createNode(), edgeMustExist_(), edgeStructure_, link(), topologyHasChanged_(), and unlink().

Referenced by createNodeFromEdge().

◆ deleteNode()

void GlobalGraph::deleteNode ( Graph::NodeId node )

virtual

Delete one node

Parameters

node	node to be deleted

Implements bpp::Graph.

Definition at line 500 of file GlobalGraph.cpp.

References isolate_(), nodeMustExist_(), nodeStructure_, topologyHasChanged_(), and bpp::TextTools::toString().

Referenced by isDA(), and orientate().

◆ edgeMustExist_()

void GlobalGraph::edgeMustExist_	(	const Edge &	edge,
		std::string	name = `""`
	)		const

protected

Check that a edge exists. If not, throw an exception.

Parameters

edge	edge that has to be checked
name	common name to give to the user in case of failure (eg: "first node")

Definition at line 95 of file GlobalGraph.cpp.

References edgeStructure_, and bpp::TextTools::toString().

Referenced by createNodeFromEdge(), createNodeOnEdge(), and getNodes().

◆ fillListOfLeaves_()

void GlobalGraph::fillListOfLeaves_	(	const Node &	startingNode,
		std::vector< Node > &	foundLeaves,
		const Node &	originNode,
		unsigned int	maxRecursions
	)		const

private

Get leaves from a starting node, filling a vector (private version).

Parameters

startingNode	root node
foundLeaves	a vector containing all the found leaves
originNode	the node where we come from, not to explore
maxRecursions	maximum number of recursion steps

Definition at line 602 of file GlobalGraph.cpp.

References getNeighbors().

Referenced by getLeavesFromNode().

◆ getAllEdges()

vector< Graph::EdgeId > GlobalGraph::getAllEdges ( ) const

virtual

Get all edges of a graph.

Returns: a vector containing the edges

Implements bpp::Graph.

Definition at line 530 of file GlobalGraph.cpp.

References edgeStructure_.

◆ getAllInnerNodes()

vector< Graph::NodeId > GlobalGraph::getAllInnerNodes ( ) const

virtual

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

Returns: a vector containing the inner nodes

Implements bpp::Graph.

Definition at line 590 of file GlobalGraph.cpp.

References getNumberOfOutgoingNeighbors(), and nodeStructure_.

◆ getAllLeaves()

vector< Graph::NodeId > GlobalGraph::getAllLeaves ( ) const

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

Implements bpp::Graph.

Definition at line 555 of file GlobalGraph.cpp.

References isLeaf(), and nodeStructure_.

◆ getAllNodes()

vector< Graph::NodeId > GlobalGraph::getAllNodes ( ) const

virtual

Get all the nodes.

Returns: a vector containing the nodes

Implements bpp::Graph.

Definition at line 579 of file GlobalGraph.cpp.

References nodeStructure_.

◆ getAnyEdge()

Graph::EdgeId GlobalGraph::getAnyEdge	(	Graph::NodeId	nodeA,
		Graph::NodeId	nodeB
	)		const

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

Implements bpp::Graph.

Definition at line 541 of file GlobalGraph.cpp.

References getEdge().

◆ getBottom()

Graph::NodeId GlobalGraph::getBottom ( Graph::EdgeId edge ) const

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;

Implements bpp::Graph.

Definition at line 495 of file GlobalGraph.cpp.

References getNodes().

◆ getDegree()

size_t GlobalGraph::getDegree ( Graph::NodeId node ) const

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

Implements bpp::Graph.

Definition at line 419 of file GlobalGraph.cpp.

References isDirected(), nodeStructure_, and bpp::TextTools::toString().

◆ getEdge()

Graph::EdgeId GlobalGraph::getEdge	(	Graph::NodeId	nodeA,
		Graph::NodeId	nodeB
	)		const

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

Implements bpp::Graph.

Definition at line 924 of file GlobalGraph.cpp.

References nodeStructure_.

Referenced by getAnyEdge().

◆ getEdges()

vector< Graph::EdgeId > GlobalGraph::getEdges ( Graph::NodeId node ) const

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 edges

Implements bpp::Graph.

Definition at line 935 of file GlobalGraph.cpp.

References getEdges_().

◆ getEdges_()

std::vector< GlobalGraph::Edge > GlobalGraph::getEdges_	(	const Node &	node,
		bool	outgoing = `true`
	)		const

private

Private version of getIncomingEdges or getOutgoingEdges. Common code of these function shared here.

Parameters

node	node to in or outgoing edges
outgoing	boolean: if true, outgoing; else incoming

Definition at line 337 of file GlobalGraph.cpp.

References nodeStructure_.

Referenced by getEdges(), getIncomingEdges(), and getOutgoingEdges().

◆ getIncomingEdges()

vector< Graph::EdgeId > GlobalGraph::getIncomingEdges ( Graph::NodeId node ) const

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

Implements bpp::Graph.

Definition at line 358 of file GlobalGraph.cpp.

References getEdges_().

◆ getIncomingNeighbors()

vector< Graph::NodeId > GlobalGraph::getIncomingNeighbors ( Graph::NodeId node ) const

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

Implements bpp::Graph.

Definition at line 353 of file GlobalGraph.cpp.

References getNeighbors_().

Referenced by isolate_(), and orientate().

◆ getLeavesFromNode()

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

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

Implements bpp::Graph.

Definition at line 619 of file GlobalGraph.cpp.

References fillListOfLeaves_().

◆ getNeighbors()

vector< Graph::NodeId > GlobalGraph::getNeighbors ( Graph::NodeId node ) const

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 neighbors

Implements bpp::Graph.

Definition at line 472 of file GlobalGraph.cpp.

References getNeighbors_().

Referenced by fillListOfLeaves_().

◆ getNeighbors_()

std::vector< GlobalGraph::Node > GlobalGraph::getNeighbors_	(	const Node &	node,
		bool	outgoing = `true`
	)		const

private

Private version of getIncomingNeighbors or getOutgoingNeighbors. Common code of these function shared here.

Parameters

node	node to in or outgoing neighbors
outgoing	boolean: if true, outgoing; else incoming

Definition at line 322 of file GlobalGraph.cpp.

References nodeStructure_.

Referenced by getIncomingNeighbors(), getNeighbors(), and getOutgoingNeighbors().

◆ getNodes()

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

virtual

Get nodes located at the extremities of an edge

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

Implements bpp::Graph.

Definition at line 483 of file GlobalGraph.cpp.

References edgeMustExist_(), and edgeStructure_.

Referenced by getBottom(), and getTop().

◆ getNumberOfEdges()

size_t GlobalGraph::getNumberOfEdges ( ) const

virtual

Get the number of edges in the graph.

Implements bpp::Graph.

Definition at line 413 of file GlobalGraph.cpp.

References edgeStructure_.

◆ getNumberOfIncomingNeighbors()

size_t GlobalGraph::getNumberOfIncomingNeighbors ( Graph::NodeId node ) const

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

Implements bpp::Graph.

Definition at line 464 of file GlobalGraph.cpp.

References nodeStructure_.

Referenced by orientate().

◆ getNumberOfNeighbors()

size_t GlobalGraph::getNumberOfNeighbors ( Graph::NodeId node ) const

virtual

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

Parameters

node	the node one wants to count its neighbors

Returns: the number of neighbors

Implements bpp::Graph.

Definition at line 444 of file GlobalGraph.cpp.

References isDirected(), and nodeStructure_.

Referenced by orientate().

◆ getNumberOfNodes()

size_t GlobalGraph::getNumberOfNodes ( ) const

virtual

Get the number of nodes in the graph.

Implements bpp::Graph.

Definition at line 407 of file GlobalGraph.cpp.

References nodeStructure_.

Referenced by isDA(), and orientate().

◆ getNumberOfOutgoingNeighbors()

size_t GlobalGraph::getNumberOfOutgoingNeighbors ( Graph::NodeId node ) const

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

Implements bpp::Graph.

Definition at line 456 of file GlobalGraph.cpp.

References nodeStructure_.

Referenced by getAllInnerNodes(), and isDA().

◆ getOutgoingEdges()

vector< Graph::EdgeId > GlobalGraph::getOutgoingEdges ( Graph::NodeId node ) const

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

Implements bpp::Graph.

Definition at line 368 of file GlobalGraph.cpp.

References getEdges_().

◆ getOutgoingNeighbors()

vector< Graph::NodeId > GlobalGraph::getOutgoingNeighbors ( Graph::NodeId node ) const

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

Implements bpp::Graph.

Definition at line 363 of file GlobalGraph.cpp.

References getNeighbors_().

Referenced by isolate_(), nodesAreMetOnlyOnce_(), and orientate().

◆ getRoot()

Graph::NodeId GlobalGraph::getRoot ( ) const

virtual

get the root node

Implements bpp::Graph.

Definition at line 803 of file GlobalGraph.cpp.

References root_.

◆ getSetOfAllLeaves()

set< Graph::NodeId > GlobalGraph::getSetOfAllLeaves ( ) const

virtual

Implements bpp::Graph.

Definition at line 567 of file GlobalGraph.cpp.

References isLeaf(), and nodeStructure_.

◆ getTop()

Graph::NodeId GlobalGraph::getTop ( Graph::EdgeId edge ) const

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;

Implements bpp::Graph.

Definition at line 490 of file GlobalGraph.cpp.

References getNodes().

◆ incomingEdgesIterator() [1/2]

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

virtual

Implements bpp::Graph.

Definition at line 904 of file GlobalGraph.cpp.

◆ incomingEdgesIterator() [2/2]

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

Definition at line 919 of file GlobalGraph.cpp.

◆ incomingNeighborNodesIterator() [1/2]

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

virtual

Implements bpp::Graph.

Definition at line 390 of file GlobalGraph.cpp.

◆ incomingNeighborNodesIterator() [2/2]

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

Definition at line 401 of file GlobalGraph.cpp.

◆ isDA()

bool GlobalGraph::isDA ( ) const

virtual

Is the graph directed acyclic?

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

Implements bpp::Graph.

Definition at line 682 of file GlobalGraph.cpp.

References allNodesIterator(), deleteNode(), getNumberOfNodes(), getNumberOfOutgoingNeighbors(), and observers_.

◆ isDirected()

bool GlobalGraph::isDirected ( ) const

virtual

Is the graph directed?

Returns: true the type of the graph is directed

Implements bpp::Graph.

Definition at line 808 of file GlobalGraph.cpp.

References directed_.

Referenced by getDegree(), getNumberOfNeighbors(), isLeaf(), and orientate().

◆ isLeaf()

bool GlobalGraph::isLeaf ( Graph::NodeId node ) const

virtual

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

Implements bpp::Graph.

Definition at line 429 of file GlobalGraph.cpp.

References isDirected(), nodeStructure_, and bpp::TextTools::toString().

Referenced by getAllLeaves(), and getSetOfAllLeaves().

◆ isolate_()

void GlobalGraph::isolate_ ( GlobalGraph::Node & node )

private

Separate a node from all its neighbors.

Parameters

node	node to isolate

Definition at line 515 of file GlobalGraph.cpp.

References getIncomingNeighbors(), getOutgoingNeighbors(), and unlink().

Referenced by deleteNode().

◆ isTree()

bool GlobalGraph::isTree ( ) const

virtual

Is the graph a tree?

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

Implements bpp::Graph.

Definition at line 646 of file GlobalGraph.cpp.

References nodesAreMetOnlyOnce_(), nodeStructure_, and root_.

◆ link() [1/2]

GlobalGraph::Edge GlobalGraph::link	(	Graph::NodeId	nodeA,
		Graph::NodeId	nodeB
	)

protectedvirtual

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

Implements bpp::Graph.

Definition at line 102 of file GlobalGraph.cpp.

References directed_, highestEdgeID_, linkInEdgeStructure_(), and linkInNodeStructure_().

Referenced by createNodeFromNode(), and createNodeOnEdge().

◆ link() [2/2]

void GlobalGraph::link	(	Graph::NodeId	nodeA,
		Graph::NodeId	nodeB,
		GlobalGraph::Edge	edgeID
	)

protectedvirtual

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

Implements bpp::Graph.

Definition at line 117 of file GlobalGraph.cpp.

References directed_, edgeStructure_, linkInEdgeStructure_(), linkInNodeStructure_(), and bpp::TextTools::toString().

◆ linkInEdgeStructure_()

void GlobalGraph::linkInEdgeStructure_	(	const Node &	nodeA,
		const Node &	nodeB,
		const Edge &	edge
	)

private

Creates a link between two existing nodes in the edge structure. If directed graph: nodeA -> nodeB. Mainly called by link().

Parameters

nodeA	source node (or first node if undirected)
nodeB	target node (or second node if undirected)
edge	the ID of the relation

Definition at line 211 of file GlobalGraph.cpp.

References edgeStructure_, and topologyHasChanged_().

Referenced by link().

◆ linkInNodeStructure_()

void GlobalGraph::linkInNodeStructure_	(	const Node &	nodeA,
		const Node &	nodeB,
		const Edge &	edge
	)

private

Creates a link between two existing nodes. If directed graph: nodeA -> nodeB. Private version of link, does not check for the reciprocity. Mainly called by link().

Parameters

nodeA	source node
nodeB	target node
edge	the ID of the relation

Definition at line 241 of file GlobalGraph.cpp.

References nodeStructure_, and topologyHasChanged_().

Referenced by link(), makeDirected(), and makeUndirected().

◆ makeDirected()

void GlobalGraph::makeDirected ( )

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.

Implements bpp::Graph.

Definition at line 813 of file GlobalGraph.cpp.

References directed_, linkInNodeStructure_(), nodeStructure_, and topologyHasChanged_().

Referenced by orientate().

◆ makeUndirected()

void GlobalGraph::makeUndirected ( )

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.

Implements bpp::Graph.

Definition at line 845 of file GlobalGraph.cpp.

References containsReciprocalRelations(), directed_, linkInNodeStructure_(), nodeStructure_, and topologyHasChanged_().

◆ nodeMustExist_()

void GlobalGraph::nodeMustExist_	(	const Node &	node,
		std::string	name = `""`
	)		const

protected

Check that a node exists. If not, throw an exception.

Parameters

node	node that has to be checked
name	common name to give to the user in case of failure (eg: "first node")

Definition at line 89 of file GlobalGraph.cpp.

References nodeStructure_, and bpp::TextTools::toString().

Referenced by deleteNode(), and setRoot().

◆ nodesAreMetOnlyOnce_()

bool GlobalGraph::nodesAreMetOnlyOnce_	(	const Node &	node,
		std::set< Node > &	metNodes,
		const Node &	originNode
	)		const

private

Check that nodes are only met once to define if the graph is cyclic.

Parameters

node	the node to explore
metNodes	a set containing all the nodes we met
originNode	the node where we come from, not to explore

Definition at line 665 of file GlobalGraph.cpp.

References getOutgoingNeighbors().

Referenced by isTree().

◆ nodeToDot_()

void GlobalGraph::nodeToDot_	(	const Node &	node,
		std::ostream &	out,
		std::set< std::pair< Node, Node > > &	alreadyFigured
	)		const

private

output a node to DOT format (recursive)

Definition at line 626 of file GlobalGraph.cpp.

References directed_, and nodeStructure_.

Referenced by outputToDot().

◆ notify_()

void bpp::GlobalGraph::notify_ ( )

private

Tell all the observers to get the last updates. Calls the method update of all the subscribers.

◆ notifyDeletedEdges()

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

virtual

Trigger E objects deleting on the observers

Parameters

edgesToDelete list of edges to delete

Implements bpp::Graph.

Definition at line 959 of file GlobalGraph.cpp.

References observers_.

Referenced by unlink().

◆ notifyDeletedNodes()

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

virtual

Trigger N objects deleting on the observers

Parameters

nodesToDelete list of edges to delete

Implements bpp::Graph.

Definition at line 967 of file GlobalGraph.cpp.

References observers_.

◆ operator=()

GlobalGraph & GlobalGraph::operator= ( const GlobalGraph & gg )

Definition at line 75 of file GlobalGraph.cpp.

References directed_, edgeStructure_, highestEdgeID_, highestNodeID_, nodeStructure_, observers_, and root_.

◆ orientate()

void GlobalGraph::orientate ( )

virtual

Orientates the graph hanging from the root

Implements bpp::Graph.

Definition at line 722 of file GlobalGraph.cpp.

References deleteNode(), getIncomingNeighbors(), getNumberOfIncomingNeighbors(), getNumberOfNeighbors(), getNumberOfNodes(), getOutgoingNeighbors(), isDirected(), makeDirected(), observers_, root_, and switchNodes().

◆ outgoingEdgesIterator() [1/2]

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

virtual

Implements bpp::Graph.

Definition at line 899 of file GlobalGraph.cpp.

◆ outgoingEdgesIterator() [2/2]

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

Definition at line 914 of file GlobalGraph.cpp.

◆ outgoingNeighborNodesIterator() [1/2]

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

virtual

Implements bpp::Graph.

Definition at line 384 of file GlobalGraph.cpp.

◆ outgoingNeighborNodesIterator() [2/2]

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

Definition at line 395 of file GlobalGraph.cpp.

◆ outputToDot()

void GlobalGraph::outputToDot	(	std::ostream &	out,
		const std::string &	name
	)		const

virtual

Output the graph in DOT format

Parameters

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

Implements bpp::Graph.

Definition at line 946 of file GlobalGraph.cpp.

References directed_, nodeStructure_, nodeToDot_(), and root_.

◆ registerObserver()

void GlobalGraph::registerObserver ( GraphObserver * observer )

virtual

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

Implements bpp::Graph.

Definition at line 306 of file GlobalGraph.cpp.

References observers_.

◆ setRoot()

void GlobalGraph::setRoot ( Graph::NodeId newRoot )

protectedvirtual

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

Parameters

newRoot the new root

Implements bpp::Graph.

Definition at line 797 of file GlobalGraph.cpp.

References nodeMustExist_(), and root_.

◆ switchNodes()

void GlobalGraph::switchNodes	(	Graph::NodeId	nodeA,
		Graph::NodeId	nodeB
	)

protected

Switch the edge between two existing nodes.

Parameters

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

Definition at line 148 of file GlobalGraph.cpp.

References edgeStructure_, nodeStructure_, topologyHasChanged_(), and bpp::TextTools::toString().

Referenced by orientate().

◆ topologyHasChanged_()

virtual void bpp::GlobalGraph::topologyHasChanged_ ( ) const

inlineprivatevirtual

Some types of Graphs need to know if they have been modified But for a Graph, it does nothing.

Definition at line 126 of file GlobalGraph.h.

Referenced by createNode(), createNodeFromEdge(), createNodeFromNode(), createNodeOnEdge(), deleteNode(), linkInEdgeStructure_(), linkInNodeStructure_(), makeDirected(), makeUndirected(), switchNodes(), unlinkInEdgeStructure_(), and unlinkInNodeStructure_().

◆ unlink()

vector< GlobalGraph::Edge > GlobalGraph::unlink	(	Graph::NodeId	nodeA,
		Graph::NodeId	nodeB
	)

protectedvirtual

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

Implements bpp::Graph.

Definition at line 131 of file GlobalGraph.cpp.

References notifyDeletedEdges(), unlinkInEdgeStructure_(), and unlinkInNodeStructure_().

Referenced by createNodeOnEdge(), and isolate_().

◆ unlinkInEdgeStructure_()

void GlobalGraph::unlinkInEdgeStructure_ ( const Edge & edge )

private

Erase a link between two existing nodes in the Edge structure. Mainly called by unLink().

Parameters

edge	the edge to unregister

Definition at line 201 of file GlobalGraph.cpp.

References edgeStructure_, topologyHasChanged_(), and bpp::TextTools::toString().

Referenced by unlink().

◆ unlinkInNodeStructure_()

unsigned int GlobalGraph::unlinkInNodeStructure_	(	const Node &	nodeA,
		const Node &	nodeB
	)

private

Erase a link between two existing nodes. If directed graph: nodeA -> nodeB. Private version of unLink, does not check for the reciprocity. Mainly called by unLink().

Parameters

nodeA	source node
nodeB	target node

Returns: the ID of the erased relation

Definition at line 218 of file GlobalGraph.cpp.

References nodeStructure_, topologyHasChanged_(), and bpp::TextTools::toString().

Referenced by unlink().

◆ unregisterObserver()

void GlobalGraph::unregisterObserver ( GraphObserver * observer )

virtual

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

Implements bpp::Graph.

Definition at line 313 of file GlobalGraph.cpp.

References observers_.

Friends And Related Function Documentation

◆ AssociationGraphImplObserver

template<class N , class E , class GraphImpl >

friend class AssociationGraphImplObserver

friend

Definition at line 725 of file GlobalGraph.h.

◆ EdgesIteratorClass

template<typename T , bool is_const>

friend class EdgesIteratorClass

friend

Definition at line 415 of file GlobalGraph.h.

◆ NodesIteratorClass

template<typename T , bool is_const>

friend class NodesIteratorClass

friend

Definition at line 412 of file GlobalGraph.h.

Member Data Documentation

◆ directed_

bool bpp::GlobalGraph::directed_

private

is the graph directed

Definition at line 88 of file GlobalGraph.h.

Referenced by containsReciprocalRelations(), isDirected(), link(), makeDirected(), makeUndirected(), nodeToDot_(), operator=(), and outputToDot().

◆ edgeStructure_

edgeStructureType bpp::GlobalGraph::edgeStructure_

private

Edges and their relations in the forward direction.. see edgeStructureType documentation

Definition at line 115 of file GlobalGraph.h.

Referenced by createNodeOnEdge(), edgeMustExist_(), getAllEdges(), getNodes(), getNumberOfEdges(), link(), linkInEdgeStructure_(), operator=(), switchNodes(), and unlinkInEdgeStructure_().

◆ highestEdgeID_

Edge bpp::GlobalGraph::highestEdgeID_

private

Highest used available ID for an Edge.

Definition at line 102 of file GlobalGraph.h.

Referenced by link(), and operator=().

◆ highestNodeID_

Node bpp::GlobalGraph::highestNodeID_

private

Highest used available ID for a Node.

Definition at line 98 of file GlobalGraph.h.

Referenced by createNode(), and operator=().

◆ nodeStructure_

nodeStructureType bpp::GlobalGraph::nodeStructure_

private

Nodes and their relations. see nodeStructureType documentation

Definition at line 109 of file GlobalGraph.h.

Referenced by containsReciprocalRelations(), createNode(), deleteNode(), getAllInnerNodes(), getAllLeaves(), getAllNodes(), getDegree(), getEdge(), getEdges_(), getNeighbors_(), getNumberOfIncomingNeighbors(), getNumberOfNeighbors(), getNumberOfNodes(), getNumberOfOutgoingNeighbors(), getSetOfAllLeaves(), isLeaf(), isTree(), linkInNodeStructure_(), makeDirected(), makeUndirected(), nodeMustExist_(), nodeToDot_(), operator=(), outputToDot(), switchNodes(), and unlinkInNodeStructure_().

◆ observers_

std::set<GraphObserver*> bpp::GlobalGraph::observers_

private

List of all the subscribers.

Definition at line 93 of file GlobalGraph.h.

Referenced by isDA(), notifyDeletedEdges(), notifyDeletedNodes(), operator=(), orientate(), registerObserver(), and unregisterObserver().

◆ root_

Node bpp::GlobalGraph::root_

private

Usualy the first node of a graph. Used for algorithmic purposes.

Definition at line 120 of file GlobalGraph.h.

Referenced by getRoot(), isTree(), operator=(), orientate(), outputToDot(), and setRoot().

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

Bpp/Graph/GlobalGraph.h
Bpp/Graph/GlobalGraph.cpp

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Nodes Functions

Updating the changes on the observers

General Management

Relations management

Detailed Description

Member Typedef Documentation

◆ Edge

◆ EdgeId

◆ edgeStructureType

◆ Node

◆ NodeId

◆ nodeStructureType

Constructor & Destructor Documentation

◆ GlobalGraph() [1/2]

◆ GlobalGraph() [2/2]

◆ ~GlobalGraph()

Member Function Documentation

◆ allEdgesIterator() [1/2]

◆ allEdgesIterator() [2/2]

◆ allNodesIterator() [1/2]

◆ allNodesIterator() [2/2]

◆ clone()

◆ containsReciprocalRelations()

◆ createNode()

◆ createNodeFromEdge()

◆ createNodeFromNode()

◆ createNodeOnEdge()

◆ deleteNode()

◆ edgeMustExist_()

◆ fillListOfLeaves_()

◆ getAllEdges()

◆ getAllInnerNodes()

◆ getAllLeaves()

◆ getAllNodes()

◆ getAnyEdge()

◆ getBottom()

◆ getDegree()

◆ getEdge()

◆ getEdges()

◆ getEdges_()

◆ getIncomingEdges()

◆ getIncomingNeighbors()

◆ getLeavesFromNode()

◆ getNeighbors()

◆ getNeighbors_()

◆ getNodes()

◆ getNumberOfEdges()

◆ getNumberOfIncomingNeighbors()

◆ getNumberOfNeighbors()

◆ getNumberOfNodes()

◆ getNumberOfOutgoingNeighbors()

◆ getOutgoingEdges()

◆ getOutgoingNeighbors()

◆ getRoot()

◆ getSetOfAllLeaves()

◆ getTop()

◆ incomingEdgesIterator() [1/2]

◆ incomingEdgesIterator() [2/2]

◆ incomingNeighborNodesIterator() [1/2]

◆ incomingNeighborNodesIterator() [2/2]

◆ isDA()

◆ isDirected()

◆ isLeaf()

◆ isolate_()

◆ isTree()

◆ link() [1/2]

◆ link() [2/2]

◆ linkInEdgeStructure_()

◆ linkInNodeStructure_()

◆ makeDirected()

◆ makeUndirected()

◆ nodeMustExist_()

◆ nodesAreMetOnlyOnce_()

◆ nodeToDot_()

◆ notify_()