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

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)

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

Detailed Description

Definition at line 18 of file GlobalGraph.h.

Member Typedef Documentation

◆ Edge

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

Definition at line 24 of file GlobalGraph.h.

◆ EdgeId

typedef unsigned int bpp::Graph::EdgeId

inherited

Definition at line 31 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 45 of file GlobalGraph.h.

◆ Node

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

Definition at line 23 of file GlobalGraph.h.

◆ NodeId

typedef unsigned int bpp::Graph::NodeId

inherited

Definition at line 30 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 38 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 19 of file GlobalGraph.cpp.

Referenced by clone(), and topologyHasChanged_().

◆ GlobalGraph() [2/2]

GlobalGraph::GlobalGraph ( const GlobalGraph & gg )

Definition at line 30 of file GlobalGraph.cpp.

◆ ~GlobalGraph()

bpp::GlobalGraph::~GlobalGraph ( )

inline

Definition at line 222 of file GlobalGraph.h.

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

Member Function Documentation

◆ allEdgesIterator() [1/2]

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

virtual

Implements bpp::Graph.

Definition at line 859 of file GlobalGraph.cpp.

◆ allEdgesIterator() [2/2]

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

Definition at line 874 of file GlobalGraph.cpp.

◆ allNodesIterator() [1/2]

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

virtual

Implements bpp::Graph.

Definition at line 338 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 343 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 220 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 841 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 219 of file GlobalGraph.cpp.

References highestNodeID_, nodeStructure_, and topologyHasChanged_().

Referenced by createNodeFromNode(), createNodeOnEdge(), and ~GlobalGraph().

◆ 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 256 of file GlobalGraph.cpp.

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

Referenced by ~GlobalGraph().

◆ 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 228 of file GlobalGraph.cpp.

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

Referenced by createNodeFromEdge(), and ~GlobalGraph().

◆ 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 236 of file GlobalGraph.cpp.

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

Referenced by createNodeFromEdge(), and ~GlobalGraph().

◆ deleteNode()

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

virtual

Delete one node

Parameters

node	node to be deleted

Implements bpp::Graph.

Definition at line 465 of file GlobalGraph.cpp.

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

Referenced by isDA(), orientate(), and ~GlobalGraph().

◆ 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 60 of file GlobalGraph.cpp.

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

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

◆ 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 567 of file GlobalGraph.cpp.

References getNeighbors().

Referenced by getLeavesFromNode(), and topologyHasChanged_().

◆ 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 495 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 555 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 520 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 544 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 506 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 460 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 384 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 889 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 900 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 302 of file GlobalGraph.cpp.

References nodeStructure_.

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

◆ 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 323 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 318 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 584 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 437 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 287 of file GlobalGraph.cpp.

References nodeStructure_.

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

◆ 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 448 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 378 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 429 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 409 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 372 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 421 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 333 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 328 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 768 of file GlobalGraph.cpp.

References root_.

Referenced by ~GlobalGraph().

◆ getSetOfAllLeaves()

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

virtual

Implements bpp::Graph.

Definition at line 532 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 455 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 869 of file GlobalGraph.cpp.

◆ incomingEdgesIterator() [2/2]

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

Definition at line 884 of file GlobalGraph.cpp.

◆ incomingNeighborNodesIterator() [1/2]

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

virtual

Implements bpp::Graph.

Definition at line 355 of file GlobalGraph.cpp.

◆ incomingNeighborNodesIterator() [2/2]

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

Definition at line 366 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 647 of file GlobalGraph.cpp.

References allNodesIterator(), deleteNode(), bpp::Graph::NodeIterator::end(), getNumberOfNodes(), getNumberOfOutgoingNeighbors(), bpp::Graph::NodeIterator::next(), 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 773 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 394 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 480 of file GlobalGraph.cpp.

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

Referenced by deleteNode(), and topologyHasChanged_().

◆ 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 611 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 67 of file GlobalGraph.cpp.

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

Referenced by createNodeFromNode(), createNodeOnEdge(), and ~GlobalGraph().

◆ 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 82 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 176 of file GlobalGraph.cpp.

References edgeStructure_, and topologyHasChanged_().

Referenced by link(), and topologyHasChanged_().

◆ 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 206 of file GlobalGraph.cpp.

References nodeStructure_, and topologyHasChanged_().

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

◆ 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 778 of file GlobalGraph.cpp.

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

Referenced by orientate(), and ~GlobalGraph().

◆ 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 810 of file GlobalGraph.cpp.

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

Referenced by ~GlobalGraph().

◆ 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 54 of file GlobalGraph.cpp.

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

Referenced by deleteNode(), setRoot(), and topologyHasChanged_().

◆ 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 630 of file GlobalGraph.cpp.

References getOutgoingNeighbors().

Referenced by isTree(), and topologyHasChanged_().

◆ 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 591 of file GlobalGraph.cpp.

References directed_, and nodeStructure_.

Referenced by outputToDot(), and topologyHasChanged_().

◆ notify_()

void bpp::GlobalGraph::notify_ ( )

private

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

Referenced by topologyHasChanged_().

◆ 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 924 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 932 of file GlobalGraph.cpp.

References observers_.

◆ operator=()

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

Definition at line 40 of file GlobalGraph.cpp.

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

Referenced by topologyHasChanged_().

◆ orientate()

void GlobalGraph::orientate ( )

virtual

Orientates the graph hanging from the root

Implements bpp::Graph.

Definition at line 687 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 864 of file GlobalGraph.cpp.

◆ outgoingEdgesIterator() [2/2]

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

Definition at line 879 of file GlobalGraph.cpp.

◆ outgoingNeighborNodesIterator() [1/2]

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

virtual

Implements bpp::Graph.

Definition at line 349 of file GlobalGraph.cpp.

◆ outgoingNeighborNodesIterator() [2/2]

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

Definition at line 360 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 911 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 271 of file GlobalGraph.cpp.

References observers_.

Referenced by ~GlobalGraph().

◆ 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 762 of file GlobalGraph.cpp.

References nodeMustExist_(), and root_.

Referenced by ~GlobalGraph().

◆ 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 113 of file GlobalGraph.cpp.

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

Referenced by orientate(), and ~GlobalGraph().

◆ 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 89 of file GlobalGraph.h.

References edgeMustExist_(), fillListOfLeaves_(), getEdges_(), getNeighbors_(), GlobalGraph(), isolate_(), linkInEdgeStructure_(), linkInNodeStructure_(), nodeMustExist_(), nodesAreMetOnlyOnce_(), nodeToDot_(), notify_(), operator=(), unlinkInEdgeStructure_(), and unlinkInNodeStructure_().

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 96 of file GlobalGraph.cpp.

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

Referenced by createNodeOnEdge(), isolate_(), and ~GlobalGraph().

◆ 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 166 of file GlobalGraph.cpp.

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

Referenced by topologyHasChanged_(), and 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 183 of file GlobalGraph.cpp.

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

Referenced by topologyHasChanged_(), and 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 278 of file GlobalGraph.cpp.

References observers_.

Referenced by ~GlobalGraph().

Friends And Related Function Documentation

◆ AssociationGraphImplObserver

template<class N , class E , class GraphImpl >

friend class AssociationGraphImplObserver

friend

Definition at line 688 of file GlobalGraph.h.

◆ EdgesIteratorClass

template<typename T , bool is_const>

friend class EdgesIteratorClass

friend

Definition at line 378 of file GlobalGraph.h.

◆ NodesIteratorClass

template<typename T , bool is_const>

friend class NodesIteratorClass

friend

Definition at line 375 of file GlobalGraph.h.

Member Data Documentation

◆ directed_

bool bpp::GlobalGraph::directed_

private

is the graph directed

Definition at line 51 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 78 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 65 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 61 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 72 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 56 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 83 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

General Management

Relations management

Nodes Functions

Updating the changes on the observers

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