dranges.graphalgorithm

Graph!(N,E) complementGraph (N, E)(Graph!(N,E) g);

Returns:
the complement graph of g: same nodes, but complementary edges: for each pair (u,v) in g.nodes, if (u,v) is in g, then it's not in the complement. Conversely, if (u,v) is not in g, then it's an edge in the complement.

See Also:
reversedGraph.

TODO:
conserve the edge properties

Graph!(N,E) completedGraph (N, E)(Graph!(N,E) g);

Returns:
the complete graph with the same nodes as g. A complete graph has all possible edges. (also, its density is 1.0).

Graph!(N,E) reversedGraph (N, E)(Graph!(N,E) g);

Returns:
The reverse graph of g: same nodes, edges inverted (ie: an edge going from A to B becomes an edge from B to A). This graph is useful in certain algorithms, like decomposing a graph into its strongly connected components and creating its metagraph.

Note:
it's not smart enough to reverse the edges' classification, if any (that would need distinguishing between forward and tree edges).

See Also:
isAcyclic(Graph g).

BUG:
refactoring, the egdes properties such as their length/weight are not properly propagated right now.

Label!(N)[] explore (N, E, L)(Graph!(N,E) g, L l, bool[L] visited = (bool[L]).init);

Explore a graph g from the node labeled l. The use of recursion makes it similar to depth-first traversal. Returns : An array of labels, which are the nodes reachable from node l.

Label!(N)[][] connectedComponents (N, E)(UndirectedGraph!(N,E) g);

Returns:
As a list of list of labels, the undirected graph connected components: the groups of nodes that are connected together.

For example:

[["A","B"], ["C"], ["D", "E", "F"]]

means that A and B have a common edge, that C is alone and that D, E and F can be reached from one another.

BUG:
UndirectedGraph is being redesigned.

Tuple!(Label!(N)[],int[Label!(N)],int[Label!(N)]) clock (N, E)(Graph!(N,E) g);

Returns:
In a tuple, the nodes sorted by decreasing post number and the pre and post-visit timings of g nodes, in associative arrays pre and post.

Label!(N)[][] stronglyConnectedComponents (N, E)(Graph!(N,E) g);

Returns:
The list of strongly connected components of g. That is, the nodes of sub-graphs where all nodes can be reached from one another.

Graph!(N,E)[] subGraphs (N, E)(Graph!(N,E) g);

Returns:
The subgraphs created by the strongly connected components of a graph.

Graph!(Node!(string,Graph!(N,E)),Edge!(string)) metaGraph (N, E)(Graph!(N,E) g);

Returns:
The meta-graph associated to g. That's the graph whose nodes are the subgraphs of g and the edges the edges between these subgraphs. The meta-graph nodes labels are the concatenation of each subgraphs nodes labels (cast to strings). The subgraphs are stored as the nodes values. This operation is also sometimes called the compaction, reduction or shrinking of a graph.

Note:
It could be coded more efficiently: all these successsive functions (reversedGraph - clock - stronglyConnectedComponents - subGraphs - metaGraph ) could be integrated into one metagraph function: some work is duplicated: while we extract the scc, we could create the metanodes and their names, and get the outgoing edge without having to painfully find them afterwards as is done there. But I'm aiming at making it work first. For my graphs, it takes a fraction of second to find the MG.

Note:
I could also ask for a labelize function that'd creates the metagraph nodes labels from the original labels, instead of casting them to string and concatenating them.

enum EdgeClassification ;

EdgeClassification[E] classifyEdges (N, E)(Graph!(N,E) g);

Classify edges between Tree&Forward edges, back edges and cross edges, without distinguishing between Tree and Forward. It returns this property map as an associative array.

bool isAcyclic (N, E)(Graph!(N,E) g);

Returns:
True if the graph is acyclic, false otherwise.

Graph!(N,E) linearize (N, E)(Graph!(N,E) g, bool testForAcyclic = false);

Returns:
The linearized version of a Directed Acyclic Graph (DAG). As there is no static way to know if a Graph is a DAG, you can use the flag testForAcyclic to decide if you want to test or not.

TODO:
either a DAG struct, or an AssumeAcyclic!Graph template.

int[Label!(N)] numNodesFrom (N, E, L)(Graph!(N,E) g, L from);

Returns:
The distance (in number of nodes) between node from and all other nodes, as an associative array. The distance from from to from is 0. if node B is not reachable from node A, distanceFrom(g, A)[B] = int.max. Why not -1? Because it's not correctly ordered with other distance and some functions here (like the radius or diameter or a graph) sort node-distances.

Remark:
another solution would be not to include B as a key in the associative array, maybe.

int[Label!(N)][Label!(N)] distanceMatrix (N, E)(Graph!(N,E) g);

Returns:
the distance matrix for g: the distance (in number of nodes) from node a to node b, far all nodes in the graph. It returns it as a double associative array. result[label1][label2] is the distance from 1 to 2. If there is not path, the distance is int.max.

TODO:
make it more efficient. numNodesFrom already makes a big part of the job.

Tuple!(double[Label!(L)],Label!(N)[Label!(N)]) dijkstra (N, E, L)(Graph!(N,E) g, L begin, bool checkForNegativeLength = false);

Implements Dijkstra's shortest path algorithm. It takes for input a Graph g which edges must have a positive "length" property which must be numerical (castable to double) and a beginning label. It's a O(n+e) algorithm, where n is number of nodes in g and e its number of edges.

An optional parameter, checkForNegativeLength (defaults to false, no check) forces the function to verify that each encountered edge length is not negative. It will throw an Exception if such an edge is found.

Returns:
As the other 'shortest path' algorithms in this module, dijkstra returns a tuple which has for first field an array containing the shortest distance from begin to the other nodes (a double[node] associative array). If a node cannot be reached, the distance is double.infinity. The second field contains the predecessor of each node in their path to begin: a Label!N[Label!N] array.

TODO:
see to this internal index problem.

Tuple!(double[Label!(N)],Label!(N)[Label!(N)]) bellmanFord (N, E, L)(Graph!(N,E) g, L begin, bool checkForNegativeCycle = false);

Implements the Bellman-Ford algorithm for finding the shortest path in graphs with positive or negative edge length. It imposes almost no condition on the graph, but it's a O(n*e) algorithm, where n is the number of nodes, and e is the number of edges. As such,it could be slower than dijkstra or dagShortestPath (my own timings on small graphs show on the contrary Bellman-Ford to be the quickest of the three).

The only condition on the graph is that there must be no negative cycle (cycles with a negative total length), but it's a general condition on shortest path algorithms: if there is a negative cycle, you can take it many times in your path, each time decreasing the path total length, without limit. An optional argument checkForNegativeCycle (default value: false) will provoke such a test (it's done at the end of the computation, so it does not change the global speed of bellmanFord ).

Obviously, the graph edges must have a .length member. This length will be cast to double, two nodes not connected having a distance of double.infinity.

As with other 'shortest path' algorithm (dijkstra and dagShortestPath), it takes for input a Graph and the label of a node, and returns a tuple of distances from the node (a double[Label] associative array) and a previous node tree, in the form of a Label[Label] array.

Tuple!(double[Label!(N)],Label!(N)[Label!(N)]) dagShortestPath (N, E, L)(Graph!(N,E) g, L begin, bool checkForAcyclicity = false);

Implements a shortest path algorithm for DAG (Directed Acyclic Graphs). As these can be linearized (with linearize(Graph g)), there is a simple O(E) algorithm for them.

The optional argument checkForAcyclicity (default: false) forces a check on g's acyclicity. In case a cycle is found, an Exception is throw.

As with other 'shortest path' algorithm (dijkstra and bellmanFord), it takes for input a Graph and a label inside the graph and returns a tuple of distances from the node (a double[Label!N] associative array) and a previous node tree, in the form of a Node[Node] array.

Tuple!(Label!(N)[],double) shortestPath (alias algo = bellmanFord, N, E, L)(Graph!(N,E) g, L from, L to, bool check = false);

Gives the shortest path in g between g's nodes from and to. The algorithm used is selected by the caller with the template parameter algo. Just pass the name of the function (it defaults to bellmanFord, the most generic but also in theory the slowest algorithm).

The optional argument check (default: false), if set to true, uses the 'with checks' version of the algorithm.

Returns:
a tuple of the distance (a double) and the path (a Label[] array) between from and to.

size_t order (N, E)(Graph!(N,E) g);

The order of a graph is the maximum valency of its nodes.

size_t eccentricity (N, E, L)(Graph!(N,E) g, L label);

Returns:
the eccentricity of a node in a graph. That's the longest path (in number of nodes) from this node to any other node in the graph.

size_t radius (N, E)(Graph!(N,E) g);

the radius of a graph (the smallest excentricity among all nodes)

TODO:
can probably coded in a more efficient way, I'll see.

size_t diameter (N, E)(Graph!(N,E) g);

the diameter of a graph, ie its highest excentricity among nodes.

Graph!(N,E) subgraph (N, E)(Graph!(N,E) g, L[] labels);

Extracts the subgraph of g corresponding from the nodes array.

Graph!(N,E) minimumSpanningTree (N, E)(Graph!(N,E) g);

Implements Kruskal's minimum spanning tree algorithm. The minimum spanning tree of a graph is a tree that connects all the graph's nodes using lowest possible length for all edges. The edges must have a .length member.

Returns:
g's spanning tree, here as a Graph.

string toGraphviz (N, E)(Graph!(N,E) g, string name = "graph");
string toGraphviz (N, E)(UndirectedGraph!(N,E) g, string name = "graph");

Returns:
a string giving the graph representation using the dot language, from Graphviz.

Also, writes the file name.dot to the current directory.

Caution:
This is just a helper/debugging function to easily visualize the graphs. Use with caution.

string[string] dmdPaths ;

Given a module name, dependencyGraph will explore its code, extract the import statements and recursively visit the corresponding modules. If you don't want it to visit the std.* or core.* part, juste use:

auto dg = dependencyGraph("myModule");

If you want it to explore the std.* and core.* modules, you must give it the directory where DMD is installed. It will then calculate the dependency graph of Phobos and the runtime along your own project's graph. Use like this:

auto dg = dependencyGraph("myModule", r"C:\dmd\");
toGraphviz(dg, "imports");
// then, in a command line: >> dot -Tpdf imports.dot -o imports.pdf

Returns:
a Graph, with nodes the modules names and edges pointing to imported modules.

BUG:
I don't get how core.* is organized. For now, it doesn't visit the core modules. It create them in the graph, though.