wisteria-vis (viscaria)

Julia toolkit for manipulating, k-core-decomposing, and visualising large directed graphs — originally built for the Wikipedia link graph.

Given a graph as an edge list (e.g. "page A links to page B"), Viscaria can extract arbitrary k-cores and their subgraphs, find shortest paths between nodes, and render the result as a high-resolution PNG via Large Graph Layout (LGL). Typical use: start with a multi-million-edge graph, pull the dense k ≥ 100 core, and generate a readable visualisation.

Originally written for Team Turing at Harrow School.

Status

Actively being cleaned up for public release — the command-line interfaces listed below are current, but some older commented-out code paths are still being pruned.

Table of contents:

• Getting Started
• File Formats
• Program Usage

Getting Started

1. Make sure you have Julia installed and accessible via the command line. If not, install it. Developed against Julia 1.8+; any modern 1.x release should work.

2. Clone this git onto your device and change directory in your command line to this folder .

3. Run the following to install necessary packages and set-up Viscaria:

   julia setup.jl

4. (Optional, only needed for image generation) Install Large Graph Layout (LGL). LGL is a Linux-only toolchain (Perl / Java / C++) that Viscaria shells out to for coordinate generation and image rendering. Only edges2png.jl invokes it directly; every other script in this repo is pure Julia and runs anywhere Julia does.

   To install LGL:

   git clone https://github.com/TheOpteProject/LGL

   Then follow the LGL Usage Guide in this repo for build and configuration steps.

5. Configure Viscaria by editing config.toml. At minimum, set LGLPATH under [LGL] to point at your LGL checkout (only required if you plan to run edges2png.jl). All other keys have sensible defaults — see inline comments in config.toml for what each does. Scripts that accept a [config.toml] argument will fall back to ./config.toml if none is supplied.

File Formats

Viscaria processes multiple file types, for which will be listed below:

1. Edges .edges or .txt

   Edges files are essentially unweighted adjacency lists of graphs that can be directed or undirected. This is the same file type that Wisteria can output in the parsing process. (This is similar to the .ncol file type that LGL can use.) For example:

   1 2
   1 3
   2 3
   

   • Each row represents one directed edge from the first node to the second. So there are edges from 1 to 2, 1 to 3, and 2 to 3 in the example above.
   • Each node must be represented in positive integers (IDs) and fit within the Int32 type.

2. Titles .titles

   Title files are files with each line consisting of a <ID> <title> pair, where:

   • Every ID has to be a unique positive integer;
   • A .titles file can be generated using the edges2titles.jl script in scripts/ from a file of only titles.

3. LGL .lgl

   The .lgl file type is a version of .edges file type, also an adjacency list, but tries to use less space. The example from above can be expressed in the .lgl format as below:

   # 1
   2
   3
   # 2
   3
   

   • The prime node (first node in the directed edge) is expressed with a # and a space before it on one line.
   • All the following lines' nodes before the next prime node (before the next # appears) are all nodes on the receiving side of the edge from the prime node.
   • More info about this file type can be found here.

4. Coordinates .coords

   The .coords file type is not processed by any of the scripts in Viscaria, but instead is generated by the LGL scripts LGL/bin/lgl.pl or LGL/bin/lglayout2D, which are executed in edges2png.jl.

   • This file is then used to generate the final high quality image of the entire edges file through LGL's ImageMaker.

5. Colors .colors

   The .colors file is generated by edges2colors.jl in scripts/ or edges2png.jl for LGL's ImageMaker to generate the final image of the graph.

   • The .colors file dictates the color of each edge in the final image, each edge on each line expressed as:

     <node_1> <node_2> <R> <G> <B>
     

     • Where <node_1> and <node_2> are IDs of the pair of nodes in that edge;
     • <R>, <G>, <B> are the RGB values in the form of decimals from 0 to 1.

   • More info here.

6. Labels .labels

   The .labels file is generated by the edges2labels.jl script in scripts/ or edges2png.jl for LGL's ImageMaker to use for labels in the final image. More info here.

Program Usage

1. Graph Degeneracy

   kdegenerate.jl is used for degenerating an edges file to K cores. More info about K-degeneracy (K-core) graphs here.

   Script usage:

   julia kdegenerate.jl <input.edges> <K> <o|i> <output.edges>

   • <input.edges> — input edges file;
   • <K> — the core number to degenerate down to;
   • <o|i> — o for out-core (keep nodes with out-degree ≥ K), i for in-core (keep nodes with in-degree ≥ K);
   • <output.edges> — output file (path allowed) for the resulting K-core graph.

   kdegen_ranged.jl does the same thing but over a range of K values, producing one K-core.edges file per K:

   julia kdegen_ranged.jl <input.edges> <lower_K> <upper_K> <i|o> <outputdir> <logfile>

   • <lower_K> and <upper_K> — inclusive lower/upper bounds of K;
   • <i|o> — in-core or out-core (as above);
   • <outputdir> — directory for the K-core.edges output files (or literal no to skip writing output files and only log statistics);
   • <logfile> — path for the run log.

2. Subgraph

   subgraph.jl generates an edges file of a subgraph of nodes within <levels> amount of distance from a center rootnode (<rootnodeid>). Where distance is the number of edges it takes to go from the rootnode to that node.

   Script usage:

   julia subgraph.jl <input.edges> <rootnodeid> <levels> <output.edges>

   • Where <rootnodeid> is the ID of the rootnode you choose;
   • <levels> is the largest shortest distance between the rootnode and any other node to include that node in the subgraph;
   • <output.edges> is the output file (can include path) of the subgraph in the form of an edges file

3. Shortest Path & Combine Path

   shortestpath.jl and combinepath.jl both make use of Breadth First Search to find the shortest path from one node to another in a directed/undirected graph and outputs them. combinepath.jl further generates subgraph with level/distance 1 (same concept as subgraph.jl) for all nodes in the path and combines those subgraphs, outputting the final subgraph as an edges file.

   There are two modes to shortestpath.jl: interactive or non-interactive. Interactive mode is turned on when startnode and endnode are not inputted as arguments, and non-interactive mode otherwise. Interactive mode lets you input startnodes and endnodes repeatedly to find their shortest paths without exiting the program, while non-interactive mode only finds shortest path once between startnode and endnode arguments.

   Script usage:

   julia shortestpath.jl <input.edges> <input.titles> <optional: startnode endnode>

   • Where <input.titles> is the .titles file to get the startnode's and endnode's IDs from;
   • startnode and endnode are both titles, not IDs

   combinepath.jl function is as explained above. The script will also generate a .labels file for all the nodes in the path to be used for LGL later if you want to generate an image.

   Script usage:

   julia combinepath.jl <input.edges> <input.titles> <startnode> <endnode> <outputprefix> [config.toml]

   • <startnode> and <endnode> are NOT optional;
   • <outputprefix> is the prefix of the output directory, .labels and .edges files generated in ./visualisation;
   • The output directory is automatically made in ./visualisation with the generated files in it;
   • [config.toml] — optional; defaults to ./config.toml. Used for label font/style lookup.

4. Edges to PNG

   edges2png.jl is a multi-step script that uses LGL to generate a high-def image of the graph. It creates a .labels and .colors files from <input.edges>; then converts <input.edges> into a .lgl file; then uses LGL's bin/lglayout2D to generate a .coords file with name lgl.out. Finally, it generates .png images with LGL's ImageMaker using all the files generated from before.

   Script usage:

   julia edges2png.jl <input.edges> <input.titles> <outputprefix> [config.toml]

   • <outputprefix> — prefix of the output directory and files generated under ./visualisation. The output directory is created automatically;
   • [config.toml] — optional; defaults to ./config.toml. The config file controls LGLPATH, threads, output resolution, label styling, and ImageMaker JVM options — see inline comments in config.toml;
   • Before running, edit config.toml and set [LGL].LGLPATH to point at your LGL checkout.

5. Compare Edges

   compare_edges.jl is a script for comparing the links of two edges files, whether they are in the .edges or .lgl formats.

   Script usage:

   julia scripts/compare_edges.jl <.edges or .txt or .lgl> <.edges or .txt or .lgl>

   • Where both arguments are the edges files in the format of .edges (.txt) or .lgl files

6. Edges to LGL

   edges2lgl.jl outputs a copy of input.edges as a .lgl file.

   Script usage:

   julia scripts/edges2lgl.jl <input.edges> <output.lgl>

7. Edges to Colors

   edges2colors.jl generates a .colors file from <input.edges>. Edges have a red-blue color gradient calculated from the difference in degrees of the pair of nodes in relation to the range of degrees in the graph.

   Script usage:

   julia scripts/edges2colors.jl <input.edges> <output.colors>

8. Edges to Labels

   edges2labels.jl generates a .labels file of <N> nodes with the top degrees in <input.edges>.

   Script usage:

   julia scripts/edges2labels.jl <input.edges> <input.titles> <N> <output.labels> [config.toml]

   • <N> — number of labels to emit (the N highest-degree nodes);
   • [config.toml] — optional; defaults to ./config.toml. Controls label styling and fonts.

9. Edges to Titles

   edges2titles.jl generates a .titles file for all nodes in a subgraph <input.edges> where the titles are fetched from a larger titles file <input.titles> of the original graph containing the subgraph.

   Script usage:

   julia scripts/edges2titles.jl <input.edges> <input.titles> <output.titles>

10. Create ID for Titles

    createIDforTitles.jl creates a .titles file (ID-title pairs) from a list of only titles in <titles.txt> since Viscaria mainly handles Int32 IDs of the nodes instead of their titles.

    Script usage:

    julia scripts/createIDforTitles.jl <titles.txt> <output.titles>

Note

To clarify, none of the code in here is from LGL. Some scripts only process or generate files that are to be used by LGL for coordinates and image generation.

License

All code in this repository is licensed under the GNU General Public License version 3.