Adaptor for adding nodes/arcs to an underlying graph. More...

Inheritance diagram for Satsuma.Supergraph:

Public Member Functions
Arc	AddArc (Node u, Node v, Directedness directedness)
	Adds a directed arc or an edge (undirected arc) between u and v to the graph. More...

Node	AddNode ()
	Adds a node to the graph. More...

int	ArcCount (ArcFilter filter=ArcFilter.All)
	Returns the total number of arcs satisfying a given filter. More...

int	ArcCount (Node u, ArcFilter filter=ArcFilter.All)
	Returns the number of arcs adjacent to a specific node satisfying a given filter. More...

int	ArcCount (Node u, Node v, ArcFilter filter=ArcFilter.All)
	Returns the number of arcs adjacent to two nodes satisfying a given filter. More...

IEnumerable< Arc >	Arcs (ArcFilter filter=ArcFilter.All)

IEnumerable< Arc >	Arcs (Node u, ArcFilter filter=ArcFilter.All)

IEnumerable< Arc >	Arcs (Node u, Node v, ArcFilter filter=ArcFilter.All)

void	Clear ()
	Deletes all nodes and arcs of the adaptor. More...

bool	DeleteArc (Arc arc)
	Deletes a directed or undirected arc from the graph. More...

bool	DeleteNode (Node node)
	Deletes a node from the graph. More...

bool	HasArc (Arc arc)
	Returns whether the given arc is contained in the graph. More...

bool	HasNode (Node node)
	Returns whether the given node is contained in the graph. More...

bool	IsEdge (Arc arc)
	Returns whether the arc is undirected (`true`) or directed (`false`). More...

int	NodeCount ()
	Returns the total number of nodes in O(1) time. More...

IEnumerable< Node >	Nodes ()
	Returns all nodes of the graph. More...

	Supergraph (IGraph graph)

Node	U (Arc arc)
	Returns the first node of an arc. Directed arcs point from U to V. More...

Node	V (Arc arc)
	Returns the second node of an arc. Directed arcs point from U to V. More...

Detailed Description

Adaptor for adding nodes/arcs to an underlying graph.

Node and Arc objects of the original graph are valid in the adaptor as well, but the converse is not true. The underlying graph must NOT be modified while using this adaptor. The adaptor is an IDestroyableGraph, but only the nodes/arcs added by the adaptor can be deleted.

Memory usage: O(n+m), where n is the number of new nodes and m is the number of new arcs.

The following example demonstrates how nodes and arcs can be added to a(n otherwise immutable) CompleteGraph:

CompleteGraph g = new CompleteGraph(10);
Supergraph sg = new Supergraph(g);
Node u = sg.AddNode(); // create a new node
Arc a = sg.AddArc(u, g.GetNode(3), Directedness.Undirected); // add an edge
Console.WriteLine(string.Format("The augmented graph contains {0} nodes and {1} arcs.",
    sg.NodeCount(), sg.ArcCount())); // should print 11 and 46, respectively

See Also: Subgraph

Definition at line 48 of file Supergraph.cs.

Constructor & Destructor Documentation

Satsuma.Supergraph.Supergraph ( IGraph graph )

Definition at line 93 of file Supergraph.cs.

Member Function Documentation

Arc Satsuma.Supergraph.AddArc	(	Node	u,
		Node	v,
		Directedness	directedness
	)

Adds a directed arc or an edge (undirected arc) between u and v to the graph.

Parameters

u	The source node.
v	The target node.
directedness	Determines whether the new arc will be directed or an edge (i.e. undirected).

Implements Satsuma.IBuildableGraph.

Definition at line 137 of file Supergraph.cs.

Node Satsuma.Supergraph.AddNode ( )

Adds a node to the graph.

Implements Satsuma.IBuildableGraph.

Definition at line 128 of file Supergraph.cs.

int Satsuma.Supergraph.ArcCount ( ArcFilter filter = ArcFilter.All )

Returns the total number of arcs satisfying a given filter.

Parameters

filter Detailed description: see Arcs(ArcFilter).

Implements Satsuma.IGraph.

Definition at line 299 of file Supergraph.cs.

int Satsuma.Supergraph.ArcCount	(	Node	u,
		ArcFilter	filter = `ArcFilter.All`
	)

Returns the number of arcs adjacent to a specific node satisfying a given filter.

Parameters

filter Detailed description: see Arcs(Node, ArcFilter).

Implements Satsuma.IGraph.

Definition at line 304 of file Supergraph.cs.

int Satsuma.Supergraph.ArcCount	(	Node	u,
		Node	v,
		ArcFilter	filter = `ArcFilter.All`
	)

Returns the number of arcs adjacent to two nodes satisfying a given filter.

Parameters

filter Detailed description: see Arcs(Node, Node, ArcFilter).

Implements Satsuma.IGraph.

Definition at line 309 of file Supergraph.cs.

IEnumerable<Arc> Satsuma.Supergraph.Arcs ( ArcFilter filter = ArcFilter.All )

Returns all arcs of the graph satisfying a given filter.

Parameters

filter

Cannot be ArcType.Forward/ArcType.Backward.

If ArcFilter.All, then all arcs are returned.
If ArcFilter.Edge, only the edges (undirected arcs) are returned.

Implements Satsuma.IGraph.

Definition at line 274 of file Supergraph.cs.

IEnumerable<Arc> Satsuma.Supergraph.Arcs	(	Node	u,
		ArcFilter	filter = `ArcFilter.All`
	)

Returns all arcs adjacent to a specific node satisfying a given filter.

Parameters

filter

If ArcFilter.All, then all arcs are returned.
If ArcFilter.Edge, only the edges (undirected arcs) are returned.
If ArcFilter.Forward, only the arcs exiting u (this includes edges) are returned.
If ArcFilter.Backward, only the arcs entering u (this includes edges) are returned.

Implements Satsuma.IGraph.

Definition at line 279 of file Supergraph.cs.

IEnumerable<Arc> Satsuma.Supergraph.Arcs	(	Node	u,
		Node	v,
		ArcFilter	filter = `ArcFilter.All`
	)

Returns all arcs adjacent to two nodes satisfying a given filter.

Parameters

filter

If ArcFilter.All, then all arcs are returned.
If ArcFilter.Edge, only the edges (undirected arcs) are returned.
If ArcFilter.Forward, only the arcs from u to v (this includes edges) are returned.
If ArcFilter.Backward, only the arcs from v to u (this includes edges) are returned.

Implements Satsuma.IGraph.

Definition at line 285 of file Supergraph.cs.

void Satsuma.Supergraph.Clear ( )

Deletes all nodes and arcs of the adaptor.

Implements Satsuma.IClearable.

Definition at line 112 of file Supergraph.cs.

bool Satsuma.Supergraph.DeleteArc ( Arc arc )

Deletes a directed or undirected arc from the graph.

Returns: true if the deletion was successful.

Implements Satsuma.IDestroyableGraph.

Definition at line 198 of file Supergraph.cs.

bool Satsuma.Supergraph.DeleteNode ( Node node )

Deletes a node from the graph.

Returns: true if the deletion was successful.

Implements Satsuma.IDestroyableGraph.

Definition at line 169 of file Supergraph.cs.

bool Satsuma.Supergraph.HasArc ( Arc arc )

Returns whether the given arc is contained in the graph.

Must return the same value as Arcs().Contains in all implementations, but faster if possible.

Note: true may be returned for arcs coming from another graph as well, if those arcs encapsulate an identifier which is valid for this graph, too.

Implements Satsuma.IGraph.

Definition at line 322 of file Supergraph.cs.

bool Satsuma.Supergraph.HasNode ( Node node )

Returns whether the given node is contained in the graph.

Must return the same value as Nodes().Contains in all implementations, but faster if possible.

Note: true may be returned for nodes coming from another graph as well, if those nodes encapsulate an identifier which is valid for this graph, too.

Implements Satsuma.IGraph.

Definition at line 317 of file Supergraph.cs.

bool Satsuma.Supergraph.IsEdge ( Arc arc )

Returns whether the arc is undirected (true) or directed (false).

Implements Satsuma.IArcLookup.

Definition at line 243 of file Supergraph.cs.

int Satsuma.Supergraph.NodeCount ( )

Returns the total number of nodes in O(1) time.

Implements Satsuma.IGraph.

Definition at line 294 of file Supergraph.cs.

IEnumerable<Node> Satsuma.Supergraph.Nodes ( )

Returns all nodes of the graph.