Digraph Datatype with Vertex labels
While many algorithms have been written to compute/manipulate directed graphs (digraphs), few do so with associated vertex names or labels.
The problem I was interested in solving required to see “who depends on who” in a complex web of inter-dependencies. I needed to answer such questions as
- Does A depend on Z?
- Explicitly or implicitly?
- What is the chain of dependencies?
- Which dependencies are redundant?
- Are there any circular dependencies?
This class provides the convenience of an underlying structure to keep the vertices associated with the indices of the Adjacency Matrix, all with performance always in mind for graphs with thousands of vertices.
This also provides a fairly convenient opening to make use of GraphViz technologies (http://www.graphviz.org/) to output a clean graph, but was left out of this class implementation due to the extreme customization allowed via GraphViz.
== UPDATE Aug2014 ==
I've replaced the 4 search functions getDirectForward, getDirectBackward, getAllForward, getAllBackward with one succinct and faster function "findall". In case you need to migrate code, the following are functionally equivalent:
getDirectForward(DG,V) -> findall(DG,V,1)
getDirectBackward(DG,V) -> findall(DG,V,-1)
getAllForward(DG,V) -> findall(DG,V,Inf)
getAllBackward(DG,V) -> findall(DG,V,-Inf)
Cite As
Steve McClure (2024). Digraph Datatype with Vertex labels (https://www.mathworks.com/matlabcentral/fileexchange/44125-digraph-datatype-with-vertex-labels), MATLAB Central File Exchange. Retrieved .
MATLAB Release Compatibility
Platform Compatibility
Windows macOS LinuxCategories
- MATLAB > Mathematics > Graph and Network Algorithms > Modify Nodes and Edges > Dijkstra algorithm >
- MATLAB > Mathematics > Graph and Network Algorithms > Construction > Directed Graphs >
Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.
@digraph/
@digraph/private/
unittest/
example/html/
Version | Published | Release Notes | |
---|---|---|---|
1.9.0.1 | Updated license |
|
|
1.9.0.0 | Adding .mltbx accessibility
|
||
1.8.0.0 | Consolidated 4 search functions into 1 with performance enhancements. Added SPY functionality. |
||
1.7.0.0 | Inheriting matlab.mixin.Copyable instead of handle. Adapted to @-folder structure. Improved error-checking. Added unittests. Improved performance of several methods. |
||
1.6.0.0 | Adding copyright for example. |
||
1.2.0.0 | Added methods to allow subclasses to preserve their classes when using superclass methods. Enhanced help. |