dranges.graph
This module contains a few graph implementations, to use the algorithms presented in dranges.graphalgorithm.
In a graph, nodes are defined by a (unique) label, and a value. A label can be of any type, string being the
most common, and will be used to refer to a particular node. A value can also be of any type and is just the payload stored
in the node.
An edge is a (directed) link from a node to another. It's represented as two labels.
The basic idea is that to construct a graph (and for many algorithms) nodes and edges just have to obey small constraints:
for a node, to have a .label and a .value member, and for an edge, to have a .from and a .to member.
To compile, all the nodes in a graph must have the same type and the edges must be compatible:
the label they point to must have the correct type (compile-time check) and the correct value (runtime check).
Then, for richer structures, nodes and edges can expose other members, typically somthing like .weight, .length,
.capacity, .flow or .color. Algorithm will check for the existence of such members and refuse to compile if they do not exist.
(An idea to pursue could be to provide a simple graph and an associative array of labels, to give the algorithm access to some property,
like a double[Edge] AA giving the lengths of edges.)
As of this writing, I changed Graph back to a struct, and UndirectedGraph also. On the other hand
directed acyclic graphs might be modelized by an assumeAcyclic wrapper, like std.algorithm does for sorted ranges. We'll see.
TODO:
lots of things. Shaping up UndirectedGraph, trying a DAG class, a bidirectional graph (with access not only to the successors/outedges of a node
but also to its predecessors/ingoing edges). Also, iterating on a graph is easy, but modifying it, not so much. I might define some cursor-like structure,
for example created by opIndex[label], that would give ref access to a node, its payload but also to its successors. See also the dranges.recursive
module for similar ideas. I get the impression that I can unite recursive ranges and cursors in one entity.
TODO:
Once this has stabilized some, make Graph a container by providing some of std.container.TotalContainer primitives. Not all make sense for a
graph
.
License:
Boost License 1.0.
Authors:
Philippe Sigaud
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- template
isNode
(N)
- constraint template.
- template
isEdge
(E)
- constraint template.
- template
Label
(N) if (isNode!(N))
- extracts the label type from a node.
- template
Value
(N) if (isNode!(N))
- extracts the value (payload) type from a node.
- template
Label
(E) if (isEdge!(E))
- extracts the label type from an edge.
- struct
Node
(Label,Value = Label);
- basic
Node
struct, the minimal interface a
Node
must provide.
- Node!(Label,Value)
node
(Label, Value)(Label label, Value value);
- creates a Node from a label and a value.
- Node!(Label,Label)
node
(Label)(Label label);
- creates a
node
which has equal label and values. Useful when you just want the structure of a graph
and are not interested in storing content in it.
- struct
Edge
(Label);
- basic edge, provides the minimum members an edge must have.
- Edge!(Label)
edge
(Label)(Label l1, Label l2);
- factory function to create an
edge
and do type deduction on labels.
- struct
WeightedNode
(Value,Label = string,Weight = double);
- First try at having a richer Node.
- struct
LenghtyEdge
(Label,Length);
- An edge with a
length member. A problem remains: how to generically
construct the reversed edge (going from 'to' to 'from') from an unknown type
providing the edge interface? The internal structure may be complicated and initialized in
a non-trivial way.
- struct
Graph
(N,E) if (isNode!(N) && isEdge!(E) && is(Label!(N) == Label!(E)));
- A simple directed graph struct, parameterized on the nodes and edge types. These must be compatible:
the nodes have at least a label (its "name") and a value, and the edges link two labels.
- alias
NodeType
;
- exposed node type.
- alias
EdgeType
;
- exposed edge type.
- alias
LabelType
;
- exposed label type.
- alias
ValueType
;
- exposed payload type.
- template
opBinary
(string op) if (op == "~")
- Concatenation operator, to create a graph with a new node in it.
- Graph!(N,E)
opBinary
(NodeType n);
- Concatenation operator, to create a graph with a new node in it.
- template
opOpAssign
(string op) if (op == "~")
- adding a node to the graph.
- void
opOpAssign
(NodeType n);
- adding a node to the graph.
- template
opBinary
(string op) if (op == "~")
- The same, with an edge.
- Graph!(N,E)
opBinary
(EdgeType e);
- The same, with an edge.
- template
opOpBinary
(string op) if (op == "~")
- ditto.
- void
opOpBinary
(EdgeType e);
- ditto.
- void
addNode
(NodeType n);
- Basic functionality. If n is already a node, does nothing.
If n is indeed new, it adds it to the graph, with no edges.
- void
addEdge
(Label!(N) from, Label!(N) to);
- Basic functionality. If to or from are not in the graph, or
if both are in the graph and an edge already exists between them, it does nothing.
Else, it adds the edge going from from to to (normal situation).
- void
addEdge
(EdgeType edge);
- Adds an edge to the grap.
- void
addNodes
(NodeType[] n);
- Add new nodes to the graph.
- void
addEdges
(Label!(N) from, Label!(N)[] toNodes);
- Add new edges (a Label!N[] array) to node n, in a batch.
- bool
isValidNode
(Label!(N) l);
- Checks if there is a node labeled l in the graph. It's a O(N lg N) operation, N being the number of nodes.
- bool
canAddEdge
(Label!(N) from, Label!(N) to);
- Checks than to and from are valid nodes labels and that no edge exists between them.
- bool
isValidEdge
(Label!(N) from, Label!(N) to);
- bool
isValidEdge
(EdgeType e);
- @property NodeType[]
nodes
();
- Returns an array containing a copy of the graph's
nodes
. It's not lazy.
- @property Label!(N)[]
labels
();
- Returns the
labels
of a graph. It's not lazy.
- @property EdgeType[]
edges
();
- Returns the
edges
as an array. It's not lazy.
- @property size_t
size
();
- A Graph
size
is its number of nodes.
- size_t
valency
(Label!(N) l);
- the
valency
of a node is the number of its outcoming edges.
- Label!(N)[]
successors
(Label!(N) l);
- Returns the children of the node labeled l, as a label array.
- bool
hasChildren
(Label!(N) l);
- returns true iff the node labeled l has children (outcoming edges).
- bool
isSink
(Label!(N) l);
- returns true iff the node labeled l is a sink in the graph (a leaf in tree parlance, a node without outgoing edges).
- bool
opIn_r
(Label!(N) l);
- returns true if l is in the graph
- bool
opIn_r
(EdgeType e);
- returns true if e is in the graph
- NodeType
opIndex
(Label!(N) l);
- returns the node labeled l. It's one of the few functions there that returns a true node.
- void
deleteNode
(Label!(N) l, bool danglingBonds = false);
- Deletes the node labeled l from the graph. You can force dangling bonds (ie, invalide edges pointing
to a now-inexistent node) by setting danglingBonds to true. I do not think it's a good idea.
- void
deleteEdge
(Label!(N) from, Label!(N) to);
- Suppresses the edge going from from to to.
- void
deleteEdge
(EdgeType e);
- Suppresses the edge e.
- void
deleteEdges
(Label!(N) l);
- Suppresses all edges going from the node labeled l (thus making it a leaf).
- string
toString
();
- to print the graph.
- @property size_t
numNodes
();
- equivalent to
.size.
- @property size_t
numEdges
();
- Returns the total number of edges. It's not a pre-calculated value. Maybe that would
be a good idea to have a counter somewhere instead of calculating it that way.
- Graph!(CommonType!(StaticFilter!(isNode,T)),Select!(is(CommonType!(StaticFilter!(isEdge,T)) == void),Edge!(typeof(CommonType!(StaticFilter!(isNode,T)).label)),CommonType!(StaticFilter!(isEdge,T))))
graph
(T...)(T edgesOrNodes);
- Builds a Graph from a list of nodes and edges. The signature may by odious, but usage is very simple: just
give it a list of nodes and edges.
auto g = graph(node("A", 1.0), node("B", 2), node("C", 3.141592), edge("A", "B"), edge("A", "C"), node("D", -1.0), edge("D", "C"));
(Curse you DDoc for making me destroy my layout to work around a bug).
The function will determine the nodes and edges types from the list, make sure they are compatible
and build the
graph
out of it. In the above example, the nodes will be labeled by a string,
and contain a value of type double.
Note that it needs at least one node to determine the Graph type,
so you cannot build a nodeless
graph
from it. Instead, just create the appropriate struct:
Graph!(Node!(Label, Value), Edge!(Label)) g;
Right now, it builds the
graph
exactly as you typed it, so you cannot add an edge linking
nodes that are not both already in the
graph
. That will change in the future: it will filter the nodes, add
them to the
graph
, and then add the edges.
- struct
UndirectedGraph
(N,E) if (isNode!(N) && isEdge!(E) && is(Label!(N) == Label!(E)));
- Undirected graph, built upon a directed graph. Still experimental.
- alias
NodeType
;
- exposed node type.
- alias
EdgeType
;
- exposed edge type.
- alias
LabelType
;
- exposed label type.
- alias
ValueType
;
- exposed payload type.
- string
toString
();
- to print the graph.
- UndirectedGraph!(CommonType!(StaticFilter!(isNode,T)),Select!(is(CommonType!(StaticFilter!(isEdge,T)) == void),Edge!(typeof(CommonType!(StaticFilter!(isNode,T)).label)),CommonType!(StaticFilter!(isEdge,T))))
undirectedGraph
(T...)(T edgesOrNodes);
- ditto.
|
on Fri Nov 12 11:55:09 2010