Skip to content

Latest commit

 

History

History
318 lines (312 loc) · 15.3 KB

ToDo.md

File metadata and controls

318 lines (312 loc) · 15.3 KB
Raw

ToDo & Issues

Milestones

  • CppCon: Sep 12-16, 2022
    • Presentation (Phil & Andrew)
    • Publish graph-v2 github repository
      • add license file (boost)
      • README.md completion
      • Views: bfs + dfs
      • Algorithms: dijkstra + warshall_transitive_closure
      • Validate Sphinx output is OK
  • Acceptance of P1709 by SG19 (Machine Learning): goal by Dec-2022
  • Acceptance of P1709 by SG6 (Numerics)
  • Acceptance of P1709 by SG14 (Low Latency)
  • Acceptance of P1709 by LEWG (Library Evolution Working Group)
  • Acceptance of P1709 by LWG (Library Working Group)
  • Acceptance of P1709 by WG21 (C++ Standards Committee)
  • Feb-2025 deadline for C++26

Open

ToDo

  • Graph Container Interface (GCI)
    • Common
      • Use Neibloid style for all CPOs
    • Ranges
    • Concepts and type_traits
      • graph: adjacency_list, sourced_adjacency_list, adjacency_matrix
      • view concepts: vertex_view, edge_view, neighbor_view returned from graph views
      • function concepts: VVF, EVF
      • Edgelist concept(s)
    • Graph API
      • depth() CPO? bfs, dfs. size() is different; depth for BFS takes extra work and is diff concept.
      • cancel() CPO? bfs, dfs: no, member only
      • replace is_undirected_edge_v & undirected_incidence_graph with is_unordered_edge_v
    • Views
      • view classes should be in graph
      • view functions should be in graph::view
      • add range overloads to appropriate views (DFS, BFS, topo_sort, etc.)
      • vertexlist
        • Use VVF&& instead of const VVF&
        • verify it is a std::ranges::view<>
        • Implement vertexlist(g,vr)
        • Implement vertexlist(g,vr,vvf)
        • Implement basic_vertexlist(g,vr)
        • Implement basic_vertexlist(g,vr,vvf)
        • Extend support for vvf(uid), in addition to vvf(u)
      • incidence
        • Use EVF&& instead of const EVF&
        • unit tests for undirected_graph<G>
        • verify it is a std::ranges::view<>
      • neighbors
        • Use VVF&& instead of const VVF&
        • Extend support for vvf(uid), in addition to vvf(u)
        • unit tests for undirected_graph<G>
        • verify it is a std::ranges::view<>
        • Implement basic_neighbors(g,vr)
        • Implement basic_neighbors(g,vr,vvf)
      • edgelist
        • Use EVF&& instead of const EVF&
        • unit tests for undirected_graph<G>
        • verify it is a std::ranges::view<>
      • vertices_dfs_view
        • validate results & add unit tests
        • support Cancelable
        • support VVF
        • support undirected_graph<G>
        • support begin, end, depth/size, empty, swap free functions
        • verify it is a std::ranges::view<>
        • create CPOs
        • Use real_target_id(g,uv,src) for both directed_incidence_graph & undirected_incidence_graph to consolidate code
        • basic_vertices_dfs_view
      • edges_dfs_view
        • validate results & add unit tests
        • support Cancelable
        • support EVF
        • support Sourced
        • support undirected_graph
        • support begin, end, depth/size, empty, swap free functions
        • verify it is a std::ranges::view<>
        • create CPOs: edges, sourced_edges
        • basic__edges_dfs_view
      • vertices_bfs_view
      • edges_bfs_view
      • topological_sort_vertices_view
      • topological_sort_edges_view
      • allow options to exclude vertex/edge reference on results (Andrew)
      • Common
        • Add depth(search) CPO for dfs, bfs, topo_sort
        • Add size(search) CPO for dfs, bfs, topo_sort
  • Algorithms
    • Algorithms (full & simplified/book)
      • Shortest Paths
        • Dijkstra_clrs (book impl from AndrewL)
        • dijkstra_shortest_path
        • bellman_ford_shortest_path
      • Clustering
        • Triangle counting
      • Communities
        • Label propagation
      • Components
        • connected_components
        • strongly_connected_components (Kosaraju & Tarjan)
        • biconnected_components
        • articulation_points
      • Directed Acyclic Graphs
        • Topological Sort, Single Source
      • Maximal Independent Set
        • Maximal Independent Set
      • Link Analysis
        • Jaccard Coefficient
      • Minimal Spanning Tree
        • Kruskal Minimum Spanning Tree
        • Prim Minimal Spanning Tree
      • Others to consider
        • page_rank; not a good candidate for the standard because there are too many options; better as an example
        • Edgelist algorithms (prove design; not for P1709)
          • Union Find (edgelist)
        • betweenness_centrality
        • triangle_count
        • Minimum spanning tree
          • kruskell_minimum_spanning_tree
          • prim_minimum_spanning_tree
        • Community Detection
          • Louvain
          • Label propagation
        • Subgraph isomorphism (pattern match)
      • Other (not for P1709)
        • copy (g1 --> g2) (not for P1709)
      • Deferred
        • Transitive Closure
          • dfs_transitive_closure
          • warshall_transitive_closure (single-threaded)
            • implement
            • validate & add unit tests
  • Graph Containers (data structures)
    • compressed_graph (for P1709)
      • Implement load_graph(), load_vertices(), load_edges() CPOs (define concepts)
    • dynamic_graph
      • Implement load_graph(), load_vertices(), load_edges() CPOs (define concepts)
      • test push_or_insert() to assure it does the right thing for const, value, &, &&, ...
      • graph with map-based vertices (requires different algorithm impl)
      • Use copyable_vertex & copyable_edge concepts in graph ctors, load functions
      • Support non-integral vertex_ids
    • constexpr graph based on std::array
    • undirected_adjacency_list<EV,VV,GV,VId,Alloc>
    • directed_adjacency_vector (retired)
    • adaptor for range of ranges (e.g. vector<list<T>>) [see rr_adaptor in ./test]
  • Testing Patterns
    • Validate content
    • Validate graph API
      • All functions work (with/without defaults) on existing data structures
      • Default values same as dynamic graph values
      • void & non-void for EV, VV & GV can store & retrieve values
      • Validate const
      • Validate copy and move to set EV, VV & GV values
    • Validate algorithms
    • Apply to multiple data structures
      • load_edges() can use copy and move to set EV & VV values
      • use load_ordered_graph() for all data structures (consistency)
      • use values, references and ptrs for value types: EV, VV, GV
      • support const on value types(?)
  • Tools, Libraries & Infrastructure
    • Create mtx parser (from nwgraph)
    • Constexpr unit tests (initial tests to verify pattern)
    • Generate doxygen output
    • Validate address sanitizer build
    • Support Clang (waiting for full concepts support)
    • Performance tests
    • Use sphinx for code documentation
  • github - graph-v2
    • Add processes to build & run unit tests on checkin
    • Make graph-v2 public. Requirements
      • 2+ algorithms implemented
      • bfs and dfs implemented
      • README.md with Description + Getting Started
  • Feature & performance comparison
    • boost::graph
    • NWGraph
    • Lemon
    • Simple ABC implementation with boost::intrusive to demonstrate embedded use of graph
  • C++20 and C++23
    • modules
    • coroutines (simplify DFS, BFS & TopoSort?)
  • Examples
    • ABC
  • Documentation
    • Decprecate original "graph" repository
    • README.md
      • Add general description
      • Add Getting Started
    • P1709
      • Google Doc --> LaTex
      • Customization Points: reword to allow either Niebloids or tag_invoke
      • Design Decisions
        • Library Organization
        • Separation of Graph Algorithm and Data Structure Requirements
        • Graph Function specialization overview & example
      • Algorithms
      • Technical Specifications
        • <graph>
        • <vertexlist>
        • <incidence>
        • <neighbors>
        • <edgelist>
        • <depth_first_search>
        • <breadth_first_search>
        • <graph_algorithm>
        • <compressed_graph>
  • Feedback
  • Code Review
    • graph concepts
    • undirected_graph<G> concept + source/target swapping in views
    • views iterator design:
      • use of subrange
      • storing values in iterator: shadow struct, setting values in operator*(), mutable value, ref_to_ptr
      • fnc obj as ptr vs. value?
      • vs. NWGraph (returning references vs. values)
    • tag_invoke design & use (access namespace, tag names, etc.)

Issues

  • SG19 Questions/Input
  • csv_parser
    • CSVReader doesn't conform to the C++20 input_range or forward_range concepts; can't define load functions properly
      • What's missing? const types; other?
      • Author has acknowledged it could be valuable but hasn't made any commitments to do that
    • leading & trailing spaces for quoted values aren't ignored (std CSV format; author won't change)
    • can it be reused for multi-pass?
  • Are the CSR vertex & edge types different? (requirement of incidence and adjacency concepts)
  • Should operator[](n) -> vertex& be a requirement for a graph? (Used by NWGraph)
  • Can std::array be used as a basis for a constexpr graph? What would the graph be?
  • How to validate constexpr? (need to use std::array)
  • CSR showed that there can be issues when an "edge" type is just an int, which is the same as the VId. Will this be an issue for existing graphs? If so, how to adapt them?
  • Should we worry about row-major & column-major ordering of adjacency_matrix? always assume row-major?
  • Is there a way for EVF to take both edge_value and fnc obj? (same for VVF & vertex_value)
  • The default for edges(g,uid) CPO isn't being found by msvc or gcc. Is there a way to only have to override one version of edges(g,)?
  • Shoud we support format() output? (Investigate work into how ranges are handled in general)
  • What is the design for CSR & CSC for matrices? (contact Christian Trott)

Resolved

ToDo Completed

  • API
    • graph types
    • vertex types
    • edge types
    • ranges
      • vertex_range
      • vertex_edge_range
    • add overridable is_undirected_edge_v & undirected_incidence_graph<G> concept
    • add overridable is_adjacencey_matrix_v<G>
    • "key" --> "id"
  • Views
    • vertexlist
    • edgelist
    • incidence
    • neighbors
    • depth_first_search: vertices, edges & sourced_edges
  • Algorithms
  • Containers (data structures)
    • dynamic_graph (adjustable to different vertex & edge containers)
      • Implement graph, vector, edge
      • Load from CSV file
      • Add <bool sourced> template parameter to include source_id
      • use copyable_vector_t & copyable_edge_t for loaders, ctors and initializer
    • compressed_graph
      • Implement graph, vertex, edge
      • Load from CSV file
      • Validate with vofl_graph tests
      • use copyable_vector_t & copyable_edge_t for loaders, ctors and initializer lists
  • C++20 and C++23
    • connection points (e.g. tag_invoke)
  • Tools, Libraries & Infrastructure
    • Use CMake Presets; must work with both VS & VSCode
    • Use conan for libraries when possible: catch2, fmt, spdlog, range-v3
    • Include csv_parser library
    • Create graph-v2 repository in github
  • Documentation
  • Feedback

Issues Resolved

  • vertex_id(g,u) now takes a vertex reference (not iterator)
    • how to define vertex_id_t without calling vertex_id()?
    • make it obvious it's unavailable for non-contiguous vertices
    • Answer: for([uid,u] : vertices(g))
  • Best way to extend vol_graph to support different container types?
    • Answer: graph_traits with template specializations for user-defined values. vol_graph renamed to dynamic_graph
  • What is the best dynamic graph to propose for the std? vol, vov? premature. Revisit later
  • Can an edgelist be trivially created by a user? (e.g. vector<pair<target_id,weight>>) yes; need to flush this out in paper
  • Can we drop the vertex_vertex_range in favor of just having vertexlist(g,u) [adjacency view]? yes
  • Can std::vector be used as a basis for a constexpr graph? No because we can't have variables of vector
  • Should CSR support source_id on edges (Sourced template parameter)? No. Views will be able to provide it so it won't be needed.
  • edge_list_graph (edgelist_edge<VId,E,EV> view?): edgelist is a view, or projection of a container
  • Are there any issues with using tag_invoke? It appears not. Others are using it in papers.
  • key vs. id? "key" is a better term, but id has been used extensively in boost and other graph libraries and will be easier for people to recognize
  • Do we need a run-time function to check for undirectedness, in addition to is_undirected_edge_v? Is it a run-time property for some graphs? A: We'll only support compile-time. If someone needs run-time they can create a wrapper for is_undirected_edge_v to use
  • Can CSR edges have a void value? (e.g. no v vector): yes
  • If we have an access namespace, do we need a container namespace? A: "access" has been renamed "tag_invoke" and is a different purpose than a container namespace we don't need a separate container namespace
  • Are bfs & bfs algorithms, views or ranges? WRT P1709 they are Views.
  • Are graphs containers (WRT the standard)? A: They are containers because they contain the data that is being operated on. They are more complex than existing containers because they include multiple ranges.
  • Use of tag_invoke namespace is required by CPO and exposed when specializing the functions. Acceptable? Better way? A: It is a requirement and is being used as part of P2300. We'll follow their lead.
  • Can transform_view be used in place of the projections in the graph views? No
  • How to support bipartite (or N-partite) graphs using different vertex value types? A: Given a compressed_graph, EV and VV can be tuples of the same length. The number of elements in the tuples determine the number of partitions. Values are stored seprately from structure and can be stored in a tuple of vectors. Additional vectors are kept for the starting index in the vertices & edges structures for each partition. For instance, VV=tuple<int32_t,double,bool> and EV=tuple<int32_t, int32_t, void> the vertex values would be stored in tuple<vector<int32_t>, vector, vector>, and the edge values would be stored as tuple<vector<int32_t>, vector<int32_t>, vector>. (void may need to be replaced with a concrete novalue struct). B: Given a more standard adjacency structure, variant could be used instead of a tuple. For instance, using the same, EV and VV tuple types, they would be translated into variant<int32_t,double,bool> and variant<int32_t, int32_t, void>.
  • Should we have a graph_reference_t type alias? Yes